Private Online Learning via Lazy Algorithms

Authors: hilal  asi
tomer  koren
daogao  liu
kunal  talwar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:00:27

Abstract: We study the problem of private online learning, specifically, online prediction from experts (OPE) and online convex optimization (OCO). 
   We propose a new transformation that transforms lazy online learning algorithms into private algorithms. We apply our transformation for differentially private OPE and OCO using existing lazy algorithms for these problems. Our final algorithms obtain regret which significantly improves the regret in the high privacy regime $\varepsilon \ll 1$, obtaining $\sqrt{T \log d} + T^{1/3} \log(d)/\varepsilon^{2/3}$ for DP-OPE and $\sqrt{T} + T^{1/3} \sqrt{d}/\varepsilon^{2/3}$ for DP-OCO. We also complement our results with a lower bound for DP-OPE, showing that these rates are optimal for a natural family of low-switching private algorithms.

Main paper: 
 introduction: 
 Online learning is a fundamental problem in machine learning, where an algorithm interacts with an oblivious adversary for T rounds. First, the oblivious adversary chooses T loss functions ℓ 1 , . . . , ℓ T : X → R over a fixed decision set X . Then, at any round t, the algorithm chooses a model x t ∈ X , and the adversary reveals the loss function ℓ t . The algorithm suffers loss ℓ t (x t ), and its goal is to minimize its cumulative loss compared to the best model in hindsight, namely its regret:Reg T = T t=1 ℓ t (x t ) -min x ⋆ ∈X T t=1 ℓ t (x ⋆ ).In this work, we study two different differentially private instances of this problem: differentially private online prediction from experts (DP-OPE) where the model x can be chosen from d experts (X = [d]); and differentially private online convex optimization (DP-OCO) where the model belongs to a convex set X ⊂ R d .Both problems have been extensively studied recently [JKT12, ST13, JT14, AS17, KMS + 21] and an exciting new direction with promising results for this problem is that of designing private algorithms based on low-switching algorithms for online learning [AFKT23b, AFKT23a, AKST23a, AKST23b] . The main idea in these works is that the privacy cost for privatizing a low-switching algorithm can be significantly smaller as these algorithms do not update their models too frequently, allowing them to allocate a larger privacy budget for each update. This has been initiated by [AFKT23b] , which used the shrinking dartboard algorithm to design new algorithms for DP-OPE, later revisited by [AKST23a] to design new algorithms for DP-OCO using a regularized follow-the-perturbedleader approach, and more recently by [AKST23b] which used a lazy and regularized version of the multiplicative weights algorithm to obtain improved rates for DP-OCO.This workDP-OPE √ T log d + min{ √ d , T 1/3 } log d ε [AS17, AFKT23b] √ T log d + T 1/3 log d ε 2/3 DP-OCO min d 1/4 √ T √ ε , √ T + T 1/3 √ d ε + T 3/8 √ d ε 3/4 [KMS + 21, AKST23b] √ T + T 1/3 √ d ε 2/3Table 1: Regret for approximate (ε, δ)-DP algorithms. For readability, we omit logarithmic factors that depend on T and 1/δ. While all of these results build on lazy-switching algorithms for designing private online algorithms, each one of them has a different method for achieving privacy and, to a greater extent, a different analysis. Moreover, it is not clear whether these transformations from lazy to private algorithms in prior work have fulfilled the full potential of lazy algorithms for private online learning and whether better algorithms are possible through this approach. Indeed, the regret obtained in prior work [AFKT23b, AKST23b] is T 1/3 /ε (omitting dependence on d) for DP-OPE, which implies that the normalized regret is 1/T2/3 ε: this is different than what exhibited in a majority of scenarios of private optimization, where the normalized error is usually a function of T ε. Our main contribution in this work is a new transformation that converts lazy online learning algorithms into private algorithms with similar regret guarantees, resulting in new state-of-the-art rates for DP-OPE and DP-OCO. We provide a summary in Table 1 and Figure 1 .L2P: a transformation from lazy to private algorithms (Section 3). Our main contribution is a new transformation, we call L2P, that allows converting any lazy algorithm into a private one with only a slight cost in regret. This allows us to use a long line of work on lazy online learning [KV05, GVW10, AT18, CYLK20, SK21, AKST23a] to design new algorithms for the private setting. Our transformation builds on two new techniques: first, we design a new switching rule that only depends on the loss at the current round, so as to minimize the privacy cost of each switching and mitigate the accumulation of privacy loss. Second, we rely on a simple, key observation that by grouping losses in a large batch, we can minimize the effect on the regret of lazy online learning algorithms. We introduce a new analysis for the regret of lazy online algorithms with a large batch size that improves over the existing analysis in [AFKT23b] ; this allows us to reduce the total number of "fake switches" needed to guarantees privacy, improving the final regret.Faster rates for DP-OPE (Section 3.1). As a first application, we use our transformation in the DP-OPE problem on the multiplicative weights algorithm [AHK12] . This results in a new algorithm for DP-OPE that has regret T log(d) + T 1/3 log(d)/ε 2/3 , improving over the best existing results for the high-dimensional regime in which the regret isT log(d) + T 1/3 log(d)/ε [AFKT23b]. 2The improvement is particularly crucial in the high-privacy regime, where ε ≪ 1: indeed, our regret shows that (for d = poly(T )) it is sufficient to set ε ≥ T -1/4 for matching the optimal non-private regret √ T log d, whereas previous results require a much larger ε ≥ T -1/6 to get privacy for free. This is also important in practice, when multiple applications of DP-OPE are necessary: using advanced composition, our result shows that we can solve K ≈ √ T instances of DP-OPE with ε = 1 and still obtain the non-private regret of order √ T ; in contrast, prior work only allows to solve K ≈ T 1/3 instances while still attaining the non-private regret.Faster rates for DP-OCO (Section 3.2). As another application, we use our transformation for DP-OCO with the regularized multiplicative weights algorithm of [AKST23b] . We obtain a new algorithm for DP-OCO that has regret√ T + T 1/3 √ d/ε 2/3, improving over the best existing results that established regret√ T + T 1/3 √ d/ε + T 3/8 √ d/ε 3/4 [AKST23b] or d 1/4 √ T / √ ε using DP-FTRL [KMS + 21].Lower bounds for low-switching private algorithms (Section 4). To understand the limitations of low-switching private algorithms, we prove a lower bound for the natural family of private algorithms with limited switching, showing that the upper bounds obtained via our reduction are nearly tight for this family of algorithms up to logarithmic factors. This shows that new techniques, beyond limited switching, are required in order to improve upon our upper bounds.Our transformation and algorithms build on a long line of work in online learning with limited switching [KV05, GVW10, AT18, CYLK20, SK21, AKST23b]. As is evident from prior work in private online learning, the problems of lazy online learning and private online learning are tightly connected [AFKT23b, AFKT23a, AKST23a, AKST23b] . In this problem, the algorithm wishes to minimize its regret while making at most S switches: the algorithm can update the model at most S times throughout the T rounds. Recent work has resolved the lazy OPE problem: [AT18] show a lower bound ofT + (T /S) log(d) on the regret, which is achieved by several algorithms such as Follow-the-perturbed-leader [KV05] and the shrinking dartboard algorithm [GVW10] . For lazy OCO, however, optimal rates are yet to be known: [AKST23b] recently show that a lazy version of the regularized multiplicative weights algorithm obtains regretT + (T /S) √ d, whereas the best lower bound is√ T + T /S [SK21]. 
