Differentially Private Online-to-batch for Smooth Losses
Authors: Qinzi Zhang
Hoang Tran
Ashok Cutkosky
Venue: NeurIPS 2022 Accept (2022)
Keywords: online learning
convex optimization
differential privacy
online-to-batch
adaptive

Abstract:   We develop a new reduction that converts any online convex optimization algorithm suffering $O(\sqrt{T})$ regret into an $\epsilon$-differentially private stochastic convex optimization algorithm with the optimal convergence rate $\tilde O(1/\sqrt{T} + 1/\epsilon T)$ on smooth losses in linear time, forming a direct analogy to the classical non-private ``online-to-batch'' conversion. By applying our techniques to more advanced adaptive online algorithms, we produce adaptive differentially private counterparts whose convergence rates depend on apriori unknown variances or parameter norms.

Differentially Private Online-to-Batch for Smooth Losses
Qinzi Zhang
Hoang Tran
Dept. of Electrical and Computer Engineering Boston University qinzizæbu.ent edu
Dept. of Electrical and Computer Engineering
Boston University
tranhp@bu.ede edu
Ashok Cutkosky
Dept. of Electrical and Computer Engineering Boston University ashok@cutkosky. com
Abstract
We develop a new reduction that converts any online convex optimization algorithm suffering ((VT) regret into an e-differentially private stochastic convex optimiza- tion algorithm with the optimal convergence rate Õ(1 + vdjeT) on smooth losses in linear time, forming direct analogy to the classical non-private "online- to-batch" conversion. By applying our techniques to more advanced adaptive online algorithms, produce adaptive differentially private counterparts whose convergence rates depend on apriori unknown variances or parameter norms.
Introduction
Solving stochastic convex optimization (SCO) problems forms a core component training models in machine learning, and is the topic of this paper. The SCO problem optimize objective L:
min C(x) = #EW
E [e(x, z~P.
(1)
Here, æ represents model parameters or weights lying in a convex domain W C Rd, Pa some unknown distribution over examples and l(x, represents loss function we will assume to be convex and smooth in æ. Although we do not know Ps, we do know the loss l, and we have access to an i..dd dataset Z = (21,..., 2y) that may have been obtained via user surveys volunteer tests. Using this information, we would like to solve the optimization problem (1). The quality of a putative solution f is measured by the suboptimality gap [(t) L(x.) for x. argmin L(x).
In addition to solving (1), we also wish to preserve privacy for the people who contributed the dataset Z. To this end, we require our algorithms to be differentially private (Dwork et al., 2006; Dwork and Roth, 2014), which means that replacing any one 2, with a different z/ has a negligible effect &. There is a delicate interplay between privacy, dataset size, and solution quality. As T grows, the influence of any individual 24 on & decreases, increasing privacy. However, for any finite T. one must necessarily leak some information about the dataset in order achieve nontrivial ((f) - C(x.). The goal, then, is to minimize [(f) C(x.) subject to the privacy constraint.
This problem has been well-studied in the literature, and by now the optimal tradeoffs are known and achievable particular, Bassily et al. (2019) exhibits a polytime algorithm that achieves
We focus on the harder stochastic optimization problem rather than empirical risk minimization, which also well-studied, e.g. (Chaudhuri et al., 2011; Kifer et al., 2012).
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

[()) [(x)) S Ó(/VT + vdjeT) where e is measure of privacy loss (large means less private), and moreover they show that this bound is tight in the worst case. Then, Feldman et al. (2020) provides an improved algorithm that obtains the same guarantee in (T") time. Further work on this problem considers assumptions on the geometry (Asi et al., 2021), gradient distributions (Kamath et al., 2021), or smoothness (Bassily et al., 2020; Kulkarni et al., 2021).
All private optimization algorithms we are aware of fall into one of two camps: either they employ some simple pre-proeessing that "sanitizes" the imputs to non-private optimization algorithm (e.g. the empirically popular DP-SGD of Abadi et al. (2016)), or they make careful analysis of the dynamics of their algorithm (e.g. bounding the sensitivity of single step of stochastic gradient descent). the former case, the algorithm typically does not achieve the optimal convergence rate for stochastic optimization. In the latter case, the algorithm becomes more rigidly tied to the privacy analysis, resulting in delicate "theory-crafted" methods that are less popular in practice.
In contrast, in the non non-private setting, there is a simple and general technique to produce stochastic optimization algorithms with optimal convergence guarantees: the online tootetcht-bthh conversion (Cesa- Bianchi et al., 2004). This method directly converts any online convex optimization (OCO)(Shalev- Shwartz, 2011; 1; Hazan, 2019; Orabona, 2019) algorithm into a stochastic optimization algorithm. OCO is a simple and elegant game- theoretic formulation of the optimization problem that has witnessed an explosion of diverse algorithms and techniques, so that this conversion result immediately implies a vast array of practical optimization algorithms. In summary: producing private stochastic optimization algorithms with optimal convergence rates is currently delicate and difficult, while producing non- private algorithms is essentially trivial.
Our goal is to rectify this issue. To do so, we produce a new differentially private online-to to-tnettt--btch conversion. In direct analogy to the non-private conversion, our method converts any OCO algorithm into a private stochastic optimization algorithm. After using our conversion, any OCO algorithm that achieves the optimal regret (the standard measure of algorithm quality in OCO), will automatically achieve the optimal suboptimality gap of ((1/V((+/)) /T VVdeT) Our conversion has additional desirable properties: although convexity is required for the guarantee on suboptimality, it is not required for the privacy guarantee, meaning that the method can be easily applied to non-convex tasks (e.g. in deep learning). Further, by largely decoupling the privacy analysis from the algorithm design through this reduction, we can leverage the rich literature of OCO to build private algorithms with new adaptive guarantees. For two explicit examples, (1) we construct an algorithm guarantceing L(t) [(x,) S Ö(a/VT++ + vd)eT), where a is the apriori unknown standard deviation in the gradient V((w, z), and (2), we construct an algorithm guaranteeing ( ((x.) S Ö(1I=. x x1ll/ / + vd/cT), where 21 is any user-supplied point. This last guarantee may have applications private fine runing (Li et al., 2022; Yu et al., 2021; Hoory et al., 2021, Kurakin et al., 2022; Mehta et al., 2022), as the bound automatically improves when the algorithm is provided with a good initialization point.
1.1 Preliminaries
Problem setup We define the loss function as T:Wx x Z + where W C R is a convex domain and Z = (21,...,2y) is an element of 2T for some dataspace 2. We assume Z is i.i.d. dataset and a ~ Pz for some unknown disribution over 2. We then define L(x) = Ez- [((z, 2)]-
Let || be norm on Rd, with dual norm || ||~ defined by ||9||~ supi|=|ls1 z). By definition, (g. .) < ||9|1~ || (Fenchel- Trenghel-Young's 's inequality). We make the following assumptions:
Assumption 1. || 2|2 is X-strongly convex w.r.t. || ||: for all x. y E Rdd and g E 0||=||
X
| 2 ||01|² + (g. y x) + fly - ==12.
2
Assumption 2. W has diameter at most D: Vx, W. ||1--|ll--00 D.
Assumption 3. E(x 2) is G-Lipschitz in æ: v E W, c Z, V((x,))]l. S G.
Assumption 4. f(r, 2) is Hmoohhth in z: V zz E W. E Z, V((x, 2) - Ve(y,))l S H r vil.
Assumption 5. []][[[(x> V((x, =)][3] < o for all z,
Assumption 6. E [[I[V[(>) - VC(y)) - [V v fly 2) .)| < o |z - y for all x. y, 2.
Note that if é is G-Lipschitz and H-smooth in x, then so it C, and Assumption 5 and 6 hold with OG S 2G and 0 < 2H.. Moreover, notice that Assumption 2 depend on the norm || -||.
2

---

Differential Privacy We now provide formal definition of our privacy metric, differential privacy (DP). The definition hinges on the notion of neighboring datasets: datasets Z (21,...; 2T) and Z' - (z),..., in z are said to be neighbors if 2 Z'I - {t 2 # z =
Definition ((c, 6)-DP (Dwork and Roth, 2014)). A randomized algorithm M : 2T -> R is
(e, ddffferrrent private for e, 5 2 if for any neighboring Z, Z' E z and S E R4:
P(M E S) S exp(c) P(M(()) 8) +
An alternative definition Rényi differential privacy (RDP), which is a generalization DP that allows us to compose mechanisms more easily and achieve tighter privacy bounds in certain cases. Definition 2 ((a, c)-RDP (Mironov, 2017)). A randomized mechanism M : z - IRd is said to be (ar R)éééi differentially private for 1, if for any neighboring datasets Z, Z' z
(
where (P(I)) A --I log Ex-q
P(x) Q(x)
RDP can be casily converted to the usual (e, 8DD as follows (Mironov, 2017): if randomized algorithm M is (a, c)-RDP, then it is also (c + log 1/8
a-1 5)-DP for all 5 (0, 1). In particular, if M is (a,, app RDD for all a 1, then it is also (2gg/0) 5D-DP for all 8 2 exp(-p²).
Throughout the paper, we also frequently the notion of sensitivity:
Definition 3 (Sensitivity). The sensitivity of function f 2T - Rd w.r.t. norm
||
D sup 12-21|=1 - (
Almost all methods for ensuring differential privacy involve injecting noise whose scale increases with the sensitivity of the output. In other words, small sensitivity implics high privacy.
2 Diffentially Private Online-to-Batch
In this section, we present our main differentially private online-to-batee algorithm. To start, we need to define online convex optimization (OCO). OCO is "game" in which for T rounds, t 1, 1,..., T, an algorithms predicts parameter wi E W. It then receives a convex loss 4, W - R and pays the loss (e()) The quality of the algorithm is measured by the regret w.r.t. a competitor u, defined as Regrety(u) = -'= (w:))) - Le()).
Online-to- algorithms Miesa-Bianchi et al., 2004) convert OCO algorithms (online learners) into stochastic convex optimization algorithms. In particular, for $1, .......Bu > 0, the anytime flline-to-batch conversion (Cutkosky, 2019) defines the t-th loss as ( (3. V( 21), w), where H, -i=1 S.w. Convergence anytime online-to-batch builds on the following key result, and its proof in Appendix for completeness.
Theorem 1 (Cutkosky (2019)). For any sequence of B, > 0, Rd, suppose online learner predicts we and receives t-th loss (z(w) (g1. w). Define I Ei=1 Then for any convex and differentiable L.
2.m where BI.t Ei= 3r
Bi.
(rr((((rr)- ((()) < Regret, (u) + Σ (B.L 9r, wt we
w). Vu Rd.
tighter bound is possible (Joulani et al., 2020), but the simpler expression above suffices for our analysis. As an immediate result, choosing Br 1 and Sr B, V ((x2, 2t) satisfies []g./2,]] 3, V.,,), so E[[(=r)= L(u)] < E[Regrety (u)l/T Therefore, any online learner with sub-linear regret guarantees convergence for the last iterate ZT. Notice that due to the formulation of the anytime online-to-batch. the iterate I, is stable. Consider the case where 3 = for all t. Then, we have ||2, r:-1l || = |ml, 11-ill/t < D/t regardless of what the online learner does. This guarantee is
Throughout this paper, we denote Ir., = E.= Be.

---

significantly stronger than the classical online-to- bo-bachh result of Cesa-Bianchi et al. (2004). We would like to take advantage of this stability to design our private online-to-batch algorithm. Intuitively, the algorithm has much lower sensitivity due to the stability of the iterates, which can be exploited to improve privacy.
Our goal will be to make the entire sequence 91....., 9T private, which, in turn, makes the entire algorithm private. To do so, we would like add noise the gi 's while still having gr be a good estimate of ([(z)). In standard non-private onlinc-to-bated stochastic gradient Vi(r,, 2+). However, directly adding noise to Vd(2,, 2)) is not good idea because its sensitivity is (1) (more specifically the sensitivity is bounded by 2G by Lipschitzness).
9e is usually defined as the
Consequently, we need to add noise to gt. whose variance is of order (11/e) )) in order to achieve e-differential privacy.
Instead, we express = -i-1 6,, where 6, = B, B,Ve((,, B.- 24 and 30 = 0. Since Ve(1,_111111
we assume l is smooth, if we set B, = 1 then || S. -1 z,-1ll S DH/i,ic.. i.c., the sensitivity of 6, is (1/i)). As a result, we can privately estimate 9: with error roughly ((1/te) using the tree aggregation mechanism (Dwork et al., 2010; Chan et al., 2011). an advanced technique that privately estimates running sums, such as our Eim 6;. Compared to directly adding noise to Vε(z,, 2e), this method adds less noise (Ō(t/te) compared ((1/c)) and thus allows us to achieve the optimal rate.
On the other hand, after using these advanced aggregation techniques, It is no longer an conditionally unbiased estimator of 3, (.x.). More specifically, although it remains the case that Ez, [2, [8. 2,1] = & - V it is not necessarily true that .,, + (z Unbiasedness plays key role in standard convergence analy- ses, but we will need a much more delicate analysis.
Moreover, although we mostly discuss the 3, = 1 case above for intuition, our algorithm is analyzed using the general case 3 = 1* for k 2 1. The guiding principle for this formula the sensitivity of 6r. For k 2 1, the sensitivity of d is of order 0(t--1) ). For A: 1. this is constant sensitivity, which is particularly intuitive for analysis. For k = 0 (i.e. the standard weighting in saline-to-batc)] the sensitivity is actually O(1/t). which is much more complicated to analyze. In order to apply the tree aggregation casily, we want the sensitivity of 5, to be polynomial in t, rather than the inverse polynomial 1/t, we define B, th and ask t k. Furthermore, in all cases except for the parameter- free case (Section 5), our results hold for all & 2 1. In the parameter-free case, we choose k for algebraic reasons.
The pseudo-code is presented in Algorithm 1, which has linear time complexity. It is similar to anytime online-to-batch, while we replace It with the more complicated definition and add noise Yt generated by the NOISE subroutine, which implements the tree aggregation. More specifically, given random noises { NOISE(t) returns E.e,, R,, where 1, is the set of cumulative sums of the binary expansion of t. That is, for some 2 [log](t]] + 1, we define bin(t) {0, 13" by t Σm= bin Then, 1, consists of all non-zero sums of the form Σi=1 bin(t)
For examples, 7 = + + 1, so 17 = {4, 6, 7}; 8 - 8, so Is = {8}.
Algorithm Differrnniillyy Priviit Online-to- to--atch
1: Input: OCO algorithm AA with domain W,, positive sequence {.,,,, distribution D, dataset Z.
2: Initialize: Set 3 0, To 0 and go 0. Set global variable R 0--
3: for t= =,,,... T do
4: Get w/ from A and compute x, (81--124-- + 3,w,) //:t)/Bi-.-
5: Compute gradient difference 6, = 3r V((r, 2x) 8- V(( 1, 2t).
6: Update St = 9t + o, and generate noise 7t = NOISE(!).
7: Send &, (w) (gt + Ye, w) to A as the 1-th loss.
8: function NOISE(!)
9:
Initialize: Set k 0, = () bin(t) be the binary encoding of and n [logz t
10: for i .,....,7. n do
11:
2 and 1, 4, U (k). Generate noise R₂ ~ D, compute R, = a R, and update R = R J (RU(R)) (R.).
If (in(() 1, update
12:
13:
Return 7 EieL. R.
4

---

Convergence Following Theorem and Fenchel- Fenchel-Young's inequality, Algorithm satisfies:
BIT(C((T) [(x*)) < Regretr((")) +
(B.V(()) 9t. Th, we - x²)
(2)
T
I (x +
((1)))(())))0 - + - Dlmll
(3)
(3) decomposes the suboptimality gap ((xr)-(()(( into three components: (1) regret Regrety (x*), (ii) error associated with variance of gt. measured by ||3, (x(x) - gell.. s. and (iii) error from DP mechanism, measured by l/ull= To get tight bound, observe that 8, L.v)) sums conditionally mean-zero random vectors (Lemma 15 in Appendix A). With a martingale bound in high dimension with general norm (Lemmaa 13), can derive the following bounds. In particular, we show (Lemma 15) that if Assumption 6 hold and set Be = t², then
9i and % are
[(I,) ge113] 4(k: (o D20 1//,
(4)
Moreover, we show (Lemma 16) that if R and E(I | I o? then
E| s (max σf) log (28)/A.
(5)
+
Privacy The next step is determine how much noise sufficient for Algorithm to be RDP. We first make the following assumption on the distribution D.
Definition 4 ((V, RDDP distribution). A distribution D on R is said to be (V, RRDD distribution on || II if it satisfies that for R ~ D (i) E(R] = (ii) El R S V, and (iii) for all p > 0 and p², then (a + pllo R n') S /
1, Rd, o² || μ //1l2/0²
the L2 norm is the multivariate normal distribution. [| = d. For the third condition, we can show that for all (1, μl and a > (N (a, o 22 o I)) < allø μ [| 11/20²² which is further bounded by ap² for all o² 2 || μ 11//2 (Lemma 18). Therefore, (0, 1) is a (d, RDD distribution for all
Remark 2. A standard (V, aV distribution
Let R ~ (0, 1) then is clear that R[R] = 0 and B||
1.
As its name suggests, adding noise sampled from RDP distribution is sufficient to make deterministic algorithm RDP. Consider function f(Z) f(Z) a R,, where R D and D is (V, RD- distribution on || |]. Let A be the sensitivity of f w.r.t || ||. Set x² > 2²/p², then by Definition 4,
Da(f(Z))((())) (Z) + RR)()(() + +oR) S ap? /2.
Thus, f (a, /222/2)-DDP. Moreover, we can compose RDP mechanisms via the tree aggregation mechanism. Specifically, we set B5 = t and define the variance of in Algorithm as follows:
of 4(k 1)² (G H max p2
|w
x;=1 11-111)2oogg (o) (2-)
(6)
se[t]
We assume ||l; -;-1 S D. Upon substituting (6) into (5), we get E
R S कī S Vo? and:
[[Il++11] < 8(k +
DDH)
12g3
(7)
Ap2
The following theorem shows that Algorithm 1 is Rényi differentially private if we define of as in (6). proof is presented in Appendix B. Note that the privacy guarantee does not require i.i.d. Z. Theorem Suppose ||- 2 is X-strongly convex, W is bounded by D, l G-Lipschitz and H H-smooth, and 'D is a (V, a)-DP distribution. 3 = t and of is as defined in (6), then Algorithm (or, cup² DP) for all datasets Z.
'Here slightly abuse the notation. For random vectors X, Y. D. denotes the Rényi divergence of the underlying distributions X and
5

---

Main Result. Now we can combine all the previous results to prove the privacy and convergence guarantee of our algorithm.
Theorem 4. Suppose Assumption I 6 hold, and D is a.) distribution. If set Br eh and define of as in (6), then Algorithm 1 is (ax, ap² / and B(f(ar) [[(x)]] is bounded by:
(k + 1) ((egett
2(k + 1)2D
oG
Don VT
(2V + DH) 12g)(2T)
Th+1
VA
pT
Moreover, recall that the online learner receives 1-th loss (((w) = (g. + Yt, w). It holds that
Ell. 91 + vell]1 S 32th G² (
4(k +)2
(og + DoH)² 2V(G + DHY 1
A
Remark 5. As an example, let's consider the Gaussian distribution (0, 1) on the 2-norm, which (d, o:--DDP distribution for all 1 (Remark 2). For many popular online learners (OSD, OMD, FTRL), Elll (w,))]1 < G for I, then E(Regrety(x")) S O(DGVT). Hence, Theorem with D N (0, I) implies that
B[((rT) - [(x")] =0 DIG+ Don) vdD(G + DH) log T
pT
This bound is of ÓL/VV + vd/pT', which can be translated to an equivalent (c, bound of /CT) This bound matches the optimal rate for private stochastic optimization with convex and smooth losses (Bassily et al. (2019)).
Proof of Theorem 4. From Eq. (3), we have:
B[[(xT) - [(x")]
1
E
(xgretyy(x") + Σ (113.V((z)) - gell= + Imlll))
B1T
Recall the bounds of V(((t) 9ell:] and [[ in (4) and (7). By Jensen's inequality, Morcover, since B₁ = th and k 2 1, it holds that B 2 T /k + 1, so:
||| ||.
Regrett
D
2(k + 1) + Do jek
V8V(k + I) DH log, +
3IT
BIT 1=1
VT
VAp
(k: +1) (agrrt))
2(k + D)&D
(aa + Don
/2V(G DH (2T)
Tk+1
VA
VT
pT
For the second part of the theorem.
Eilgg: + 7a [2] s Bl V2 + l19. (V,(()))) ? + 11x111
We bound the first term by Lipschitzness, the second by (4), and the third by (7)
< 312k 12(k: + () + DDoo 24V 1)²(G DH1 12T)
Ap2
4(k + 1)2
( + D
2V DII log (2T)
3k2k G2
p²t²
3 The Optimistic Case
In this section, we show that choosing an optimistic online learner (Chiang et al., 2012; Rakhlin and Sridharan, 2013; Steinhardt and Liang, 2014) will accelerate DP online-to-batch algorithm. Optimistic algorithms provided with additional "hints" in the form of (ww {gt, w) as an

---

approximation of the true loss (x(w) (gt. w). and they can incorporate l to decide The regret of an optimistic algorithm depends on the quality of hints: if ÿt gt, then it achieves low regret. Formally, in this paper, say online learning algorithm is optimistic w.r.t norm its regret the following:
T Σ
Regrety (x*) SO
D
l
9:
(8)
where D denotes the diameter of the learner's domain.
common choice of the hint År gt-1, the gradient in the last round since intuitively, one could expect 9t-1 R 9t when the loss functions are smooth. In this section, we also follow this choice. Recall that in Algorithm
the online learner receives t-th loss (ww)) = (gt + Yt, w), where 9t = -i=1 ò, is the sum of gradient differences, and 7t is some noise. Therefore, we define the t-th hint 9t 91-1 76-1-
Theorem 6. Suppose Assumption hold, and D is a (V, aR--DDDPPPPPPP RDP distribution. Set Br = th and of as defined in (6), If the online learner is optimistic (satisfying (8)) with t-th gradient 9t 7 and 1-th hint Gt- I1-1. then
E [egrety so (DIG PIG+DDN DH) (1+ VVlog log Vxp
vV
DD)
B1T
T3/2
The proof is in Appendix D. As an immediate corollary, if we further assume Assumption and 6, then Thcorem 4 applies. Together with this thcorem. they imply that optimistic learners achieve the following convergence rate that is adaptive to the variance:
(Plee + DoH), VT
VāD(G DH) log T pT
E(((xT) [(x")]
VT
Compared to the bound in the non-optimistic case (Remark 5), this bound has de instead of G in the first term. Thus, when the gradient ((((,,2)) has low variance, i.e., oG < G, the optimistic bound outperforms the standard bound.
4 The Strongly Convex Case
In this section, we prove that in the case of strong convexity, our algorithm can be improved by regularizing the loss of online learner. If L is strongly convex, then we can prove similar result to Theorem (the proof is in Appendix E).
Lemma 7. Suppose C is p-strongly convex w.r.f. || we replace (e(w) (gt + Ve w) with ((ww) = (w) 2el2 w r2ll2 in Algorithm and denote the associated regret by Regrety, then
3:1 1|w, x11
(Ir(C(aT)) L(x*)) S Regret,
((.)) St
N/s we x²)
8
2133.VC(zz) - 9: 7t
S Regrety(x"))
Beja
Compared Lemma and Equation in the strongly convex case, there is an additional term 9: We 112,, which allows the improved convergence rate:
Theorem 8. Suppose Assumption 1 6 hold, and 'D is (V, RDD distribution. Also suppose L is
ju-strongly convex. Set 3r = 1* and of as defined in (6). Then B[C(ær) - L(x*)] ] is bounded by:
(k + 1) E) (egrett 16(k + 1)² ((GG Don)² Tk-1
2V + DH) 1og2
+
Ay
T
T272
Moreover; for all ğe (l:(w.),
4G2 + 222 + 16(h: + 1)²
(ag + D
2V + DH) 1og3(27)
El 2 < 22
A
22t2

---

Remark 9. As an example, again consider the case D (0 7) with L2 norm. Online subgradient descent (OSD) with appropriate learning rate on 14:-ttonglyy convex losses & achieves:
1
Regretr(u) S
2 2
where 9: @ll( In our case, || 112 is 2-strongly convex and the regularized loss & is feft -strongly convex, i.e. 1r = 1ut* /2 and Σi= b4 = O(utht2). Therefore, by Theorem 8,
T E Regret (x 5o
G² + 12222 + (og + DoH)² d(G + DH) log T
-
/
T
p²T²
Consequently,
(G [G+uD μD + )
d(G + DH) log 2
[[[(rT) - [(x")
up2
This again matches the optimal private convergence rates.
Proof of Theorem 8. We have already bounded B[[B3,VL(H)) 9 [12] and [[] in (4) and (7)
respectively, so
E 9t 7ell21 < 2 2 2 gell + [1
8(k 1)2(2k11 ( Don) 2V + DH)² (2T)
X
p²t
Upon substituting this into Lemma 7 and replace Be th, we get:
S1r [[((xr) - [(x*)]
T
16(k + 1)2(1-1
(ao DoH)² (Dc++DHH²++
2V + DH logg
< Re/gree (x))]
+1
AM
p²t
1=1
16(k + 1)²
(GG TT 2V + DIT) log (2T)
Re.egrety (x*)
Au
Dividing both sides by 31. 2 T /kk + 1) proves the first part of the theorem.
For the second part, recall that (w) = (g: + Yt, w) + B.u || 12 Therefore, for all gr E 0l, (w),
4
z. + + o where 0|| w/ ==11 2 We follow the same argument in Theorem 4:
[1 < 4 [ + [
ga 112 11 + ||
Here v E al[w; - 12. We bound the first term by Lipschitz, the second by (4), and the third by (7).
Moreover, by chain rule (Proposition 21), show that ||||| 2D, so:
2k G2 + 16(k (ac + Do 2
32 + ()²(G + 2H log3 (2T) + D2th
+
Ap2
16(k + 1)2
[ao + DoH)²
2V DH) 1og2
< 226 |C + p2222
X
1212
Parameter-free Algorithm
In this section, we apply Algorithm with "parameter-free" online learner. These are algorithms that guarantee Regrety (u) < (([u]IVVT) for all competitors simultancously (Orabona and Pál,

---

2016; Cutkosky and Orabona, 2018; Mhammedi and Koolen, 2020). By shifting coordinates, it is possible to obtain (egretr(")) O11 zal vT) for any pre-specified point Thus, if xg R a is some good initialization, perhaps generated by pretraining, this bound yields significantly smaller regret than if we had used the worst-case diameter bound ||u zoll - D.
In order obtain this refined bound with privacy, we need to make a small modification to our conversion. For simplicity, we focus on Euclidean space with 2-norm, and we assume the distribution D is in addition sub-Gaussian, i.c., for R
D.
P( sup (R ( exp (- ||l||=1
é
2o (T20²)
In general, the proof extends to any Banach space and any distribution DD that concentrates on it.
In previous analysis (Equation (3)), we roughly bound ||w, x"1l S D. However, in this section, we come up with a finer high probability bound that maintains a dependence on || || || We then replace the loss & (w: in Algorithm 1 with regularized loss f (w) + E/|lw]12 + 14 [rlll=l22 and we show that the new algorithm with regularized loss can achieve a parameter-Iree bound. The complete proof is presented in Appendix F.
Theorem 10. Suppose w.r.t. 2-norm, W is bounded by D and & is G-Lipschitz and H H-smooth. Suppose D is (V, RDDP distribution and is a -uub-aaussian. If we set Br t (i.e. k = 3) and set of as defined in (6), then with probability at least 1 - 8,
T
C(xr)- f(x))
4 T4
Reggett(("")
Σ
Ce(llwell2 + 112) + (e || 118)
where C is a universal constant, A 8/2C2, A' = 8vdop == 1+ DH/G. and
1/4 = 2 +b Vlog blog, (2T)
20dI log(2k()
& = AG A'G DH)
5
Theorem 11. Following the assumptions and notations in Theorem 10, if we replace & (w) in Algorithm with regularized loss (e(w) (ww) Sellw|1a wel wellull and denote the associated regret as Regret,, then with probability least 6, L(xr) f(x") ) is bounded by:
(2ggretr &AI|=* [G + 28 x H T
8A'[< (I + DH) log, (2T)
VT
pT
Moreover, with probability at least 6, for all t and all w E W, De E 0E, (w).
1lāel22 S Gt + A(2G 57DH) + 2A'(G + DH) + log (27)
P
Remark 12. If 1100 S & for all parameter-free algorithms achieve regret bound Regrety ((I Therefore, with D = (o, I), D is I-sub-Gaussian and A' = O(vd), so Theorem 11 implies that with probability
5,
Regretr(x*) = T
|| || -0(11)/2G VT
|| 12 DH), + I DH)
T
3T3/2
Consequently,
|| |I* DH)
|l*Ilavd(G + DH)
- ((xt))((x")+ 5
VT
pf
Proof of Theorem 11. The regularized regret satisfies
Regrety (x*) Regrety (x*)
Σ &ollww ||0*|12) + e (1w ||>0 112).

---

Hence, upon substituting this equation into Theorem 10, we get: with probability at least 6,
4Regrety (xx)
- -(r))-(xx))
& 2| 1l2 + 1/
T
T
4Regrety(x")
8(AG x211=1 112 + 28AH 1B)
8A'G DH) log2 (2T) |001|
74
VT
pf
The second inequality is from Et=1 & S Tx because & is increasing with & (so is 14).
For the second part of the theorem, for each fixed and for all He E (wr)), Dt = ge+ Eru 2v, where u E Øl[w, ll and thus ||u||2 S Therefore,
| 2 < 119 3 (x,)) 12 + ||8, VC((2))l2 + lllll + ||E,u|12 + 1|2
By Lipschitzness. || V (ax))) Gt Since W bounded, || 112 < 2Dv, Also, ||E/u|12 I &c. Moreover, we can prove (in Eq. 14 and 17) that for each i, with probability at least 1 5/2T,
VL(x)) -ella s 4
i H|w x.-1ll2)² s A4(G - DH)
==1
lnll S (G DH) (G (2T)
Upon laking the union bound for all and the definition &e, vs, we get the desired bound.
Conclusion
We have presented new online-to-bate conversion that produces private stochastic optimization algorithms smooth losses. Online algorithms achieving the optimal O(vT) regret automatically achieve the optimal Õ(1/VT vd/cT) convergence rate. Combining this technique with the literature on online learning can yield new private optimization algorithms.
Limitations: Our algorithm requires smoothness, and unlike some other bounds, we cannot tolerate large H. In the worst case when H = /T and = H, our standard bound in Remark 5 becomes O(1). In other words, we need to assume H o( (() to ensure non-trivial bound. Removing this restriction would significantly improve the generality of the procedure.
The dependence on H comes from the sensitivity of 6 (Lemmaa 15), where we apply smoothness to bound [V 2,) [f( II S 3. zt-1ll and use the stability of x, to further bound| [2 Iz-1ll || I D3, /51.. which are necessary steps in order to bound the sensitivity of 5 by -(tk-1), Hence, it's not clear how to remove the smoothness assumption.
References
Abadi, M., Chu, A., Goodfellow, L., McMahan, H. B., Mironov, I,, Talwar, K., and Zhang, L. (2016). Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318.
Asi, H., Duchi, J., Fallah, A., Javidbakht, O., and Talwar, K. (2021). Private adaptive gradient methods for convex optimization. In International Conference Machine Learning, pages 383-392, PMLR.
Bassily, R., Feldman, V., Guzmán, C., and Talwar, (2020). Stability stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381 4491.
Bassily, R., Feldman, V., Talwar, K., and Thakurta, A. (2019). Private stochastic convex optimization with optimal rates. Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 11822-1129..
Bauschke, H. H., Combettes, L., et al. (2011). Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer
10

---

Cesa-Bianchi, N., Conconi, A., and Gentile, C. (2004). On the generalization ability of on-line learning algorithms. Information Theory, IEEE Transactions on, 50()))2000-20577
Chan, T.-H. H., Shi, E., and Song, D. (2011). Private and continual release of statistics. ACM Transactions Information and System Security (TISSEC), 14(3):1-24.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. (2011). Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3).
Chiang. C.-K., Yang. T., Lee, C.-J,, Mahdavi, M., Lu, C.-J,, Jin, R., and Zhu, S. (2012). Online optimization with gradual variations. In Conference on Learning Theory, pages 6-1.
Cutkosky, A. (2019). Anytime online-to-batch, optimism and acceleration. In International Confer- ence on Machine Learning, pages 1446-1454.
Cutkosky, A. and Orabona, F. (2018). Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pages 1493-1529.
Dwork, C., McSherry, F., Nissim, K., and Smith, (2006). Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. (2010). Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715-724.
Dwork, and Roth, A. (2014). The algorithmic foundations of differential privacy. Found. Trends Theor Comput. Sci., 9(3-4)2211-077,
Feldman, V., Koren, T., and Talwar, K. (2020). Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449.
Hazan, E. (2019). Introduction online convex optimization. arXiv preprint arXiv:1909.05200
Hoory, S., Feder, A., Tendler, A., Erell, S., Peled-Cohen, A., Laish, I., Nakhost, H., Stemmer, U., Benjamini, A., Hassidim, A., et al. (2021). Learning and evaluating differentially private pre- trained language model. In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 1 1178-1189.
Jin, C., Netrapalli, P., Ge, R., Kakade, M., and Jordan, M. (2019). A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint 192.v:190.
Joulani, Raj, A., György, A., and Szepesvári, C. (2020). A simpler approach accelerated stochastic optimization: Iterative averaging meets optimism. Internation Conference on Machine Learning.
Kamath, Liu, X., and Zhang. H. (2021). Improved rates for differentially private stochastic convex optimization with hcavy-tailed data. arXiv preprint arXiv:2106 0..6366.....
Kifer. D., Smith, A., and Thakurta, A. (2012). Private convex empirical risk minimization and high-dimensionall regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings.
Kulkarni, J., Lee, Y. T., and Liu, D. (2021). Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps. arXiv preprint arXiv:2103.155 15352.
Kurakin, A., Chien, S., Song, S., Geambasu, R., Terzis, A., and Thakurta, A. (2022). Toward training at imagenet scale with differential privacy. arXiv preprint arXiv:2201.12322.
Li, T., Zaheer, M., Reddi, S. J., and Smith, V. (2022). Private adaptive optimization with side information. arXiv preprint arXiv:2202.0550 05963.
Mchta, H., Thakurta, A., Kurakin, A., and Cutkosky, A. (2022). Large scale transfer learning for differentially private image classification. arXiv preprint arXiv:2205.02977 02973.
11

---

Mhammedi, Z. and Koolen, W. M. (2020). Lipschitz and comparator-none adaptivity in online learning. Conference on Learning Theory.
Mironov, 1. (2017). Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE.
Orabona, F. (2019). A modern introduction to online learning. arXiv preprint arXiv: 132113
Orabona, F. and Pál, D. (2016). Coin betting and parameter-free free online learning. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I,, and Garnett, R., editors, Advances in Neural Information Processing Systems 29, pages 577-585. Curran Associates, Inc.
Rakhlin, A. and Sridharan, K. (2013). Online learning with predictable sequences. In Conference on Learning Theory (COLT), pages 993-1019.
Shalev-Shwartz, S. (2011). Online learning and online convex optimizatiio. Foundations and Trends in Machine Learning, 4(2):
Steinhardt, J. and Liang. P. (2014). Adaptivity and optimism: An improved exponentiated gradient algorithm. International Conference on Machine Learning (ICML).
Yu, D., Naik, S., Backurs, A., Gopi, S., Inan, H. A., Kamath, G., Kulkarni, J., Lee, T., Manoel, A., Wutschitz, L.,, et al. (2021). Differentially private fine-tuning of language models. arXiv preprint arXiv:2110.06500
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See discussion in Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [No] This paper addresses mathematical problems, and we do nol anticipate negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes] See Section 1 for all assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] In the main text, we only leave the proofs for the most important results because of page limitation. However, the complete proofs of all results are included in the supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No] We did not experiments.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [No] We did not run experiments.
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [No] We did not run experiments.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [No] We did not run experiments.
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [No] We did not run experiments.
(b) Did you mention the license of the assets? [No] We did not run experiments.
(c) Did you include any new assets either in the supplemental material or as URL? [No]
We did not run experiments.
12

---

(d) Did you discuss whether and how consent was obtained from people whose data you 'e using/curating? [No] We did not run experiments.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] We did not experiments.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [No] We did not use crowdsourcing nor conduct research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [No] We did not use crowdsoureing nor conduct research with human subjects.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [No] We did not use crowdsourcing nor conduct research with human subjects.
13


Reviews:
[{"review_id": "yjfHwGvyYGM", "reviewer": "Reviewer_toms", "summary": "This paper proposes a novel online-to-batch conversion algorithm with theoretical guarantees, which aims to achieve optimal convergence rate of expected risk under differential privacy constraints. Relationships between regret bound and expected risk are also provided under different conditions of loss function.", "questions": "What is the relationship between the proposed algorithm and existing differentially private online learning algorithms? ", "limitations": "My major concern is about the reproducibility of the proposed algorithm. This paper proposes a novel online-to-batch algorithm with theoretical guarantees rather than only provides theoretical analyses for existing learning algorithms. Thus, empirical analyses are essential for demonstrating the effectiveness and efficiency of the novel algorithm with differential privacy constraints. Besides, some important related works about differentially private online learning are missing.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1.\tThis work is well-motivated with theoretical analyses. \n\n2.\tOnline-to-batch conversion technology is an important topic in online learning, and differentially private is also important in streaming data.\n\n3.\tRegret bound and expected risk are analyzed under different conditions of loss function.\n\nWeaknesses:\n\n1.\tSome efforts have been made to the topic of differentially private online learning (DPOL) in [Jain et al., 2012]. The comparison with DPOL is missing.\n\n2.\tLack of analysis of computational complexity.\n\n3.\tThe paper lacks mostly discussion and insights for the theoretical results. \n\n4.\tThis paper lacks empirical analyses, which limits the reproducibility of the proposed algorithms.\n\n[Jain et al., 2012] Differentially private online learning, COLT 2012.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OKjhU3Qabx-", "reviewer": "Reviewer_HZ7s", "summary": "Under the assumption of a smooth loss function, this paper investigates a new online-to-batch conversion method for private stochastic optimization.", "questions": "Is the cardinality of I_t an r.v. in Line 13 of Algorithm 1? If not, can we simplify the part involved I_t? If it is a r.v., can we use the randomness to amplify privacy?", "limitations": "The writing could be improved to make it more reader-friendly, and experiments are encouraged..", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper offers a fresh look at stochastic optimization with DP guarantees. However, it appears to have been rushed and does not demonstrate well. Even though the smoothness assumption is a limitation, experiments for the smooth loss case and comparison with other existing methods are preferred to provide a sense of the utility advantage claimed in this paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Privacy and Security (e.g., consent)"]}, "extra_text": {}}, {"review_id": "G-i8vfjAlE7", "reviewer": "Reviewer_ycjh", "summary": "Online to batch conversions are a classical reduction from adversarial online learning to stochastic optimization. This work introduces the use of such reductions in the context of Differentially Private Stochastic Convex Optimization (DP-SCO). This extension is nontrivial, as it is known that in this context classical online to batch leads to suboptimal rates. Therefore, in this work a more careful weighted regret scheme (known as anytime online to batch conversions, Cutkosky 2019) is used. This method is used in conjunction with a tree aggregation DP mechanism (Dwork et al. 2010), that allows for optimal noise addition of partial sums; and with a recursive stochastic gradient estimator, which has been proved useful in DP-SCO (Asi et al. 2021, Bassily et al. 2021). It is interesting that the technique is quite general, and it is applicable to settings beyond $\\ell_2$ DP-SCO, which by now is well understood.  The work includes extensions to strongly convex losses and rates for which (the non-private $O(1/\\sqrt{n})$ term) adapts to the level of noise. \n\n* Asi, Feldman, Koren, Talwar. Private stochastic convex optimization: Optimal rates in l1 geometry (ICML'21) https://arxiv.org/ abs/2103.01516.\n* Bassily, Guzman, Nandi. Non-Euclidean Differentially Private Stochastic Optimization (COLT'21) https://arxiv.org/pdf/2103.01278.pdf\n* Cutkosky. Anytime online-to-batch, optimism and acceleration (ICML'19) https://arxiv.org/pdf/1903.00974.pdf\n* Dwork, Naor Pitassi, Rothblum. Differential Privacy under Continual Observation (STOC'10)\n", "questions": "1. Assumption 1, page 2. It seems that the strong convexity inequality is incorrectly written. Shouldn't it be $\\|y\\|^2\\geq \\|x\\|^2+\\langle g,y-x\\rangle+\\frac{\\lambda}{2}\\|y-x\\|^2$? It should also be said that this function is strongly convex with respect to $\\|\\cdot\\|$.\n2. Algorithm 1, page 4. The subroutine NOISE is somewhat confusing, and I expect that any reader unfamiliar with the tree aggregation mechanism will have difficulties following it. What is the binary expression of $t$? do you mean ``binary expansion'', and then does this mean the bit encoding? I think a brief description of tree aggregation with references can go a long way. As well as adding a short lemma that elaborates on the connections between the binary encoding, $s_t$, $I_t$, $S_t$, etc. (e.g., that $S_t$'s partition $[t]$).\n3. Equation (3). It is unclear to me why you use triangle inequality and Holder here. I thought the point is that these are zero mean conditional random variables (in fact, in the previous page this is exactly what is done in the last paragraph). I am not saying that dependencies on the norms of these vectors would not affect the final rates (because they do), but upper bounding in this way here is misleading to what is ultimately done in the analysis.\n4. Main Result, page 5 (and other places). I understand it is possible to choose different values of $k$ for the averaging, but it is never thoroughly discussed why would one want this level of generality. A couple of results use particular choices of $k$, but it is never discussed why this choice matters.\n5. Theorem 6, page 6. What is the value of $k$ for this result? What is the importance of the $3/2$ exponent of $T$ in the average weighted regret?\n6. Definition of sub-Gaussianity, Page 8. What is $R_i$ here? Reading this feels out of context.\n7. Theorem 10, page 8. What is the importance of $k=3$ here?\n8. Conclusion, Page 9. It is said that ``we cannot tolerate large $H$.'' This issue is never discussed in the paper, neither its nature or whether it seems inherent. I am afraid Theorem statements neither make this limitation clear. Please elaborate where it corresponds.\n9. Line 391-392, Page 13. Please remove $\\nabla$ in various terms where they shouldn't be (I believe it was meant to be ${\ncal L}$, rather than $\\nabla {\\cal L}$).\n10. Lemma 15, page 14. Say that $\\|\\cdot\\|^2$ must be strongly convex ``with respect to $\\|\\cdot\\|$''. And add the expectation sign to $\\|\\delta_t\\|_{\\ast}$ (o.w. it is not true). Also add the conditional expectation to $\\mathbb{E}[\\|X_i\\|_{\\ast}^2]$ in (iii), to be consistent with (ii).\n11. Proof of Theorem 3. The quick preliminaries of the tree aggregation procedure should be converted into a short Lemma. That would make it easier to find for the interested reader (these notations and claims are used beyond this theorem).\n12. Theorem 19, page 19. Is this result ever used?\n13. Line 546, page 20. Use the expectation operator on $\\|\\delta_t\\|_{\\ast}$.\n14. Could the authors elaborate on the comparison with a recent work on DP-SCO with streaming data: Han et al. 2022 (On Private Online Convex Optimization: Optimal Algorithms in lp-Geometry and High Dimensional Contextual Bandits, https://arxiv.org/pdf/2206.08111.pdf). Maybe the results of the current submission subsume some of these results?\n", "limitations": "There are two technical aspects of this work that are worth a more extensive discussion:\n\n1. Are the new online to batch conversion results presented in this paper capable of addressing $\\ell_1$-geometry (Asi et al. 2021, Bassily et al. 2021). This is an important question, since this is the only general case where we can avoid polynomial dependence on $d$ in the rates. This is not a direct corollary of what is currently done in the paper, as the stochastic Frank-Wolfe algorithms of the references above are not clearly applicable to the online setting.\n\n2. The issue about the smoothness constant $H$ is currently lacking a more thorough discussion.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The unifying perspective on DP-SCO, capable to recover optimal rates without specialized arguments, or reductions between convex and strongly convex losses through regularization.\n2. The perspective of online to batch conversions provides a rather straightforward extension to non-Euclidean norms, for which optimal methods are still scarce (Bassily et al. 2021).\n3. Adaptivity to the noise level. All kinds of adaptivity in differential privacy are challenging, and not well understood, so this result in itself is significant.\n4. The paper is fairly well written, and the proofs and analyses are not complicated and principled.\n\nWeaknesses:\n\n1. I think this unifying perspective becomes more interesting in geometries which are not $\\ell_2$. More exploration of the consequences of the results of the paper to these settings would have been an interesting addition.\n2. Aside from the noise adaptive rates and the parameter free algorithm, the rates derived in the paper are not new (namely, optimal rates have already been established). I don't think this is a major problem though, mostly because making these methods more broadly applicable is interesting and necessary to better understand DP-SCO.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept