Differentially Private Optimization with Sparse Gradients

Authors: badih  ghazi
cristóbal  guzmán
ravi  kumar
pasin  manurangsi
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:49:47

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.

Main paper: 
 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 a 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, we create trainable parameters w 1 , . . . , w K ∈ R k , and use w a 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 are guaranteed to be sparse; when the input feature is a, then only the gradient with respect to w a is non-zero. Given the prevalence of sparse gradients in practical deep learning applications, GPUs/TPUs that are optimized to 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. 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 are stated for constant success probability, the function parameters and polylog(n) factors are omitted, R ε,δ = d ln(1/δ)/(εn), R ε = d/(εn), and our improvements are highlighted .We initiate the study of DP optimization under gradient sparsity. More precisely, we consider a stochastic optimization (SO) problem, min{F D (x) : x ∈ X }, where X ⊆ R d is a convex set, and F D (x) = E z∼D [f (x, z)], with f (•, z) enjoying some regularity properties, and D is a probability measure supported on a set Z. Our main assumption is gradient sparsity: for an integer 0 ≤ s ≤ d, ∀x ∈ X , z ∈ Z : ∥∇f (x, z)∥ 0 ≤ s , where ∥y∥ 0 denotes the number of nonzero entries of y. We also study empirical risk minimization (ERM), where given a dataset S = (z 1 , . . . , z n ) we aim to minimize F S (x) :=1 n i∈[n] f (x, z i ). 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 a new high-dimensional rate 1 (see Table 1 and Table 2 , for precise rates). These results imply in particular that even for high-dimensional models, this problem is tractable under gradient sparsity. Without sparsity, these polylogarithmic rates is impossible due to known lower bounds [8] .In Section 3, we start with the fundamental task of ℓ 2 -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 a convex relaxation that makes our algorithms efficient. Note that for pure-DP, even our large dataset rate of √ sd/(εn) can be substantially smaller than the dense pure-DP rate of d/(εn) [8] , whenever s ≪ d. For approximate-DP we also obtain a sharper upper bound by solving an ℓ 1 -regression problem of a 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 4, we prove lower bounds that show the near-optimality of our algorithms. For pure-DP, we obtain a new lower bound of Ω(s log(d/s)/(nε)), which is based on a packing of sparse vectors.While this lower bound looks weaker than the standard Ω(d/(nε)) 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-DP, 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 ln(d/s) 1/4 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-DP. We propose the use of stochastic gradient (SGD) with a 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 are 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 a 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 a 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 ℓ ∞ projection post-processing step. While this projection step is rather unusual, its role is clear from the analysis: it leverages the ℓ ∞ 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 a 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-independent rates for this problem.DP optimization is an extensively studied topic for over a decade (see [8, 19, 20] , and the references therein). In this field, some works have highlighted the role of model sparsity (e.g., using sparsitypromoting ℓ 1 -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 is that gradients lie (approximately) in a 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, as 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 ℓ ∞ bound on individual gradients, the following partitioning sparsity assumption is imposed. The dataset S can be uniformly partitioned into subsets S 1 , . . . , S m with a uniform gradient sparsity bound: for all k ∈ [m] and x ∈ X , z∈S k ∇f (x, z) 0 ≤ c 1 . The work shows polylogarithmic in the dimension rates, for both convex and nonconvex settings. Our results only assume individual gradient sparsity, so on 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 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.We present some of the main open questions and future directions of this work. First, we conjecture that for approximate-DP mean estimation-similarly to the pure-DP case-a lower bound Ω s log(d/s) ln(1/δ)/[nε] should exist; such construction could be bootstrapped with a blockdiagonal dataset for a tight lower bound (Lemma 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 s; note that all our mean estimation algorithms (which carries over to our optimization results) depend crucially on knowledge of this parameter. While we can treat s 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] . 
notation and preliminaries: 
 In this work, ∥ • ∥ = ∥ • ∥ 2 is the standard Euclidean norm on R d . We will also make use of EQUATIONNote that Jensen's inequality implies: if ∥x∥ 0 ≤ s and 1 ≤ p < q ≤ ∞, then ∥x∥ p ≤ s 1/p-1/q ∥x∥ q .Remark 2.1. The upper bound results in this paper hold even if we replace the set S d s of sparse vectors by the strictly larger ℓ 1 -ball B d 1 (0, L √ s). Note that while our upper bounds extend to the ℓ 1 assumption above, our lower bounds work under the original sparsity assumption.Let f : X × Z → R be a loss function. The function evaluation f (x, z) represents the loss incurred by hypothesis x ∈ X on datapoint z ∈ Z. In stochastic optimization (SO), we consider a data distribution D, and our goal is to minimize the expected loss under this distributionmin x∈X F D (x) := E z∼D [f (x, z)] .(SO) Throughout, we use x * (D) to denote an optimal solution to (SO), which we assume exists. In the empirical risk minimization (ERM) problem, we consider sample datapoints S = (z 1 , . . . , z n ) and our goal is to minimize the empirical error with respect to the samplemin x∈X F S (x) := 1 n i∈[n] f (x, z i ) . (ERM)We denote by x * (S) an arbitrary optimal solution to (ERM), which we 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 Z be a sample space, and X an output space. A dataset is a tuple S ∈ Z n , and datasets S, S ′ ∈ Z n are neighbors (denoted as S ≃ S ′ ) if they differ in only one of their entries.Definition 2.2 (Differential Privacy). Let A : Z n → X . We say that A is (ε, δ)-(approximately) differentially private (DP) if for every pair S ≃ S ′ , we have for all E ⊆ X that Pr[A(S) ∈ E] ≤ e ε • Pr[A(S ′ ) ∈ E] + δ. When δ = 0, we say that A is ε-DP or pure-DP. 
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 d dimensions as the queries of interest: this way, the ℓ 2 -error on private query answers corresponds exactly to the ℓ 2 -norm estimation error. A key difference to the approach in [9] and related works is that we project the noisy answers onto the setK := B d 1 (0, L √ s), which is a (coarse) convex relaxation of conv(S d s ). This is crucial to make our algorithm efficiently implementable. Due to space limitations, proofs from this section have been deferred to Appendix B.Algorithm 1 Projection_Mechanism(z(S), ε, δ, n) Require: Vector z(S) = 1 n n i=1 z i from dataset S ∈ (S d s ) n ; ε, δ ≥ 0, privacy parameters z = z(S) + ξ, with ξ ∼    Lap(σ) ⊗d with σ = 2L √ s nε if δ = 0 , N (0, σ 2 I) with σ 2 = 8L 2 ln(1.25/δ) (nε) 2 if δ > 0 . return ẑ = argmin{∥z -z∥ 2 : z ∈ K}, where K := B d 1 (0, L √ s) Lemma 3.1. In Algorithm 1, it holds that ∥ẑ -z(S)∥ 2 ≤ 2L∥ξ∥ ∞ √ s, almost surely.We now provide the privacy and accuracy guarantees of Algorithm 1. Theorem 3.2. For δ = 0, Algorithm 1 is ε-DP, and with probability 1 -β:∥ẑ -z(S)∥ 2 ≲ L • min √ sd ln(d/β) nε , s ln(d/β) nε .Theorem 3.3. For δ > 0, Algorithm 1 is (ε, δ)-DP, and with probability 1 -β:∥ẑ -z(S)∥ 2 ≲ L • min ( √ d+ √ log(1/β)) √ ln(1/δ) nε , (s log(1/δ) log(d/β)) 1/4 √ nε .Sharper Upper Bound via Compressed Sensing In Appendix B.4 we propose a 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 a 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 of the stable and noisy recovery properties of compressed sensing [10] , together with the Approximate Carathéodory Theorem. 
lower bounds for dp mean estimation with sparse data: 
 We provide matching lower bounds to those from Section 3. 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 we provide a packing-type construction based on sparse vectors. This is used in a novel block-diagonal construction, which provides the right low/highdimensional transition. On the other hand, for approximate-DP, a block diagonal reduction with existing fingerprinting codes [38, 13] , suffices to obtain lower bounds that exhibit a nearly tight low/high-dimensional transition. For simplicity, we consider the case of L = 1, i.e., S d s = {z ∈ R d : ∥z∥ 0 ≤ s, ∥z∥ 2 ≤ 1}; it is easy to see that any lower bound scales linearly in L. We defer proofs from this section to Appendix C.Our main lower bound for pure-DP mechanisms is as follows.  
bias reduction method for dp-erm with sparse gradients: 
 We now start with our 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, ∥x 0 -x * (D)∥ ≤ D; for ERM, ∥x 0 -x * (S)∥ ≤ D. (A.2) Diameter bound: ∥x -y∥ ≤ D, for all x, y ∈ X . (A.3) Convexity: f (•, z) is convex, for all z ∈ Z. (A.4) Loss range: f (x, z) -f (y, z) ≤ B, for all x, y ∈ X , z ∈ Z. (A.5) Lipschitzness: f (•, z) is L-Lipschitz, for all z ∈ Z. (A.6) Smoothness: ∇f (•, z) is H-Lipschitz, for all z ∈ Z.(A.7) Individual gradient sparsity: ∇f (x, z) is s-sparse, for all x ∈ X and z ∈ Z.The most natural and popular DP optimization algorithms are based on SGD. Here we show how to integrate the mean estimation algorithms from Section 3 to design a stochastic first-order oracle that can be readily used by any stochastic first-order method. The key challenge here is that estimators from Section 3 are inherently biased, which is known to dramatically deteriorate the convergence rates. Hence, we start by introducing a bias reduction method.Algorithm 2 Subsampled_Bias-Reduced_Gradient_Estimator(x, S, N, ε, δ)Require: Dataset S = (z 1 , . . . , z n ) ∈ Z n , ε, δ > 0 privacy parameters, L-Lipschitz loss f (x, z) with s-sparse gradient, x ∈ X , batch size parameter N ∼ TGeom(M ) with M = ⌊log 2 (n)⌋ -1 Let B ∼ Unif n 2 N +1 , O, E a partition of B with |O| = |E| = 2 N , I ∼ Unif([n]) G + N +1 (x, B) = Projection_Mechanism(∇F B (x), ε/4, δ/4, 2 N +1 ) (Algorithm 1) G - N (x, O) = Projection_Mechanism(∇F O (x), ε/4, δ/4, 2 N ) G - N (x, E) = Projection_Mechanism(∇F E (x), ε/4, δ/4, 2 N ) G 0 (x, I) = Projection_Mechanism(∇f (x, z I ), ε/4, δ/4, 1) Return (below p k = P[TGeom(M ) = k]) G(x) = 1 p N G + N +1 (x, B) -1 2 G - N (x, O) + G - N (x, E) + G 0 (x, I) Algorithm 3 Subsampled_Bias-Reduced_Sparse_SGD(x 0 , S, ε, δ) Require: Initialization x 0 ∈ X ; Dataset S = (z 1 , . . . , z n ) ∈ Z n ; ε, δ, privacy parameters; stepsize η > 0; gradient oracle for L-Lipschitz and with s-sparse gradient loss f (•, z) t ← -1 while 2 ln 4 δ t-1 s=0 3•2 Ns+1 +1 16n 2 + ε 2 t-1 s=0 3•2 Ns+1 +1 16n 2 ≤ 1 2 and t-1 s=0 3•2 Ns+1 +1 16n ≤ 1 4 do t ← t + 1 N t ∼ TGeom(M ) where M = ⌊log 2 (n)⌋ -1 G(x t ) = Subsampled_Bias-Reduced_Gradient_Estimator(x t , S, N t , ε/8, δ/4) (Alg. 2) x t+1 = Π X x t -ηG(x t ) end while return x = 1 t+1 t s=0 x s if f (•, z) is convex , x t where t ∼ Unif({0, . . . , T }) iff (•, z) is not convex.We propose Algorithm 2, inspired by a debiasing technique proposed in [14] . The idea is the following: we know that the projection mechanism2 would provide more accurate gradient estimators with larger sample sizes, and we will see that its bias improves analogously. We choose our batch size as a random variable with exponentially increasing range, and given such a realization we subtract the projection mechanism applied to the whole batch minus the same mechanism applied to both halves of this batch. 3 This subtraction, together with a multiplicative and additive correction, results in the expected value of the outcome G(x) corresponding to the estimator with the largest batch size, leading to 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 to the smallest possible one). The caveat with this technique, as we will see, relates to a heavy-tailed distribution of outcomes, and therefore great care is needed for its analysis.Instrumental to our analysis is the following truncated geometric distribution with parameter M ∈ N, whose law will be denoted by TGeom(M ): we say N ∼ TGeom(M ) if it is supported on {0, . . . , M }, and takes value k with probabilityp k := C M /2 k , where C M = (2(1 -2 -(M +1) )) -1 , is the normalizing constant. Note that 1/2 ≤ C M ≤ 1,thus it is bounded away from 0 and +∞.We propose Algorithm 3, which interacts with the oracle given in Algorithm 2. For convenience, we will denote the random realization from the truncated geometric distribution used in iteration t by N t . The idea is 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 to shift by one the termination condition in the algorithm. In particular, our algorithm goes over the reduced privacy budget of (ε/2, δ/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 (ε, δ)-DP.We provide bias and second moment estimates for our debiased estimator of the empirical gradient.In summary, we show that this estimator has bias matching that of the full-batch gradient estimator, while at the same time its second moment is bounded by a mild function of the problem parameters.Lemma 5.2. Let d ≳ nε √ s ln(d/s) √ ln(1/δ). Algorithm 2, enjoys bias and second moment boundsE[G(x) -∇F S (x)|x] ≲ L[s ln(d/s) ln(1/δ)] 1/4 √ nε =: b, E[∥G(x)∥ 2 |x] ≲ L 2 ln(n) √ s ln(d/s) ln(1/δ) ε =: ν 2 .Proof. For simplicity, we assume without loss of generality that n is a power of 2, so that 2 M +1 = n.EQUATIONG - k (x) = E[G - N (x, E) | N = k, x] = E[G - N (x, O) | N = k, x],where the last equality follows from the identical distribution of O and E. Noting further thatG + k (x) = G - k (x)(which follows from the uniform sampling and the cardinality of the used datapoints), and using the law of total probability, we haveE[G(x) | x] = M k=0 G + k (x) -G - k-1 (x) + E[G 0 (x, I) | x] = G + M +1 (x) -G - 0 (x) + E[G 0 (x, I) | x] = E[G + M +1 (x) -∇F S (x)|x] + ∇F S (x),where we also used thatE[G 0 (x, I) | x] = G - 0 (x) (since I is a singleton). Next, by Theorem B.1 ∥E[G(x) | x] -∇F S (x)∥ ≤ ∥E[G + M +1 (x) -∇F S (x)|x]∥ ≲ L [s ln(d/s) ln(1/δ)] 1/4 √ nε .Second moment bound. Using the law of total probability, and that O, E are a partition of B:EQUATIONx, N = k .We now use Theorem B.1, to conclude thatE G + N +1 (x, B) -∇F B (x) 2 x, N = k ≲ L 2 √ s ln(d/s) ln(1/δ) 2 k+1 ε max A∈{O,E} E G - N (x, A) -∇F A (x) 2 x, N = k ≲ L 2 √ s ln(d/s) ln(1/δ) 2 k ε E G 0 (x, I) 2 x ≲ L 2 √ s ln(d/s) ln(1/δ) ε.Recalling that M + 1 = log 2 n and p k = 2 -k , these bounds readily imply that E∥G(x)∥ 2 ≲ ν 2 .The previous results provide useful information about the privacy, bias, and second-moment of our 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., a lower bound on the stopping time of Algorithm 3,T := inf t : ε 2 < ε 2 ln 4 δ t s=0 3•2 Ns +1 +1 16n 2 1/2 + ε 2 2 t s=0 3•2 Ns +1 +1 16n or δ 4 < t s=0 (3•2 Ns +1 +1)δ 16n.(EQUATIONThe proof of Theorem 5.2 implies that moments of G increase exponentially in M . This heavy-tailed behavior implies that T may not concentrate strongly enough to 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ε t = (3 • 2 Nt+1 + 1)ε/[16n],we have thatE t s=0 ε 2 s = (t+1)ε 2 (16n) 2 E (3 • 2 N1+1 + 1) 2 ≤ 2(t+1)ε 2 (16n) 2 9E[2 2(N1+1) ] + 1 ≲ tε 2 n ,where in the last step we used thatE 2 2(N1+1) = C M M +1 k=1 2 k ≲ n.This in-expectation analysis can be used in combination with ideas from stopping times to establish bounds for T . Lemma 5.3. Let 0 < δ < 1/n 2 . Let T be the stopping time defined in eqn. (2). Then, there exists t = Cn/ log(2/δ) (with C > 0 an absolute constant) such that P[T ≤ t] ≤ 1/4. On the other hand,n 2 (n+1) ln(4/δ) -1 ≤ E[T ] ≤ 64n 9 ln(4/δ) .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 a (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 satisfiesP F S (x) -F S (x * (S)) ≲ LD √ ln n[s ln(d/s) ln 3 (1/δ)] 1/4 √ εn ≥ 1 2 .• In the nonconvex case, additionally assuming smoothness (Item (A.6)) and the following initial suboptimality assumption: namely, that given our initialization x 0 ∈ R d , there exists Γ > 0 such that F S (x 0 ) -F S (x * (S)) ≤ Γ; Algorithm 3 satisfiesP ∥∇F S (x t)∥ 2 2 ≲ √ ΓHL ln(n) ln(1/δ) + L 2 [s ln(d/s) ln(1/δ)] 1/4 √ εn ≥ 1 2 .Boosting the Confidence of the Bias-Reduced SGD To conclude, in Appendix F we provide a boosting algorithm that can exponentially amplify the success probability of Algorithm 3. The approach is based on making parallel runs of the method and using private model selection to obtain the best performing model. 
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 a 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 ∥ • ∥ ∞ -projection. This type of projection leverages the concentration of the noise in 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 description is included in Algorithm 4. We defer missing proofs from this section, as well as additional results, to Appendix G.Require:Dataset S = (z 1 , . . . , z n ) ∈ Z n , ε, δ ≥ 0 privacy params., f (•, z) L-Lipschitz convex function (if δ = 0 further assume H-smooth) with s-sparse gradient, λ ≥ 0 regularization param. Let x * λ (S) = argmin x∈X F λ S (x), where F λ S (x) := F S (x) + λ 2 ∥x∥ 2 2 x = x * λ (S) + ξ, with ξ ∼    Lap(σ) ⊗d with σ = 2 √ 2sL λεn 2H λ + 1 if δ = 0 , N (0, σ 2 I) with σ 2 = 8L 2 ln(1.25/δ) [λεn] 2 if δ > 0 . return x = argmin x∈X ∥x -x∥ ∞ (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 (ε, δ)-DP, and it satisfies the following excess risk guarantees, for any 0 < β < 1:• If δ = 0, and under the additional assumption of smoothness (A.6) and unconstrained domain,X = R d , then selecting λ = L 2 H D 2 s log(d/β) εn 1/3, it holds with probability 1 -β thatF S (x) -F S (x * (S)) ≲ L 2/3 H 1/3 D 4/3 s log(d/β) εn 1/3 . • If δ > 0 then selecting λ = L D • [s log(1/δ) log(d/β)] 1/4√ εn, we have with probability 1 -β thatF S (x) -F S (x * (S)) ≲ LD • (s log(1/δ) log(d/β)) 1/4 √ ε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 it is a natural question whether the smoothness assumption is essential. In Appendix G.3, we provide a version of the exponential mechanism that works without the smoothness and unconstrained domain assumptions. This algorithm is inefficient and it does require an structural assumption on the feasible set, but it illustrates the possibilities of more general results in 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 a different tuning of the regularization parameter λ. Theorem 6.3. Consider a problem (SO) under bounded initial distance (Item (A.1)) (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 (ε, δ)-DP, and for 0 < β < 1,• If δ = 0, and under the additional assumption of smoothness (A.6) and unconstrained domain,X = R d . Selecting λ = L 2 H D 2 s log(d/β) εn 1/3, then with probability 1 -βF S (x) -F S (x * (D)) ≲ L 2/3 H 1/3 D 4/3 s log(d/β) εn 1/3 + B ln(1/β) n . • If δ > 0. Selecting λ = L D ln(n) ln(1/β) n + √ s ln(1/δ) ln(d/β) εn 1/2, then with probability 1 -βF D (x) -F D (x * (D)) ≲ LD [s ln(1/δ) log(d/β)] 1/4 √ εn + (LD √ ln n + B) ln(1/β) n .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., [1] ).Fact A.1 (Laplace & Gaussian mechanisms). For all g :Z n → R d (a) If the ℓ 1 -sensitivity of g is bounded, i.e., ∆ g 1 := sup S≃S ′ ∥g(S) -g(S ′ )∥ 1 < +∞, then A g Lap (S) := g(S) + ξ where ξ ∼ Lap ⊗d (∆ g 1 /ε) is ε-DP. (b) If the ℓ 2 -sensitivity of g is bounded, i.e., ∆ g 2 := sup S≃S ′ ∥g(S) -g(S ′ )∥ 2 < +∞, then A g N (S) := g(S) + ξ, where ξ ∼ N 0, σ 2 I for σ ≥ ∆ g 2 √ 2 log(1.25/δ) ε is (ε, δ)-DP. Fact A.2 (Laplace & Gaussian concentration). Let σ > 0 and 0 < β < 1. (a) For ξ ∼ Lap(σ) ⊗d : (i) ∥ξ∥ ∞ ≲ σ log(d/β) holds with probability 1 -β, and (ii) ∥ξ∥ 2 ≲ σ √ d log(d/β) holds with probability 1 -β. (b) For ξ ∼ N (0, σ 2 I), (i) ∥ξ∥ ∞ ≲ σ log(d/β) holds with probability 1 -β, (ii) ∥ξ∥ 2 ≲ σ √ d + log(1/β) holds with probability 1 -β, and (iii) E∥ξ∥ 2 2 = dσ 2 .We note the existence of packing sets of sparse vectors (e.g., [39, 40] ). Denote byC d s the set of all s-sparse vectors in {0, 1/ √ s} d ; note that C d s ⊆ S d s . Lemma A.3. For all s and d such that s ≤ d/2, there exists a subset P ⊆ C d s such that |P| ≥ (d/s -1/2) s/2 and for all u, v ∈ P, it holds that ∥u -v∥ 2 ≥ 1/ √ 2.Proof. This follows from a simple packing-based construction (see, e.g., [40] ). There are 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 an exact sparsity pattern.Lemma A.4 (Dataset bootstrapping argument from [8] ). Suppose for some n, there exists a mechanism A such that for all S ∈ (S d s ) n , it holds with probability at least 1/2 that ∥A(S) -z(S)∥ 2 ≤ C, for some C ≥ 0. Then for all n * < n, there exists a mechanism A ′ such that for all S ′ ∈ (S d s ) n * , it holds with probability at least 1/2 that ∥A(S ′ ) -z(S ′ )∥ 2 ≤ C n n * . Furthermore, A ′ satisfies the same privacy guarantees as A, namely if A is ε-DP (or (ε, δ)-DP), then so is A ′ . Proof. Given mechanism A, consider mechanism A ′ that for any dataset S ′ ∈ (S d s ) n * , builds dataset S by adding n -n * copies of 0 to S ′ and returns n n * A(S). From the guarantees of A, it holds thatP [∥A(S) -z(S)∥ 2 ≤ C] ≥ 1 2 . Since A ′ (S ′ ) = n n * A(S) and z(S ′ ) = n n * z(S), it follows that P ∥A ′ (S ′ ) -z(S ′ )∥ 2 ≤ C n n * ≥ 1 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 we state work on the distributional sense.Lemma A.5 (Packing-based mean estimation lower bound, adapted from [12, 8] ). Let P ⊆ R d be an α 0 -packing set of vectors with |P| = p. Then, there exists a distribution µ over P n that induces an (α, ρ)-distributional lower bound for ε-DP mean estimation with α = α0 2 min 1, log(p/2) εn and ρ = 1/2.Proof. Let n * = log(p/2) ε . First, consider the case where n < n * . We construct p datasets S 1 , . . . S p where S l consists of n copies of z l , and define µ = Unif({S 1 , . . . , S p }). Note that for all k ̸ = l, it holds that ∥z(S k ) -z(S l )∥ 2 ≥ α 0 . Suppose µ does not induce a distributional lower bound. Then there exists A which is ε-DP and has ℓ 2 -accuracy better than α 0 /2 w.p. at least 1/2: this implies in particular thatP l∼Unif([p]) A(S l ) ∈ B d 2 (z l ), α0 2 ) ≥ 1 2 .For all distinct k, l, the datasets S k and S l differ in all n entries, and hence for any ε-DP mechanism A, it holds thatEQUATION2 )] ≥ 1 2 e -εn . However, by construction,EQUATION2 ) are pairwise disjoint. Hence,1 ≥ p k=1 P S∼µ [A(S) ∈ B d 2 (z k , α 0 /2)] = p j=1 p k=1 P S∼µ [A(S) ∈ B d 2 (z k , α 0 /2)|S = z j ] 1 p ≥ e -εn p p j=1 p k=1 P S∼µ [A(S) ∈ B d 2 (z k , α 0 /2)|S = z k ] ≥ e -εn p 2 .Thus, we get that n ≥ log(p/2) ε , which is a contradiction since we assumed n < n * . Hence, µ induces an (α 0 /2, 1/2)-distributional lower bound for ε-DP mean estimation. Next, consider the case where n > n * . Then the previous argument together with Lemma A.4 implies an (α, ρ)-lower bounded, where α = n * 2n and ρ = 1/2, as 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 ((ε, δ)-DP Filter, [15] ). Suppose (A t ) t≥0 is a sequence of algorithms such that, for any t ≥ 0, A t is (ε t , δ t )-DP, conditionally on (A 0:t-1 ) (in particular, (ε t , δ t ) t is (A t ) t -predictable). Let ε > 0 and δ = δ ′ + δ ′′ be the target privacy parameters such that δ ′ > 0, δ ′′ ≥ 0. Letε [0:t] := 2 ln 1 δ ′ t s=0 ε 2 s + 1 2 t s=0 ε 2 s , and δ [0:t] := t s=0 δ s ,and define the stopping timeT ((ε t , δ t ) t ) := inf t : ε < ε [0:t+1] ∧ inf t : δ ′′ < δ [0:t+1] .Then, the algorithmA 0:T (•) (•) is (ε, δ)-DP, where T (x) = T (ε t (x), δ t (x) t≥0 .B Missing Proofs from Section 3B.1 Proof of Lemma 3.1Proof. From the properties of the Euclidean projection, we haveEQUATIONHence,EQUATION≤ ⟨ẑ -z(S), ξ⟩≤ 2 • max u∈K ⟨u, ξ⟩ ≤ 2 • max u∈K ∥u∥ 1 • ∥ξ∥ ∞ = 2L∥ξ∥ ∞ √ s,where we used the fact that conv(S d s ) ⊆ K.Proof. First, the privacy follows from the ℓ 1 -sensitivity bound of the empirical mean∆ 1 = sup S≃S ′ ∥z(S) -z(S ′ )∥ 1 = 1 n sup z,z ′ ∈S d s ∥z -z ′ ∥ 1 ≤ 2L √ sn , together with Theorem A.1(a).For the accuracy, the first term follows from Theorem A. We propose Algorithm 5, a more accurate method for approximate-DP mean estimation based on compressed sensing [10] . The precise improvements relate to reducing the log(d) factor to log(d/s), and a faster rate dependence on the confidence β. The idea is that for sufficiently high dimensions, a small number of random measurements suffices to estimate a noisy and approximately sparse signal. These properties follow from existing results in compressed sensing, which provide guarantees based on the ℓ 2 -norm of the noise, and the best sparse approximation in the ℓ 2 -norm (known as ℓ 2 -ℓ 2 -stable and noisy recovery) [10] . We will exploit such robustness in two ways: regarding the noise robustness, this property is used in order to perturb our measurements, which will certify the privacy; on the other hand, the approximate recovery property is used to find a 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 a sparse vector whose sparsity increases more moderately with n than the empirical average [11] .An interesting feature of this algorithm is that ℓ 1 -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 ℓ 1minimization problem does not require exact optimality for the privacy guarantee, hence approximate solvers can be used without compromising privacy.Algorithm 5 Gaussian ℓ 1 -Recovery(z(S), ε, δ, n)Require: z(S) = 1 n i∈[n] z i ∈ R d from dataset S ∈ (S s,d ) n ; privacy parameters ε, δ > 0 m ≂ nε s ln(d/s) ln(1/δ) return ẑ =        z(S) + ξ, where ξ ∼ N (0, σ 2 I d×d ) and σ 2 = 8L 2 ln(1.25/δ) (nε) 2 , if d < m ln 2 m, z • 1{∥z∥ 2 ≤ 2L}, where z = arg min{∥z∥ 1 : Az = b}, A ∼ (N (0, 1 m )) m×d , b = Az(S) + ξ and ξ ∼ N (0, σ 2 I m×m ) with σ 2 = 18L 2 ln(2.5/δ) (nε) 2 , otherwise Theorem B.1. If 6 exp{-cm} ≤ δ < s ln(d/s) m 2(where c > 0 is a constant) and 0 < ε ≤ 1, then Algorithm 5 is (ε, δ)-DP, and with probability 1 -δ/2 -β,EQUATIONMoreover, we have the following second moment estimate,E[∥ẑ -z∥ 2 2 ] ≲ L 2 min d ln(1/δ) (nε) 2 , s ln(d/s) ln(1/δ) nε .Proof. First, if d < m ln 2 m, then Algorithm 5 is (ε, δ)-DP by privacy of Gaussian noise addition and the post-processing property of DP. Moreover, its (high probability and second moment) accuracy guarantees follow from Theorem A.2.Next, if d ≥ m ln 2 m, we start with the privacy analysis. Let S ≃ S ′ and suppose they only differ in their ith entry. We note that due to our choice of m, A is an approximate restricted isometry with probability 1 -3 exp{-cm} [41] (where c is the same as in the theorem statement); in particular, letting K ≂ , we have that for all v ∈ R d which is (sK)-sparse1 2 ∥v∥ 2 ≤ ∥Av∥ 2 ≤ 3 2 ∥v∥ 2 .Hence, due to our assumption on δ, the event above has probability at least 1 -δ/2, and therefore∥A(z -z′ )∥ 2 = 1 n ∥A(z i -z ′ i )∥ 2 ≤ 3L n ,where we used the fact that z i -z ′ i is (2s)-sparse. We conclude by the choice of σ 2 that Az + ξ is (ε, δ)-DP, and thus z is (ε, δ)-DP 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 1 -δ/2) we have∥ẑ -z∥ 2 ≲ ∥ξ∥ 2 + inf z: ∥z∥0≤sK ∥z -z∥ 2 .For the first term, we use Gaussian norm concentration to guarantee that with probability 1 -β,∥ξ∥ 2 ≲ √ m + ln(1/β) σ ≲ Ks ln(d/s) + ln 1 β L ln(1/δ) nε .For the second term, by the Approximate Carátheodory Theorem [11] , the infimum above is upper bounded by O(L/ √ K); for this, note that z lies in the convex hull of S d s . Given our choice of K, we have that, with probability1 -δ/2 -β ∥ẑ -z∥ 2 ≲ L [s ln(d/s) ln(1/δ)] 1/4 √ nε + ln(1/β) ln(1/δ) nε .We conclude by providing the second moment estimate, by a simple tail integration argument. First, by the law of total probability, and letting E be the event of A being an approximate restricted isometry,E∥ẑ -z∥ 2 2 ≤ E[∥ẑ -z∥ 2 2 |E] + 9L 2 δ, where we also used that ∥ẑ∥ 2 ≤ 2L and ∥z∥ 2 ≤ L, almost surely. Now, conditionally on E, we havethat letting α ≂ L [s ln(d/s) ln(1/δ)] 1/4 √ nε (below c > 0 is an absolute constant), E[∥ẑ -z∥ 2 2 |E] = ∞ 0 P ∥ẑ -z∥ 2 ≥ u (2u)du ≤ α 2 2 + ∞ 0 P ∥ẑ -z∥ 2 -α ≥ τ 2(α + τ )dτ ≤ α 2 2 + ∞ 0 2 exp - c(nε) 2 L 2 ln(1/δ) τ 2 (α + τ )dτ ≲ α 2 2 + 2αL ln(1/δ) nε + L 2 ln(1/δ) (nε) 2 ≲ α 2 ,where in the second inequality we used the previous high probability upper bound (here c > 0 is an absolute constant), and in the last step we used that nε > ln(1/δ). Finally, by our assumptions on δ, 9L 2 δ ≲ α 2 , and this concludes the proof.C.1 Proof of Lemma 4.3Proof. Consider an n × d data matrix D whose rows correspond to datapoints of a dataset S, and whose columns correspond to their d features. We will indistinctively refer to S or D as needed (these are equivalent representations of a dataset). This data matrix will be comprised of K diagonal blocks, D 1 , . . . , D K ; in particular, outside of these blocks, the matrix has only zeros. These blocks are sampled i.i.d. from the hard distribution µ given by hypothesis. Denote μ the law of D.Let now zk (D k ) ∈ R t be the mean (over rows) of dataset D k . Then, the mean (over rows) of dataset D is given by z(D) = n0 n z1 (D 1 ) . . . zK (D K ) , where [z 1 | . . . |z K ] ∈ R d denotes the concatenation of z 1 , . . . , z K (note that if K < d/t, then the concatenation above needs to be padded with (d -tK)-zeros, which we omit for simplicity).A be an (ε, δ)-DP algorithm, and let A k its output on the kth block variables, thenEQUATION. Let now B k (D) := n n0 A k (D),k := 1 {∥B k (D)-z k (D k )∥2≥α0} , we have P ∥A(D) -z(D)∥ 2 2 ≥ α 0 n 0 n 2 ρ 0 K 2 ≥ P K k=1 Y k ≥ ρ 0 K 2 .We will now use a coupling argument to lower bound the probability above. First, we let U 1 , . . . , U K i.i.d.∼ Unif([0, 1]), and W k = 1 {Ui≥ρ0} which are i.i.d. On the other hand, we definep k (y 1 , . . . , y k-1 ) := P[Y k = 1|Y 1 = y 1 , . . . , Y k-1 = y k-1 ] Ỹk := 1 {U k ≥p k ( Ỹ1,..., Ỹk-1 )} .Noting that Y d = Ỹ , and that Ỹk ≥ W k almost surely, due to the fact that p k ≥ ρ 0 almost surely (which it follows from the ℓ 2 -error argument discussed above), we haveP K k=1 Y k ≥ ρ 0 K 2 = P K k=1 Ỹk ≥ ρ 0 K 2 ≥ P K k=1 W k ≥ ρ 0 K 2 ≥ 1 -exp(-ρ 0 /8),where we used a one-sided multiplicative Chernoff bound.Therefore, ∥A(D) -z(D)∥ . Let n 0 = s ln(1/δ)/ε, t = s, and K = n n0 ≲ d s , where the last inequality holds by our regime assumption. The classic sdimensional mean estimation lower bound by [42] provides an α 0 ≳ 1 lower bound with constant probability. Hence by Lemma 4.3, the sparse mean estimation problem satisfies a lower boundΩ α0n0 n √ K ≳ 1 √ K ≳ (s ln(1/δ)) 1/4 √ εn, with constant probability.We conclude with the final range, n≳ d √ ln(1/δ) √ sε . First, letting n * ≂ d √ ln(1/δ) √ sε, we note that this sample size falls within the range of the previous analysis, which implies a lower bound with constant probability of (s ln(1/δ)) 1/4 ε √ n * ≳ √ s √ d . Now, if n > n * ,Given the heavy-tailed nature of our estimators, our guarantees for a single run of SGD with biasreduced first-order oracles only yields constant probability guarantees. Here we prove pathwise bounds that facilitate such analyses.First, we provide a path-wise guarantee for a run of SGD with a biased oracle. Importantly, this guarantee is made of a method which runs for a random number of steps.Proposition D.1. Let (F t ) t be the natural filtration, and T be a random time. Let (x t ) t be the trajectory of projected SGD with deterministic stepsize sequence (η t ) t , and (biased) stochastic first-order oracle G for a given function F . If x * ∈ arg min{F (x) : x ∈ X }, then the following event holds almost surelyT t=0 [F (x t ) -F (x * )] ≤ 1 2η t ∥x 0 -x * ∥ 2 + T t=0 η t 2 ∥G(x t )∥ 2 + ⟨∇F (x t ) -G(x t ), x t -x * ⟩ .Proof. By convexityF (x t ) -F (x * ) ≤ ⟨∇F (x t ), x t -x * ⟩ = ⟨∇F (x t ) -G(x t ), x t -x * ⟩ :=bt +⟨G(x t ), x t -x * ⟩ ≤ b t + ⟨G(x t ), x t -x t+1 ⟩ + ⟨G(x t ), x t+1 -x * ⟩ ≤ b t + η t 2 ∥G(x t )∥ 2 + 1 2η t ∥x t -x t+1 ∥ 2 + ⟨∇G(x t ), x t+1 -x * ⟩ ( * ) ≤ b t + η t 2 ∥G(x t )∥ 2 + 1 2η t ∥x t -x t+1 ∥ 2 + 1 η t ⟨x t+1 -x t , x * -x t+1 ⟩ = b t + η t 2 ∥G(x t )∥ 2 + 1 2η t ∥x t -x * ∥ 2 - 1 2η t ∥x t+1 -x * ∥ 2 ,where the second inequality follows by the Young inequality, and step ( * ) we used the optimality conditions of the projected SGD step:⟨η t G(x t ) + [x t+1 -x t ], x -x t+1 ⟩ ≥ 0 (∀x ∈ X ).Therefore, summing up these inequalities, we obtainT t=0 [F (x t ) -F (x * )] ≤ 1 2η 0 ∥x 0 -x * ∥ 2 + T t=0 η t 2 ∥G(x t )∥ 2 + b t .Plugging in the definition of b t proves the result.Proposition D.2. Let F satisfy (A.6), and let G be a biased first-order stochastic oracle for F . (x t ) t the trajectory of SGD with oracle G, constant stepsize 0 < η ≤ 1/[2H], and initializationx 0 such that F (x 0 ) -min x∈R d F (x) ≤ Γ.Let T be a random time. Then the following event holds almost surelyT t=0 ∥∇F (x t )∥ 2 2 ≤ Γ η + ηH 2 T t=0 ∥G(x t )∥ 2 2 - T t=0 ⟨∇F (x t ), G(x t ) -∇F (x t )⟩Proof. By smoothness of f , we haveF (x t+1 ) -F (x t ) ≤ -η⟨∇F (x t ), G(x t )⟩ + η 2 H 2 ∥G(x t )∥ 2 2 ≤ -η∥∇F (x t )∥ 2 2 -η⟨∇F (x t ), G(x t ) -∇F (x t )⟩ + η 2 H 2 ∥G(x t )∥ 2 2 .Therefore,T t=0 ∥∇F (x t )∥ 2 2 ≤ F (x 0 ) -F (x T +1 ) η - T t=0 ⟨∇F (x t ), G(x t ) -∇F (x t )⟩ + ηH 2 T t=0 ∥G(x t )∥ 2 2 ≤ Γ η - T t=0 ⟨∇F (x t ), G(x t ) -∇F (x t )⟩ + ηH 2 T t=0 ∥G(x t )∥ 2 2 .E Missing proofs from Section 5E.1 Proof of Lemma 5.1Proof. The proof is based on the fully adaptive composition theorem of DP [15] . For this, we consider {A t } t≥0 , where A 0 (S) = (x 0 , N 0 ) (here N 0 the first truncated geometric parameter), and inductively, A t+1 (A t (S), S) for t ≥ 0 takes as input A t (S) = (x t , N t ), computes G(x t ) using the subsampled debiased gradient estimator (Algorithm 2), and performs a projected gradient step based on G(x t ). Let H t be the σ-algebra induced by (A s ) s=0,...,t .Suppose now that A t is (ε t , δ t )-DP, where (ε t , δ t ) are H t -measurable (we will later obtain these parameters), and let T := inf{t : ε [0:t] > ε/2, δ [0:t] > δ/2}, in the language of Theorem A.6 (notice that in the context of that theorem, we are choosing δ ′ = δ ′′ = δ/4). We first claim that (x t ) t=0,...,T -1 is (ε/2, δ/2)-DP, which follows directly from Theorem A.6. Next, we will later show that ε t ≤ ε/4 and δ t ≤ δ/4, almost surely (this applies in particular to x T ), and therefore by the composition property of DP, (x t ) t≤T is (ε, δ)-DP.Next, we provide the bounds on (ε t , δ t ) required to conclude the proof. For this, we first note thatconditionally x t , N t and B t -the computation ofG + Nt+1 (x t , B t ), G - Nt (x t , O t ), G - Nt (x t , E t ), is (3ε/32, 3δ/16)-DP. Furthermore, by privacy amplification by subsampling, this triplet of random variables is (ε ′ , δ ′ ), withε ′ = ln 1 + 2 Nt+1 n (e 3ε/32 -1) ≤ 2 Nt+1 n 3ε 16 , δ ′ = 2 Nt+1 n 3δ 16 ,where we used above that ε ≤ 1. Similarly, we have that G 0 (x, I) is ε 16n , δ 16n -DP. Therefore, by the basic composition theorem of DP, we have the following privacy parameters for the tth iteration of the algorithmε t = (3 • 2 Nt+1 + 1) ε 16n , δ t = (3 • 2 Nt+1 + 1) δ 16n .This proves in particular that (ε t , δ t ) are H t -measurable, and that ε t ≤ ε/4, and δ t ≤ δ/4 almost surely, which concludes the proofEQUATION2 , and note that for t ≤ T + 1, A ≤ 1 almost surely. Then, we have thatε [0:t-1] = 2 ln(4/δ)ε 2 A + ε 2 2 A ≤ 2ε 2 ln(4/δ)A.Now, by eqn. ( 2) and the union bound,P[T ≤ t] ≤ P 2ε 2 ln(4/δ)A > ε/2 + P t-1 s=0 (3 • 2 Nt+1 + 1) > 4n ≤ P t-1 s=0 3 • 2 Nt+1 + 1 2 > 32n 2 ln 4 δ + P t-1 s=0 (3 • 2 Nt+1 + 1) > 4n ≤ t ln 4 δ 16n 2 9E[2 2(Nt+1) ] + 1 + t 4n [6(M + 1) + 1] ≤ t ln 4 δ 16n 2 [18n + 1] + t 4n [6 log(n) + 1]≤ 1/4, where the third step follows from Markov's inequality and the fact that (N s ) s are i.i.d., and the last step follows from our choice of t = Cn/ log(4/δ) with C > 0 sufficiently small (here we use the fact that δ < 1/n 2 ).For the second part, we use that by the definition of T (eqn. ( 2))ε 2 < 2ε 2 ln 4 δ T s=0 (3 • 2 Ns+1 + 1) 2 (16n) 2 + ε 2 2 T s=0 (3 • 2 Ns+1 + 1) 2 (16n) 2 ∨ 1 4 < T s=0 3 • 2 Ns+1 + 1 16n =⇒ n 2 < max 8 ln 4 δ T s=0 (3 • 2 Ns+1 + 1) 2 (16) 2 , n T s=0 3 • 2 Ns+1 + 1 4Taking expectations and bounding the maximum by the sum allows us to use Wald's identity as follows,n 2 < E[T + 1] 8 ln 4 δ 2(9n + 1) 16 2 + n 3 log(n) + 1 4 ≤ E[T + 1] ln 4 δ (n + 1),which proves the claimed bound.The upper nound on E[T ] is obtained similarly. Again, by eqn. (2),32n 2 ln(4/δ) ≥ E T -1 s=0 3 • 2 Ns+1 + 1) 2 ≥ E[T ] 9n 2 .Re-arranging terms provides the claimed lower bound.As a 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, namelyR T := T t=0 [F S (x t ) -F S (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 T is a stopping time, the event {T ≥ t} is F t-1 -measurable (here and throughout, F t = σ((x s ) s≤t ) is the natural filtration). This permits using our bias and second moment bounds similarly to the case where T is deterministic. 5 Moreover, for the sake of analysis, we will consider Algorithm 3 as running indefinitely, for all t ≥ 0. This would of course eventually violate privacy. However, since our algorithm stops at time T , then privacy is guaranteed as done earlier in this section. Proposition E.1. Let R t := t t=0 [F S (x t ) -F S (x * (S))], let T be the stopping time defined in eqn. (2) . ThenE[R T ] ≤ 1 2η ∥x 0 -x * (S)∥ 2 + E[T + 1] ην 2 2 + Db ,where b and ν 2 are defined as in Lemma 5.2.Proof. By Proposition D.1 (see Appendix D),E[R T ] ≤ E 1 2η ∥x 0 -x * (S)∥ 2 + T t=0 η 2 ∥G(x t )∥ 2 + ⟨∇F (x t ) -G(x t ), x t -x * (S)⟩ = E 1 2η ∥x 0 -x * (S)∥ 2 + ∞ t=0 η 2 E[1 {T ≥t} ∥G(x t )∥ 2 |F t-1 ] + E[1 {T ≥t} ⟨∇F (x t ) -G(x t ), x t -x * (S)⟩|F t-1 ] = E 1 2η ∥x 0 -x * (S)∥ 2 + ∞ t=0 η1 {T ≥t} 2 E[∥G(x t )∥ 2 |F t-1 ] + 1 {T ≥t} E[⟨∇F (x t ) -G(x t ), x t -x * (S)⟩|F t-1 ]where in the first equality we used the tower property of the conditional expectation, and in the second equality we used that{T ≥ t} = {T ≤ t -1} c is F t-1 -measurable. Now, by Lemma 5.2, E[⟨∇F (x t ) -G(x t ), x t -x * (S)⟩|F t-1 ] ≤ Db and E[∥G(x t )∥ 2 |F t-1 ] ≤ ν 2(note that F t-1 does not include the randomness of N t , and therefore the bias and moment estimates as in the mentioned lemma hold), thusE[R T ] ≤ 1 2η ∥x 0 -x * (S)∥ 2 + E[T + 1] ην 2 2 + Db .We conclude with the constant probability guarantee for the biased and randomly stopped SGD, Algorithm 3.Theorem E.2. Consider a (SO) problem under convexity (Item (A.3)), initial distance (Item (A.1)), Lipschitzness (Item (A.5)) and gradient sparsity (Item (A.7)) assumptions. Let τ = C ′ n ln(2/δ) , whereC ′ > 0 is an absolute constant. Let η = D ν √ τ , U = CD[ν √ τ + bτ ],where C > 0 is an absolute constant. Then Algorithm 3 satisfiesP F S (x) -F S (x * (S)) ≤ U τ ≥ 1/2.Proof. We start by noting thatP F S (x) -F S (x * (S)) > U τ ≤ P {T ≤ τ } ∪ {R T > U } ≤ P T ≤ τ ] + P[R T > U ].For the first event, by Lemma 5.3, we have that P[T ≤ τ ] ≤ 1/4 (which determines C ′ ). On the other hand, using Proposition E.1 and Lemma 5.3, we have that for our choice of η, we have thatE[R T ] ≤ Dν √ τ 2 + E[T + 1]D ν 2 √ τ + b ≲ √ τ + τ b].In particular, for our choice of U (with C > 0 sufficiently large),EQUATIONThe above result implies a nearly optimal empirical excess risk rate for DP-SCO,O LD √ ln n[s ln(d/s) ln 3 (1/δ)] 1/4 √ εn ,but only with constant probability. We defer to the next section how to boost this guarantee to hold with arbitrarily high probability.For nonconvex objectives it is known that obtaining vanishing excess risk is computationally difficult. Hence, we 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 can establish bounds on the success probability of the algorithm.Theorem E.3. Consider a (nonconvex) (SO) problem, under the following assumptions: Lipschitzness (Item (A.5)), smoothness (Item (A.6)), gradient sparsity (Item (A.7)), and the following initial suboptimality assumption: namely, that given our initialization x 0 ∈ R d , we know Γ > 0 such thatEQUATIONLet τ = C ′ n ln(2/δ) with C ′ > 0 an absolute constant. Let η = Γ Htν 2 and U = C √ ΓHτ ν + Lτ bwith C > 0 an absolute constant. Then Algorithm 3 satisfies P ∥∇F S (x t)∥ 2 2 ≤ U τ ≥ 1/2, andU τ ≲ √ ΓHL ln(n) ln(1/δ) + L 2 [s ln(d/s) ln(1/δ)] 1/4 √ εn .Proof. First, given any U > 0, we have thatP ∥∇F S (x t)∥ 2 > U τ ≤ P[T < τ ] + P[T ∥∇F S (x t)∥ 2 2 > U ] ≤ 1 4 + E[T ∥∇F S (x t)∥ 2 2 ] U ,where the last step follows by Lemma 5.3 and Chebyshev's inequality, respectively. Next, by definition of t and Proposition D.2 (see Appendix D.2),E[(T + 1)∥∇F (x t)∥ 2 2 ] = E T t=0 ∥∇F (x t )∥ 2 2 ≤ Γ η + ηH 2 E T t=0 ∥G(x t )∥ 2 2 -E T t=0 ⟨∇F (x t ), G(x t ) -∇F (x t )⟩ ≤ Γ η + ηH 2 ∞ t=0 E[1 {T ≥t} ∥G(x t )∥ 2 2 ] - ∞ t=0 E[1 {T ≥t} ⟨∇F (x t ), G(x t ) -∇F (x t )⟩] ≤ Γ η + ηH 2 ∞ t=0 P[T ≥ t]E E[∥G(x t )∥ 2 2 |F t-1 ] - ∞ t=0 P[T ≥ t]E E[⟨∇F (x t ), G(x t ) -∇F (x t )|F t-1 ⟩] ≤ Γ η + ηH 2 E[T + 1]ν 2 + E[T + 1]Lb ≲ √ ΓHτ ν + τ Lb,where the third inequality holds since {T ≥ t} is F t-1 -measurable (see the proof of Theorem E.1 for details), and the fourth inequality follows from Theorem 5.2, used the upper bound on E[T ] from Lemma 5.3, and our choice for η.Selecting U = C √ ΓHτ ν + Lτ b with C > 0 sufficiently large, we get E[T ∥∇F (x t)∥ 22 ]/U ≤ 1/4, concluding the proof.We conclude by providing a boosting method to amplify the success probability of our bias-reduced method. This private boosting method is a particular instance of a 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] . Proof. The privacy analysis follows easily from [17] . First, by basic composition, we have that for each k the pair (x k , s k ) is (ε 1 , δ 1 )-DP, with ε 1 = ε/6, and δ 1 = (δ/[4K]) 2 . By [17, Thm 3.4] , the private selection with random stopping used in Algorithm 6 is such that x is (3ε1 + 3 √ 2δ 1 , √ 2δ 1 K + δ/2)-DP; notice that 3ε 1 + 3 2δ 1 ≤ ε 2 + 3 √ 2 δ K ≤ ε,and 2δ 1 K + δ/2 ≤ δ, due to our choices of ε 1 , δ 1 . This proves that the algorithm is (ε, δ)-DP.The accuracy of the algorithm closely follows [17, Theorem 3.3] . First, let κ be the number of runs the algorithm makes before stopping, and let α > 0 to be determined. Conditioning on κP F S (x) -F S (x * (S)) > α = K k=1 P F S (x) -F S (x * (S)) > α κ = k P[κ = k] = K k=1 P F S (x) -F S (x * (S)) > α κ = k (1 -γ) k-1 γ.We will now bound the conditional probability above. By the subexponential tails of the Laplace distribution, we have that lettingE := {(∀j ∈ [κ]) : |ξ j | ≤ α ′ } (here, α ′ > 0 is arbitrary), P[E c |κ = k] = P (∃j ∈ [κ]) |ξ k | > α ′ κ = k ≤ 2k exp - nεα ′ 12B.HenceP F S (x) -F S (x * (S)) > α κ = k ≤ P F S (x) -F S (x * (S)) > α ∩ E κ = k + P[E c |κ = k].Next we haveP F S (x) -F S (x * (S)) > α ∩ E κ = k ≤ P F S (x k) + ξ k -F S (x * (S)) > α -α ′ ∩ E κ = k = P min k∈[κ] F S (x k ) + ξ k -F S (x * (S)) > α -α ′ ∩ E κ = k ≤ P min k∈[κ] F S (x k ) -F S (x * (S)) > α -2α ′ κ = k ≤ P F S (x 1 ) -F S (x * (S)) > α -2α ′ k ,where in the last step we used that the runs are i.i.d.We now choose α, α ′ such that α -2α ′ = U/τ (where U, τ are those from Theorem E.2). Hence,P F S (x) -F S (x * (S)) > α κ = k ≤ 2 -k + 2k exp - nεα ′ 12B .We can now bound the failure probability as follows:P F S (x) -F S (x * (S)) > α ≤ K k=1 2 -k + 2K exp - nεα ′ 12B (1 -γ) k-1 γ = 1 2 γ 1 -γ 2 + 2 γ ln 2 δ exp - nεα ′ 12B ≤ β 2 + 2 γ ln 2 δ exp - nεα ′ 12B ,where in the last step we used that γ = min{1/ For the nonconvex case, we need to replace B by 2L in the Laplace concentration bound. Further, we consider the event {∥∇F (x k )∥ 2 > α} (as opposed to the optimality gap event). This implies that we need to set α > 0 such that α -2α ′ ≥ U/τ from Theorem E.3. This leads toP ∥F S (x)∥ 2 > α ≤ K k=1 2 -k + 2K exp - nεγ 24L (1 -γ) k-1 γ.The rest of the derivations are analogous.G Missing Proofs and Results from Section 6G.1 Proof of Theorem 6.1Proof. We proceed by cases:• Case δ = 0. First, we prove that privacy of the algorithm. To do this, we first establish a bound on the ℓ 1 -sensitivity of the (quadratically) regularized ERM. Note that the first-order optimality conditions in this case correspond tox * λ (S) = - 1 λ ∇F S (x * λ (S)).Therefore, if S ≃ S ′ , where S = (z 1 , . . . , z n ) and S = (z ′ 1 , . . . , z ′ n ) only differ in one entry,∥x * λ (S) -x * λ (S ′ )∥ 1 ≤ 1 λ ∥∇F S (x * λ (S)) -∇F S ′ (x * λ (S ′ ))∥ 1 ≤ 1 λn n i=1 ∥∇f (x * λ (S), z i ) -∇f (x * λ (S ′ ), z ′ i )∥ 1 ≤ 1 λn (n -1) √ 2sH∥x * λ (S) -x * λ (S ′ )∥ 2 + 2 √ 2sL ≤ 1 λn 4 √ 2sHL n -1 λn + 2 √ 2sL ≤ 2 √ 2sL λn 2H λ + 1 .Above, in the third inequality we used the gradient sparsity (A.7), and the smoothness (A.6), assumptions. In the fourth inequality we used that the regularized ERM has ℓ 2 -sensitivity 4L λn [44, 45, 46] . We conclude the privacy then by Theorem A.1(a).We also remark that by Theorem A. , with probability 1 -β.We continue with the accuracy analysis, making a unified presentation for both pure and approximate-DP. First, by the optimality conditions of the regularized ERM,EQUATION)We need the following key fact, which follows by the definitions of x and x,EQUATIONUsing these two bounds, we proceed as followsF S (x) -F S (x * (S)) ≤ F S (x) -F S (x * λ (S)) + λ 2 D 2 ≤ ⟨∇F S (x), x -x * λ (S)⟩ + λ 2 D 2 ≤ ∥∇F S (x)∥ 1 ∥x -x * λ (S)∥ ∞ + λ 2 D 2 ≤ √ 2sL∥ξ∥ ∞ + λ 2 D 2 ,where the second inequality follows by convexity of F S , and the fourth one by the gradient sparsity assumption and (7) .The conclusion follows by plugging in the respective bounds of λ and ∥ξ∥ ∞ , for both pure-and approximate-DP cases.G.2 Proof of Theorem 6.3Remark 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 proof below-using the 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 -β over the algorithm internal randomnessE S [F D (x) -F D (x * (D))] ≲ L 2/3 H 1/3 D 4/3 s log(d/β) εn 1/3 , E S [F D (x) -F D (x * (D))] ≲ LD [s ln(1/δ) log(d/β)] 1/4 √ εn .Proof. Using the ℓ 2 -sensitivity of x * λ (S), ∆ 2 = 4L λn , we have the following generalization bound [47] : with probability 1 -β/2F D (x * λ (S)) -F S (x * λ (S)) ≲ L 2 λn ln(n) ln 1 β + B ln 1 β n =: γ.The bound of ( 6) can be obviously modified by comparison with the population risk minimizer, x * (D): in particular, the event above 6 implies thatF D (x * λ (S)) -F D (x * (D)) ≲ F S (x * λ (S)) -F S (x * (D)) + γ ≤ λ 2 ∥x * (D)∥ 2 2 + γ ≲ λD 2 + γ.On the other hand, the bound (7) works exactly as in the proof of Theorem 6.1. Hence, we have that with probability 1 -β/2,F D (x) -F D (x * (D)) ≲ F D (x) -F D (x * λ (S)) + λD 2 + γ ≲ ⟨∇F D (x), x -x * λ (S)⟩ + λD 2 + γ ≲ 2L √ s∥ξ∥ ∞ + L 2 λn ln(n) ln 1 β + λD 2 + B √ n ln 1 β ,where in the last step we used that ∥∇FEQUATIONthe last step which follows by the gradient sparsity), inequality (7) , and the definition of γ.We proceed now by separately studying the different cases for δ:• Case δ = 0. The bound above becomesF D (x) -F (x * (D)) ≲ L 2 λn s ln(d/β) ε H λ + 1 + ln n ln(1/β) + λD 2 + B ln(1/β) n .Our choice of λ provides the claimed bound.• Case δ > 0. Here, the upper bound takes the formF D (x) -F (x * (D)) ≲ L 2 λn s ln(d/β) ln(1/δ) ε + ln(n) ln(1/β) + λD 2 + B ln(1/β) n .The proposed value of λ leads to the bound below that holds with probability 1 -β,F D (x) -F D (x * (D)) ≲ B ln(1/β) n + LD ln n ln(1/β) n + s ln(1/δ) log(d/β) εn ≲ (LD √ ln n + B) ln(1/β) n + LD [s ln(1/δ) log(d/β)] 1/4 √ εn .We now prove that the rates of pure DP-ERM in the convex case above can be obtained without the smoothness assumption, albeit with an inefficient algorithm. This algorithm is 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 set:xEQUATIONwhere x| P ∈ R d is the vector such that x P,j = x j if j ∈ P , and x P,j = 0 otherwise. We will say that X is sparsifiable if (8) holds. Note this property holds e.g., for ℓ p -balls centered at the origin. Lemma G.2. Let X be a convex sparsifiable set. Consider the problem (ERM) under convexity (Item (A.3)), bounded diameter (Item (A.2)), Lipschitzness (Item (A.5)) and gradient sparsity (Item (A.7)), assumptions. If x * (S) is an optimal solution of (ERM) and τ > 0, then there exists x ∈ X such that ∥x∥ 0 ≤ 1/τ 2 , andF S (x) -F S (x * (S)) ≤ L √ sτ. Proof. Let x ∈ R d be defined as xj = x j if |x * S,j | ≥ τ 0 otherwise.Note that x ∈ X since x * (S) ∈ X and X is sparsifiable. Now we note that∥x∥ 0 ≤ j: |x * S,j |≥τ (x * S,j ) 2 τ 2 ≤ 1 τ 2 .Finally, for the accuracy guarantee, we use convexity as follows,F S (x) -F S (x * (S)) ≤ ⟨∇F S (x), x -x * (S)⟩ ≤ ∥∇F S (x)∥ 1 ∥x -x * (S)∥ ∞ ≤ L √ sτ,where in the last step we used that ∇f (x, z i ) ∈ S d s and the definition of x.We present now the sparse exponential mechanism, which uses the result above to approximately solve (ERM) with nearly dimension-independent rates.Require: Dataset S = {z 1 , . . . , z n } ⊆ Z, ε privacy parameter, f (•, z) L-Lipschitz convex function with s-sparse gradients and range bounded by B, 0 < β < 1 confidence parameter Let τ > 0 be such thatτ 3 ln(d/[τ β]) = L √ sεn BLet N τ be a τ -net of 1/τ .Proof. Let x be the vector whose existence is guaranteed by Theorem G.2. By the high probability guarantee of the exponential mechanism [1] with probability 1 -β,F S (x) -F S (x) ≤ B εn ln |N τ | + ln(1/β) ≲ B εn ln d τ β τ 2 .Hence, using Theorem G.2 with the upper bound above, Guidelines:F S (x) -F S (x * (S)) ≤ F S (x) -F S (x) + F S (x) -F S (x * (S)) ≲ B εn ln(d/[τ β]) τ 2 + L √ sτ ≲ L 2 B• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] . Justification: The paper poses no 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 be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] . Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?We will generally refer to high-dimensional or nearly dimension-independent rates indistinguishably, meaning more precisely that the rates scale polylogarithmically with the dimension.Note that we use the projection mechanism (Algorithm 1) as subroutine for Algorithm 2 only to have a self-contained presentation in the main body of the paper. We will analyze and state the sharper bounds obtained with Algorithm 5 as subroutine.We follow the Blanchet-Glynn notation of O and E to denote the 'odd' and 'even' terms for the batch partition[14]; this partitioning is arbitrary.While [42] only provides 1-dimensional distributional lower bounds for approximate-DP mean estimation, it is easy to convert these into higher dimensional lower bounds, see, e.g.,[26,43].This idea is related to the Wald identities[16]; however, we provide a direct analysis for the sake of clarity.We also need concentration to upper bound FS(x * (D)) -FD(x * (D)). However, this is easy to do by e.g., Hoeffding's inequality, leading to a bound ≲ γ.1/3, where we used our choice of τ . 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

