Private Online Learning via Lazy Algorithms
Authors: Hilal Asi
Tomer Koren
Daogao Liu
Kunal Talwar
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Online Optimization
Primary area: privacy
TL;DR: Improved regret bounds for Privacy Online Learning and OCO via a general Lazy-to-Private transformation

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.

Private Online Learning via Lazy Algorithms
Hilal Asi Apple hilal. asi aewi940mmail..mmmmmmmm
Tomer Koren
Tel Aviv University tkoren@tauex. tau. ac
Daogao Liu"
Kunal Talwar
University of Washington 1 Hudaogao@ggail.ccmmmm com
Apple kunal@kunaltalver org
Abstract
We study the problem private online learning, focusing on online prediction from experts (OPE) and online convex optimization (OCO). We propose new transformation that translates lazy, low-switching online learning algorithms into private algorithms. We apply our transformation to differentially private OPE and OCO using existing lazy algorithms for these problems. The resulting algorithmss attain regret bounds that significantly improve over prior art in the high privacy regime, where & 1, obtaining O(vT log d + T1/3 (d) (22) regret for DP- results
OPE and O(VT + /d/e/// regret for DP-OCO. We complement with a lower bound for DP-OPE, showing that these rates are optimal for natural family of low-switching private algorithms.
1 Introduction
Online learning is fundamental problem in machine learning, where an algorithm interacts with an oblivious adversary for 7'' rounds. First, the oblivious adversary chooses 7 loss functions .1,...,4 ey X' over fixed decision X. Then, at any round f, the algorithm chooses model #; E X. and the adversary reveals the loss function &, The algorithm suffers loss (xx),, and its goal is to minimize its cumulative loss compared to the best model in hindsight, namely its regret:
Regr Σ (1.)))
min l(xt).
xEEX
In this work, we study two different differentially private instances of this problem: differentially private online prediction from experts (DP-OPE) where the model can be chosen from experts (X' [d];; and differentially private online convex optimization (DP-OCO) where the model belongs to convex set X' c I
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 that the privacy cost for privatizing low-switching algorithm can be significantly smaller as these algorithms do not update their models too frequently, allowing them to allocate larger privacy budget for each update. This has been initiated by [AFKT23b], which used the shrinking dartboard algorithm design new algorithms for DP-OPE, later revisited by [AKST23a] to design new algorithms for DP-OCO using a regularized follow-the- teelow-th---ertubbed leader approach, and more recently by [AKST23b] which used lazy and regularized version of the multiplicative weights algorithm to obtain improved rates for DP-OCO.
Part of this work was done while interning Apple.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Prior work
This work
Volog + min Vd. T logd VT VT + T 2a/9
Vllog + T logd
DP-OPE DP-OCO
AFKT23bb
VT + T2/s// 2273
min
ga/e
[KMS+ AKST23b]
ga/3
Table Regret for approximate (e algorithms. For readability, we omit logarithmic factors that depend on I and 1/6.
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 greater extent, a different analysis. Moreover, it is not clear whether these transformations from lazy private algorithms in prior work have fulfiiled 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 / (omitting dependence on d) for DP-OPE, which implies that the normalized regret is 1 1/ this is different than what exhibited in majority of scenarios of private optimization, where the normalized error is usually function of Ts.
1
(K3S 21)
0.8
0.8
0.8
0.6
0.6
0.6
BRMS
0.4
0.4
0.4
0
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6 0.8
0
0.2
0.4
0.6
0.8
a
(a) OP-OCO (d
log 7)
(b) DP-OCO (d = T
(c) DP-OPE
Figure 1: Regret bounds for (a) DP-OCO with d = poly log(T). (b) DP-OCO with d = T and
(c) DP-OPE with T. We denote the privacy parameter & T and regret 7 and plot as function of (ignoring logarithmic factors).
1.1 Our contributions
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 summary in Table and Figure 1.
L2P: a transformation from lazy to private algorithms (Section 3). Our main contribution new transformation, we call L2P. that allows converting any lazy algorithm into private one with only a slight cost in regret. This allows us to use long line of work on lazy online learning IKVO5, GVWIO, ATIS, CYLK20, SK21, AKST23a] 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 simple, key observation that by grouping losses learning algorithms. We introduce batch size that improves over the existing analysis [AFKT23b]: this allows us to reduce the total number of "fake switches" needed to guarantees privacy, improving the final regret.
design new algorithms for the
large batch, we can minimize the effect on the regret of lazy online analysis for the regret of lazy online algorithms with large
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 new algorithm for DP-OPE that has regret /T log (d) + 1/3 log(d)/e2/3 improving over the best existing results for the nigh-dimensional regime in which the regret is
1/3 log(d)/e [AFKT23b].
[[AFK233b] has another algorithm which slightly improves over this regret in high-privage regime and obtains regret 2/5 /e455 We include this algorithm in Figure 1.

---

The 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 2 T-1/1 for matching the optimal non-private regret VTlog d, whereas previous results require a much larger 2 T' 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 vT instances of DP-OPE with e 1 and still obtain the non-private regret of order vT; in contrast, prior work only allows solve K T instances while still attaining the non-private regret.
Faster rates for DP-OCO (Section 3.2). As another application, we use transformation for DP-OCO with the regularized multiplicative weights algorithm of [AKST23b]. We obtain new algorithm for DP-OCO that has regret vT + +T//8 improving over the best existing results that established regret V + T1/3 + T3/3 + [AKST23b] or d /L/ATT// 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 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, required in order to improve upon our upper bounds.
Related work. Our transformation and algorithms build on a long line of work in online learning with limited switching VK5 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 of VT + (T/S) log(d) on the regret, which is achieved by several algorithms such Follow-the whw.-perturbdd-eeaeeeee
[K VO5] and the shrinking dartboard algorithm [GVW 10]. 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 regret VT + (T/S) d, whereas the best lower bound vT + T/S [SK21].
2 Preliminaries
2.1 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 f by C= { e - R]. Then, at each round t E [T]. the algorithm ALG, which observed &, ... l1-1 chooses iy E X, and then the loss function l, chosen by Adv is revealed. The regret of the algorithm ALG is defined below:
T
Reg, = Σ ((x)))
min Σ x' EX
l(xx))
We study online optimization under the constraint that the algorithm is differentially private. For an algorithm ALG and a sequence S = (L1,.... "ii,...,.y, (T) chosen by oblivious adversary Adv, we let ALG(S) == (.i..... ,T) denote the output of ALG over the loss sequence S. We have the following definition of privacy against oblivious adversaries.
Definition 2.1 (Differential privacy). A randomized algorithm ALG is (e, () -iffferrrettilllly private against oblivious adversaries ((e, 8)-DP) if, for all neighboring sequences S (f1,...,&y (r) E CT
2 "Our regret bound may invalid with an adaptive adversary. but our algorithms will satisfy a stronger notion of differential privacy against adaptive adversaries (see [AFKT23bJ). However, to keep the notation and analysis simpler, we limit our attention to privacy against oblivious adversaries.
3

---

and S' = (e....,, E L² that differ in single element, and for all events O in the output space of ALG, have
Pr(ALG(S) EO) S Pr(ALG(8) O +
We focus two important instances of differentially private online optimization:
DP Online Convex Optimization (DP-OCO). In this problem, the adversary picks loss 8
functions E Loco = { X' - R is convex and L-Lipschitz} where X' C IRd is convex with diameter D di) = sups,yeX ||æ y/I, and the algorithm chooses Ft E X. The goal of the algorithm is to minimize regret while being (e, diffferrrett private.
(ii) DP Online Prediction from Experts (DP-OPE). In this problem, the adversary picks loss functions LOPE = {e é : [d] [0, 1I} where X' [d] is the set of experts, and the algorithm chooses E [d]. The goal of the algorithm is to minimize regret while being
(E, 8) difffrreetilll private.
2.2 Tools from differential privacy
Our analysis crucially relies on the following divergence between two distributions.
Definition 2.2 (f-Approximate Max Divergence). For two distributions, and v, we define
In p(S) -
D& (ulli) =
sup SCsupp()).
v(S)
We let D (1, p) D (n)le), D (v)la))
We also use the notion of indistinguishabiliyy between two distributions. Definition 2.3. ((s, 8) indiisinnuuisabbbitt)) Two distributions are (c, 6) iiiiistiinuuuisable, de- noted (),6) v, D (p, v) S 8.
Note that if an algorithm ALG has ALG(S) (c.8) ALG(S") for all neighboring datasets S.S' then ALG (e, d)-differentially private. We direct readers to Appendix for additional background information and detailed preliminaries.
L2P: From Lazy to Private Algorithms for Online Learning
This section presents L2P transformation, which turns lazy online learning algorithms into private ones. The transformation has an input algorithm A with measure f4e at round and samples 2 from the normalized measure Th which satisfies the following condition:
Assumption 3.1. The online algorithm A has time measure (4 that is function of l,, ...... 4-1 (and density function 14,) such that for some 6g S 1 and 0 < S 1/10 that are data-independent, we have
. (2e S
* ( = func(6e,ar) for all x E X where func is 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 the shrinking dartboard (Section 3. l) and lazy regu- larized multiplicative weights (Section 3.2). Moreover, any algorithm that satisfies this assumption can be made lazy via reduction.
Technique Overview: Suppose the neighboring datasets differ from the su-th loss function. The high-level intuition behind our framework that our algorithm only loses the privacy budget when makes a switch (draws fresh sample) whenever / > 8p. Hence, in the framework, we try to make the algorithm make as few switches as possible. This modification can lead additional regret compared to lazy online learning algorithms, and we need to balance the privacy-regret trade-off. The family of

---

lwichhit 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 sample from It-1 T is likely a good sample from P. and therefore switching at round t is often not necessary. In particular, at round t, these algorithms sample a Bernoulli random variable S. Ber(c- Tí. (z;-1)/ (xx-1)) for some constant and use the same model Iy = - if S; = 1, and otherwise sample new model Iz ~ 13 if St = 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 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
Sample S ~ Ber(C (1 and S ~ Ber(1 - p)
Sample new F4, if S: = 0 or S =0
Otherwise set 2; 2
This 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 The (x:--1)) / (Ix-1) is usually a function of the whole history f1,...,&, l,. 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 & at time affects the switching probability only at time t, hence paying privacy cost for switching only in a single round. To this end, we construct a parallel sequence of models {ye hEe(T (independent of 2τ) that is used for normalizing the ratio (xt-1)) 1 to become independent of the history. In particular, at round i, we switch with probability proportional to
[1((21-1) (e-1(1--1)
B4 ( [e(
The main observation here is that P--1 [1= (,(1)-1) (w:-1)
- F Me(xa-1)
(e-1( and this ratio (elWe-1)
function of 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 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 new analysis of the effect of batching on the regret of lazy algorithms (Proposition 3.3), which states that running lazy online algorithm with batch size of B would have additive error of TB2,, to the regret where 7 is a measure of distance between (4, and 11 This significantly improves over existing analysis by [AFKT23b, Theorem 2] which shows that batching can add an additive term of B/n to the regret.
Having reviewed our main techniques, we proceed to present the full details of our L2P transformation in Algorithm 1, denoting V/2 = M(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 17 we denote its regret
T min xEX
Regr Regr((m))_1))
Σ E. (x)(
((x).
t=1
t=1
The following theorem summarizes the main guarantees of Algorithm 1.
Theorem 3.2. Lei E (0, and B E N. Assuming Assumption 3.1, Tp/ B 2 1, and any 81 > 0 such that B log(1/10/g)) (1/81)/p < 1, our transformation L2P is (c, 8DD with
2m
3Tm2p log( (181)
+ /6T (1/61)/BB
8 =
+ 17
p
2B
5

---

Algorithm 1: L2P
Input: Parameter 7), measures (ut hE(T)) batch size B, fake switching parameter p:
2 Sample ø1, 1/1 V1;
Observe f fB and suffer loss Ei= (x(1));
for s 2, ..... T PBBd do
va((0-1) Sample S₂ Ber min (1, 22 1 1o( )) and Sy Ber(1 p);
if S. 0 or S then
Sample 2g ~ V else
Set F2 = Fg 1
Sample A, ~ Ber(1 p);
11
A. = 0 then
Sample y/a V
13
else
Set Ys 1s-1i
15
Play Fzi
Observe l(s- (l-1))+l......... LBB and suffer loss Σ 1i= (xx)):
16
8 +
2T
and has regret
Regr (Regr(()))))) +0 1B²,, 8o1 log(
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 lazy online learning algorithm.
Proposition 3.3 (Regret of Batched Lazy Algorithm). Let ALG be online learning algorithm that satisfies Assumption 3.1. Let nB log(1/61)/p S and 81, < 1/2. Then running L2P with the input al algorithm ALG has regret
TB'p + o log(
Reg, < &Regy +0
?
To prove Proposition 3.3, first show that that samples from V. at each round. This is due to the following lemma, which shows that |0, - V. Pallrv small where Ds is the marginal distribution of v. in Algorithm 1.
instead analyze the utility of simpler algorithm
Lemma 3.4. Let V. be the marginal distribution of x, in Algorithm 1. When BB (loglo//))))))) s we have ||> - P. TV S 3(x (2e + (1/((//)/// Bög-
We also require the following lemma which allows to build coupling over multiple variables, such that the variables are as close as possible. This will be used to construct 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.l. common a a-finite measure. Then, there exists coupling T, such that for any variables X, Y E S, have Pr[X= + Y] < X X
We are now ready to prove Proposition 3.3
Proof. Let Reg' denote the regret when the marginal distribution of De is vt instead of D, induced the Algorithm. Since each loss function is bounded,
Reg,
Reg'r + B
Σ | D.llrv. BE

---

By Lemma 3.4, we have
Regr S Regr + Σ
3(s 1)(2/1 + log((/6))/)))eBbbb
sE[T/R] B
S Regz + 8T 0g
Thus, it now suffices to upper bound Reg7.
Due the preconditions that D'y (#(+1:14) 14) 7) and dn 1, we know ||/441 - Hullry S 2n.. Recall that we assume I, ~ Fg. Suppose is the action taken by the input lazy algorithm A for E [2] and the marginal distribution of 2; is n. By Lemma 3.5, we can construct a coupling I', between 24 and z == (Z(s-1)
2sB), such that
Pr
Bi E [(s 1)B + 1, 1B8 # v.s S Bn-
Letting I, = 1(Ei E [[s B)B + +,11,,8 L. 23 x,), we have
E
((xs)) =
E
Σ
(xxs))
(
11++1)B+1
(= BB+
sB
E
(1 - Is)
i=ss-1)++1 ((2)))
Σ
2
BB
1
(1(5))
J Zn|
i=(s
1)
sB
<
E (1
[s)
(=(--1)B+1 l((z))
Σ
2,,
1
Σ
(4(z)+
1)B+1
E zore
((2,) O(B 13
i= 1)B+1
Hence we get Reg/ Reg, ((m))=)) + T O(Ba)²), 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 new model æt from the distribution μr, We defer the proof to Appendix B.
Lemma 3.6. Let {Pt)T_ satisfy Assumption 3.1 where S 1/10. Then for any neighboring sequences S and S' with corresponding {Pt ) and {14)T= that differ one loss fanction, have
D160 (T... 2m..
We use correlated sampling in the algorithm rather than sampling from Ia 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 & E [T/ if nB (1g))))))// & 1, then with probability at least - -22/1 + log(1/61)/p) eBo, 81.
Vo+1(#s) Vy (I..)
Vo(We)
E 12- 2Bn
Vs+ 1 (ya)
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.
7

---

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 output two datasets D and D a query 9s. and receives the answer Y; ~ M,(D;, 9:) for the secret bit b E {0,1}. advanced composition theorem.
answers V1, ... Y;-1 (denoted by Yi-11 for simplicity), can
1). If each M, is (e;, -DD, then the joint distributions over the answers Y(a) satisfy the
In our case, however, we know there exists subset Gi-1(D) such that with probability at least 1 Xo MI-1 E G.-1(D) Conditional on Yi- E OhE 10.1) GD-1(D)-1)
M,(D), Yi-1j E (i (().5)) M,(D,, Yi-1I E (Dtto.))i-11PP-
Then we have the following lemma:
Lemma 3.8. Given the mechanisms satisfying the Condition (1), then the class of mechanisms
satisfy (Eg, 1 (1 () 8t)) + [eEM( DDDD under k-fold adaptive composition, with Eg defined in Equation (4).
Proof. Without losing generality, suppose we know the adversary and how they generate the databases
and queries. We can construct series of mechanisms M', such that M draws Y; from M 4s). and outputs Y, if Y; (a, (
and outputs O otherwise. Let (Y L....... xg,0) be
the outputs of M with secret bit b, and we know the TV distance between (Vi,r" (%,6) and
(Yi,s, Yx,6) is at most E{E(A) d for any b {0, 13. Moreover, we know
(Yio
Y%,o) (1111-(1-8) (Yi,,, ... Y%,1)
by the advanced composition. The basic composition finishes the proof.
3.1 Application to DP-OPE
This section discusses the first application of transformation differentially private online prediction from experts (DP-OPE). Towards this end, we apply our transformation over the multi- plicative weights algorithms [AHK12], which can be made lazy done in the shrinking dartboard algorithm (GVW10). It has the following measure at round f.
mW ( - -
The following proposition shows that this measure satisfies the desired properties required by our transformation. We let Ji! denote the density corresponding 1 mw
Lemma 3.9. Assume e , lr where la [d] [0, 1). Then have that
1. Du (T p. 17 with do 0.
2.
e ndx(x) for all x E [d].
Proof. The first item follows from the guarantees of the exponential mechanism fx(x) [0, for all x E [d]. The second item follows immediately from the definition of mm
gives the following theorem. Theorem 3.10 (DP-OPE). Let f,...., ......,,, by where & [d] 1]. Setting B 1/s and min(E0, 2)2/3 1/3 where Eo - 3/4 the L2P transformation (Algorithm 1) applied with the measure {pmm)? 3T" is (e, DD and has regret
Having proved desired properties, our transformation
Reg, =0 (VTlogd
T log d
2233
8

---

Proof. First, based on theorem 3.2, note that the setting of B = 1/e and S min((o, E /33/3////////// where Eo T log d guarantee the algorithm is (e, 6)-P..
To upper bound the regret, we use existing guarantees of the multiplicative weights algo- rithm [AHK12], combined with Theorem 3.2 to get that the regret is
1/ log(d)
Regr 00
+ +TB²1²
"1
nT log(d)
TT
0
+
"
E²
00 (Teo) 2/3 T log
22/3
c2/3
T1/3 log(d)
0 Tllg
22/3
where the second inequality follows by setting B = L/E, and the third incquality follows by setting
n S (un(so,))383 /T213, and the last inequality follows since Eo T--1/4 log"/4 d.
3.2 Application to DP-OCO
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 measure
14 rmw (x) = ( (1))111111)))
Letting nm denote the corresponding density function, we have the following properties.
Lemma 3.11. Assume E,,...,ey l X - IR be convex and fidisschit,functtonn Then we have that
1. Dde (mrm p!m) where 231. X
8BL2 log(2/60)
2. PELl
----Be (L,((a) for all E.
Proof. The first item follows from Lemma 3.5 in [GLL22, AKST23b). The second item follows immediately from the definition of pmm..
Combining these properties with transformation, we get the following result.
Theorem 3.12 (DP-OCO). Let ly...., Ex X - RR be convex and L-Lipschitz, functions.
U--ipschitt,functions.. Setting B 2e (1 f max ( (VT, yalog 3 x/2/227 "j (og(/8) and p n/e, the L2P transformation (Algorithm 1) applied with the measure {urTT) )T= is (e, 6)DP and has regret
2/3
Reg, = LD- (VT+ T2/3 Vdllg T (og()
2/3
Proof. First, based on Theorem 3.2, note that there are three constraints to make the algorithm private:
n/p E//2,
TV Tolog( T S 5/2 nB BBlog(1/8)/p35
Setting of B log(1/
1 max VV, dd }. B 1/1/20L2, TT/5|og(T/8) and
2/3
p = T//E guarantees the algorithm is (s, DD..
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 regret
Reg, 5o (DD2
=0(x2=+
L +
log(T) (T)
+ LDTB39p)
3

---

0o LDVT+ + +D2 L'd
+ LDTB317
Anp²
SLD.0 (VT+ T1/3 Va/s/loog 7 (og(T/5)
22/3
4 Lower bound for low-switching private algorithms
In this section, prove lower bound for DP-OPE for natural family of private low-switching algorithms that contains most of the existing switshihhingg 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 I, ALG allowed either 24+1 It or sample I++1 p4++1 where pt++1 a function of li....,, le and is supported over X. The algorithm releases the resampling rounds (11,...,4s) and models : )
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 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. and is cC,C then there exists oblivious adversary that chooses ( ly [d] + [0, 1] such that the regret lower bounded by
2 and e 2 100 (dTT)) Ifan algorithm ALG satisfies Condition
1/3 2/3
Regr 2 Ω
VT+ V
Finally, we note that this lower bound only holds for switching-based algorithms: indeed, the binary-tree- traa--e algorithm of [AS17] obtains regret Vo which is better in the low- dimensional regime. This motivates the search for new strategies beyond limited switching for the nigh-dimensional regime.
5 Conclusion
In this paper, we proposed 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 wow-switching-beee required for low-switching algorithms improve 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 to v (d/(sT)22/3 2/3 This is different than most applications in private optimization where the normalized error is usually a function of vd/(sT). Hence, is natural to conjecture that the normalized regret can be improved to (2/33/(7)22//
private algorithms, which shows that new techniques
transformation's regret. This begs the
terms, is proportional
References
[AFKT23a] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Near-optimal algorithms for private online optimization the realizable regime. Proceedings of the 40th International Conference Machine Learning, 2023.
10

---

[AFKT23b] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private online prediction from experts: Separations and faster rates. Proceedings of the Thirty Sixth Annual Conference Computational Learning Theory, 2023.
[AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta algorithm and applications. Theory of Computing. 8(1):121-144, 2012.
[AKST23a] Naman Agarwal, Satyen Kale, Karan Singh, and Abhradeep Thakurta. Differentially private and lazy online convex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 4599 4632. PMLR, 2023.
[AKST23b] Naman Agarwal, Satyen Kale, Karan Singh, and Abhradeep Thakurta. Improved differentially private and lazy online convex optimization. arXiv:2312.11554 (cs.CR), 2023.
[AS17] Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Proceedings of the 34th International Conference on Machine Learning, pages 32 40, 2017.
[AS19] Omer Angel and Yinon Spinka. Pairwise optimal coupling of multiple random variables. arXiv preprint arXiv: 1903. 000322, 2019.
[AT18] Jason Altschuler and Kunal Talwar. Online learning over finite action set with limited switching. In Proceedings of the Thirty First Anmual Conference on Computational Learning Theory, 2018
[BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, ex- tensions, and lower bounds. In Theory of Cryptography 14th International Conference, TCC 2016-B, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 635-658, 2016.
[CYLK200] Lin Chen, Qian Yu, Hannah Lawrence, and Amin Karbasi. Minimax regret of switching- constrained online convex optimization: No phase transition. Advances in Neural Information Processing Systems, 33:3477-3486, 2020.
[GLL22] Sivakanth Gopi. Yin Tat Lee, and Daogao Liu. Private convex optimization via ex- ponential mechanism. In Conference on Learning Theory, pages 1948-1989, PMLR, 2022.
[GVW10] Sascha Geulen, Berthold Vöcking, and Melanie Winkler. Regret minimization for online buffering problems using the weighted majority algorithm. In Proceedings of the Twenty Third Annual Conference on Computational Learning Theory, 2010.
[KT12] Prateck Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Proceedings of the Twenty Fifth Annual Conference on Computational Learning Theory, 2012.
[TT14] Prateek Jain and Abhradeep Thakurta. (Near) dimension independent risk bounds for differentially private learning. Proceedings of the 31 International Conference on Machine Learning, pages 476-484, 2014.
[MS++21] Peter Kairouz. Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. arXiv:2103.0003 [cs. CRJ, 2021.
[KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385 PMLR, 2015.
[KV05] A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005.
[SK21] Uri Sherman and Tomer Koren. Lazy oco: Online convex optimization on switching budget. Proceedings of the Thirty Fourth Annual Conference on Computational Learning Theory, 2021.

---

[ST13] Adam Smith and Abhradeep Thakurta. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems 26, 2013.
12

---

A Missing details for preliminaries
In this section, 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 a-Renyi divergence (ax > 1) between two probability measures:
Da(ullv) = log (/ (A(W) v(w)
do(w))
Concentrated DP is defined below:
Definition A.1 (concentrated DP). Let p 2 O. We say an algorithm ALG satisfies p-concentrated differential privacy (p-CDP) against oblivious adversaries if for any neighboring sequences S = (f1,..., (T) C and S' (e1 (ei,..., (7) L that differ in single element, and any a 2 1, Da (AAGG(DD) I op.
Now list few standard results from the privacy literature that in the paper, namely group privacy and privacy composition.
Lemma A.2. (Group Privacy) Let ALG be an (eP algorithm and let S, S' L be two datasets that differ in k elements. Then for any measurable set S in the output space of ALG
Pr(ALG(S) E O) S th Pr(ALG((8) EO] + (ke 5.
Lemma A.3 (Advanced Conposition,(KOV155) For any E, 0,8, (0, for t [k], and
Ó E (0,1) 1), the class of (et, dt) - mechanisms satisfy (ěz. (1 8)1l1e11 (1 -DD under k-fold adaptive composition, for
Σ 2c? log(e + V VIEN of KE
&3- =
Σ E min [E(R]
25 1og(1/8)
(4)
KE(M
Moreover, we use the fact that distributions with bounded D& satisfy the following property.
Lemma A.4. Let $ 1/10. 1. If Do (u,v) S 6/2 then we have
-=== p(X) Pr X~p
(X) S e 2 68/s and Pr Xov
S 5 2 1 68/8.
x
Finally, we have the following standard conversion from p-concentrated DP to (s, DD-
Lemma A.5 ([BS16)). If ALG is p-CDP with p I 1, then it is ///ploo(//0)) 6) for all 5 e (0,1/4)
A.1 Proof of Lemma A.4
Let S' = [X
x(
v(xi E [e=s,e=]] and assume towards a contradiction that u(S") < 1 1 -65/s. Then
there is a set S = S such that /u[$] > 60/e. We divide S by letting Si = {X E S ((X)/u(X)>
ef} and S2- 5 S1.
Case (1): ((Si) Z (25)/2 2 38/8. Then we know
In ((Si) - ln ((S)) -
m(Si) 2 Inc 3/8-1 2 In 2/2 = =/2,
v(Si)
3/E
where we use that (u(t)) 2 vl(iSs and 1 5/3 e- e/2 for 1/10. This is a contradiction.
Case (2): Suppose (xS2)) 2 35/e. We know S2 = (X E S (xX)/v(X) < <e = (x E S
v(X)/u(X) > e.}. Then know v(S2) 2 c (((2) 2 3e 8/c. Similarly, we have In ((2)) 8 ((22)
e/2.
This is contradiction well and proves the statement.
13

---

B Missing Proofs for Section 3
B.1 Proof of Theorem 3.2
The regret bound follows directly from Proposition 3.3. It suffices prove the privacy guarantee.
Fix two arbitrary neighboring datasets and S', and suppose the sequences differ at step. that is differ one loss function from (1(o-1))++1" .%,,)-
B,,B) 1)
Define Çe as the indicator that least one of Ar+1, Si+1 and S/41 is zero. Let {( yes hetry and f(rl, vl hetmy be the random variables with neighboring datasets. Let Σ, {(I,. Vr, Sr) re((] be the random variables for the first I-iterations. We will argue that (( Me. hejry and [(1), v/ heee are indistinguishable, and privacy will follow immediately.
Let F, be the event such that **+a(xe) (x(x))
v((m)) (141( [e (c-2Bn, (e-2Bmee2BB) Hence we know Pr(E,] >
1 1 (2+ log(/////////e
81 by Lemma 3.7 for any t. Define E; in similar way. Moreover, let
Eg be the event that E712 1(A, or S =) s 2T'p log(l/,))) (106 By Chernoff bound, know
T/B
Pr(Ec) Pr( Pri
1 1(A 0 or = 0) S 2T log poppog(1/6)))) 2 - 61.
1=2
((() 111 E |e- (e-2Bn,e2Buj Lemma 3.7 implies that Pr[E]] 2 - (2/n + log(L/ Then it suffices show { Ves be)te and {(r/, yi hee are (e, 8g) -iindistinnuuihhable con- ditional on E == Eg E'g WE (E, U E2). Then this will imply that {(x,, Ur. Se) hem and {(rl, v/e he are (E, + (2T + 2)81 + (2/n + log(L/81)/))eBo)) http:///peBooiiiiiiiiiiiiueeeeee -indistinguuishabl..
We also let E, be the event such that (e=1( _.(.))
for any t. Define EY in similar way.
Now we show, conditional on F. any value E such that E₁_1 E/_ = Σ, (xt, Ue, Se) and (44, v6. G) (e,, do) -indisstinguuieaall where
0,
< to
6x
2n/p to
G: .1 > to
Case 1 (t < 4n): It is clear that the claim is correct for / S to (Ix, (2r, Gr) and (1 v/e ( have same distribution then.
Case (t = to)= Now consider the case where = to-
Note that (Iig )to) and (3',, H6o)) have identical distributions, and it suffices to consider the indistin- guishability of Sep and S,.-
We have
(1 - p)² Vip 1((1o)
Mip (2re))
Pr[Sro =0 0 Ttg Vtoo
ezeuvng (arg)
veg (860)
Pr Pr(C/, C/ =0 0 Σ - 2 2 Vio
11 (vin)
(1 p)2
ca (5)
2 12
1/o (yro) Msot Mtot (xto)
v/ott (2xto) Vo (11))
x 29
Similarly, we have
1 - (1 - p)2 + (1-20) -1)
(1a4) Mep (2eg))
Pr[Cr, = 1 De Ita Mrol
G2Bupin (Z10)
Beg (M
Pr[Cr, = 2/ 2oo Vio.
12 (10k
M/, (v/
1
p)2 + -1- 21
zaBuol (Z
14

---

(1 - 1-)) v ( 2/ (8h.)
Mea+ (wegg) Peo (eo()
(209 vg (= 60 11 (366)
2 (210)) Meg (2(1))))
1
Vig (a% ei (9%
1 - (1 - p)² + (1 p)
aaniee (m voo (16
2 1
$ 1
221/1
p
Case 3 (t > to): As for the case when t > to. when S. = (At+1 = S1+1 S/ = 1), the variables O-indistinguishable since 2; 3t-1 and y/ - in this case. Consider the remaining possibility. Given the assumption that /4+1/14 /4, is a function of &,, for any possible E, we have
Pr[C: 1 Σ 2 Pr(ci Σ = E].
For any set S, by the assumption on IT, we have
Pr[c: = (zr, S Σ, Σ
= Pr(( E -
E, = 1| Pr|s: = 1 E = =
= =Pr((as, M1) E S -
= Pr(s = - = -
Se." Pr[[2 v/) E S -, = E, Pr(c =1 1 = _ + 460
=e Pr(C = 1, (z), v/) E 1 = 2 + 460.
where the inequality comes from Lemma 3.6 by the divergence bound between Ji, and Thp This completes the proof of Equation (5).
The final privacy guarantee follows from combining Equation (5) and Advanced composition (Lemma A.3)
B.2
Proof of Lemma 3.4
We prove this statement by induction. For t the statement is obviously correct. We assume [ / < 3(1 ((((1))((e// log(1 ( (/1)/p)))))))) Bög + 61) prove that [1++11 Detillrv 32
log( (/6))//)) Bdg.
Let Xgood := fz log P(( E i-n,,, Bri}} and Yoood := ty log P((r)
(x))
Deti(y) S i- Brj}. Let
(y(y) be the distribution of yt. Note that the distribution of y/ is independent of {z, / mj while the distribution of xt+1 is independent of yt+1 but depends on ye. By the assumption and group
privacy, we know DB 80 (vL+1, S By, and hence we have
(Y good) S e 2eda/1)-
Let to I be largest integer such that Ar, = 1, that is, y is sampled from Vi, for some random to S f. We have
Pto (y Bu((ttoo) 14 VY
(1 (o) Bdge Bn(( Bu(tttt)
With probability least 1 51, we know It tol - (////// Hence we get
Pr [y E Ygooal 2 1 - 2(e/n + log 1/1,)/p) - 61. g-
We know
Pr [r E Xgood, y E Ygood] a.
Pr good] Pr [ar E Xgood y goood] 2NI7
y-
> 1 2(e//1 + logg(/1))///)B/// 81.
Denote the good
S Sgood (xx,y) x E X good, Y Ygood? ).
15

---

Let Gi be the distribution of yu conditional on St Y good- Let I be the marginal distribution over (04,, yr), that is 24 ~ 2/ and Yt ~ Pr. Let r, be the distribution over (æt, yt) where 2, Vt, Dt Pt. and F3 be the distribution T conditional on (It, yt) goodd
We know ||,, - lrv S (2e/n + log(1 ///1/////))// Bdt 2). Let 7-11 be the distribution of +++1 if (Ie, We) is sampled from I, instead of T,, By the property that post-processing does not increase the TV distance, we know
10 Detallav & [|f, -
Now it suffices to bound the TV distance between T4t1 and F++1- For any set E, we have
/ (Pr|S) = 0, #+41 E E
a++1 (E)
It = I, = yl
PP[[S] = S. 0,+1 E' It = I, Yt
+ +P[[S = 1, 1,41+1 E E Ir = I. Vt (r, v)d(s,))
pp (E) + (1 1) (E) / (1- (2 vx+1(1)
(2+1(1)
me(y)
[x(xx
12)1(2) n4()) (x
+ +(1 1(xEE) (2Bru((s) M1+1(1)
Thus we have
(B) - (141 s / P(+1(0) Fe(y) (,, w)d(z,))
(((EE)) e2Bnu((x) Deti
(E)) /
(e+1(x) vr(y) Fr(z, v)d
(2B De4)
Note that for any (z, y) Sgoods we have
Te(x,y) (x(
(r(Snond)
Fixing any y. we know the above term is bounded by
(2)
2Br (T) ( (Spood) (T++1 (E (gooo)) - De+ (E5TT++ (X (Xgooa)] S 2(e/n + B log(1/61)
where the last inequality follows from F441 (X 2 1 Bdg Hence, we prove that |1a+t1 vetillrv S 2(e/n log(1/66)/)))Bb
This suggests that
|| De+illTv S |Pe41 Tetillrv + 17441 De+1llrv S 66(e/n+ log(1/)))))
B.3 Proof of Lemma 3.6
Let S = (LI,...,ey) er) and S = (fl...., en) differ in single round to- We fix and prove the claim is correct. If 5 to, then the claim clearly holds as F3, The For Assumption 3.1 implies that D (7. (..)) S 17 and Dda (T4 Ti,,) 17, hence by group privacy we get that +1660 (Ty, Tt) < 2n.. Finally, for > to + 1. note that Assumption 3.1 implies that 14: = H40 func(()) func((2) ... func(f,-1) and μ4ر = #4 func(E() func((') ... func(E) Thus, swapping the losses at rounds / and ln results in the same distributions μ, and μ/g therefore privacy follows from the same arguments as the case when = 4o + 1. The final claim follows as e" + +154 4.
+ 1, note that
16

---

B.4 Proof of Lemma 3.7
To prove lemma 3.7, we first prove the same result under a simpler setting where zt Di and yt Ve. Lemma B.1. For any 0 S 1 T/B L, if Bn S 1/20, Vt and ye independently, then with probability at least 6e 6000/
(++1
(ve) [e 2Bn 2
v((e))
1/41 (ybe)
Proof. Let Zi (o(x)da We know V. Ze by notation. Then we have that (4+1(T2)
ve(8t)
(z))(
(e(3)) Zz+1
(x()
P141(1))
(z,
(141(36)24
V141(z)) Be(())
(x(
14+1(1))
The statement follows from the Assumption 3.1 and the group privacy
D Bu (v)-1, S Brj.
Then the statement follows from Lemma A.4, the independence between Zz, yr and Union bound. We are now ready to prove Lemma 3.7.
Proof. Fix any Let to t be largest integer such that Ac, 1, that is, ys is sampled from Vio for Be (o (ve, Mco) (co) I Bn(t to).
some random tu By the group privacy, we know D Define the bad set
(++1(2) vx(x)
me(3)
Shod {y
$ le 2B te-2ng 2n vej.
(4+1(y)
By Lemma B. we know
vely Stad) S Bn 50/"1
Therefore, we have that
(y Stad) S Bu(t-ta) ve E Sbad) + (t to BB Bo(t- (otttt)
< 2e Bolt Böo/n + Bôo - to)e By(e-
By the CDF of the geometric distribution, we know with probability at least - 81, we get 1/0 - 11 s log(1 (1/ Let be the event that 140 - I| S log(1/6,) Hence we know
Vio (y E Stad) S 1/oo (y Stad F) Pr(F) + Pr(E') S (2/ 1 + (og(1/6/)///) eBd + 8,.
C
Missing proofs for Section 4
We prove a sequence of lemmas that are needed for the proof. The first lemma shows that the algorithm has to split the privacy budget across all resampling rounds. To this end, let S be random variable that corresponds to the number of resampling steps the algorithm, variable corresponding to the round of the i'th resampling (where we let T, = T + if i > S), and let Z; be the random variable corresponding to the model sampled at time T; (letting Z, lif > S).
T, be the random
Lemma C.1. (Composition) Let S, S.T.2 7, and S' Tí Z denote the random variables for two neighboring datasets. Under the assumptions of Theorem 4.2, if ALG 2 2CDDP, then for all a 2 1
Σ (Z. T:) s as²
17

---

Proof. As ALG =2 concentrated DP and outputs .' and Zi...., Zs, we have that
ae² 2 Da .i..,,,, .Ts. Ls....,,... .gy 4's.)
,',
2 (T1, ( Zr |
TT....,77777
T
Da (Zili T:),
where the second inequality follows as the random variables T. Zq and T Zj are constant for i > S
and S", and the last inequality follows Z: is independent of (T1,..-3 T;) and (71, .... 7 1) given T,
L
We defer the proof of the following Lemma to the appendix.
Lemma C.2. T 2 1, S T/T and 1/2. Assume [d] - 10.1) where {[a]] ~ (er(1
each x E [d]. Let D = (f, ................................ E) and let ALG be (e,8)-DP algorithm that outputs (21,-.-> 2T)
ALG(D). Then
T
(
Tτ
72
((z)) 2
2
2
2
We are now ready prove our main lower bound.
Proof. (of Theorem 4.2) We consider the following construction for the lower bound: the adversary sets Sadv = (T')2/3, the sequence of losses will have E' Sadv epochs, each size B T/E T/(Te)4/3 (55 Inside each epoch, the adversary samples & Ber(1/2) 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, argue that each switch must have a small privacy budget (Lemma C.I), and thus, the price inside each epoch has to be large (Lemma C.2). Let Ti, ... Ts be the rounds where the algorithm resamples (T; = 7 + 1 for > 5) and Z1, Zz,.... , Zg be the resampled models (Z, = for > S). Lemma C. implies that
Σ Da (Z.1Z T.) ) S as
Now note that inside an epoch e, if the algorithm does not switch, then will suffer loss B/2 in that epoch. Otherwise, if it switches, assume without loss of generality there is at most switch inside each epoch (see Lemma C.2). Let je E [T'] denote the index such that Zj, was sampled in epoch e. Note that the algorithm in this epoch has Da (Z, I T,.) = ae hence it is e²- CDP. Standard conversion from concentrated DP to approximate DP (Lemma A.5) implies that is (3s, (osee/log(11)) log(l1 (10), 5) where 8 < 1/73d. Hence Lemma C.2 implies the error for this epoch is B 3Bs, 3Bc. (ogg(/1)
1/T. Letting Eswisch C [b} denote the epochs where there is switch, we have that the loss of the algorithm
2
T
L(ALG) = (e(x))
E
2
eg Exwitch
3 log(1/8)
B
1//T
2
Le Evwitch
E
(E
- 5)
B
+
B
Σ
3B2 E. 1og(110)
oE eEEawitch
18

---

3B V log(1/6)
=
E
Σ Bewseen
Ee
2
3B V E log((1/8)
T/2
where the last inequality follows since Eee Ee S V loss of the best expert is
E c S VEe. Note also that the
== min dEd
Σ
14(x)=T/2 VBB
Overall we get that the regret of the algorithm is
3B² Ploog118)e
L(ALG) - 2 VEB
2
T
3 log((16)
2 (TE)2/3
v E
(Te)
2(T5)2/3g2
/
3 3o/og(1/0)E
62/3
2(TE)2/88
T1/3
8olog(1/0)
g2/3
2e
/3/
(8)
g2/3
where (i) follows since E < (Te) and (ii) holds since
3
\/o((1/66
T1/3
for E
25
2:273
100 1o0log" 3/2 (dT) 27 log 1/2 (1/6)/T. The claim follows.
C.1 Proof of Lemma C.2
Proof. For this lower bound, we assume that the algorithm has full access to D to release 21....y 27 First, note that the algorithms picks 2, with probability 1 1/T and releases (z,..., 2), then has the same eтror since
TT)] TE T Σ ((e) = E > (())).
Therefore, we assume that the algorithm releases a single ALG(D) that is 8e.8)-DP. Denote D, (e...., E). Note that we sample & ~ Ber(1/2)4 the probability p Pr(f fo) Pr(f (1) for all lo. e1 e {0, 1] Letting
L, we have that
E B~Ber
((ALG(D))
= T
[((AG((D))
T.
Σ
Pr (e= - ((A)(A
Barr(11/2]
1))
T
Σ
pE (E + (6(ALG(D))))
(0E
2
E [co(ALG((D.)) + +Z((LG(() &E((0.1)
min
Now note that for any to we have
E [(oo(ALG(DE.)) + (OLGG(D))
19

---

Σ Pr(ALG(D()) =)(o(2) + Pr(ALG(D),) 2)Ro(2)
sEld
Σ Pr(ALG(DE.) = =2(0(=) + Pr(ALG(D))) - 2) Lo(2))
=E[d
= -1+ + Σ Ro(=) (Pr(ALG(DE)) 2) - Pr(ALG(D)) 2))
=E'd]
2 1+ Σ Ro(z) (c TE Pr(ALG(D)))
= =2) - PP((AGG(D))) = =))
=Eid]
2 1 Tdo Σ la(2) == (E- - 1)
=E(d]
2 1 - -d6 Σ
(o(z) Pr(ALG(D))) = =\T's
=E(d]
2 1 T TE,
where the first inequality follows since ALG is (c, 5)-DP and group privacy. The claim follows
20

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide new algorithms with improved guarantees for heavy-tailed private SCO in several settings, which is what we claim in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses places where the main result is lossy, providing an appendix section dedicated towards improving to be optimal. also compares results another similar bound in the literature, discussing regimes where our bound is weaker.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification:
We provide full set of verifiable details for all of our theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
wttps.cc/ppblccc//cccccccpcppppp geiic//gugee.... CoodeSummii www.nnoolicciooeooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
23

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative emrrr rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: bittpa:/nneurppll http://errrrpp.cccpplpl///tattaa wwtppppclc/tpciiccoooococccccpee cttph//eeeeiicicceeeeeeeeeeeeeee
Answer: [Yes]
Justification:
We read the ethics guidelines and believe meet them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 paper poses significant negative societal impact, as it is about making existing learning algorithms differentially private under less stringent distributional assumptions, which 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 overclaim this effect because our results are primarily theoretical.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
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 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in package should be provided. For popular datasets, paperswi wwwode.hcoe...c. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
25

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "MnOxPw9FCc", "reviewer": "Reviewer_FJx4", "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.", "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?\n\n- What are some non-lazy algorithms that satisfy Assumption 3.1? What would the regret bound look like for these non-lazy algorithms.\n\n- 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": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem is well-motivated. Even though previous private algorithms have good theoretical guarantees, their privatized mechanism is usually tailor-made to solve a specific problem, which limits their applicability. The new black box algorithm makes converting a non-private to a private one simple and seamless.\n\n-  The private term has improved dependence in the $\\epsilon$ term which could be valuable in the high privacy regime (where $\\epsilon \\ll 1$). \n\n- The authors also provide lower bounds that match their upper bound.\n\n- The paper is well-written overall.", "weaknesses": "- 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.\n\n- It would be nice if there are some proof of concept experiments to compare the new mechanism with the algorithms in previous works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n- 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.\n\n- 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).\n\n- 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.\n\n- 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jPMgwWh6op", "reviewer": "Reviewer_rLS6", "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.", "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": "Yes the paper has discussed the limitations and provides improvement in the appendix.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written with all claims supported by proofs. Compared to previous works, the L2P algorithm proposed uses a new correlated sampling strategy to avoid accumulation of privacy cost, and the paper improves the regret of lazy algorithms due to batching. In addition, the paper provides a lower bound for the DP-OPE problem, showing that limited switching is not enough to obtain faster rate, suggesting the need for other techniques.", "weaknesses": "The lower bound is only valid for the family of slow-varying algorithms, thus the algorithms proposed might not be optimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and feedback. Below, we address the main comments; we are glad to clarify further as needed during the discussion period.\n\n1. 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.\n\n2. 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6iJp8H7M3g", "reviewer": "Reviewer_MEJp", "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.", "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.\n* 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? \n* 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": "See above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The improvements in results for DP-OPE and DP-OCO are highly valuable. \n* The research motivation of this work is clear, and the proposed transformation (L2P) is a very solid contribution to DP online learning.", "weaknesses": "* 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. \n* The theoretical innovation in this paper is limited, as it largely follows previous work [AFKT23b].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nAdaptive 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.\n\nInnovation: 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.\n\n\nWe also answer the reviewer’s questions below.\n\nQ1: 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.\n\nQ2: 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$.\n\nQ3: 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).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fBBwFswvpR", "reviewer": "Reviewer_djv7", "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.", "questions": "1. The paper assumes an oblivious adversary. Can the results be extended to the adaptive adversarial setting?\n2. 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": "Irrelevant.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The proposed method is a general transformation, namely, it applies to any algorithms that satisfy certain properties.\n2. The results obtained outperform previous bounds, especially in the high privacy regime ($\\varepsilon \\ll 1$).\n3. A matching lower bound is provided.", "weaknesses": "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nImprovement 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.\n\nLower 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).\n\n\nQuestion 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.\n\nQuestion 2: Yes, you are right. Our lower bounds should hold for this family of algorithms as well.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)