problem setup: 
 We consider an interactive T -round game between an algorithm ALG and an oblivious adversary Adv. Before the interaction, the adversary Adv chooses T loss functions ℓ 1 , . . . , ℓ T ∈ L = {ℓ | ℓ : X → R}. Then, at each round t ∈ [T ], the algorithm ALG, which observed ℓ 1 , • • • , ℓ t-1 chooses x t ∈ X , and then the loss function ℓ t chosen by Adv is revealed. The regret of the algorithm ALG is defined below:Reg T (ALG) := T t=1 ℓ t (x t ) -min x * ∈X T t=1 ℓ t (x * ).We study online optimization under the constraint that the algorithm is differentially private. For an algorithm ALG and a sequence S = (ℓ 1 , . . . , ℓ T ) chosen by an oblivious adversary Adv, we let ALG(S) := (x 1 , . . . , x T ) denote the output of ALG over the loss sequence S. We have the following definition of privacy against oblivious adversaries. 3Definition 2.1 (Differential privacy). A randomized algorithm ALG is (ε, δ)-differentially private against oblivious adversaries ((ε, δ)-DP) if, for all neighboring sequences S = (ℓ 1 , . . . , ℓ T ) ∈ L T and S ′ = (ℓ ′ 1 , . . . , ℓ ′ T ) ∈ L T that differ in a single element, and for all events O in the output space of ALG, we havePr[ALG(S) ∈ O] ≤ e ε Pr[ALG(S ′ ) ∈ O] + δ.We focus on two important instances of differentially private online optimization:(i) DP Online Convex Optimization (DP-OCO). In this problem, the adversary picks loss functions ℓ ∈ L OCO := {ℓ | ℓ : X → R is convex and L-Lipschitz} where X ⊂ R d is a convex set with diameter D = diam(X ) := sup x,y∈X ∥x -y∥, and the algorithm chooses x t ∈ X . The goal of the algorithm is to minimize regret while being (ε, δ)-differentially private.(ii) DP Online Prediction from Experts (DP-OPE). In this problem, the adversary picks lossfunctions ℓ ∈ L OP E = {ℓ | ℓ : [d] → [0, 1]} where X = [d]is the set of d experts, and the algorithm choosesx t ∈ [d].The goal of the algorithm is to minimize regret while being (ε, δ)-differentially private.Our analysis crucially relies on the following divergence between two distributions. Definition 2.2 (δ-Approximate Max Divergence). For two distributions µ and ν, we defineD δ ∞ (µ∥ν) := sup S⊆supp(µ),µ(S)≥δ ln µ(S) -δ ν(S) . 