The main contributions of the paper are as follows:

DP 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.

Lower 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.

Algorithms 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.
strength_weakness: strength_weakness: 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.
questions: questions: I can't fine the results regarding DP-SCO in the paper. Maybe I am missing something in the paper.

1- Is there any way to extend the results to the case with approximate sparsity? 

2- what is p_n in algorithm 2?

3- What is the importance of random batch size?

4- Theorem A.6 seems to have a typo?

5- 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.

6- What is the shortcoming of “equal” privacy budget allocation as in the BST14 paper?

7- What is the issue with using full-batch for computing the gradient?

8- What is the definition of $\mathcal{F}_{t-1}$ in prop. E.1?

9- Line 644, it is not clear to me why conditional expectation of bias and variance are also bounded by b and v.
limitations: limitations: N/A
paper_summary: paper_summary: The paper provide algorithms for DP optimization with sparse gradient, proving both upper bounds and lower bounds, which are almost match.
strength_weakness: strength_weakness: 1. It is a pure theory paper, it would be more interesting to see if the algorithm can inspire improved practical applications.
2. The content is a bit dense, without summary or conclusion sections.
questions: 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: Limitations are well covered in the content.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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?

3. 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?

[1] Evading the Curse of Dimensionality in Unconstrained Private GLMs. AISTATS, 2021.

