Spec the single epoch optimization

[csharrison]

In Cookie monster, if only a single epoch is considered, we do not need to deduct budget based solely on value, maxValue, and epsilon. We can instead deduct budget based on the actual L_p sensitivity of the histogram (i.e. we can replace value with lpSensitivity.

I don't believe this optimization buys you that much for p=1 and we're in the pure DP setting, but maybe it's worth speccing for completeness. Certainly in the case of last touch attribution, this doesn't buy you anything based on how last-touch is spec'd today.

I'd love to hear use-cases where this is really critical for the Laplace case.

[csharrison]

I thought of an MTA algorithm that benefits from this optimization in the p=1 case: a variant of time decay. Imagine a simplified "last touch" time decay algorithm that selects the most recent impression, but scales its value down via some exponential factor $e^{-\lambda t}$ where $t$ is the time since the action. In this way the attribution algorithm can opt not to spend the full budget.

[martinthomson]

That seems fine, but it only works if the impressions it touches are within an epoch. I presume that you are thinking that you would be able to do that reliably. How do you deal with the weekly rollover in that case? (We'd probably want a consistent time for that to make it easier to plan these sorts of queries.)

[csharrison]

@martinthomson indeed I was assuming we introduced an "epoch" filter. AFAIK this is fundamental to this optimization in any case. I don't have a solution to weekly rollover other than either 1) accepting loss at the boundary or 2) missing this optimization at the boundary.