l2p: from lazy to private algorithms for online learning: 
 This section presents our L2P transformation, which turns lazy online learning algorithms into private ones. The transformation has an input algorithm A with measure µ t at round t and samples x t from the normalized measure µ t , which satisfies the following condition: Assumption 3.1. The online algorithm A has at time t a measure µ t that is a function of ℓ 1 , . . . , ℓ t-1 (and density function µ t ) such that for some δ 0 ≤ 1 and 0 < η ≤ 1/10 that are data-independent, we have• D δ0 ∞ (µ t+1 , µ t ) ≤ η, • µ t+1 (x)/µ t (x) = func(ℓ t , x) for all x ∈ Xwhere func is a data-independent function. While algorithms satisfying Assumption 3.1 need not be lazy, this assumption is satisfied by most existing lazy online learning algorithms such as the shrinking dartboard (Section 3.1) and lazy regularized multiplicative weights (Section 3.2). Moreover, any algorithm that satisfies this assumption can be made lazy via our reduction.Technique Overview: Suppose the neighboring datasets differ from the s 0 -th loss function. The high-level intuition behind our framework is that our algorithm only loses the privacy budget when it makes a switch (draws a fresh sample) whenever t > s 0 . Hence, in the framework, we try to make the algorithm make as few switches as possible. This modification can lead to additional regret compared to lazy online learning algorithms, and we need to balance the privacy-regret trade-off. The family of low-switching algorithms is ideal for privatization because its built-in low-switching property can achieve a better trade-off.Our starting point is the ideas in [AFKT23b, AKST23b] to privatize low-switching algorithms, which use correlated sampling to argue that a sample from x t-1 ∼ µ t-1 is likely a good sample from µ t and therefore switching at round t is often not necessary. In particular, at round t, these algorithms sample a Bernoulli random variable S t ∼ Ber(c • µ t (x t-1 )/µ t-1 (x t-1 )) for some constant c and use the same model x t = x t-1 if S t = 1, and otherwise sample new model x t ∼ µ t if S t = 0 (which happens with small probability). This guarantees that the marginal probability of the lazy iterates remains the same as the original iterates. Finally, to preserve the privacy of the switching decisions, existing algorithms add a fake switching probability p where the algorithm switches independently of the input. To summarize, existing low-switching private algorithms work roughly as follows:            At each round t:-Sample S t ∼ Ber(C • µ t (x t-1 )/µ t-1 (x t-1 )) and S ′ t ∼ Ber(1 -p) -Sample new x t ∼ µ t if S t = 0 or S ′ t = 0 -Otherwise set x t = x t-1This sketch is the starting point of our transformation, and we will introduce two new components to improve performance. The first component aims to avoid the accumulation of privacy cost for switching in the current approaches where each user can affect the switching probability for all subsequent rounds: this happens since µ t (x t-1 )/µ t-1 (x t-1 ) is usually a function of the whole history ℓ 1 , . . . , ℓ t , and hence the existing low-switching private algorithms lose the privacy budget even it does not make real switches. To address this, we deploy a new correlated sampling strategy in L2P where the loss ℓ t at time t affects the switching probability only at time t, hence paying a privacy cost for switching only in a single round. To this end, we construct a parallel sequence of models {y t } t∈[T ] (independent of x t ) that is used for normalizing the ratio µ t (x t-1 )/µ t-1 (x t-1 ) to become independent of the history. In particular, at round t, we switch with probability proportional toµ t (x t-1 ) µ t-1 (x t-1 ) • µ t-1 (y t-1 ) µ t (y t-1) .The main observation here is that µ t (xt-1)µ t-1 (xt-1) • µ t-1 (yt-1) µ t (yt-1) = µt(xt-1) µt-1(xt-1) • µt-1(yt-1)µt(yt-1) and this ratio is a function of ℓ t our input online learning algorithms which satisfies Assumption 3.1. This will, therefore, improve the privacy guarantee of the final algorithm.The second main observation in L2P is that having a large batch size (batching rounds together) does not significantly affect the regret of lazy online algorithms compared to non-lazy algorithms but can further reduce the times to make switches and save the privacy budget. Our main novelty is a new analysis of the effect of batching on the regret of lazy algorithms (Proposition 3.3), which states that running a lazy online algorithm with a batch size of B would have an additive error of T B 2 η 2 to the regret where η is a measure of distance between µ t and µ t-1 . This significantly improves over existing analysis by [AFKT23b, Theorem 2] which shows that batching can add an additive term of B/η to the regret.Having reviewed our main techniques, we proceed to present the full details of our L2P transformation in Algorithm 1, denoting ν s = µ (s-1)B+1 where B is the batch size.The regret of our transformation depends on the regret of its input algorithm. For the measure {µ t } T t=1 , we denote its regretReg T ({µ t } T t=1 ) := T t=1 E xt∼µ t [ℓ t (x t )] -min x∈X T t=1 ℓ t (x).The following theorem summarizes the main guarantees of Algorithm 1. Theorem 3.2. Let p ∈ (0, 1) and B ∈ N. Assuming Assumption 3.1, T p/B ≥ 1, and for anyδ 1 > 0 such that ηB log(1/δ 1 )/p ≤ 1, our transformation L2P is (ε, δ)-DP with ε = 2η p + η + 3T η 2 p log(1/δ 1 ) 2B + 6T η 2 p log 2 (1/δ 1 )/B, Algorithm 1: L2P Input: Parameter η, measures {ν t } t∈[T ], batch size B, fake switching parameter p ; Sample x 1 , y 1 ∼ ν 1 ; Observe ℓ 1 , . . . , ℓ B and suffer lossB i=1 ℓ i (x 1 ); for s = 2, • • • , T /B do Sample S s ∼ Ber min 1, νs(xs-1) e 2Bη νs-1(xs-1) • νs-1(ys-1) νs(ys-1) and S ′ s ∼ Ber(1 -p); if S s = 0 or S ′ s = 0 then Sample x s ∼ ν s ; else Set x s = x s-1 ; Sample A s ∼ Ber(1 -p); if A s = 0 then Sample y s ∼ ν s ; else Set y s = y s-1 ; Play x s ;Observe ℓ (s-1)B+1 , . . . , ℓ sB and suffer loss sB i=(s-1)B+1 ℓ i (x s );δ = 2T (2/η + log(1/δ 1 )/p)eBδ 0 + 2T δ 1 ,and has regretReg T ≤ Reg T ({µ t } T t=1 ) + O T B 2 η 2 + δ 0 T 2 log( 1 δ1 ) η .We begin by proving the utility guarantees of our transformation. It will follow directly from the following proposition, which bounds the regret of running L2P over a lazy online learning algorithm. Proposition 3.3 (Regret of Batched Lazy Algorithm). Let ALG be an online learning algorithm that satisfies Assumption 3.1. Let ηB log(1/δ 1 )/p ≤ 1, and δ 1 , η < 1/2. Then running L2P with the input algorithm ALG has regretReg T ≤ Reg T ({µ t } T t=1 ) + O T B 2 η 2 + δ 0 T 2 log( 1 δ1 ) η .To prove Proposition 3.3, we first show that we can instead analyze the utility of a simpler algorithm that samples from ν s at each round. This is due to the following lemma, which shows that ∥ ν s -ν s ∥ T V is small where ν s is the marginal distribution of x s in Algorithm 1. Lemma 3.4. Let ν s be the marginal distribution ofx s in Algorithm 1. When ηB log(1/δ 1 )/p ≤ 1, we have ∥ ν s -ν s ∥ T V ≤ 3(s -1)(2e + log(1/δ 1 )/p)Bδ 0 .We also require the following lemma which allows to build a coupling over multiple variables, such that the variables are as close as possible. This will be used to construct a coupling between the lazy algorithm and the L2P algorithm that runs it. Lemma 3.5 ([AS19]). Given a collection S of random variables, all absolutely continuous w.r.t. a common σ-finite measure. Then, there exists a coupling Γ, such that for any variables X, Y ∈ S, we have Pr[X ̸ = Y ] ≤ 2∥X-Y ∥ T V 1+∥X-Y ∥ T V .We are now ready to prove Proposition 3.3Proof. Let Reg ′ T denote the regret when the marginal distribution of x t is ν t instead of ν t induced in the Algorithm. Since each loss function is bounded,Reg T ≤ Reg ′ T + B s∈[T /B] ∥ν s -ν s ∥ T V .By Lemma 3.4, we haveReg T ≤ Reg ′ T + B s∈[T /B] 3(s -1)(2/η + log(1/δ 1 )/p)eBδ 0 ≤ Reg ′ T + 8T 2 δ 0 log(1/δ 1 )/η.Thus, it now suffices to upper bound Reg ′ T . Due to the preconditions that D δ0 ∞ (µ i+1 , µ i ) ≤ η and δ 0 ≤ η, we know ∥µ i+1 -µ i ∥ T V ≤ 2η. Recall that we assume x s ∼ ν s . Suppose z i is the action taken by the input lazy algorithm A for i ∈ [T ] and the marginal distribution of z i is µ i . By Lemma 3.5, we can construct a coupling Γ s between x s and z := (z (s-1)B+1 , • • • , z sB ), such thatPr (xs,z)∼Γs [∃i ∈ [(s -1)B + 1, sB], z i ̸ = x s ] ≤ Bη. Letting I s = 1(∃i ∈ [(s -1)B + 1, sB], z i ̸ = x s ), we have E xs∼νs sB i=(s-1)B+1 ℓ i (x s ) = E (xs,z)∼Γs sB i=(s-1)B+1 ℓ i (x s ) = E xs,z∼Γs (1 -I s ) sB i=(s-1)B+1 ℓ i (z i ) + E xs,z∼Γs I s sB i=(s-1)B+1 ℓ i (x s ) ≤ E xs,z∼Γs (1 -I s ) sB i=(s-1)B+1 ℓ i (z i ) + E xs,z∼Γs I s sB i=(s-1)B+1 (ℓ i (z i ) + O(Bη)) ≤ E zi∼µ i sB i=(s-1)B+1 ℓ i (z i ) + O(Bη • B 2 η).′ T ≤ Reg T ({µ t } T t=1 ) + T B • O(B 3 η 2 ), which completes the proof. Now we turn to prove the privacy of L2P. We begin with the following lemma, which provides the privacy guarantees of sampling a new model x t from the distribution µ t . We defer the proof to Appendix B. Lemma 3.6. Let {µ t } T t=0 satisfy Assumption 3.1 where η ≤ 1/10. Then for any neighboring sequences S and S ′ with corresponding {µ t } T t=0 and {µ ′ t } T t=0 that differ one loss function, we haveD 4δ0 ∞ (µ t , µ ′ t ) ≤ 2η.We use correlated sampling in the algorithm rather than sampling from x t directly. To this end, we need the following lemma, which provides upper and lower bounds on the ratio used for correlated sampling. Lemma 3.7. For any s ∈ [T /B], if ηB log(1/δ 1 )/p ≤ 1, then with probability at least 1 -(2/η + log(1/δ 1 )/p) • eBδ 0 -δ 1 , ν s+1 (x s ) ν s (x s ) • ν s (y s ) ν s+1 (y s ) ∈ [e -2Bη , e 2Bη ].The privacy proof will build on the previous two lemmas to control the privacy cost of updating the model and the cost of the switching time. We defer the proof to Appendix B.One remaining issue is we need to conditional on the high probability events in Lemma 3.7 for the privacy guarantee and can not directly apply Advanced Composition (Lemma A.3). Now, we modify the Advanced Composition for our usage. In the classic k-fold adaptive composition experiment, the adversary, after getting the first i -1 answers Y 1 , • • • , Y i-1 (denoted by Y [i-1]for simplicity), can output two datasets D 0 i and D 1 i , a query q i , and receives the answer In our case, however, we know there exists a subsetY i ∼ M i (D b i , q i ) for the secret bit b ∈ {0, 1}. If each M i is (ε i , δ i )-DP,G i-1 (D b [i-1]), such that with probability at leastEQUATIONThen we have the following lemma: Lemma 3.8. Given the k mechanisms satisfying the Condition (1), then the class of mechanisms satisfy(ε δ , 1 -(1 -δ)Π t∈[k] (1 -δt )) + 2 t∈[k] λ t -DP under k-fold adaptive composition, with εδ defined in Equation (4).Proof. Without losing generality, suppose we know the adversary and how they generate the databases and queries. We can construct a series of mechanismsM ′ i , such that M ′ i draws Y i from M i (D b i , q i ), and outputs Y i if Y i ∈ ∩ b∈{0,1} G i-1 (D b [i-1]), and outputs0 otherwise. Let (Y ′ 1,b , • • • , Y ′ k,b) be the outputs of M ′ i with secret bit b, and we know the TV distance between(Y ′ 1,b , • • • , Y ′ k,b ) and (Y 1,b , • • • , Y k,b ) is at most t∈[k] λ t for any b ∈ {0, 1}. Moreover, we know (Y ′ 1,0 , • • • , Y ′ k,0 ) ≈ εδ,1-(1-δ)Π t∈[k] (1-δt)) (Y ′ 1,1 , • • • , Y ′ k,1 )by the advanced composition. The basic composition finishes the proof.This section discusses the first application of our transformation to differentially private online prediction from experts (DP-OPE). Towards this end, we apply our transformation over the multiplicative weights algorithms [AHK12] , which can be made lazy as done in the shrinking dartboard algorithm [GVW10] . It has the following measure at round tEQUATIONThe following proposition shows that this measure satisfies the desired properties required by our transformation. We let µ mw t denote the density corresponding to µ mw t . Lemma 3.9. Assume ℓ 1 , . . . , ℓ T where ℓt : [d] → [0, 1]. Then we have that 1. D δ0 ∞ (µ mw t+1 , µ mw t ) ≤ η with δ 0 = 0.2.µ mw t+1 (x) µ mw t (x) = e -ηℓt(x) for all x ∈ [d].Proof. The first item follows from the guarantees of the exponential mechanism asℓ t (x) ∈ [0, 1] for all x ∈ [d].The second item follows immediately from the definition of µ mw .Having proved our desired properties, our transformation now gives the following theorem. Theorem 3.10 (DP-OPE). Let ℓ 1 , . . . , ℓ T where ℓ t : [d] → [0, 1]. Setting B = 1/ε and η = min(ε 0 , ε) 2/3 /T 1/3 where ε 0 = T -1/4 log 3/4 d, the L2P transformation (Algorithm 1) applied with the measure {µ mw t } T t=1 is (ε, δ)-DP and has regretReg T = O T log d + T 1/3 log d ε 2/3 .Proof. First, based on theorem 3.2, note that the setting of B = 1/ε and η ≤ min(ε 0 , ε) 2/3 /T 1/3 where ε 0 = T -1/4 log 3/4 d guarantee the algorithm is (ε, δ)-DP.To upper bound the regret, we use existing guarantees of the multiplicative weights algorithm [AHK12] , combined with Theorem 3.2 to get that the regret isReg T ≤ O ηT + log(d) η + T B 2 η 2 ≤ O ηT + log(d) η + T η 2 ε 2 ≤ O (T ε 0 ) 2/3 + T 1/3 log(d) ε 2/3 + T 1/3 ε 2/3 ≤ O T log d + T 1/3 log(d) ε 2/3 ,where the second inequality follows by setting B = 1/ε, and the third inequality follows by setting η ≤ min(ε 0 , ε) 2/3 /T 1/3 , and the last inequality follows since ε 0 = T -1/4 log 3/4 d.In this section, we use our transformation for differentially private online convex optimization (DP-OCO) using the regularized multiplicative weights algorithm [AKST23b] , which has the following measureEQUATIONLetting µ rmw denote the corresponding density function, we have the following properties. Lemma 3.11. Assume ℓ 1 , . . . , ℓ T : X → R be convex and L-Lipschitz functions. Then we have that1. D δ0 ∞ (µ rmw t+1 , µ rmw t ) ≤ η where η = 2βL 2 λ + 8βL 2 log(2/δ0) λ .2.µ rmw t+1 (x) µ rmw t (x) = e -βℓt(x) for all x ∈ X .Proof. The first item follows from Lemma 3.5 in [GLL22, AKST23b] . The second item follows immediately from the definition of µ rmw t .Combining these properties with our transformation, we get the following result. Theorem 3.12 (DP-OCO). Let ℓ 1 , . . . , ℓ T : X → R be convex and L-Lipschitz functions. Setting B =1 2ε log(1/δ) , λ = L D max{ √ T , √ d log T η }, β = η 2 λ/20L 2 , η = ε 2/3T 1/3 log(T /δ) and p = η/ε, the L2P transformation (Algorithm 1) applied with the measure {µ rmw t } T t=1 is (ε, δ)-DP and has regretReg T = LD • O √ T + T 1/3 √ d log T log(T /δ) ε 2/3 .Proof. First, based on Theorem 3.2, note that there are three constraints to make the algorithm private:η/p ≤ ε/2, η T p log(1/δ)/B ≤ ε/2, ηB log(1/δ)/p ≤ 1. Setting of B = 1 2ε log(1/δ) , λ = L D max{ √ T , √ d log T η }, β = η 2 λ/20L 2 , η = ε 2/3T 1/3 log(T /δ) and p = η/ε guarantees the algorithm is (ε, δ)-DP.For utility, we use theorem 3.2 with the existing regret bounds for the regularized multiplicative weights algorithm (Theorem 4.1 in [AKST23b] ) to get that the algorithm has regretReg T ≤ O λD 2 + L 2 T λ + d log(T ) β + LDT B 2 η 2 ≤ O LD √ T + λD 2 + L 2 d log T λη 2 + LDT B 2 η 2 ≤ LD • O √ T + T 1/3 √ d log T log(T /δ) ε 2/3 .4 Lower bound for low-switching private algorithmsIn this section, we prove a lower bound for DP-OPE for a natural family of private low-switching algorithms that contains most of the existing low-switching private algorithms such as our algorithms and the ones in [AFKT23b, AKST23b] . Our lower bound matches our upper bounds for DP-OPE and suggests that new techniques beyond limited switching are required in order to obtain faster rates.For our lower bounds, we will assume that the algorithm satisfies the following condition: Condition 4.1. (Limited switching algorithms) The online algorithm ALG works as follows: at each round t, ALG is allowed to either set x t+1 = x t or sample x t+1 ∼ µ t+1 where µ t+1 is a function of ℓ 1 , . . . , ℓ t and is supported over X . The algorithm releases the resampling rounds {t 1 , . . . , t S } and models {x t1 , . . . , x t S }.Our lower bound will hold for algorithms that satisfy concentrated differential privacy. We use this notion as it allows to get tight characterization of the composition of private algorithms and in most settings have similar rates to approximate differential privacy. We can also prove a tight lower bound for pure differential privacy using the same techniques. We have the following lower bound for concentrated DP. We defer the proof to Appendix C.Theorem 4.2. Let T ≥ 1 and ε ≥ 100 log 3/2 (dT )/T . If an algorithm ALG satisfies Condition 4.1 and is ε 2 -CDP, then there exists an oblivious adversary that chooses ℓ 1 , . . . , ℓ T : [d] → [0, 1] such that the regret is lower bounded byReg T ≥ Ω √ T + T 1/3 ε 2/3 .Finally, we note that this lower bound only holds for switching-based algorithms: indeed, the binary-tree-based algorithm of [AS17] obtains regret √ d log(d)/ε which is better in the lowdimensional regime. This motivates the search for new strategies beyond limited switching for the high-dimensional regime. 