[2] When Does Differentially Private Learning Not Suffer in High Dimensions? NeurIPS, 2022.

[3] Dimension Independent Generalization of DP-SGD for Overparameterized Smooth Convex Optimization. arXiv, 2022.

[4] DPZero: Private Fine-Tuning of Language Models without Backpropagation. ICML, 2024.

[5] The Power of Sampling: Dimension-free Risk Bounds in Private ERM. arXiv, 2024.

[6] Deep learning with label differential privacy. NeurIPS, 2021.

[7] On Convex Optimization with Semi-Sensitive Features. COLT, 2024.

[8] On the Bias-Variance-Cost Tradeoff of Stochastic Optimization. NeurIPS, 2021.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Can the authors provide the running times analysis for Algorithms 2 and 3?
limitations: limitations: The authors address the limitation of this work in the checklist

Comments: title: Further responses
Answer to question 6 by reviewer 9vLf
Official comment by reviewer L9WR
comment: Thank you for engaging in further discussions. We proceed to answer your comments/questions.

*[..] Please check their arguments carefully and include a detailed discussion in the next version of the paper.*

We appreciate the provided references, and we will make sure to incorporate them in the next version.

*In my understanding, if the gradients are always sparse and the support is fixed, then dimension-independent rates are natural regardless of the constrained sets as one can transform this d dimensional problem to an s dimensional one. However, if the support is not fixed, I am not clear what will happen. For the sparsity assumption, let me clarify my question. What I am confused is that $x_t$ can always be dense since we add noise to make it DP. Then how strong is this gradient sparsity assumption evaluated on every dense $x_t$?*

