Private Online Learning via Lazy Algorithms

We would like to thank the reviewer for the feedback. We respond to the reviewer’s main comments below; we are glad to clarify further as needed during the discussion period.

Improvement for small $\epsilon$: It is true that in many applications, $\epsilon$ is set to be some constant number. But the online setting is a bit different. Take the DP-OPE, as the non-private regret term $\sqrt{T}$ can dominate the other term, we can get privacy for free even when $\epsilon \ll 1$, and hence the high-privacy regime becomes more important and interesting. This is also crucial in scenarios where many applications of DP-OPE are necessary: in this case, our results show that we can run more such instances of DP-OPE than existing work while satisfying privacy.

Lower bound for CDP: Lower bounds in the oblivious setting turn out to be elusive, and prior work has only resulted in the trivial lower bound of $1/\epsilon$. Therefore, we restricted ourselves to the family of low-switching algorithms. The choice of CDP is made so that it is easier to prove the tight composition of the privacy budget. We can prove similar (tight) lower bounds for pure DP as it has a simple tight composition (our upper bounds are tight for pure DP).

Question 1: The privacy guarantee may be extended to adaptive adversaries, but the utility guarantee may be broken. As the algorithm is low-switching with the same model choice over a batch, the adaptive adversarial may design some loss functions with very large regret based on this. We note that our main goal in this paper is to study oblivious adversaries, especially given the recent work [AFKT23], which studies adaptive adversaries and gives tight lower bounds for certain privacy regimes.

Question 2: Yes, you are right. Our lower bounds should hold for this family of algorithms as well.

We would like to thank the reviewer for the feedback. Please see our responses below; we are glad to clarify further as needed during the discussion period.

Adaptive adversary: we note that our main focus in this work is oblivious adversaries since the recent work of [AFKT23] studies adaptive adversaries and shows tight lower bounds for certain privacy regimes. Given the separation in rates between adaptive and oblivious adversaries, the goal of our work is to study and understand the fundamental limits of oblivious adversaries.

Innovation: Some works in this line implicitly show the connection between lazy algorithms and private algorithms, but we are the first to formalize this connection explicitly via our L2P framework that can convert general lazy algorithms into private ones. The framework does not follow previous works like [AFKT23b] directly and requires new techniques and analysis, such as the new correlated sampling strategy through a parallel sequence of models, or the new regret guarantees that measure the effect of batching on lazy online algorithms.

We also answer the reviewer’s questions below.

Q1: This is correct. Our regret bound may be invalid with an adaptive adversary, and there are some challenges in extending it further. For example, as our algorithm consistently produces output over one batch, the adversary can know our next $B$ predictions and might choose some bad loss functions. The privacy guarantee, however, holds against adaptive adversaries. This is similar to several results in DP ML, where we get privacy for any input sequence, while utility holds under some distributional assumptions. In other words, if our assumptions are invalid, we may get worse utility but will not lose privacy.

Q2: We will lose the privacy budget each time we make a switch, and it is unavoidable to weaken the privacy guarantee. However, we set the privacy budget for each time step in a way that guarantees that the final privacy parameter guaranteed by the algorithm is satisfactory. This requires that the number of rounds $T$ is bounded, as is the case in most private optimization procedures: for example, in DP-SGD with full batch size, the privacy weakens over iterations as well, and therefore we need to bound $T$.

Q3: Lower bound for CDP: lower bounds in the oblivious setting turn out to be elusive and prior work had only resulted in the trivial lower bound of $1/\varepsilon$. Therefore, we restricted to the family of low-switching algorithms. The choice of CDP is made so that it is easier to prove the tight composition of the privacy budget. We can prove similar (tight) lower bounds for pure DP as it has a simple tight composition (our upper bounds are tight for pure DP).

Thanks for your review and feedback. Below, we address the main comments; we are glad to clarify further as needed during the discussion period.

1. Lower bounds: we acknowledge that the conditional lower bound is not ideal, but it is important to note that this is the first non-trivial (even conditional) lower bound for oblivious adversaries. Several papers have studied DP-OPE and DP-OCO, and so far, none has come up with a better lower bound than the trivial $1/\varepsilon$ lower bound (though for adaptive adversaries, there are some lower bounds). We, therefore, believe that our conditional lower bound (while admittedly not entirely satisfactory) is a step in the right direction towards proving general non-trivial lower bounds for oblivious adversaries. Finally, we note that our lower bound proves that our rate is the best possible using existing techniques that have been pursued by the recent line of work based on limited switching.

2. Organization: we will reorganize the paper, add more discussions, and defer less important definitions and details to the appendix, in order to make the paper more readable for people less familiar with differential privacy.

Thanks for your time in reviewing and feedback. Please see our responses below; we are glad to clarify further as needed during the discussion period.

• Improvement for small $\varepsilon$: First, by modifying the parameter settings, we can recover the previous best results when $\epsilon \ge \Omega(1)$; second, as the non-private regret $\sqrt(T)$ can dominate the private cost in regret when $\epsilon$ is large, the high privacy regime is interesting and non-trivial. In practice, people are usually forced to use constant epsilon as smaller values of epsilon degrade the performance significantly. However, in our setting, we can get privacy for free (when the non-private regret $\sqrt{T}$ dominates) even if $\epsilon \ll 1$. Therefore finding the smallest $\varepsilon$ (or best privacy) possible that allows the non-private regret $\sqrt{T}$ is an interesting open question, and our work provides progress towards resolving it.

• Q1, Intuition for concentrated DP: Lower bounds in the oblivious setting turn out to be elusive, and prior work has only resulted in the trivial lower bound of $1/\varepsilon$. Therefore, we restricted ourselves to the family of low-switching algorithms. The choice of CDP is made so that it is easier to prove the tight composition of the privacy budget. We can prove similar (tight) lower bounds for pure DP as it has a simple tight composition (our upper bounds are tight for pure DP).

• Q2, non-lazy algorithms: The classic Multiplicative Weights algorithm (that draws a fresh sample at each iteration) may be non-lazy, but still satisfies Assumption 3.1. As long as it satisfies Assumption 3.1, we can prove the regret bound as claimed.

• Q3, setting of $\varepsilon$ in Theorem 3.2: The theorem provides a way to calculate $\varepsilon$ based on the parameters of the algorithms such as $\eta$ and $p$. As a result, we can tolerate much smaller values of $\varepsilon$: indeed, in Theorem 3.9 and Theorem 3.11, we instantiate Theorem 3.2 with several hyperparameters that result in small values of $\varepsilon$. Hope this clarifies your concern.