conclusion: 
 In this paper, we proposed a new transformation that allows the conversion of lazy online learning algorithms into private algorithms and demonstrates two applications (DP-OPE and DP-OCO) where this transformation offers significant improvements over prior work. Moreover, for DP-OPE, we show a lower bound for natural low-switching-based private algorithms, which shows that new techniques are required for low-switching algorithms to improve our transformation's regret. This begs the question of whether the same lower bound holds for all algorithms or whether a different strategy that breaks the low-switching lower bound exists. As for DP-OCO, it is interesting to see whether better upper or lower bounds can be obtained. The current normalized regret, omitting logarithmic terms, is proportional to√ d/(εT ) 2/3. This is different than most applications in private optimization where the normalized error is usually a function of √ d/(εT ). Hence, it is natural to conjecture that the normalized regret can be improved to d 1/3 /(εT ) 2/3 . 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: We do not believe our paper poses a significant negative societal impact, as it is about making existing learning algorithms differentially private under less stringent distributional assumptions, which we do not foresee being used in any significant malicious cases. We do believe that our algorithms can have positive societal impacts, but do not wish to overclaim to this effect because our results are primarily theoretical.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper does not release data or models. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: In this section, we provide additional preliminaries and provide missing details for some of the results in the preliminaries section.For our lower bounds, we require the notion of concentrated differential privacy. To this end, we first define the α-Renyi divergence (α > 1) between two probability measures:D α (µ∥ν) := 1 α -1 log µ(ω) ν(ω) α dν(ω) .Concentrated DP is defined below: Definition A.1 (concentrated DP). Let ρ ≥ 0. We say an algorithm ALG satisfies ρ-concentrated differential privacy (ρ-CDP) against oblivious adversaries if for any neighboring sequences S = (ℓ 1 , . . . , ℓ T ) ∈ L T and S ′ = (ℓ ′ 1 , . . . , ℓ ′ T ) ∈ L T that differ in a single element, and any α ≥ 1, D α (ALG(D)∥ALG(D ′ )) ≤ αρ. Now we list a few standard results from the privacy literature that we use in the paper, namely group privacy and privacy composition. Lemma A.2. (Group Privacy) Let ALG be an (ε, δ)-DP algorithm and let S, S ′ L T be two datasets that differ in k elements. Then for any measurable set S in the output space of ALGPr[ALG(S) ∈ O] ≤ e kε Pr[ALG(S ′ ) ∈ O] + ke (k-1)ε δ.Lemma A.3 (Advanced Composition, [KOV15] ). For any ε t > 0, δ t ∈ (0, 1) for t ∈ [k], and δ ∈ (0, 1), the class of (ε t , δ t )-DP mechanisms satisfyEQUATIONMoreover, we use the fact that distributions with bounded D δ ∞ satisfy the following property.Lemma A.4. Let ε ≤ 1/10. If D δ ∞ (µ, ν) ≤ ε/2 then we have Pr X∼µ e -ε ≤ µ(X) ν(X) ≤ e ε ≥ 1 -6δ/ε and Pr X∼ν e -ε ≤ µ(X) ν(X) ≤ e ε ≥ 1 -6δ/ε.Finally, we have the following standard conversion from ρ-concentrated DP to (ε, δ)-DP.). If ALG is ρ-CDP with ρ ≤ 1, then it is (3 ρ log(1/δ), δ)-DP for all δ ∈ (0, 1/4).Let S ′ = {X : µ(X) ν(X) ∈ [e -ε , e ε ]}, and assume towards a contradiction that µ(S ′ ) < 1 -6δ/ε. Then there is a set S = S ′ , such that µ[S] > 6δ/ε. We divide S by letting S 1 = {X ∈ S : µ(X)/ν(X) > e ε } and S 2 = S \ S 1 .Case (1): µ(S 1 ) ≥ µ(S)/2 ≥ 3δ/ε. Then we knowln µ(S 1 ) -δ ν(S 1 ) > ln e ε µ(S 1 ) -δ µ(S 1 ) ≥ ln e ε 3/ε -1 3/ε ≥ ln e ε/2 = ε/2,where we use that µ(S 1 ) ≥ e ε ν(S 1 ) and 1 -ε/3 ≥ e -ε/2 for ε < 1/10. This is a contradiction.Case (2): Suppose µ(S 2 ) ≥ 3δ/ε. We know S 2 = {X ∈ S : µ(X)/ν(X) < e -ε } = {X ∈ S : ν(X)/µ(X) > e ε }. Then we know ν(S 2 ) ≥ e ε µ(S 2 ) ≥ 3e ε δ/ε. Similarly, we haveln ν(S 2 ) -δ µ(S 2 ) > ε/2.This is a contradiction as well and proves the statement.The regret bound follows directly from Proposition 3.3. It suffices to prove the privacy guarantee.Fix two arbitrary neighboring datasets S and S ′ , and suppose the sequences differ at t 0 -step, that is {ℓ (t0-1)B+1 Pr(E G ) = Pr[ T /B t=2 1(A t = 0 or S ′ t = 0) ≤ 2T p log(1/δ 1 )/B] ≥ 1 -δ 1 .We also let E t be the event such thatνt+1(xt) νt(xt) • νt(yt) νt+1(yt) ∈ [e -2Bη , e 2Bη ]. Lemma 3.7 implies that Pr[E t ] ≥ 1 -(2/η + log(1/δ 1 )/p)eBδ 0 -δ 1 for any t. Define E ′ t in a similar way. Then it suffices to show {(x t , y t , ζ t )} t∈[T ] and {(x ′ t , y ′ t , ζ ′ t )} t∈[T ] are (ε, δ x )-indistinguishable con- ditional on E := E G ∪ E ′ G ∪ t∈[T /B] (E t ∪ E ′ t ). Then this will imply that {(x t , y t , ζ t )} t∈[T ] and {(x ′ t , y ′ t , ζ ′ t )} t∈[T ] are (ε, δ x + (2T + 2)δ 1 + 2T (2/η + log(1/δ 1 )/p)eBδ 0 )-indistinguishable. Now we show, conditional on E, any value Σ such that Σ t-1 = Σ ′ t-1 = Σ, (x t , y t , ζ t ) and (x ′ t , y ′ t , ζ ′ t ) are (ε t , δ 0 )-indistinguishable where ε t =    0, t < t 0 2η/p t = t 0 ζ t • η t > t 0 (5)Case 1 (t < t 0 ): It is clear that the claim is correct for t ≤ t 0 as (x t , y t , ζ t ) and (x ′ t , y ′ t , ζ ′ t ) have the same distribution then.Case 2 (t = t 0 ): Now consider the case where t = t 0 .Note that (x t0 , y t0 ) and (x ′ t0 , y ′ t0 ) have identical distributions, and it suffices to consider the indistinguishability of ζ t0 and ζ ′ t0 . We havePr[ζ t0 = 0 | Σ t0-1 , x t0 , y t0 ] Pr[ζ ′ t0 = 0 | Σ ′ t0-1 , x ′ t0 , y ′ t0 ] = (1 -p) 2 νt 0 +1(xt 0 ) e 2Bη νt 0 (xt 0 ) • νt 0 (yt 0 ) νt 0 +1(yt 0 ) (1 -p) 2 ν ′ t 0 +1 (x ′ t 0 ) e 2Bη ν ′ t 0 (x ′ t 0 ) • ν ′ t 0 (y ′ t 0 ) ν ′ t 0 +1 (y ′ t 0 ) = ν t0+1 (x t0 ) ν ′ t0+1 (x t0 ) • ν ′ t0+1 (y t0 ) ν t0+1 (y t0 ) ≤ e 2η .Similarly, we havePr[ζ t0 = 1 | Σ t0-1 , x t0 , y t0 ] Pr[ζ ′ t0 = 1 | Σ ′ t0-1 , x ′ t0 , y ′ t0 ] = 1 -(1 -p) 2 + (1 -p) 2 (1 - νt 0 +1(xt 0 ) e 2Bη νt 0 (xt 0 ) νt 0 (yt 0 ) νt 0 +1(yt 0 ) ) 1 -(1 -p) 2 + (1 -p) 2 (1 - ν ′ t 0 +1 (x ′ t 0 ) e 2Bη ν ′ t 0 (x ′ t 0 ) ν ′ t 0 (y ′ t 0 ) ν ′ t 0 +1 (y ′ t 0 ) ) = 1 + (1 -p) 2 ( ν ′ t 0 +1 (x ′ t 0 ) e 2Bη ν ′ t 0 (x ′ t 0 ) ν ′ t 0 (y ′ t 0 ) ν ′ t 0 +1 (y ′ t 0 ) - νt 0 +1(xt 0 ) e 2Bη νt 0 (xt 0 ) νt 0 (yt 0 ) νt 0 +1(yt 0 ) ) 1 -(1 -p) 2 + (1 -p) 2 (1 - ν ′ t 0 +1 (x ′ t 0 ) e 2Bη ν ′ t 0 (x ′ t 0 ) ν ′ t 0 (y ′ t 0 ) ν ′ t 0 +1 (y ′ t 0 ) ) ≤ 1 + e 2η -1 p ≤ e 2η/p .Case 3 (t > t 0 ): As for the case when t > t 0 , when ζ t = 0 (A t+1 = S t+1 = S ′ t+1 = 1), the variables are 0-indistinguishable since x t = x t-1 and y t = y t-1 in this case. Consider the remaining possibility. Given the assumption that µ t+1 /µ t is a function of ℓ t , for any possible Σ, we havePr[ζ t = 1 | Σ t-1 = Σ] = Pr[ζ ′ t = 1 | Σ ′ t-1 = Σ].For any set S, by the assumption on µ t , we havePr[ζ t = 1, (x t , y t ) ∈ S | Σ t-1 = Σ] = Pr[(x t , y t ) ∈ S | Σ t-1 = Σ, ζ t = 1] Pr[ζ t = 1 | Σ t-1 = Σ] = Pr[(x t , y t ) ∈ S | Σ t-1 = Σ, ζ t = 1] Pr[ζ ′ t = 1 | Σ ′ t-1 = Σ] ≤e 2η Pr[(x ′ t , y ′ t ) ∈ S | Σ ′ t-1 = Σ, ζ ′ t = 1] Pr[ζ ′ t = 1 | Σ ′ t-1 = Σ] + 4δ 0 =e 2η Pr[ζ ′ t = 1, (x ′ t , y ′ t ) ∈ S | Σ ′ t-1 = Σ] + 4δ 0 ,where the inequality comes from Lemma 3.6 by the divergence bound between µ t and µ ′ t . This completes the proof of Equation (5).The final privacy guarantee follows from combining Equation (5) and Advanced composition (Lemma A.3).We prove this statement by induction. For t = 1, the statement is obviously correct. We assume∥ ν t -ν t ∥ T V ≤ 3(t -1)(2(e/η + log(1/δ 1 )/p)Bδ 0 + δ 1 ) prove that ∥ ν t+1 -ν t+1 ∥ T V ≤ 3t(2e + log(1/δ 0 )/p)Bδ 0 .Let X good := {x : log νt+1(x) νt(x) ∈ [-Bη, Bη]} and Y good := {y : log νt(y) νt+1(y) ≤ [-Bη, Bη]}. Let φ t (y) be the distribution of y t . Note that the distribution of y t is independent of {x τ } τ ∈[T /B] , while the distribution of x t+1 is independent of y t+1 but depends on y t . By the assumption and group privacy, we know D Be Bη δ0 ∞ (ν t+1 , ν t ) ≤ Bη, and hence we haveν t (Y ∁ good ) ≤ e Bη δ 0 /η ≤ 2eδ 0 /η.Let t 0 ≤ t be largest integer such that A t0 = 1, that is, y t is sampled from ν t0 for some random t 0 ≤ t. We have -t0) . With probability at least 1 -δ 1 , we know |t -t 0 | ≤ log(1/δ 1 )/p. Hence we getν t0 (Y ∁ good ) ≤ e Bη(t-t0) • ν t (Y good ) + (t -t 0 )Bδ 0 e Bη(tPr y∼ φt [y ∈ Y good ] ≥ 1 -2(e/η + log(1/δ 1 )/p)Bδ 0 -δ 1 . We know Pr x∼νt,y∼ φt [x ∈ X good , y ∈ Y good ] = Pr y∼ φt [y ∈ Y good ] Pr x∼νt [x ∈ X good | y ∈ Y good ] ≥ 1 -2(e/η + log(1/δ 1 )/p)Bδ 0 -δ 1 .Denote the good setS good = (x, y) : x ∈ X good , Y good .Proof. As ALG is ε 2 -concentrated DP and outputs T 1 , . . . , T S and Z 1 , . . . , Z S , we have thatαε 2 ≥ D α (T 1 , Z 1 , . . . , T S , Z S ||T ′ 1 , Z ′ 1 , . . . , T ′ S ′ , Z ′ S ′ ) ≥ D α (T 1 , Z 1 , . . . , T T , Z T ||T ′ 1 , Z ′ 1 , . . . , T ′ T , Z ′ T ) ≥ T i=1 D α (Z i ||Z ′ i | T i ),where the second inequality follows as the random variables T i , Z i and T ′ j , Z ′ j are constant for i > S and j > S ′ , and the last inequality follows as Z i is independent of (T 1 , . . . , T i ) and (Z 1 , . . . , Z i-1 ) given T i .We defer the proof of the following Lemma to the appendix.Lemma C.2. Let T ≥ 1, ε ≤ 1/T and δ ≤ 1/2. Assume ℓ : [d] → {0, 1} where ℓ[x] ∼ Ber(1/2) for each x ∈ [d]. Let D = (ℓ, . . . , ℓ) and let ALG be an (ε, δ)-DP algorithm that outputs (z 1 , . . . , z T ) = ALG(D). Then E[ T t=1 ℓ(z t )] ≥ T • 1 2 - T ε 2 - T 2 dδ 2 .We are now ready to prove our main lower bound.Proof. (of Theorem 4.2) We consider the following construction for the lower bound: the adversary sets S adv = (T ε) 2/3 , the sequence of losses will have E = S 2 adv epochs, each of size B = T /E = T /(T ε) 4/3 = 1 (T ε) 1/3 ε . Inside each epoch, the adversary samples ℓ ∼ Ber(1/2) d and plays the same loss function for the whole epoch.Let S be random variable denoting the number of switches in the algorithm. In this case, we argue that each switch must have a small privacy budget (Lemma C.1), and thus, the price inside each epoch has to be large (Lemma C.2). Let T 1 , . . . , T S be the rounds where the algorithm resamples (T i = T + 1 for i > S) and let Z 1 , Z 2 , . . . , Z S be the resampled models (Z i = 1 for i > S). Lemma C.1 implies that T i=1 D α (Z i ||Z ′ i | T i ) ≤B • 1 2 - 3Bεe √ log(1/δ) 2 -1/T . Letting E switch ⊂ [E]denote the epochs where there is a switch, we have that the loss of the algorithm isL(ALG) := E[ T t=1 ℓ t (x t )] = E   e / ∈E switch B 2   + E e∈E switch B 1 2 - 3Bε e log(1/δ) 2 -1/T = E (E -S) B 2 + S B 2 - e∈E switch 3B 2 ε e log(1/δ) 2 -1 = T /2 -1 - 3B 2 log(1/δ) 2 E e∈E switch ε e ≥ T /2 -1 - 3B 2 E log(1/δ)ε 2 ,where the last inequality follows since e∈E switch ε e ≤ E E e=1 ε 2 e ≤ √ Eε. Note also that the loss of the best expert isL ⋆ := min x∈[d] T t=1 ℓ t (x) = T /2 - √ EBOverall we get that the regret of the algorithm isL(ALG) -L ⋆ ≥ √ EB - 3B 2 E log(1/δ)ε 2 -1 ≥ (T ε) 2/3 T (T ε) 4/3 - 3 log(1/δ) 2(T ε) 2/3 ε 2 √ Eε -1 = T 1/3 ε 2/3 - 3 log(1/δ)E 2(T ε) 2/3 ε -1 (i) ≥ T 1/3 ε 2/3 - 3 log(1/δ) 2ε -1 (ii) = Ω T 1/3 ε 2/3 ,where (i) follows since E ≤ (T ε) 4/3 , and (ii) holds since3 √ log(1/δ) 2ε≤ T 1/3 2ε 2/3 for ε ≥ 100 log 3/2 (dT )/T ≥ 27 log 3/2 (1/δ)/T . The claim follows.Proof. For this lower bound, we assume that the algorithm has full access to D to release z 1 , . . . , z T . First, note that if the algorithms picks z = z i with probability 1/T and releases (z, . . . , z), then it has the same error sinceE[ T t=1 ℓ(z)] = T E[ℓ(z)] = T E[ 1 T T t=1 ℓ(z t )] = E[ T t=1 ℓ(z t )].Therefore, we assume that the algorithm releases a single z = ALG(D) that is (ε, δ)-DP. Denote D ℓ = (ℓ, . . . , ℓ). Note that as we sample ℓ ∼ Ber(1/2) d , the probability p := Pr(ℓ = ℓ 0 ) = Pr(ℓ = ℓ 1 ) for all ℓ 0 , ℓ 1 ∈ {0, 1} d . Letting ℓ = 1 -ℓ, we have that Justification: We read the ethics guidelines and believe we meet them.E ℓ∼Ber(1/2) d T t=1 ℓ(ALG(D ℓ )) = T • E ℓ∼Ber(1/2) d [ℓ(ALG(D ℓ ))] = T • ℓ0∈{0,1} d Pr ℓ∼Ber(1/2) d (ℓ = ℓ 0 ) • E [ℓ 0 (ALG(D ℓ0 ))] = T 2 • ℓ0∈{0,1} d p E ℓ 0 (ALG(D ℓ0 )) + ℓ 0 (ALG(D ℓ0 )) ≥ T 2 • min ℓ0∈{0,1}Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).[AFKT23b] has another algorithm which slightly improves over this regret in the high-privacy regime and obtains regret T 2/5 /ε 4/5 . We include this algorithm in Figure1.Our regret bound may be invalid with an adaptive adversary, but our algorithms will satisfy a stronger notion of differential privacy against adaptive adversaries (see[AFKT23b]). However, to keep the notation and analysis simpler, we limit our attention to privacy against oblivious adversaries. 