We agree that the fixed support sparse gradient case is straightforward. We also agree that $x_t$ (and furthermore, its minibatch gradients) can be fully dense. However, this is not a contradiction as our assumption is imposed on the ***individual gradients at arbitrary points***. Now, if your question is directed to how strong is in practice to have sparse gradients at dense $x_t$, our answer is that  for our applications of interest is not strong. E.g. for embedding models the sparsity arises from the embedding of categorical features, hence it works regardless of the iterate. We hope this resolves your question.

*[..] I increase the score to 5, which is on the positive side. I am willing to support the acceptance of the paper.*

Thank you for taking our feedback into account.
Thank you for the response. I will keep my score.
Thanks for your response!

I think a better understanding regarding the separation between constrained and unconstrained case mentioned in papers [1,2,5] is valuable to the community. Please check their arguments carefully and include a detailed discussion in the next version of the paper.

In my understanding, if the gradients are always sparse and the support is fixed, then dimension-independent rates are natural regardless of the constrained sets as one can transform this d dimensional problem to an s dimensional one. However, if the support is not fixed, I am not clear what will happen. For the sparsity assumption, let me clarify my question. What I am confused is that $x_t$ can always be dense since we add noise to make it DP. Then how strong is this gradient sparsity assumption evaluated on every dense $x_t$?

