Differentially Private Optimization with Sparse Gradients
Authors: Badih Ghazi
Cristóbal A Guzmán
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Stochastic Optimization
Convex Optimization
Sparsity
Primary area: privacy

Abstract: Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of _individual_ gradients.  We start with  new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high-dimensional regime. The corresponding lower bounds are based on a novel block-diagonal construction that is combined with existing DP mean estimation lower bounds.
Next, we obtain pure- and approximate-DP algorithms with almost optimal rates 
for stochastic convex optimization with sparse gradients; the former represents the first nearly dimension-independent rates for this problem. Furthermore, by introducing novel analyses of bias reduction in mean estimation and randomly-stopped biased SGD we  obtain nearly dimension-independent rates for near-stationary points for the empirical risk in nonconvex settings under approximate-DP.

Differentially Private Optimization with Sparse Gradients
Badih Ghazi Google Research badihghazi
Cristóbal Guzmán Google Research and Pontificia Universidad Católica de Chile crguzman@google. com
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Google Research
Google Research ravi kww8km5i1.cccmmmm com
Google Research
pritishk@google.com com
pasinggoogle, com
Abstract
Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high- dimensional regime. The corresponding lower bounds are based on a novel block- diagonal construction that is combined with existing DP mean estimation lower bounds. Next, we obtain pure- and approximate- DP algorithms with almost optimal rates for stochastic convex optimization with sparse gradients; the former represents the first nearly citnensioo-independdee ducing novel analyses of bias reduction in mean estimation and randomly-stopped biased SGD we obtain nearly dimension-indeeeeddem rates for near-stationary points for the empirical risk in nonconvex settings under approximate-DP.
rates for this problem. Furthermore, by intro-
1 Introduction
The pervasiveness of personally sensitive data in machine learning applications (e.g., advertising. public policy, and healthcare) has led to the major concern of protecting users' data from their exposure. When releasing or deploying these trained models, differential privacy (DP) offers rigorous and quantifiable guarantee on the privacy exposure risk [1].
Consider neural networks whose inputs have categorical features with large vocabularies. These features can be modeled using embedding tables; namely, for a feature that takes K distinct values, create trainable parameters W1, WK RR and use W. as input to the neural network when the corresponding input feature is a. A natural outcome of such models is that the per-example gradients guaranteed be sparse; when the input feature is a, then only the gradient with respect to w. is non-zero. Given the prevalence of sparse gradients in practical deep learning applications, GPUs/TPUs that are optimized leverage gradient sparsity are commercially offered and widely used in industry [2, 3, 4, 5]. To leverage gradient sparsity, recent practical work has considered DP stochastic optimization with sparse gradients for large embedding models for different applications including recommendation systems, natural language processing, and ads modeling [6, 7].
Despite its relevance and promising empirical results, there is limited understanding of the theoretical limits of DP learning under gradient sparsity. This gap motivates our work.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Setting
Upper bound
Lower bound
s-DP
1
v/sd
(Thm. 3.2)
Il(d//en))
s/d (Thm.
4.1)
en
en
en
en
(1((78)) (Thm. B.1)
(= [in(1/6) (Thm. 4.5)
(5, 6)-DP
Ven
En
Ven
en
Table
Rates for DP mean estimation with sparse data of unit m--norm. Bounds stated for constant highlighted
success/failure probability, resp. We use a b to denote min(a, b). New results
New Upper bound (sparse)
Upper bound (non-sparse)
Setting
Guarantee
(#In(d) ln(1/6))
Convex ERM
A Re,8
(Thm. 5.4, 6.1)
R.,5
(c,
SCO
(sln(d) (n(1/8)))/4
A Re, + Va
(Thm. 6.3)
Re,8 , +
Ven
1/3
Convex ERM
In(d)
AR=
(Thm. 6.1, G.4)
R₂
e-DP
SCO
Iníd)
1/3
A RR
(Thm. 6.3)
R. + v
1
(e, (PDP)
Emp. Grad. Norm
In(d///) In (1/8)///8 (sm)174
(Re,a) (Thm. 5.4)
(R.,a) 2/3
Table 2: Rates for DP optimization with sparse gradients, compared to best-existing upper bounds in the non-sparse case. In the above, the bounds stated for constant success probability, the function parameters and polylog(n) factors omitted, Rg /dlm(1/8)\(en) R. dd(en), and our improvements are highlighted.
1.1
Our Results
We initiate the study of DP optimization under gradient sparsity. More precisely, we consider stochastic optimization (SO) problem, min (x) E X), where X' C Rd is a convex set, and Fo(x) En 2)], with f(,,2 enjoying some regularity properties, and D probability measure supported on a set Z. Our main assumption is gradient sparsity: for an integer 0 s s S d,
Vx E X, E 2
[V =)1lo S 8,
where l/y/lo denotes the number of nonzero entries of y. We also study empirical risk minimization (ERM), where given dataset $ (#1: 2n) aim to minimize Fs(x)) = Eiets) fax,, 24).
Our results unearth three regimes of accuracy rates for the above setting: (i) the small dataset size regime where the optimal rate is constant, (ii) the large dataset size where the optimal rates are polynomial in the dimension, and (iii) an intermediate dataset size regime characterized by new high-dimensional rate' (see Table and Table 2, for precise rates). These results imply in particular that even for high-dimensiooal models, this problem is tractable under gradient sparsity. Without sparsity, these polylogarithmic rates impossible due to known lower bounds [8].
In Section 3, we start with the fundamental task of fz-mean estimation with sparse data (which reduces to ERM with sparse linear losses [8]). Here, we obtain new upper bounds (see Table 1). These rates are obtained by adapting the projection mechanism [9], with convex relaxation that makes our algorithms efficient. Note that for pure-DP, even our large dataset rate of / Vsd/(sn) can be substantially smaller than the dense pure-DP rate of d/ (e(n) [8], whenever & d. For approximate- DP also obtain sharper upper bound by solving an é eerrgression problem of noisy projection of the empirical mean over a random subspace. Its analysis combines ideas from compressed sensing [10] with sparse approximation via the Approximate Carathéodory Theorem [11].
In Section we prove lower bounds that show the netr-optimality of our algorithms. For pure-DP, we obtain new lower bound of l(s log (d/ (ne)), which is based on packing of sparse vectors.
'We will generally refer to high gegh-dmensional or nearly dimension -ndereenddeeettttt rates indistinguishably. meaning more precisely that the rates scale polylogarithmicaly with the dimension.

---

While this lower bound looks weaker than the standard ((d/(ne)) lower bound based on dense packings [12. 8]. we design a novel bootstrapping via a block diagonal construction where each block contains a sparse lower bound as above. This, together with a padding argument [8], yields lower bounds for the three regimes of interest. For approximate-DFi we also use the block diagonal bootstrapping, where this time the blocks use classical fingerprinting codes in dimension s [8, 13]. Our approximate-DP lower bounds, however, have a gap of in(d/))// in the high-dimensional regime; we conjecture that the aforementioned compressed sensing- based upper bound is tight.
In Section 5, we study DP-ERM with sparse gradients, under approximate-DD We propose the use of stochastic gradient (SGD) with mean estimation gradient oracle based on the results in Section 3. This technique yields nearly-tight bounds in the convex case (similar to first row of Table 2), and for the nonconvex case the stationarity rates nearly dimension independent (last row of Table 2). The main challenge here is the bias in mean estimation, which dramatically deteriorates the rates of SGD. Hence we propose bias reduction method inspired by the simulation literature [14]. This technique uses a random batch size in an exponentially increasing schedule and a telescopic estimator of the gradient which- used in conjunction with our DP mean estimation methods provides a stochastic first-order oracle that attains bias similar to the one of a full-batch algorithm, with moderately bounded variance. Note that using the full-batch in this case would lead to polynomially weaker rates; in turn, our method leverages the batch randomization to conduct more careful privacy accounting based on subsampling and the fully-adaptive properties of DP [15]. The introduction of random batch sizes and the random evolution of the privacy budget leads to various challenges in analyzing the performance of SGD. First, we analyze a randomly stopped method, where the stopping time dictated by the privacy budget. Noting that the standard SGD analysis bounds the cumulative regret, which is a submartingale, we carry out this analysis by integrating ideas from submartingales and stopping times [16]. Second, this analysis only yields the desired rates with constant probability. Towards high probability results, we leverage a private model selection [17] based on multiple runs of randomly-stopped SGD that exponentially boosts the success probability (details in Appendix F).
In Section 6, we study further DP-SO and DP-ERM algorithms for the convex case. Our algorithms are based on regularized output perturbation with an fxo projection post-processing step. While this projection step is rather unusual, its role clear from the analysis: leverages the for bounds of noise addition, which in conjunction with convexity provides an error guarantee that also leverages the gradient sparsity. This algorithm is nearly-optimal for approximate-DP. For pure-DP, the previous algorithm requires an additional smoothness assumption, hence we propose second algorithm based on the exponential mechanism [18] run over a net of suitably sparse vectors. Neither of the pure-DP algorithms matches the lower bound for mean estimation (the gap in the exponent of the rate is of 1/6), but they attain the first nearly dimension -nnnsiionn-deeeddeent rates for this problem.
1.2 Related Work
DP optimization is extensively studied topic for over decade (see [8, 19, 20], and the references therein). In this field, some works have highlighted the role of model sparsity (c.g., using sparsity- promoting ball constraints) in near-dimension independent excess-risk rates for DP optimization, both for ERM and SCO [21, 22, 23, 24, 25, 26, 27]. These settings are unrelated to ours, as sparse predictors are typically related to dense gradients.
Another proposed assumption to mitigate the impact of dimension in DP learning that gradients lie (approximately) in low dimensional subspace [28, 29, 30, 31] or where dimension is substituted by a bound on the trace of the Hessian of the loss [32]. These useful results are unfortunately not applicable to our setting of interest, we are interested in arbitrary gradient sparsity patterns for different datapoints.
Substantially less studied is the role of gradient sparsity. Closely related to our work, [6] studied approximate DP-ERM under gradient sparsity, with some stronger assumptions. Aside from an additional foo bound on individual gradients, the following partitioning sparsity assumption is imposed. The dataset can be uniformly partitioned into subsets St...., S.mm with a uniform gradient sparsity bound: for all & E [m]] and x E X, ||Ess, Vf(r, 2) < c1. The work shows polylogarithmic the dimension rates, for both convex and nonconvex settings. Our results only assume individual gradient sparsity, so top of being more general, they are also faster and provably nearly optimal in the convex case. Another relevant work is [7], which studies the computational and utility benefits for DP with sparse gradients in neural networks with embedding tables. With the
3

---

caveat that variable selection on stochastic gradients is performed at the level of contributing buckets (i.e., rows of the embedding table), rather than on gradient coordinates, this work shows substantial improvements on computational efficiency and also on the resulting utility.
In [33], bias reduction is used to mitigate the regularization bias in SCO. While they also borrow inspiration from [14], both their techniques and scope are unrelated to ours.
1.3 Future Directions
We present some of the main open questions and future directions of this work. First, we con- jecture that for approximate-Di mean iioimaaion-smmlllle to the pure-DP case-a lower bound O(V/log(d/s (n(1/))/[me]) should exist; such construction could be bootstrapped with a block- diagonal dataset for tight lower bound (Lemmaa 4.3). Second, for pure DP-SCO, we believe an algorithm should exist that achieves rates analogous to those for mean estimation. Unfortunately, most of variants of output perturbation (including phasing [20, 24, 34)) cannot attain such rates. From a practical perspective, the main open question is whether our rates are attainable without prior knowledge of 8; note that all our mean estimation algorithms (which carries over our optimization results) depend crucially on knowledge of this parameter. While we can treat 8 as a hyperparameter, it would be highly beneficial to design algorithms that automatically adapt to it.
We believe our bias reduction is of broader interest. For example, [35, 36] have shown strong negative results about bias in DP mean estimation. While similar lower bounds may hold for sparse estimation, bias reduction allows us to amortize this error within an iterative method, preventing error accumulation.
Finally, there is no evidence of our nonconvex rate being optimal. In this vein, we should remark that even in the dense case the optimal stationarity rates are still open [37].
2 Notation and Preliminaries
In this work. || 1- || = || 2l2 the standard Euclidean norm on R.d. We will also make use of fp-norms, where ||^||p
(Ejeja) (2,)²)) 1/p for 1 p co. For p 0, we the notation ||ж||o = [[j e [d] æy # 03}. i.e., the size of the support of We denote the r-radius ball centered at of the p-norm in TRd' by (x, r) == fy Rd |ly - zlIp S r}. Given E [d] and L > 0, the set of s-sparse vectors is (the scaling factor L is omitted in the notation for brevity)
S = fo E Rd
||0||e S s, || < L}.
(1)
Note that Jensen's 's inequality implies: if || llo S and 1 p <<poo q S oc, then ||=||, S 5//001/99111
Remark 2.1. The upper bound results in this paper hold even if we replace the set St of sparse vectors by the strictly larger fi-ball B (0, Lvs). Note that while upper bounds extend to the l assumption above, our lower bounds work under the original sparsity assumption.
Let f: X' x Z + R be a loss function. The function evaluation f(x, represents the loss incurred by hypothesis x E X on datapoint: 2 E Z. In stochastic optimization (SO), we consider a data distribution D, and our goal is to minimize the expected loss under this distribution
min {Po(s) := Ez-D// =)]}
(SO)
Throughout, x= (D) to denote an optimal solution to (SO), which assume exists. In the empirical risk minimization (ERM) problem. we consider sample datapoints = (21,..., kn) and our goal is to minimize the empirical error with respect the sample
minzex FF(()) := 1/ Eigi f(x, }
(ERM)
We denote by x= (S) an arbitrary optimal solution to (ERM), which assume exists. Even when S is drawn i.i.d. from D, solutions (or optimal values) of (SO) and (ERM) do not necessarily coincide.
We present the definition of differential privacy (DP), deferring useful properties and examples to Appendix A. Let 2 be a sample space, and X an output space. A dataset is a tuple S 2", and datasets S, S e 2 are neighbors (denoted as S ~ S') if they differ in only one of their entries.

---

Definition 2.2 (Differential Privacy). Let A: Z" + X. We say that A is (c. (approxixi)))) differentially private (DP) if for every pair S S', we have for all & _ X that Pr[A(S)
El S 6 .Pr(A(S") E E + 8. When á = 0, we say that A is e-DP or pure-DP.
3 Upper Bounds for DP Mean Estimation with Sparse Data
We first study DP mean estimation with sparse data. Our first result is that the projection mechanism [9] is nearly optimal, both for pure- and approximate-DP. In our case, we interpret the marginals on each of the dimensions as the queries of interest: this way, the f2-error on private query answers corresponds exactly to the f2-norm estimation error. A key difference to the approach in [9] and related works that we project the noisy answers onto the set K := B (0, Lvss, which is a (coarse) convex relaxation of conv(S)). This is crucial make our algorithm efficiently implementable. Due to space limitations, proofs from this section have been deferred to Appendix B.
Algorithm Projection Bactoo__eehahiiiiieeeeeeeaa E(
Require: Vector Z(S) = :/2 Ex=1 24 from dataset S (8:));; E, 2 0, privacy parameters
Lap(o) with o = ( (2اا3 ===(S)+ +,, with &
if 8 = 0,
ns
o((0,21) with 0² SL (5/12)//)) if 0. (ne)²
return 2 = argmin {||z - E112:2 E KJ, where K. == B (0, LV3)
Lemma 3.1. In Algorithm 1, it holds that || 2(5)112 S 22 l almost surely.
We now provide the privacy and accuracy guarantees of Algorithm Theorem 3.2. For ō 0, Algorithm / is c-DP, and with probability 1 1-8
2 - 2((() & L min Ind/n(d/3)
sln(d/8) ne
Theorem 3.3. For 5 > 0, Algorithm / is (c, O)-11,, and with probability 1 B::
_ = $ L- min (1tt/10(1//))) mm(188)
(4log(1/d) 1 log(d//))
Vnn
Sharper Upper Bound via Compressed Sensing In Appendix B.4 we propose faster mean estimation approximate-DP algorithm. Its rate nearly matches the lower bound we will prove in Theorem 4.4. We believe that this rate is essentially optimal. This algorithm projects the data average into a low dimensional subspace (via a random projection matrix), and uses compressed sensing to recover noisy version of this projection: this way, noise provides privacy, which is further boosted by the random projection, and the accuracy follows from an application the stable and noisy recovery properties of compressed sensing [10], together with the Approximate Carathéodory Theorem.
4 Lower Bounds for DP Mean Estimation with Sparse Data
We provide matching lower bounds to those from Section Moreover, although the stated lower bounds are for mean estimation, known reductions imply analogous lower bounds for DP-ERM and DP-SCO [8, 19]. First, for pure-DP DD we provide a packing-type construction based on sparse vectors. This is used in novel block-diagonal construction, which provides the right low/high- dimensional transition. On the other hand, for approximate-DDR a block diagonal reduction with existing fingerprinting codes [38, 13], suffices to obtain lower bounds that exhibit nearly tight low/high-dimensionall transition. For simplicity, we consider the case of L, = 1, i.e., St = {a E Rd || I ||=1||2 I 1); it is easy to see that any lower bound scales linearly in L. We defer proofs from this section to Appendix C.
4.1 Lower Bounds for Pure-DP
Our main lower bound for pure-DP mechanisms is as follows.
5

---

Theorem 4.1. Let > 0 and < <d/2. Then the empirical mean estimation problem over S
satisfies
inf A:c-DP SE(S))"
sup
[|A(S)- 2(S)]l 2 min {1,
lonld/(en])
vsd
2
The statement above-as as well as those which follow-shoule be read as "for all DP algorithms A, there exists dataset S, such that the mean estimation error is lower bounded by a(n, d, e, 2, with and Z 1).
probability at least ((n, d, e, 8)" (where in this case a Z min {I, logid/len)
en
We also introduce a strengthening of the worst case lower bound, based on hard distributions.
Definition 4.2. We say that probability y over 2" induces an (a,, (o, -iddtttiibatii lower bound for (s, 6DD mean estimation if inf A: (e,6).DP De
Pss... [IlAs)) 2(S)]l2 2 2 3.
Note this type of lower bound readily implies worst case lower bound. On the other hand, while the existence of hard distributions follows by the existence of hard datasets (by Yao's minimax principle), provide explicit constructions of these distributions, for the sake of clarity.
Theorem 4.1 follows by combining the two results that we provide next. First, and our main technical innovation in the sparse case is block-diagonal dataset bootstrapping construction, which turns low-dimensional lower bound into high-dimensional one.
Lemma 4.3 (Block- Milock-Diagonal Lower Bound Bootstrapping). Let ng, E N. Let μ be distribution over (5 that induces (0o, Po) -iidstribbuii lower bound for (e, ()-D)- mean estimation. Then, for any d t, no and K S min { " 4 there exists it over (5%)" " that induces an (a, distribbuiiil lower bound for 0D, mean estimation, where a 2 Oattn V and
p 1
Note that the above result needs base lower bound for which packing-based constructions suffice. Theorem 4.4. Let & > and d/2. Then there exists an (a,, (o,,p)-distriie disttribbbutl lower bound for e-DP mean estimation over (5 with a 2 min {1, llg(d/s) ) and p 1/2.
en
4.2 Lower Bounds for Approximate-DP
While the lower bound for the approximate-DP case is similarly based on the block-diagonal reduction, its base lower bound follows more directly from the dense case.
Theorem 4.5. Let e E (0, 1]. 20((n) < - Then the empirical mean estimation problem over St satisfies
inf A: (e, SE(S!)
sup
[A((S) - E(S))l 2 min (1,
[sl((1/)) Vne
/dln(1/8)
11
Bias Reduction Method for DP-ERM with Sparse Gradients
We now start with study of DP-ERM with sparse gradients. We defer some proofs to Appendix E. In this section and later, we will impose subsets of the following assumptions:
(A.1) Initial distance: For SCO, ||.0 x² (D) < D; for ERM, |2 - xx xx()) D.
(A.2) Diameter bound: ||æ - y|l & D, for all x, X.
(A.3) Convexity: f(,,2) is convex, for all E Z.
(A.4) Loss range: [x, =) f(y, =) < B, for all x, y E X, E Z.
(A.5) Lipschitzness: f(- 2) is L-Lipschitz, for all 2 E Z.
(A.6) Smoothness: V-(,,) 2) is H H-Lipschitz, for all E Z.
(A.7) Individual gradient sparsity: V fz 2) is s-sparse, for all x X' and E 2.
The most natural and popular DP optimization algorithms are based on SGD. Here we show how to integrate mean estimation algorithms from Section design stochastic first-order oracle that can be readily used by any stochastic first-order method. The key challenge here is that estimators from Section are inherently biased, which is known to dramatically deteriorate the convergence rates. Hence, we start by introducing bias reduction method.

---

Algorithm 2 Subsampled Subsamplee_BBis-Reeuuiee Bias--aeduced Caaaa-Beddcedd_rrdiientt,, Grradient_Esttimatorrt.. S, e,
Require:
Dataset S (2,,..,, En) E 2", E, > privacy parameters, L-Lipschitz loss f(x, 2)
with s-sparse gradient, X, batch size parameter N ~ TGeom (M) with M = [loge (n)
Let B ~ Unif (2 O, E partition of B with [0] = 2%, T ~ Unif([n))
G (z, B)
(Algorithm
G (z, E) = Vtapccccio..cccaaaime///ooooee..
(z 0) =
Ga I) Projectioon_Mechanssml (/gaaaaaa_mmm1ggg((())/04444222
Return (below pk = P[TGeom k))
(xx)
1.
( (I, B) 2 () (z,, + Go(z, 1)
Algorithm 3 SaaiaddiBBiaseeduueeessperreee S,,E,,
Require: Initialization xº E X:; Dataset S = ...,.... 2n) E 2"; E, o, privacy parameters; stepsize 0; gradient oracle for L-Lipschitz and with s-sparse gradient loss f(.,2)
while V 2 (1) E.=
(32 16n
1)) 16n
I
and Σ
322 <
16n
do
t -+=2 +1
N₂ ~ TGeo (M) where
[nog
(xx') Subsampled
Estimator 2. (Alg. 2)
x++1_ = 1xx [x' (/(x()))
end while
I = +1
1 Σ E x"
if f(,22) is convex,
return
x² where i ~ Unif((......)))) TY)
if, is not convex.
5.1 Subsampled Bias-Reduced Gradient Estimator for DP-ERM
We propose Algorithm 2, inspired by a debiasing technique proposed in [14]. The idea is the following: know that the projection mechanism' would provide more accurate gradient estimators with larger sample sizes, and we will see that its bias improves analogously. We choose our batch size random variable with exponentially increasing range, and given such realization subtract the projection mechanism applied to the whole batch minus the same mechanism applied to both halves of this batch. This subtraction, together with multiplicative and additive correction, results in the expected value the outcome ((x) corresponding to the estimator with the largest batch size, leading its expected accuracy being boosted by such large sample size, without necessarily utilizing such amount of data (in fact, the probability of such batch size being picked is polynomially smaller, compared the smallest possible one). The caveat with this technique, as we will see, relates heavy-tailed distribution of outcomes, and therefore great care is needed for its analysis.
Instrumental to analysis is the following truncated geometric distribution with parameter M N, whose law will be denoted by GGemm MM: we say N ~ TGeom (M) it is supported on (O...., .....,,, M). and takes value & with probability ph == CM /2*, where Cs = (2(1 2 22M(+)+))))) -1 the normalizing constant. Note that 1/2 < CM S thus is bounded away from and +00.
We propose Algorithm which interacts with the oracle given Algorithm 2. For convenience, we will denote the random realization from the truncated geometric distribution used in iteration / by N,, The idea that, using the fully adaptive composition property of DP [15), we can run the method until our privacy budget is exhausted. Due to technical reasons, related to the bias reduction, we need
Note that we use the projection mechanism (Algorithm 1) as subroutine for Algorithm 2 only to have self-contained presentation in the main body of the paper. We will analyze and state the sharper bounds obtained with Algorithm
subroutine. 'We follow the Blanchet- Blanchet-Glynn notation of O and E to denote the "odd" and 'even" terms for the batch partition [14]: this partitioning arbitrary.
7

---

to shift by one the termination condition in the algorithm. In particular, our algorithm goes over the reduced privacy budget of (e/2. 8/2). The additional slack in the privacy budget guarantees that even with the extra oracle call the algorithm respects the privacy constraint. Lemma 5.1. Algorithm 3 is (e. DD..
5.2 Bias and Moment Estimates for the Debiased Gradient Estimator
We provide bias and second moment estimates for debiased estimator of the empirical gradient. In summary, we show that this estimator has bias matching that the full-batch gradient estimator, while at the same time its second moment is bounded by mild function of the problem parameters.
Lemma 5.2. Let d ney neyshiid/s hidd/s)
Algorithm 2, enjoys bias and second moment bounds
v /m(1//)
[[g(a)- FFs())
[[g(<)
x
V Lis I[sdn(d/s) In(1//))) =: b,
{[ / = =2.2.
Proof. For simplicity, we assume without loss of generality that n is power of 2, that 2
Bias. Let, for = O....,,,,,. G (x) = E (2. B) N = k. x²) and
G (x) ElG E) N k, =
E (z. O) N k,r),
where the last equality follows from identical distribution of and E. Noting further that G (z:) G (z) (which follows from the uniform sampling and the cardinality of the used data- points), and using the law of total probability, we have
B(g(x) æ]
En= (Gt (x) -0-----1100 (x) + EIGo(x, I) a]
G (x) - Go (2) + B[Go !) x]
E[G - (x))) + VFs(a),
where we also used that E[Go( I) x] GD (I) (since / is singleton). Next, by Theorem B.1
[E(((z) x] VFs(=))
[E[ (z) V F=s(+))=|1 & L (sldd//)) (116))114
Vne
Second moment bound. Using the law of total probability, and that O, E partition of B: [[1(())) [x]
M Σ
P&
-))
Pk
(1, 0) (Fo(z) + G (z. - [x(()) + Go(æ, 1) /|² x. N = k]
2pk
1 E G -B8))-Fn(1r)) - sr, =
< 2E[||Go(z, 1)1 xx] +
Pk
k==
E
() -Fo(F)
+ -
2, =x]
We now use Theorem B.I. conclude that
E G VFB(T) |
I [z,N=k]
=k] -k
1.2 (/
2hT
E B
A) VF ||?
x, N k
In(1/)))
maxxc(O,m)
24e
E [oo 1)|l
x S
1.2
/sln(d/s)) In(1/8)
Recalling that M + 1 log, and pı 2- these bounds readily imply that [1| S2²
0

---

5.3 Accuracy Guarantees for Subsampled Bias-Reduced Sparse SGD
The previous results provide useful information about the privacy, bias, and proposed oracle. Our goal now is to provide excess risk rates for DP-ERM. For this, we need to prove the algorithm runs for long enough, i.e., lower bound on the stopping time of Algorithm 3,
of our
T = inf {t: (
22
3-2 3-2
1/2
3.2Na+++1
(3.2Net1
16n
16n
==0
==0
(2)
The proof of Theorem 5.2 implies that moments of 9 increase exponentially in M. This heavy-tailed behavior implies that T may not concentrate strongly enough obtain high probability lower bounds for T. What we will do instead is showing that with constant probability T behaves as desired.
To justify the approach, let us provide a simple in-expectation bound on how the privacy budget accumulates in the definition of T: letting & (3 2N++1 + 1)e/[16n]] we have that
E c
(++1)=2 (16m)=
S (3 2 +1 1)2
1)= (16n)"
9 ( + 11)
- ts n
where in the last step we used that E [[23(N++1)
Cm E 2 S This in-expectation analysis can be used combination with ideas from stopping times to establish bounds for T'.
Lemma 5.3. Let 8 1/n2² _ Let T be the stopping time defined in eqn. (2). Then, there exists t = Cn/ 1og(2/8) (with C >> 0 an absolute constant) such that IPT < t] S 1/4. On the other hand,
E[T]
64n (lm(4/8)
ln(4/8)
With our bounds on T. further analysis involving regret bounds on randomly stopped SGD yields the following bounds for convex and nonconvex losses. See Theorem E.2 and Theorem E.3 for details.
Theorem 5.4. Consider (SO) problem under initial distance (Item (A.1)). Lipschitzness (Item (A.5)) and gradient sparsity (Item (A.7)) assumptions.
In the convex case (Item (A.3)), Algorithm 3 satisfies
P(Fs(0) Fs(x*(S)) & LD ind/ss In In (1/5))2/4
1
Ven
2
In the nonconvex case, additionally assuming smoothness (Item (A.6)) and the following initial suboptimality assumption: namely, that given our initialization d. Rd, there exists 1 >> 0 such that (=(x²)= Fs(x* S T; Algorithm 3 satisfies
is (sln(d/s) (n(1/))))(
P P (TH
1.2)
Ven
Boosting the Confidence of the Bias-Reduced SGD To conclude, in Appendix F we provide boosting algorithm that can exponentially amplify the success probability of Algorithm The approach is based on making parallel runs of the method and using private model selection to obtain the best performing model.
6 DP Convex Optimization with Sparse Gradients via Regularized Output Perturbation
We conclude our work introducing another class of algorithms that attains nearly optimal rates for approximate-DP ERM and SO in the convex setting. These algorithms are based on solving regularized ERM problem and privatizing its output by an output perturbation method. The main innovation of this technique is that we reduce the noise error by a projjcctio.... This type of projection leverages the concentration of the noise high-dimensions. We carry out an analysis that also leverages the convexity of the risk and the gradient sparsity to obtain these rates. The full deseription included in Algorithm 4. We defer missing proofs from this section, as well as additional results, to Appendix G.

---

Algorithm 4 Output_Perturbatiio
Require:
Dataset S (219...;22)) E 2", E, 0 privacy params,, f(., L-Lipschitz convex
function (if 5 = 0 further assume H-smooth) with s-sparse gradient, X 2 0 regularization param.
Let x (S) = argmin ZE (1)x), where (a)) = [Fs(z) + 2 [
3 (5) + &. with ş ~ Lap(r) with 2//2/ 2H
Den ( + +1) if 0,
02( with o² SL. lm(1.25/6)
i > 0.
[Aen]²
return è argmin texl1æ ølloo (breaking ties arbitrarily)
Theorem 6.1. Consider an ERM problem under assumptions: initial distance (Item (A.1)), convexity (Item (A.3)), Lipchitzness (Item (A.5)) and gradient sparsity (Item (A.7)). Then, Algorithm 4 is (E, (D. and it satisfies the following excess risk guarantees, any 0 < 3 <
ff 0, and under the additional assumption of smoothness (A.6) and unconstrained domain,
X = Rd, then selecting X == -12 slogld/H)
L2HH
1/3
it holds with probability 1 - 3 that
Fs(Ø) - Ps(x*(8) S 2 / ( #log(d/8) 1/3
Ifō then selecting X - 1- [=log(1/8) logld/3) we have with probability that ven
Fs(0) Fs(x & LD (slog(1/8) log(d/p))/44
v/n
Remark 6.2. For approximate-DP the theorem above can also be proved if we replace assumption (Item (A.1)) by the diameter assumption (Item (A.2)). On the other hand, for the pure-DP case natural question whether the smoothness assumption is essential. In Appendix G.3, we provide version of the exponential mechanism that works without the smoothness and unconstrained domain assumplions. This algorithm is inefficient and it does require structural assumption the feasible set, but illustrates the possibilities of more general results the pure-DP setting.
We note that the proposed output perturbation approach (Algorithm 4) leads to nearly optimal population risk bounds for approximate- DP, by different tuning of the regularization parameter X.
Theorem 6.3. Consider a problem (SO) under bounded initial distance (Item (A. (or bounded diameter, Item (A.2), if >> 0), convexity (Item (A.3)), Lipschitzness (Item (A.5)), bounded range (Item (A.4)), and gradient sparsity (Item (A.7)). Then, Algorithm 4 is (c, D)-P, and for 0 < 3
If 0, and under the additional assumption of smoothness (A.6) and unconstrained domain, 1/3
X' Rd. Selecting X = L2H
llggd//)) D
then with probability 1
Fs(2) - Fs(x (D)) & 1/ D4/3
elog(d/0)
1/3
BB
In(1/B)
1 Selecting 1/ In(1/))(
1/2
Iten with probability 1
FD(ě) Fo(x= (D)) & LD (elell(11)) 1o
(LDVinn+ BBV ln(1/2)
Ven
Acknowledgments and Disclosure of Funding
C.G.'s research was partially supported by INRIA Associate Teams project, ANID FONDECYT 1210362 grant, ANID Anillo ACT210005 grant, and National Center for Artificial Intelligence CENIA FB210017, Basal ANID.
10

---

References
[1] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput, Sci., 9(3-4)2211440 2014.
[2] Alec Gunny, Chirayu Garg, Levs Dolgovs, and Akshay Subramaniam. Accelerating wide deep recommender inference on GPUs, 2019. accelerating- witpa/--wwwwddddeee-eeeeeeeeeeee wwweenndrrriiffeeneeeeee on-uuss............
wttp:eelllee...iiiiaaaaee..eeeaa nvidia. wwwidi..oo/bbiiiaae.. www.ccomolllo.
[3] Zehuan Wang, Yingean Wei, Minseok Lee, Matthias Langer, Fan Yu, Jie Liu, Shijie Liu, Daniel G Abel, Xu Guo, Jianbing Dong, et al. Merlin hugeCTR: GPU-accelerated recommender system training and inference. In RecSys, 2022.
[4] Gagik Amirkhanyan and Bruce Fontaine. Building large scale recommenders using cloud TPUs, 2022. https://clood google http//loogoooppp http://tooppss/eeeeeeeerrsss /wt/vvdeeeeeessseeeeeeeeeeeeeeee paaperrssppacttiioees.... building-
www.rmmmmeeddednunnnneee cloud- tpus.
[5] Norm Jouppi, George Kurian, Sheng Li, Peter Ma, Rahul Nagarajan, Lifeng Nai, Nishant Patil, Suvinay Subramanian, Andy Swing, Brian Towles, al. TPU v4: an optically reconfigurable supercomputer for machine learning with hardware support for embeddings. In ISCA, 2023.
[6] Huanyu Zhang, Ilya Mironov, and Meisam Hejazinia. Wide network learning with differential privacy. CoRR, abs/2103.01294, 2021.
[7] Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang, Sparsity-preserving differentially private training of large embedding models. In NeurIPS, 2023.
[8] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In FOCS, pages 464-473, 2014.
[9] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In STOC, pages 351-360, 2013.
[10] Przemyslaw Wojtaszczyk. Stability and instance optimality for Gaussian measurements in compressed sensing. Foundations of Computational Mathematics, 10:1-13, 2010.
[11] G Pisier. Remarques sur un résultat non publié de b. maurey. Séminaire Analyse fonctionnelle (dit), pages 1-12, 1981.
[12] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, pages 705-714, 2010.
[13] Thomas Steinke and Jonathan R. Ullman. Between pure and approximate differential privacy. Priv. Confidentiality, 7(2), 2016.
[14] Jose H. Blanchet and Peter W. Glynn. Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In WSC, pages 3656-3667. 2015.
[15] Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Steven Wu. Fully-adaptive composition in differential privacy. In ICML, pages 36990-37007, 2023.
[16] Jeffrey S Rosenthal. A First Look at Rigorous Probability Theory. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, second edition, 2006.
[17] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In STOC, pages 298-309, 2019.
[18] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. FOCS, pages 94-103, 2007.
[19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In NeurIPS, 2019.
[20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In STOC, pages 439-449, 2020.

---

[21] Prateck Jain and Abhradeep Guha Thakurta. (Near) dimension independent risk bounds for differentially private learning. In ICML, pages 476-484, 2014.
[22] Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry. CoRR, abs/1411.544 2014.
[23] Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly-optimal private LASSO. In NIPS, pages 3025-3033, 2015.
[24] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: Optimal rates in LI geometry. In ICML, pages 393-403, 2021.
[25] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non- Euclidean differentially private stochastic convex optimization. In COLT, pages 474-499, 2021.
[26] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. Ann. Stat., 49(5):2825 28850, 2021.
[27] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy in generalized linear models: Algorithms and minimax lower bounds. CoRR, abs/201 1.03900, 2020.
[28] Yingxue Zhou, Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private SGD with gradient subspace identification. In ICLR, 2021.
[29] Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (Nearly) Dimension Independent Private ERM with AdaGrad Rates via Publicly Estimated Subspaces. In COLT, pages 2717-2746, 2021.
[30] Xuechen Li, Daogao Liu, Tatsunori Hashimoto, Huseyin Inan, Janardhan (Jana) Kulkarni, Yin Tat Lee, and Abhradeep Guha Thakurta. When does differentially private learning not suffer high dimensions? In NeurlPS, November 2022.
[31] Yin Tat Lee, Daogao Liu, and Zhou Lu, The power of sampling: Dimension-free risk bounds in private ERM. CoRR, abs/2105. 2024.
[32] Yi-An Ma, Teodor Vanislavov Marinov, and Tong Zhang. Dimension independent generalization of DP-SGD for overparameterized smooth convex optimization. CoRR, abs/2206.01 006826 2022.
[33] Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Stochastic bias-reduced gradient methods. In NeurlPS, 2021.
[34] Hilal Asi, Daniel Lévy, and John C Duchi. Adapting to function difficulty and growth conditions in private optimization. In NeurIPS, pages 19069-19081, 2021.
[35] Gautam Kamath, Argyris Mouzakis, Matthew Regehr. Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. Shas-variance-privi trilemma for statistical estimation, 2023.
[36] Aleksandar Nikolov and Haohua Tang. Gaussian noise is nearly instance optimal for private unbiased mean estimation. CoRR, abs/2301.138500 2023.
[37] Raman Arora, Raef Bassily, Tomás González, Cristóbal A Guzmán, Michael Menart, and Enayat Ullah. Faster rates of convergence to stationary points in differentially private optimization. In ICML, pages 1060-1092, 2023.
[38] Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan. Fingerprinting codes and the price of approximate differential privacy. In STOC, pages 1-10, 2014.
[39] Roman Vershynin. On the role of sparsity in compressed sensing and random matrix theory, 2009.
[40] Emmanuel J. Candès and Mark A. Davenport. How well can estimate a sparse vector? Applied and Computational Harmonic Analysis, 34(2):317-323, 2013.
[41] E.J. Candes and T. Tao. Decoding by linear programming. TOIT,
2005.
12

---

[42] Mark Bun, Thomas Steinke, and Jonathan R. Ullman. Make up your mind: The price of online queries in differential privacy. In SODA, pages 1306-1325, 2017.
[43] Gautam Kamath and Jonathan R. Ullman. A primer on private statistics. CoRR, ab/22005.00010, 2020.
[44] Olivier Bousquet and André Elisseeff. Stability and generalization. JMLR, 2:499-526 2002.
[45] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, 2009.
[46] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. JMLR, 12:1069-1109 2011.
[47] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In COLT, pages 610-626, 2020.
13

---

Appendix
A Auxiliary Privacy Results
The privacy and accuracy of some of the perturbation based methods we use to privatize our algorithms are based on the following simple facts (see, e.g., (I]..
Fact A.1 (Laplace & Gaussian mechanisms). For all 2 + Rd
(a) If the --senniitivtty of g is bounded, i.e., A = sups=s' (lg(S) - 9(5"))1 < +00, then
(S) == g(S) + where & ~ Lap Sd [ /c) ) is E-P..
(b) If the ez-sensitivity of is bounded, i.e., A == sups2s' - 9(S)) < +00, then (S) g(S) + E, where & (0, for A 1og(1.26/6) (),
Fact A.2 (Laplace & Gaussian concentration). Let > and < <1.
(a) For ~ La: (i) +x E a log(d/3) holds with probability 1 B, and (ii) ||E||a 2 ovdlog(d/ B) holds with probability B-
(b) For & o(0,021) (i) I & ooolog(d] ///o(d//)) B) holds with probability 1 - B, (ii) lk S
a aVdd+ Vlog(1/)) holds with probability 1 - 9, and (iii) R.|El1 = do².
We note the existence of packing sets of sparse vectors (e.g., [39, 40]). Denote by C the set of all 8-sparse vectors in 10.1/V8)d note that C. C SS
Lemma A.3. For all and d such that S d/2. there exists subset P S Cg such that [P] 2
(d/s - 1/2)a/2 and for all u, P, it holds that ||u - 2/|2 1/v2.
Proof. This follows from a simple packing- basdd construction (see, e.g., [40]). There are (:) vectors
in Cd. and for each vector u Ct.. there most (13/2)) many vectors u E Cd. such that |lu-ollo s
8/2 and hence ||u v112 I 1/v2. Thus, greedily pick vectors to be C, guaranteeing that all d
vectors u, Cd satisfy ||u vilo > 8/2, and have |C| Z (1/2)))) ( -))
For completeness, we provide a classical dataset bootstrapping argument used for DP mean estimation lower bounds [8]. Whereas in the original reference this bootstrapping is achieved by appending dummy vectors which mutually cancel out with the goal of maintaining the structure of vectors, we simply append zero vectors as dummies as we do not need to satisfy exact sparsity pattern.
Lemma A.4 (Dataset bootstrapping argument from [8]). Suppose for some n. there exists a mecha- nism A such that for all S (S")", it holds with probability at least 1/2 that [[A(()) -((S)] < C. for some C 2 O. Then for all n² < n, there exists a mechanism A' such that for all S' E (St)"" holds with probability at least 1/2 that [|A((") =(S')ll2 t. Furthermore, A' satisfies the same privacy guarantees as A. namely A is s-DP (or (e, 0DD)), then is A'
Proof. Given mechanism A, consider mechanism A' that for any dataset S" E (Sd)"", builds dataset by adding n copies of 0 to S' and returns A A(S). From the guarantees of A, it holds that (IIA(S) 2(S) < C] 2 3.2 Since A'(S') = - A(S) and E(S") = = ESS) , follows that
P [[IA'(S))) - (()))l2 < C n" 2
Since A' just applies A once, it follows that A' satisfies the same privacy guarantee as A.
Next we provide a generic reduction of existence of packing sets with pure-DP mean estimation lower bounds. Note however that the lower bounds state work on the distributional sense.
14

---

Lemma A.5 (Packin-bbsee mean estimation lower bound, adapted from [12, 8)). Let S R be an ag pacpaickng set of vectors with [P] = p. Then, there exists a distribution şt over pm that induces an (ar, distrrbbbbttinn lower bound for e-DP mean estimation with a = on min log(n/2) and en
p 1/2.
Proof. Let log(p/2) First, consider the case where < n". We construct p datasets St.... Sp where S₁ consists of n copies of 2t, and define μ Unif([S).... .Sp....))p)))))).. Note that for all l & L, it holds that [|=(S²) (S))]l 2 2 og. Suppose μ does not induce distributional lower bound. Then there exists A which is e-DP and has f2-accuracy better than 00/2 w.p. at least 1 1/2: this implies in particular that
Ul) [A(S)) E (a)), 2 2
2
For all distinct i L, the datasets Sy and S differ in all n entries, and hence for any E-DP mechanism A. it holds that P[[A(S)) E (2k, 20) 2 2e eeenn However, by construction, (2, 2 are pairwise disjoint. Hence,
P
P
P
Σ
P S (A(S) E B2 0o/2)]
ΣΣ j=1
P. PSu (A())
(2 0z a0/2) 23}
2 P j=
P S (A(S) E (2K,, o0/ 2k
e
pp
2
Thus, we get that n 1og(p/2) which is a contradiction since we assumed n < n.. Hence, μ induces an (ax/2, 1/2, 1.s2)--distiibutionall lower bound for e- e-DP mean estimation. Next, consider the case where > n Then the previous argument together with Lemma A.4 implies an (a, pl-lower bounded, where 2m and p 1/2, desired.
We will make use of the following fully adaptive composition property of DP, which informally states that for a prescribed privacy budget, a composition of (adaptively chosen) mechanisms whose privacy parameters are predictable, if we stop the algorithm before the (predictable) privacy budget is exhausted, the result of the full transcript is DP.
Theorem A.6 ((s, 5)-DP Filter, [15]). Suppose (At)22a is sequence of algorithmss such that, for any 2 0, Ar is (Et, 5c)-Dr conditionally on (Aa=-1) (in particular, (Et, dt) e predittbtl)))lle))
Let E > 0 and 8 8' + 8" be the target privacy parameters such that 8' 0, 8" 2 0. Let
2
se and
6,xx] =
8.r
==0
==0
==0
and define the stopping time
T((E,, 6c))) inf {t: < m inf ft: 8" <0octt). Then, the algorithm (.r(()()) is (c, DD- where T(x) = (((e(()),
B Missing Proofs from Section 3
B.1 Proof of Lemma 3.1
Proof.
From the properties of the Euclidean projection, we have
(2 - -SS() 2 2) < O.
(3)
Hence,
R
- 10)) = (2 (8- 155-210 E(S), 8- + (2-
- ((=())))
< 2 max (u.E)
< 2 max
||u/|1 1|El = 21|| flo Vs.
wek
wek
where we used the fact that (S!) K.
15

---

B.2 Proof of Theorem 3.2
Proof. First, the privacy follows from the & Ej-sensitvvity bound of the empirical mean
A s [[(()) - x( su ||2 2'111 - 2
together with Theorem (a)
For the accuracy, the first term follows from Theorem A.2(a)-(ii), and the fact that Euclidean projection does not increase the ez-estimation error, and the second term follows from Lemma 3.1 with the fact Ly log(d/8)) holds with probability at least 1 - B, by Theorem A.2(a)-(i). O
that || 00
B.3 Proof of Theorem 3.3
Proof. The privacy guarantee follows from the fz-sensitivity bound of the empirical mean, A = 21. together with Theorem Abl(b). For the accuracy, the first term in the minimum follows from Theorem A.2( and the fact that Euclidean projection does not increase the f2-estimation error. The second term follows from Lemma 3.1 and Theorem A.2(
n
B.4 Sharper DP Mean Estimation Upper Bounds via Compressed Sensing
We propose Algorithm 5, a more accurate method for approximate- DP mean estimation based on compressed sensing [10]. The precise improvements relate reducing the log(d) factor log(d/s). and a faster rate dependence on the confidence 8. The idea is that for sufficiently high dimensions, a small number of random measurements suffices estimate noisy and approximately sparse signal. These properties follow from existing results in compressed sensing, which provide guarantees based on the fn-morm of the noise, and the best sparse approximation the f--norm (known as f2-lz-stable and noisy recovery) [10]. We will exploit such robustness in two ways: regarding the noise robustness, this property is used in order perturb our measurements, which will certify the privacy; on the other hand, the approximate recovery property is used to find sparser approximation of our empirical mean. As the approximation is only used for analysis, we can appeal to the Approximate Caratheodory Theorem to certify the existence of sparse vector whose sparsity increases more moderately with than the empirical average [11].
An interesting feature of this algorithm is that f--minimization promotes sparse solutions, and thus we expect our output to be approximately sparse: this is not a feature that we particularly exploit, but it may be relevant for computational and memory considerations. Furthermore, note that the f minimization problem does not require exact optimality for the privacy guarantee, hence approximate solvers can be used without compromising privacy.
Algorithm 5 Gaussian & (.-
Require: E(S) + Eijjn E Rd from dataset S E (Sa,a)"; privacy parameters s, 6 0
#In(d/e) In(1/8)
m ~ nE
=(S) + E, where - o2 and σ² SL. In(1.25/8) (ne))
if < m mn? m,
return 2
8 1 $ 2L), where = arg min [| : Az = b). A (N 1. mxd
b= AE(S) + and & ~ NO, o² (mxx) with 0² 18L In(2.5/8)
otherwise
{ne)²
Theorem B.1. If (xeep(-em) < < slnld/s) (where e > is a constant) and < S then m²
Algorithm 5 is (8,8)-D1 and with probability 1 5/2
2 2(S) & min ( (Va+ (m(1/8) (m(1/8) (n
V ln(1/3) ln(1/8)
(4)
ae
Vne
ne
Moreover, we have the following second moment estimate,
d11n(1/8) (ns)²
/s In lnd/s)) In In(1/8)
E|lla
|| S L min
Ne
16

---

Proof. First, if < mIn m, then Algorithm 5 is (e, 8)-DP by privacy of Gaussian noise addition and the protepsccs property of DP. Moreover, its (high probability and second moment) accuracy guarantees follow from Theorem A.2.
Next, if d 2 m In2 m, we start with the privacy analysis. Let S = S' and suppose they only differ in their ith entry. We note that due our choice of m, A is approximate restricted isometry with probability 3 3cxpf-cmm [41] (where e is the same as in the theorem statement); in particular, we have that for all E I which (*K)
letting K Valn(d/s)m((16))
3
|lull2 | S I1lll2
Hence, due to our assumption on 8, the event above has probability at least 1 - 5/2, and therefore
||A - 22) - |A(2 20112
3L
where we used the fact that 2; 2/z is (2s)-sparse. We conclude by the choice of o² that AE + E is (e, DDDD, and thus 8 (e, 6D by postprocessing.
We now proceed to the accuracy guarantee. By [10, Theorem 3.6 (b)), under the same event as stated above (which has probability 6/2) have
2 2 2|12 S 1kEll2
inf =IllooSSKK
|| 2||2.
For the first term, we use Gaussian norm concentration to guarantee that with probability B,
in ( L Lnln(110)
|k x (Vm vi((1/8) = (VKsln(d/s) (ttl://))<<(KKsiiin
nE
For the second term, by the Approximate Carátheodory Theorem [11], the infimum above is upper bounded by (L)VK)) for this, note that lies in the convex hull of S.. Given our choice of K, we have that, with probability 1 - 8/2 B
[s [sln(d/)) ln(1/8)1444 (in(1/p)(n(110))
2 - 2112 - L
VNE
We conclude by providing the second moment estimate, by a simple tail integration argument. First, by the law of total probability, and letting & be the event of A being an approximate restricted isometry,
B|
21 < B - 2| + 9L28,
where also used that || < 2L and || L, almost surely. Now, conditionally on E, we have that letting L (n |m(16))1/ (below is absolute constant),
Vne
Bl[
P
||
E||2 / (2u)du
a
F|1l2- E|[2 - 2 2(2 T)dr
2
a
ecxp {
c((n)2
/0) } } TTdr
a2
2aL (m((1/6
+ 1 ln(1/))
+
2
(n=)²
S a²
where in the second inequality used the previous high probability upper bound (here >>> 0 is an absolute constant), and in the last step used that ne vIn(1/0). Finally, by assumptions 8, 9 < a², and this concludes the proof.
17

---

C Missing Proofs from Section
C.1 Proof of Lemma 4.3
Proof. Consider an n x data matrix D whose rows correspond to datapoints of a dataset S, and whose columns correspond their d features. We will indistinctively refer S or D as needed (these are equivalent representations of dataset). This data matrix will be comprised of K diagonal blocks, DI,..., Dr: in particular, outside of these blocks, the matrix has only zeros. These blocks are sampled i..d. from the hard distribution lr given by hypothesis. Denote fi the law of D.
Let now (Dk) E IR be the mean (over rows) of dataset DR. Then, the mean (over rows) of IRd denotes the concatenation of 21,..., 2K (note that if K < d/t, then the concatenation above needs to be padded with (d - tK) -zeros, which we omit for simplicity).
dataset D is given by Z(D) na | (Di) [ [ (Dx)] where
Let A be (e, 6D- algorithm, and let Aş its output the kth block variables, then
K Σ
[IA(D) 2DD]
(a(D)
7l 2k (D))
Ax(D) 120
Ex (Dx)
72
Let now Bx(D) := Ax(). and note it is (c, 5)-P w.r.t D3 (as is DP w.r.t D); further, by the no independence of D1...., DR. [B²(D) Ex Dx) must be at least ag. with probability at least Po (both Dx and the internal we have
condition (Di)s to conclude that the squared E2-error
randomness of Bx). Letting Ys == 1 (D)) (D, )la2
P[ILA(D) 2(D)
Co 2
Pa K
P
K
Yx
Pa 2
2
k=
We will now use a coupling argument to lower bound the probability above. First, we let iid. Unif([O, 1J), and W' 1002200 which are i.id. On the other hand, we de-
UI...., UK
fine
P4
yd- = Ply 1 = 01...., VK-1 2k-1)
Yx = (U22 (P V...)).....))
Noting that Y - Y, and that Yz W& almost surely, due to the fact that pk Pu almost surely (which it follows from the e--error argument discussed above), we have
K
K
PoK
PaK
PoK
Y
Σ
W
21-exp (1-eep(-po/8)
-
2
2
k=1
where we used a one-sided multiplicative Chernoff bound.
Therefore, [|A(() - {D)I N
Ko with probability - exp(-po/8) We conclude that
j induces an (a, p) -istribbution lower bound for (s, 6)DP mean estimation, as claimed.
C.2 Proof of Theorem 4.4
Proof. By Lemma A.3, there exists a set P of 1 1/Vc-igg vectors on Cd. with log((P)) log(d/s) Lemma A.5 thus implies the desired lower bound.
C.3 Proof of Theorem 4.1
With all the building blocks in place, we now prove Theorem 4.1.
Proof of Theorem 4.1. We divide the analysis into the different regimes of sample size n. First, if logíd/s) then Theorem 4.4 provides an ?(1) lower bound.
Next we consider the case s llog(d/s)
S S 4. For s < t S d to be determined, let no = s slo((t/s)
n2 this can be attained by choosing t = de log (d). This implics in the We choose t so that & mg
18

---

context of Lemma 4.3 that K = By Theorem 4.4, this implies lower bound do 2 1, with constant probability 1/2 for sparse mean estimation in dimension t. By Lemma 4.3, we conclude sparse mean estimation lower bound of aggo probability.
V2
22
llg(dd/nz) holds with constant en
K
On the other hand, Z 5. let n ~ H. By the previous paragraph. for datasets of size the following lower bound holds, ②2 the lower bound 2
sllggd//en") en
For any n,, by Lemma A.4, we have
((V3 lVari
yad
holds with constant probability. e7
C.4 Proof of Theorem 4.5
Proof. We divide the analysis into the different regimes sample size n.. First, if S V (l((///)//, then embedding an s-dimensional lower bound construction [42]* and padding it with zeros for the remaining d features, provides an (2(1) lower bound with constant probability.
Next, we consider the case v In(1/5) 2 dv/m(1/88) Let no /sln(1/o)/e, t s. Vee
and K no a* where the last inequality holds by regime assumption. The classic dimensional mean estimation lower bound by [42] provides an og Z 1 lower bound with constant probability. Hence by Lemma 4.3, the sparse mean estimation problem satisfies a lower bound 0
Co
K
2V
(11)(1 with constant probability.
Ven
dv/n(1/5)
First, letting n² d (m(5/))
We conclude with the final range, Z
v we note that this
ves
sample size falls within the range of the previous analysis, which implies lower bound with constant probability of (8))(1/8))144 eV"'
La Now, if > n², by Lemma A.4, we conclude that the following
lower bound holds with constant probability, Ω
5 [nn Vi n
y (11(1//6)
ne
D Analysis of Biased SGD
Given the taived nature of our estimators, our guarantees for single run of SGD with bias- reduced first-order oracles only yields constant probability guarantees. Here we prove pathwise bounds that facilitate such analyses.
D.1 Excess Empirical Risk: Convex Case
First, provide path-wise guarantee for of SGD with biased oracle. Importantly, this guarantee is made of a method which runs for a random number of steps.
Proposition D.1. Let (Fi), be the natural filtration, and T' be a random time. Let (x'); be the trajectory of projected SGD with deterministic stepsize sequence (πx), and (biased) stochastic first-order oracle G for given function F. If x² arg min E X}. then the following event holds almost surely
T [(F(2)) - F(x")) S
1 21je
T
1000
211
+ 7=
Σ
-VF()))
2
0m0
'While [42] only provides 1 I-dimensional distributional lower bounds for approximate-DD mean estimation. it is easy convert these into higher dimensional lower bounds, see, e.g., [26, 43].
19

---

Proof. By convexity
F(x') - (VF("))) x²) (VF(x>) g(xx)))))))))) x - x5) +(9(x x²)
S b + (9(x'), xf -x xlt1) + (9(x²). x x²))
1
< 4 + (9(())) ||2 +
||
112 + (vg
(z))),, ) 1+1 x²)
2
27
( I b, + ||(("")|12
1
1
-
1|
-x
112
+ (2
x², xx - x 1
2/11.
7
b + 11 (1((('))) 2
1
1|x
x=1
1=112-
1
|1attl-
x=
27
277
where the second inequality follows by the Young inequality, and step (*) we used the optimality conditions of the projected SGD step:
(n=)(x") + [x't] - x' x
2
(Vx x²)
Therefore, summing up these inequalities, we obtain
T Σ
Σir(+))-((+)) S 1 11- 11
T
b
[1((z')1 21 +bb]
21j0
2
1=0
1=0
Plugging in the definition of b, proves the result.
D.2 Stationary Points: Nonconvex Case
Proposition D.2. Let F satisfy (A.6), and 9 be a biased first-order stochastic orucle for Let (xf)) be the trujectory of SGD with oracle G, constant stepsize 0 < S 1/(2H,, and initialization d such that F(x") mingers F(x) & T. Let be a random time. Then the following event holds almost surely
+ nH T 119(()11
[VF('') 1
-VF)
17 1=0
1=0
t=
Proof. By smoothness of f. we have
F(att1) - F(x²)= < (VF(2'), T2
2 |[(()')11
$ -->IVF(>>)) - - + n2
((((2())
Therefore,
|F F(*0) F(xT+1)
n
[(VF(E').00)) VVF('))
Σ
|ل('')|
1
2
t=0
< r Σ (VF - + nH Σ |g(x)))1
7
E Missing proofs from Section 5
E.1 Proof of Lemma 5.1
Proof. The proof is based on the fully adaptive composition theorem of DP [15]. For this, we consider [Ar) where An(5) = (n") No) (here No the first truncated geometric parameter), and inductively, A S) for / > 0 takes as input A(()) (x', N.), computes G(ar)) using the subsampled debiased gradient estimator (Algorithm 2), and performs projected gradient step based on G(x²). Let H, be the a algebra induced by (AA.)s=0....
20

---

Suppose now that A, is (Ez, DDP, where (Et, are H He-measurable (we will later obtain these parameters), and let T := it Ejost E/2, 6[o:1] > 6/2). in the language of Theorem A.6 (notice that in the context of that theorem, we are choosing 8' 8" 8/4). We first claim that (a" to.........TTT is 12/2, 6/2)-DP, which follows directly from Theorem A.6. Next, we will later show that Et S e/4 and 6, S 8/4, almost surely (this applies in particular to IT), and therefore by the composition property of DP, (Iz)sTT is (E, 8D-P.
Next, we provide the bounds on (Ex, 5t) required to conclude the proof. For this, we first note that conditionally on xxr N, and the computation of + (x* Bi), Gy, (x', Oz). Gw, (x' Et), is (3e/32, 36/ -DP. Furthermore, by privacy amplification by subsampling, this triplet of random
variables is 8'), with
=IIn (1+ 2N++1
(620//22 (1+22
35 2N
2 38
<
8'
n
16
n 16
where we used above that & S 1. Similarly, we have that Go(z, 1) is ( 16n 16n the basic composition theorem of DP, have the following privacy parameters for the /th iteration of the algorithm
5 -DP. Therefore, by
5
& 2 2 + 1) 16n'
=3 (3. 23.2%%.2 N 1) 16m
This proves in particular that (e,, 5,) are H4-measurable, and that 6, S e/4, and o; S 6/4 almost surely, which concludes the proof
E.2 Proof of Lemma 5.3
Proof. Let A -1=1 have that
N. 11 1)) and note that for t S T A S 1 almost surely. Then, we 16n
E²
e|0:-11] 22 +
A
< 28 2ln(//O)A.
2
Now, by eqn. (2) and the union bound,
P
< t)
<
25 21
8/2 +P Σ
(3
2
+ 1) > 4n
a=0
32n (+)
IP
(3 N3+2
+ 1)
+
(3 2 + 1) > 4n
==0
In
(9 + +) + An
[6(M + +1
16n2
t tnn (2)
[18n + 1]+
66 log((n) +
16n2
< 1/4,
where the third step follows from Markov's s inequality and the fact that (Ne), are i.i.d., and the last step follows from our choice of t = Cn/Iogl (n/log((46) with C > 0 sufficiently small (here use the fact that < 1/n²).
For the second part, we use that by the definition of T (eqn. (2))
2N.
+
1)2
2
(3 2 +1 + +1)2
1
3 No+1 +1
2. ln
V
2
(16n)2
2 am0
(16n)2
16n
s=0
T
N1
+1
+
1)2
T 3
2N
n
< max
8l
n
(16)2
4
0=0
Taking expectations and bounding the maximum by the sum allows us to use Wald's identity as follows,
4 2(9n 11
3 3log(n) +
n² < E/T + (8
5
162
+
< ET + 11 (z)
(n + 1),
21

---

which proves the claimed bound.
The upper nound B[T] is obtained similarly. Again, by eqn. (2),
32n² In 448))
T-1
(3 (3.2N,+H + +))) 2 E[T) 9n
Σ
2
Re-arranging terms provides the claimed lower bound.
E.3 Excess Empirical Risk in the Convex Setting
As first application, we study the accuracy guarantees of Algorithm 3 in the convex setting. We remark that these rates will be slightly weaker than those provided in Section 6, but this example is useful to illustrate the technique. Towards this goal, we analyze the cumulative regret of the algorithm, namely RT == -t=ol (Fs - Fs(x" (S)) Although this is a standard and well-studied object in optimization, we need to obtain bounds for this object when the stopping time T is random. The key observation here is that since I is stopping time, the event {I'S 2 t is 1-masuuurrrbllle (here and throughout, F, ((())))() is the natural filtration). This permits using our bias and second moment bounds similarly the case where T is deterministie." 5 Moreover, for the sake of analysis, we will consider Algorithm as running indefinitely, for all / 2 0. This would of course eventually violate privacy. However, since our algorithm stops time T, then privacy is guaranteed as done earlier in this section.
Proposition E.1. Let R2 = (i=o(Fs(>") - Fs(x Fs(x let T be the stopping time defined in eqn. (2). Then
mu? 1N( + Db).
E - 2n
11-0-==' (S)) E 1](
2
where b and v² are defined as in Lemma 5.2.
Proof. By Proposition D.1 (see Appendix D),
E RT
<
E
1
1x00 (S))
+ Σ 1 + -
x² (5))))
2m
E
120 x (S)]1
21
"
F|
[1
(T2
2
E
1/00 x (S))
2n
80
(T21)
112 -
2
1=0
where in the first equality we used the tower property of the conditional expectation, and in the second 1). equality we used that {T t = [T - is F measurable.
Now, by Lemma 5.2, (( (note that F,-1 does not include the randomness of No. and therefore the bias and moment estimates as in the mentioned lemma hold), thus
f(z'), x (S) s Db and (1]]((2'))1 < 1/
E |
< - 1| -2")))+++EE
1
E 11( mu2 +
2n
We conclude with the constant probability guarantee for the biased and randomly stopped SGD, Algorithm 3.
'This idea is related to the Wald identities [16]; however, provide direct analysis for the sake of clarity.
22

---

Theorem E.2. Consider (SO) problem under convexity (Item (A.3)), initial distance (Item (A.1)), Lipschitzness (Item (A.5)) and gradient sparsity (Item (A.7)) assumptions. Let T [m(2/8)) where
C'n
D C² > O is an absolute constant. Let WVT"' U = CDIPVT + br], where C > 0 is an absolute constant, Then Algorithm 3 satisfies
U P Fs( Fs(x*(S)) _ 2 1/2.
Proof. We start by noting that
U - P Fs((3) Fs(x
u U3 S U}.
For the first event, by Lemma 5.3, have that PTT < r] < 1/4 (which determines C²). On the other hand, using Proposition E.1 and Lemma 5.3, we have that for our choice of 1). we have that
DVVT + +ET+ 11D ET < 2
v
+ D(VFF+
2VF
In particular, for our choice of (with sufficiently large),
E(Ry] -
P[R U1
The above result implies nearly optimal empirical excess risk rate for DP-SCO,
o(L Iindlsln(d/s)nn
In (1/0)//))
Ven
but only with constant probability. We defer to the next section how boost this guarantee hold with arbitrarily high probability.
E.3.1 Near Stationary Points for the Empirical Risk
For nonconvex objectives it is known that obtaining vanishing excess risk is computationally difficult. Hence, study the more modest goal of approximating stationary points, i.e., points with small norm of the gradient. By combining known analyses of biased SGD with our bias-reduced oracle, we establish bounds the success probability of the algorithm.
Theorem E.3, Consider a (nonconvex) (SO) problem, under the following assumptions: Lipschitz- ness (Item (A.5)), smoothness (Item (A.6)), gradient sparsity (Item (A.7)), and the following initial such that
suboptimality assumption: namely, that given our initialization x. E IRd, we know I
Fs(#0) Fs(x" (S)) S..
(5)
Let r C'n with C' > an absolute constant. Let 1) = lm(2/6)
v r
H and = C(VTHTV + LTb)
with C an absolute constant. Then Algorithm satisfies IP
(z=) < 4 2 1/2, and
U S (VTHLVIn()) L2)
(n(d//s)) In d/s) In(1/))
Ven
Proof. First, given any U > 0. we have that
U - V
p P|IVFs((3)11>> > / PTT +
23

---

where the last step follows by Lemma 5.3 and Chebyshev's inequality, respectively. Next, by definition of and Proposition D.2 (see Appendix D.2),
[ 1)
EE
n
VF (xF(x)))(x)) v
$ +
r H
S
B (T20 [
E (T22 (VF4)) -VF())) VF(2')))
1=0
H
$
+
PIT (B((11992))
1=0
P(T 2 (BFF(((F('")) -
1=0
r
H E[T + 1|/2 E[T L]
S TTHTH Lb,
where the third inequality holds since (T 2 t] is -ee--uuasue (see the proof of Theorem E.1 for details), and the fourth inequality follows from Theorem 5.2, used the upper bound E[7] from Lemma 5.3, and our choice for 7). Selecting U C(VTHTv + Lrb) with C > 0 sufficiently large, we get V (2)) < 1/4, concluding the proof.
F Boosting the Confidence for the Bias-Reduces Stochastic Gradient Method
We conclude by providing boosting method amplify the success probability of our bias-reduced method. This private boosting method is particular instance of private selection method [17], and it is based on running a random number of independent runs of Algorithm 3 with noisy evaluations of their performance. Among the independent runs, we select the best performing one based on the noisy evaluations. This particular implementation sharpens some polylogarithmic factors that would appear for other private selection methods, such as Report Noisy Min [18, 1].
Algorithm Boosting_Biass -Raaaeeddddddddd....... 6, K)
Require: Dataset S ~ D 8 privacy parameters, random stopping parameter y E (0, 1) K + (n) for A 1......... K do
Run Algorithm with privacy budget (s/12, (8/[4K))²), &g its output and if f(; convex then
Set s
(fs(()) + Ex], where & Lap(X), and À 12B me
else
Set są |I| + Ex), where & Lap(A), and 21L end
ne Flip r-biased coin: with probability 7, return di. where i arg minigg 81
end for
Return á &. where K = arg ming5 8k
Theorem F.1. Lete, such that 8 S s/100 Then Algorithm 6 (e, 8) Let 0 < 8 < 1 and
7 m1n///2.3//4 In the convex case, Algorithm 6 attains excess risk P Fs(2) Fs(x*(S))
> 1 1- 8, where
a. $ LD Innd/sn((d/s) (1n(1/))((38))
B nE
In In 2 )
Ven
24

---

On the other hand, in the nonconver case,
P
[VVFs S a 2 B, where (n
a as (vTHLy In(n)) In (n(1/0)) + 1.2)
In )
In
38
Ven
ne
Proof. The privacy analysis follows easily from [17]. First, by basic composition, we have that for
each k the pair (&R, sx) is (11,,))-DD with é1 = =/66, and 51 (6/[4)))² By [17, Thm 3.4], the private selection with random stopping used in Algorithm 6 is such that & is (3s) + +3/201, 2 K -/2)-DP: notice that
321 + 3v 201 - + +332 5 S.
K
and
28 K + 6/2 S 8,
due to our choices of E,, , This proves that the algorithm is (e,6)-DP
The accuracy of the algorithm closely follows [17, Theorem 3.3]. First, let k be the number of runs the algorithm makes before stopping, and let a > 0 to be determined. Conditioning on
K
([(s(()) (s(x > a]
P P[Fs($) Fs((*(()) > a/x= = k]IP(x k]
K
P(Fs(t) Fs(x' > a k) 7)
We will now bound the conditional probability above. By the subexponential tails of the Laplace distribution, we have that letting & := [(Vj E [k]) l6yl S a') (here, a' > 0 is arbitrary),
P\E k] PP (3j [+]) |sxl > a' k) s 2kx
nea'
12B }
Hence
P (()s - Es(a (S)) x/== s <p((F(())) (S)) [() = +P|8"/=
Next we have
((s((t) - Fs(x > a) no k= $) < ( Es Fs(x (S)) a a-
=P(
min [F((C)) Em] Fs(x" (S)) - -d' ng =k k)
kE(m)
p min
[Fs(#x) Fs(= (S)) > 22a x = k
kEin
(P( Fs(x"(())
20 20d))²
where in the last step we used that the runs are i.i.d.
We now choose a, a' such that a - 2x' = U/T (where U, are those from Theorem E.2). Hence,
P P[Fs(t) - Fs(x*(S)) a/w= = k] $ + 2k {
nsa'
12B
We can now bound the failure probability as follows:
(PFs(()) Fs(x" (S)) > a
2
+
22expp
2K
exp
nea'
1)
-11
12B
k=1
1
2
2
nEa'
+
In
exp
2
22
7
12B
8
2
2
nea!
7
In
exp
12B
f
25

---

where in the last step we used that min/1/2,35/4). It is clear then that a'
12/8
In
16 30
In (3)
makes the probability above at most 3. These choices lead to a final bound
ne
U + 2a' LD a
LD (nnnssn(ddss) In (In(1/))[380]]44
B In
In (
VEN
ne
For the nonconvex case, we need to replace B by 2L in the Laplace concentration bound. Further, we consider the event {l)VF(& at (as opposed to the optimality gap event). This implies that need
0 such that 2a' 2 /U/T from Theorem E.3. This leads
K
P [s(0))]2
af S Σ
2
+ 2K exp {
nEY 24L }) 7))--17.
k=
The rest of the derivations are analogous.
G Missing Proofs and Results from Section 6
G.1 Proof of Theorem 6.1
Proof. We proceed by cases:
Case First, we prove that privacy of the algorithm. To do this, we first establish bound on the f fi-seviitvv of the (quadratically) regularized ERM. Note that the first-order optimality conditions this case correspond
1 (F)()
x3(8)
Therefore, if S S", where S (31,..., and = (E/, :44) only differ in one entry,
1 V F3(
(x)(S) - =
(2
Vf(x)()), 2)) - (S))
(n 1) ( (S')ll2 + 2
An
(4V2sHL
n n-1 +2/2sL)
An
An
2/22L 2H An (x +1)
Above, in the third inequality used the gradient sparsity (A.7), and the smoothness (A.6), assumptions. In the fourth inequality we used that the regularized ERM has f2-sensitivity Xn [44, 45, 46). We conclude the privacy then by Theorem (a)
4L
We also remark that by Theorem A.2(a)-(i), |o $
LVElu(d/3) Ane
( +1). with probability 1 - B.
Case 0. The privacy guarantee follows from the fact that the l en-seniitiv of x An [44, 45, 46], together with Theorem A. (bb).
L/lad//B Ang
Moreover, by Theorem A.2(b)-(i), ||E <
with probability 1 3.
We continue with the accuracy analysis, making unified presentation for both pure and approximate- DP. First, by the optimality conditions of the regularized ERM,
Fs(x Fs(x (S)) < |a (S)1 > D2.
(6)
26

---

We need the following key fact, which follows by the definitions of å and I,
|| - ( S || 0|/00 + | (5))|s>> S 2||5||
Using these two bounds, we proceed as follows
F5( Fs(x"(()) - Fs( (s(r + -/22 (VFs(8)) - + - D2
[VPs - x5 - D2
S <2sT[llll> > > 2
where the second inequality follows by convexity of Fs, and the fourth one by the gradient sparsity assumption and (7).
The conclusion follows by plugging in the respective bounds of X and ||E for both pure- and approximate-DD cases.
G.2 Proof Theorem 6.3
Remark G.1. Note first that in the proof below we are not addressing the privacy of Algorithm 4, as this has already been proven in Theorem 6.1.
On the other hand, note that the same broof below- using the in in-expectation generalization guarantees of uniformly stable algorithms [44] provides a sharper upper bound for the expected excess risk for the pure and approximate- DP cases, which would hold w.p. 1 - 3 over the algorithm internal randomness
log(d/3) 1/3
Es(Fx( Fo(x (D))
X
4/3 D4/3
en
[sln(1 /5) log(d/3))
(s(Fb( Fo(x" (D))
LD
Ven
Proof. Using the fz-sensitivity of (S), A
we have the following generalization bound An
AL
[47]: with probability 1 8/2
1 An In(n) In (7) + BB
Fo(c)(()) x
-%7
The bound of (6) can obviously modified by comparison with the population risk minimizer, x² (D): in particular, the event above implies that
(D)) - Fo(x (D)) S (s(x)(S)) - Fs(x* + 7 (D) + + S XD2 + 7.
On the other hand, the bound (7) works exactly as in the proof of Theorem 6.1. Hence, have that with probability 1 3/2,
FD( - FD(a" (D)) S Fo ( - (x(x)((()) + XD2 +
S V FD) - (S)) + XD2 +
2
In(n) In
XD2
B
(n(())
In
An
3
Vn
V
where in the last step we used that VVF VV 2)]1 S E. (t, 2)]
$ LVs
(the last step which follows by the gradient sparsity), inequality (7), and the definition of 7.
We proceed now by separately studying the different cases for 6:
"We also need concentration to upper bound Fs(ø" (D)) - Fb(x" (D)). However, this is easy to do by e.g., HoooHding's 's inequality, leading to bound $ 7
27

---

Case 8 = 0. The bound above becomes
I s slndd/3)
H xx+1) + +1nin(1/8)) + +D² + B\ In(1/8)
FD(ā) F(x - An
Our choice of À provides the claimed bound.
Case 5 > O. Here, the upper bound takes the form
I (nl/n ln(1/)) + In(n) In(13)) + AD2 + +B/ In(1/33
FD( F(x" (D)) 2 An
n
The proposed value of leads to the bound below that holds with probability - -3
In(1/3)
In (n133)
/ In (1/()) log(d/3))
Fp(#) - Fb(æ" (D)) S B
LD
n
n2
en
In(1/8) n
[s (1/8) log(d/ d/
2 (LDvinn+ B)V
LD
VEN
G.3 Pure DP-ERM Algorithm for Nonsmooth Losses
We prove that the rates of pure DP-ERM in the the smoothness assumption, albeit with an inefficient algorithm. This algorithm based on the exponential mechanism, and it leverages the fact that the convex ERM with sparse gradient always has an approximate solution which is sparse. This result requires an additional assumption on the feasible
case above be obtained without
(8) where xlp Rd is the vector such that JPJ x if P. and xP. otherwise. We will say that X' is sparsifiable if (8) holds. Note this property holds e.g., for ba-balls centered at the origin.
(#EXAPE(d)
x/p E X,
Lemma G.2. Let X be a convex sparsifiable set. Consider the problem (ERM) under convex- ity (Item (A.3)), bounded diameter (Item (A.2)), Lipschirzess (Item (A.5)) and gradient sparsity (Itmm (A.7)), assumptions. If (S) is an optimal solution of (ERM) and T > 0, then there exists X such that | lo < 1/72, and
Fs(#) Fs(x"(S)) LVST.
Proof. Let 2 E Fd be defined as
i 5 {
Ij if 1 | ZT otherwise.
Note that 2 E X' since (S) E X' and X' is sparsifiable. Now we note that
|
Σ
22
A: b 12
Finally, for the accuracy guarantee, we use convexity as follows,
Fs(ā) FS(x*(S)) < (V)s x² 2*))
< [Fs(()
- - =S)
< LV
where in the last step we used that ff 2;) E S and the definition of ă.
present now the spurse exponential mechanism, which uses the result above to approximately solve (ERM) with nearly dimension-independeee rates.
28

---

Algorithm/ 7 Sparse_ Exporentai.po MatieeatntiaaMMMMMiieaiaii sm
Require: Dataset S {.1,..., 2nd S Z, privacy parameter, f(, z) L-Lipschitz convex function
with s-sparse gradients and range bounded by B,0 < 3 < confidence parameter
Let be such that [n(d/(=31) Lv/
Let NV be 7-net of sparse vectors over X' with [W;] - (1/r2) (2)
Let é be a random variable supported on Ny such that P(e = x:] exp B [s(x))
Return 3
Remark G.3. The bound on [& claimed in Algorithm 7 follows from a standard combinatorial
argument (e.g., [39]). Moreover, it follows that [ - (4) 1/+²
Theorem G.4. Let be a convex sparsifiable set. Consider a problem (ERM) under bounded diameter (Item (A.2)), convexity (Item (A.3)). bounded range (Item (A.4)), Lipschitaness (Item (A.5)) and gradient sparsity (Item (A.7)), assumptions. Then Algorithm 7 satisfies with probability
(L)Berd)))
(Tv/sen d) 1/3
Fs(#) - Fs(x" & 1//////3 In
En
B
Proof. Let J be the vector whose existence is guaranteed by Theorem G.2. By the high probability guarantee of the exponential mechanism [1] with probability 1 13
B En
B In
Fs(#) Fs(
S
In In|NG/+In11/0)))
x
TB
EN
72
Hence, using Theorem G.2 with the upper bound above,
(.) Fs (S)) - F.( Fs( Fs(B) - Fs(x" (S))
B In(d/(T]])
+ LV/T
72
/En d
11)3)
1/3
L3B
In
3
en
where we used our choice of т.
29

---

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:
All results have full proofs and are self-contained.
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 in the paper and important assumptions and limitations. A No or NA answer 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 it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper includes a description of current limitations the Future Directions section.
Guidelines:
The answer NA means that the paper has no 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 "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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of 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 be used by reviewers 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 an important role 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 set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

All proofs contain precise description of the underlying assumptions and proofs. Some of the proofs were deferred the Appendix due space limitations.
Justification:
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 the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided appendix or 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 not.
dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
If the contribution
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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 a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) 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 way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-soures models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

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 the NeurIPS code and data submission guidelines (https://nips.. cc/
public/guia Sgwidee/CodeSubblee wwwpbbiisssssooooolooooooooooooe onoolioyyy PePoollyyy)))). for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for 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: /niiss. httppplllgudde/////p/p/ppppaee//
ssiisssioo wwwpommmisssooooooiioooooo.o ceiionnPoccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material,
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of 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 authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims the paper.
The factors variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
32

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs 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 NeurIPS Code of Ethics https / htt////eerrp...ee cc
Answer: [Yes]
Justification: The work in this paper is theoretical, and therefore there ethical concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 sure to preserve anonymity (e.g., if there is a special considera- tion 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: This work is theoretical in nature and thus it has negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will 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 out. For example, legitimate to point out that an improvement in the quality of generative models could be used to
33

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should released with necessary safeguards 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 take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA].
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the pack- age should be provided. For popular datasets, paperswi thcode. com/ hmmdataaeee has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
34

---

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 of the dataset/code/model 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 is 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. Crowdsourcing 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 as 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 in the supplemental material fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country 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 on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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 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 the institution conducting the review.
35


Reviews:
[{"review_id": "jWpaygVgX9", "reviewer": "Reviewer_9vLf", "summary": "This paper addresses the problem of DP-Convex optimization and DP-SCO in scenarios where the gradient of each individual sample is $s$ sparse. The main question explored is how sparsity can help improve the known rates for DP convex optimization.\n\nThe main contributions of the paper are as follows:\n\nDP Sparse Mean Estimation of High-Dimensional Vectors: The authors investigate DP mean estimation under the assumption of sparsity. They use the projection mechanism from Nikolov et al. to propose algorithms for both pure-DP and approximate-DP settings. The error of the algorithm scales with  $s$ when the number of samples is moderate. The main results are presented in Theorems 3.2 and 3.3.\n\nLower Bound for Mean Estimation under Sparsity: The authors provide lower bounds for mean estimation under sparsity. Note that due to the reduction in BST14, the lower bound on mean estimation can be translated to a lower bound on DP-ERM.\n\nAlgorithms for DP-ERM under Sparsity: The authors propose an interesting algorithms for DP-ERM under the sparsity assumption. To compute gradients, they use their proposed algorithm for mean estimation as a black-box. Unlike DP-SGD, the gradient in this case is \"biased.\" To address this issue, the authors introduce an interesting approach using random batch sizes with an exponentially increasing schedule to achieve a bias similar to that of a full-batch algorithm.", "questions": "I can't fine the results regarding DP-SCO in the paper. Maybe I am missing something in the paper.\n\n1- Is there any way to extend the results to the case with approximate sparsity? \n\n2- what is p_n in algorithm 2?\n\n3- What is the importance of random batch size?\n\n4- Theorem A.6 seems to have a typo?\n\n5- Line 641 to 642, 1[T>=t] has been changed to 1[T<=t]. It is not clear to me? Step 1 needs more clear explanation.\n\n6- What is the shortcoming of “equal” privacy budget allocation as in the BST14 paper?\n\n7- What is the issue with using full-batch for computing the gradient?\n\n8- What is the definition of $\\mathcal{F}_{t-1}$ in prop. E.1?\n\n9- Line 644, it is not clear to me why conditional expectation of bias and variance are also bounded by b and v.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think the paper addresses an important problem with practical relevance. I think the paper is complete in the sense that the authors provide near complete story of optimization under sparsity at least in terms of achievable rates. The idea of behind the optimization algorithm is interesting.", "weaknesses": "The main drawback of this work is its presentation. Some of the proof is very difficult to parse. I have difficulty understanding the many algorithmic choices behind Algorithm 2. In particular, the idea of using random batch size, fully adaptive DP mechanism, specific distribution for batch size are not clear to me. I think the authors should provide a discussion on the necessity of these particular algorithmic choices.", "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 valuable and detailed feedback. \n\nFirstly, we apologize for the lack of clarity of the algorithmic choices and the proofs in our submission.  Here is an overview of the choices behind Algorithm 2.  As discussed in the paper, the near-optimal mean estimation algorithms we introduce are _biased_. Simply using SGD with this mean estimation procedure for minibatch gradients would result in a _polynomial degradation_ of the rates (see, e.g., [6: Zhang, Mironov and Hejazinia], who carry out this approach). To handle this issue, we propose a _bias-reduction method_, which closely follows the approach in [14: Blanchet and Glynn]. This randomized method produces an estimator that telescopes in expectation, resulting in bias which scales as the one of the largest possible batch, but with minibatch sizes that are typically much smaller. The exponential range of the batch size follows from the telescoping idea.\n\nThe bias-reduction approach is beneficial for privacy, because when minibatches are smaller, one can leverage _privacy amplification by subsampling_. However, since batch sizes are random, the classical advanced composition DP analysis does not suffice. Here is where we use the _fully adaptive composition_ theorem [15: Whitehouse, Ramdas, Rogers and Wu]: in particular, since our batch randomization is predictable, we can define stopping times in such a way that we do not exceed the privacy budget. This however introduces challenges in the SGD analysis, which are addressed by the _boosting_ procedure. \n\nWe will include a better detailed overview of this algorithm and its analysis in the revision.\n\n__Questions__\n\nAbout DP-SCO results. Due to space limitations, all results for DP-SCO were deferred to Appendix G. In the final version of the paper we will include the main results from that section (particularly, Appendix G.2).\n\n1. Yes. As pointed out in Remark 2.1, in all of our upper bounds we can replace the set of sparse vectors by a scaled $\\ell_1$-ball. This set is a more robust way to quantify sparsity, as known from the compressed sensing literature.\n\n2. $p_n$ is the probability of choosing a batch size $2^{n+1}$, i.e., $p_n=C_M/2^n$ (where $C_M$ is a normalizing constant). This is explained in lines 233-236, but we will make it explicit in the pseudocode to avoid confusion.\n\n3. Random batch sizes allow bias reduction with smaller minibatches, which are amenable for privacy amplification by subsampling. Using a full batch estimator would incur similar bias, but no privacy amplification. We will make sure to expand on this important aspect.\n\n4. Thank you. We found an incorrect indexing: $[1:t-1]$ instead of the correct $[0:t-1]$.\n\n5. Apologies for causing confusion: we simply wrote the same event in two different ways, i.e.,  $\\{t\\leq T\\}$ and $\\{T\\geq t\\}$. In the revision, we will retain the same notation.\nIn the first step we use the regret bound for biased SGD, and in the second step we write the finite sum from $0$ to $T$ as a series with zero terms (due to the indicator) for $t>T$. Please let us know if more clarification is needed.\n\n6. We are not sure which part of the paper you are referring to. Can you please let us know, and we can clarify it accordingly?\n\n7. Please see answer 3 above.\n\n8. $\\\\{ \\cal F_t \\\\}_{t\\in\\mathbb{N}}$ is the natural filtration, i.e., ${\\cal F}_t = \\sigma((x^s), {s \\leq t})$. We will add a clarification of this in the revision. \n\n9. The sources of randomness used in Lemma 5.2 are only the batch size r.v. N and the DP noise used to compute ${\\cal G}(x)$. While we could have stated Lemma 5.2 for an iterate $x^t$ (and correspondingly condition on ${\\cal F}_{t-1}$), we believe the current presentation of this lemma is cleaner, and avoids unnecessary notation.", "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": "1OEvQxFxKA", "reviewer": "Reviewer_JAyy", "summary": "The paper provide algorithms for DP optimization with sparse gradient, proving both upper bounds and lower bounds, which are almost match.", "questions": "The proposed algorithms seems not too hard to use in practice, could the authors comment whether they can be used practically? Or if the authors tested them in practice, it would be interesting to see some results.", "limitations": "Limitations are well covered in the content.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper has a nice presentation, starting from sparse mean estimation upper bounds and lower bounds and then go into ERM with sparse gradients and deal with bias issues introduced by the projection estimator. \n2. The upper bounds and lower bounds almost match.", "weaknesses": "1. It is a pure theory paper, it would be more interesting to see if the algorithm can inspire improved practical applications.\n2. The content is a bit dense, without summary or conclusion sections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We will now elaborate on the comments.\n\nThank you for your comment on practical applications. In this regard, the idea of gradient sparsity has already impacted practical DP optimization. The most immediate references in this respect are [6: Zhang, Mironov, Hejazinia] and [7: Ghazi, Huang, Kamath, Kumar, Manurangsi]. Regarding the specific contributions of this work, we believe that significant components of our results can inspire practical improvements. First, the projection mechanism and compressed sensing approaches are easy to apply and should lead to better statistical performance in mean estimation than, e.g., the sparse vector technique (which is the main approach in [6,7]).  Second, our regularized output perturbation approaches for DP-SCO (Section G) are easy to implement.  Third, towards neural network applications (such as embedding models), the computational benefits of sparsity are more significant under structured sparsity, e.g., in the case of embedding models we need the sparsity to operate at the level of rows of the embedding matrix. We believe that ideas used in the context of group or structured sparsity can be of use here, but this is out of the scope of the current submission. Finally, a major roadblock for practical applications is the heavy-tailed nature of the bias-reduced gradient estimator used for SGD. While the algorithm in its current form might be less practical, we hope our work may inspire further ideas and lead to more practical methods.\n\nWe apologize for the current dense content; in the revision, we will try to rewrite to make it more accessible.  \n\n__Questions__\n\nAs we mention above, the bias reduction method may be hard to implement in practice. Particularly, the heavy-tailed nature of the gradient estimator may pose convergence challenges. Boosting might mitigate this, but we are interested in continuing investigating alternative approaches that can be more practical.", "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": "mEiTybY5Dk", "reviewer": "Reviewer_GgyX", "summary": "The paper studies differentially private optimization under the sparse gradient assumption. The paper first considers private and sparse mean estimation. Both lower-bounds and nearly matching upper bounds are established. The paper then use the mean estimation algorithm to construct private gradients in DP-SGD and obtain new dimension independent rates for both DP-ERM and DP-SCO under convex and non-convex settings of the objective function.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "A crucial issue in differentially private optimization is that the utility rates depend on the dimension. This prevents the use of DP techniques to large models whose dimension scales to billions. The paper contributes to an important line of work in DP that tries to develop dimension free error rates under structual assumptions of the problem. Both the settings that gradients are sparse and the theoretical results under the sparsity assumption are novel and new.", "weaknesses": "1. There are several missing related works that should be included. [1-7] all derived dimension independent rates for DP optimization under various settings. [1] relaxed the dimension to a dependence on the rank of the feature matrix. [2, 5] studied the relaxed Lipschitz condition. [3,4] relaxed the dimension to a dependence on the trace of the Hessian. [6, 7] studied the semi-feature setting. Although they are not based on sparse gradients, I think it help to better position this paper when including all these existing dimension free rates in the DP optimization literature. Specifically, the assumption in [2, 5] is also only on the gradients, and [5] also develops an exponential mechanism that could be used for the pure DP case (though they did not discuss). In addition, [8] also studied multi-level Monte-Carlo for stochastic optimization.\n\n2. All previous dimension free rates [1-5] are for the unconstrained case. As discussed in [1, 2], there seems to be a separation between the constrained and unconstrained settings. For unconstraiend case, with additional assumptions, both dimension free upper and lower bounds can be established. However, the dimension dependent lower bound in [Bassily, 2014] is constructed for a constrained generalized linear loss, which also applies to the case where gradients have additional structure. See more discussions in [2, 5]. Results in this paper seem to be contradictory to these related works, where dimension free rates exist for constrained optimization. Can authors explain why and provide more insights?\n\n3. Other questions: (1) In the ideal case, the results for the sparse case should recover the non-sparse case when s=d. However, there seems to be a large gap; (2) In the algorithms, the knowledge of the sparsity s is required. How to determine s in practical applications and is it possible to design algorithms without knowing s? (3) Some assumptions overlap with each other. For example, if f is L-Lipschitz and domain is bounded by D, this already implies that $|f(x) - f(y)|\\leq LD$; (4) In private optimization, we need to add noise to gradients, which makes gradients not sparse any more. How hard is it for the sparsity assumption to hold along the trajectory? Can sparsity be preserved for all x_t?\n\n[1] Evading the Curse of Dimensionality in Unconstrained Private GLMs. AISTATS, 2021.\n\n[2] When Does Differentially Private Learning Not Suffer in High Dimensions? NeurIPS, 2022.\n\n[3] Dimension Independent Generalization of DP-SGD for Overparameterized Smooth Convex Optimization. arXiv, 2022.\n\n[4] DPZero: Private Fine-Tuning of Language Models without Backpropagation. ICML, 2024.\n\n[5] The Power of Sampling: Dimension-free Risk Bounds in Private ERM. arXiv, 2024.\n\n[6] Deep learning with label differential privacy. NeurIPS, 2021.\n\n[7] On Convex Optimization with Semi-Sensitive Features. COLT, 2024.\n\n[8] On the Bias-Variance-Cost Tradeoff of Stochastic Optimization. NeurIPS, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable feedback.\n\n1. Thank you for the references; we will make sure to add them to properly position our work within the field. \n\n2. Unfortunately, it is not true that dimension-free rates are known only for unconstrained settings.  In fact, that there are works providing (nearly) dimension-free rates for the case of polytope feasible sets [22,23:Talwar, Thakurta, Zhang], [24: Asi, Feldman, Koren, Talwar] and [25: Bassily, Guzman, Nandi].  More importantly, there is _no contradiction with the lower bounds in BST14_, since their construction of fingerprinting codes (and packings for the pure case) uses _dense_ vectors. In fact, the key observation behind our sparse DP lower bound is that the sparsity constraint weakens this construction, and a block diagonal construction with blocks as in BST14 yields a nearly optimal lower bound. Note too that polynomial-in-the-dimension lower bounds are still obtained for large enough sample size $n$, showing a smooth transition between the different regimes.\n\n3. Other questions\n\n    1. For mean estimation (Table 1), our upper bounds smoothly transition between the different regimes. For DP-SCO and DP-ERM (Table 2), it is also possible to obtain this transition (simply by selecting the algorithm with the best rate depending on the instance parameters). In the original table we decided to include only the new high-dimensional rates, but we have now added the different regimes (see the attached file). We apologize if this caused confusion.\n\n    2. Each specific application may have an ad-hoc way of estimating $s$. For example, in embedding models, the sparsity (for the embedding layer) will be the number of columns. Alternatively, $s$ can be a hyperparameter (this does not compromise privacy, as long as the hyperparameter selection is done privately).  Designing algorithms that work without knowing $s$ is an interesting question for future research---we will add this to the revision.  \n\n   3. Regarding the overlap in Lipschitzness and boundedness assumptions, we opted to keep this (sometimes redundant) parameterization since we are combining different assumptions for different results. Thank you for pointing this out.  \n  \n   4. There might be a potential misunderstanding here; the gradient sparsity assumption is made over the raw _noise-free_ gradients. Any noise addition (or more general DP procedure) applied to these gradients does not break the sparsity assumption. Please let us know if this resolves your question.", "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": "mmnyTpOwUv", "reviewer": "Reviewer_L9WR", "summary": "This paper explores differentially private optimization under the data/gradient sparsity assumption. For mean estimation with sparse data, it introduces new near-optimal bounds, improving previous results, especially in the high-dimensional setting. The corresponding lower bound is established using a novel block-diagonal construction. For DP ERM/SO with sparse gradients, the paper introduces a bias-reduced, randomly stopped SGD method, building upon their mean estimation mechanism. This approach achieves a nearly dimension-independent risk rate in the sparse gradient setting.", "questions": "Can the authors provide the running times analysis for Algorithms 2 and 3?", "limitations": "The authors address the limitation of this work in the checklist", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is technically solid, with results covering both ERM and SO. In addition, some results also include lower bounds.\n* The novel block diagonal construction of lower bound and the analysis of randomly stopped noisy SGD will benefit future research.", "weaknesses": "The organization of the paper could be improved. For instance, adding more content to Section 6 and briefing the proof part in Section 5 would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment and feedback..\n\nIn the revision, we will reorganize the content.  As you suggest, we will include results for DP-SCO from Section 6 (specifically from Appendix G.2), as well as a more extensive motivation and detailed proofs in Section 5.\n\n__Questions__\n\nThank you for raising this question.  Regarding the running times, for Algorithm 2 we need to compute $2^{N+1}+1=O(n)$ gradients (where N is truncated geometric), and apply Gaussian mechanism and projection over the $\\ell_1$-ball four times (these two algorithms run in time nearly linear in the dimension $d$). Overall, the gradient complexity is $O(n)$ and the computational complexity is $O(nd)$.\n\nFor Algorithm 3, we can use Lemma 5.3 to provide an upper bound on the expected number of iterations (which is $O(n)$), and then multiply this number by the worst-case estimate of the complexity of Algorithm 2. This provides an in-expectation bound for the complexity of the algorithm.\n\nWe will make sure to add these details in the revision.", "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:
Updated table incorporating the low and high dimensional rates for DP optimization.

Meta-review: Pros:

- address the important problems of DP mean estimation and optimization in the natural setting where each individual point/gradient is guaranteed to be sparse.

- the rate for mean estimation is nearly complete with upper and lower bounds that are close

Cons:

- the current rates for optimization in the sparse case are polynomially different from the rates for the general dense case and it is not clear if they are optimal.

- the assumption of exact sparsity can be restrictive. Several reviewers suggest addressing the approximately sparse setting.

The paper's formatting deviates from the template (the page size is 9.68in by 11in). Please fix this issue.
Decision: Accept (poster)