Decision: This manuscript studies the problem of online prediction from experts (OPE) and online convex optimization (OCO) under the differential privacy constraints. The main contribution of this work is that, instead of applying individualized privatized methods, it proposes a new mechanism that converts lazy online learning algorithms into private algorithms in a black-box manner. The significance is two-fold: first, this new mechanism improves the best-known regret bounds for private OPE and OCO problems; second, this new mechanism can be applied to many other non-private methods and thus has a great potential to generalize. This idea is greatly appreciated by all reviewers, and so leads to my decision of acceptance.

Reviews: review: paper_summary: paper_summary: This paper proposes a new mechanism that converts lazy online learning algorithms into private algorithms. Unlike previous private online algorithms that use individualized privatized methods, the paper's new mechanism is a black box private algorithm that can be applied to many popular non-private methods such as the lazy shrinking dartboard algorithm or the regularized multiplicative weights algorithms.
strength_weakness: strength_weakness: - I'm not sure if I agree with the claim that the new bound is an improvement over the previous bound. Obviously, the high privacy regime is very important, and as the authors have mentioned, this would allow for the composition of more instances. However, as far as I know, a lot of practical application of DP algorithm uses $\epsilon \approx O(1)$ so the new bound could be worse than previous results.

- It would be nice if there are some proof of concept experiments to compare the new mechanism with the algorithms in previous works.
questions: questions: - Can the author provide some intuition on why we would want to use concentrated DP to prove the lower bound? How does concentrated DP make it easier for us to construct the lower bound?