Anyway, I don't have other problems. I increase the score to 5, which is on the positive side. I am willing to support the acceptance of the paper.
Thank you for the clarification. Before answering, please keep in mind that for Noisy SGD algorithms the minibatch gradients estimators are unbiased, so what we discuss next is specific to the sparse setting. 

In the sparse setting we only have at our disposal (minibatch gradient) mean estimation algorithms whose bias scales as $1/\sqrt{B}$ where $B$ is the batch size. Our main limitation then comes from this bias (which does not vanish with a larger number of iterations); moreover, note that the benefits of privacy amplification by subsampling take place for smaller values of $B$. Hence these two effects pose a strong privacy/accuracy tradeoff. 

Regardless of the batch size, and as you correctly point out, we also need to take into account the effect of composition. Optimizing on both batch size and number of steps, one can see that the biased SGD algorithm will converge with a rate which has polynomial gaps  in $1/\varepsilon$ and $s$ (compared to the lower bounds); see, e.g. the work of Zhang, Hejazinia and Mironov [6]. By contrast, our bias reduction approach leads to smaller bias but can still benefit from privacy amplification by subsampling. This leads to various technical challenges which are the core of our analysis in Section 5.

We hope this resolves your question and allows you to better appreciate our technical contributions.
Thanks for the detailed response! 

Regarding question 6 in my initial review: the "usual" analysis of DPGD is based on the following: assume we want to run the algorithm for $T$ iterations and the privacy budget is $\rho$-zCDP. Then, we set the noise variance such that the privacy budget at each iteration is $\rho/T$. I want to better understand the shortcomings of this approach compared to the proposed method in the paper.
Thank you for answering my question. I will keep my score.