- What are some non-lazy algorithms that satisfy Assumption 3.1? What would the regret bound look like for these non-lazy algorithms.

- I'm a bit confused about the setting of $\epsilon$ in Theorem 3.2. To get the optimal regret bound, we need to set $\epsilon$ using the provided formula which I think is roughly $O(1)$. Doesn't that defeat the point of the proposed framework where we only see improvement when $\epsilon <<1$.
limitations: limitations: N/A
paper_summary: paper_summary: The paper studies the differentially private (DP) variants of the classical online prediction form experts problem (OPE) and online convex optimization (OCO) problem. The main contribution is a (black-box) approach to transform lazy (i.e. slow-varying) online learning algorithms into private algorithms. The paper shows that the transformation only incurs a small additional regret as compared to the regret for the classical OPE/OCO regret. In particular, for the  DP-OPE and DP-OCO, the proposed algorithms improve the O(1/eps) regret in previous works to O(1/eps^{2/3}). In addition, a matching regret lower bound is provided for the family of low-switching private algorithms for the DP-OPE problem.
strength_weakness: strength_weakness: The lower bound is only valid for the family of slow-varying algorithms, thus the algorithms proposed might not be optimal.
questions: questions: The paper is relatively dense, with many definitions related to differential privacy (section 2), which might be unfamiliar for people who have little knowledge about differential privacy before. I’m wondering if all those definitions are necessary for the main part of the paper (maybe some can be moved to the appendix)?
limitations: limitations: Yes the paper has discussed the limitations and provides improvement in the appendix.
paper_summary: paper_summary: This paper investigates private online learning, focusing on online prediction from experts (OPE) and online convex optimization (OCO). The authors propose a new transformation that translates lazy, low-switching online learning algorithms into private algorithms. Based on this transformation, their resulting algorithms attain regret bounds that significantly improve over prior art in the high privacy regime. Furthermore, they complement their results with a lower bound for DP-OPE, showing that these rates are optimal for a natural family of low-switching private algorithms.
strength_weakness: strength_weakness: * The transformation in this work is based on low-switching online algorithms, and is only applicable to oblivious adversaries. In contrast, previous DP-OCO algorithms [ST13, AS17, KMS+21]  can adapt to non-oblivious setting. 
* The theoretical innovation in this paper is limited, as it largely follows previous work [AFKT23b].
questions: questions: * In footnote 2, the authors state that their algorithms will satisfy a stronger notion of differential privacy against adaptive adversaries. However, I believe that for non-oblivious adversaries, the proposed DP online algorithms in this work cannot provide regret guarantees. Is this correct? If so, I would like to understand why the low-switching private algorithms cannot handle non-oblivious adversaries, whereas previous work using binary tree techniques [ST13, AS17, KMS+21]  can.
* From Theorem 3.2, it is evident that $\epsilon$ of L2P increases over time, meaning that its privacy weakens progressively. Could this be a concern for the proposed DP algorithm? 
* The authors established a lower bound for low-switching private online algorithms based on **CDP** analysis, whereas the upper bound provided in this paper is based on **DP** analysis, i.e, Theorem 3.2 and 3.9. Could you clarify the implications of this difference?
limitations: limitations: See above
paper_summary: paper_summary: This paper studies private online prediction from experts (OPE) and online convex optimization (OCO) problems and proposes a general transformation that converts lazy (non-private) algorithms into private algorithms. By applying it to existing lazy algorithms, they obtain improved regret bounds for both problems. A lower bound for lazy algorithms is also provided, suggesting that new techniques other than lazy algorithms are needed if one wants a better regret.
strength_weakness: strength_weakness: 1. The improvement made in this paper may not be very significant. It only improves the dependency on $\varepsilon$, while in many scenarios $\varepsilon$ is treated as a constant.
2. The lower bound may not be essentially matched -- Theorem 4.2 requires the algorithm to be $\varepsilon^2$-CDP instead of $(\varepsilon,\delta)$-DP. It does not mean that every $(\varepsilon,\delta)$-DP algorithm should have that lower bound.
questions: questions: 1. The paper assumes an oblivious adversary. Can the results be extended to the adaptive adversarial setting?
2. It looks like Condition 4.1 is not limited to algorithms with a small number of switches. It only requires that once the algorithm resamples, the resampling distribution depends only on past loss functions and not on internal randomness. Is my understanding correct?
limitations: limitations: Irrelevant.

Comments: comment: Thank you for your addressing my questions. I decide to keep my positive score.
Thank the authors for the additional comments on the lower bound! I will keep my score!
Thanks for your response, which has addressed my concerns. I decide to keep my positive score.