Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
Authors: Hilal Asi
Daogao Liu
Kevin Tian
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic Convex Optimization
Heavy-Tailed Distributions
Differential Privacy
Primary area: privacy
TL;DR: We give the first algorithm attaining near-optimal error rates for DP-SCO assuming heavy-tailed gradients, and several improvements in structured cases.

Abstract: We study the problem of differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a $k^{\text{th}}$-moment bound on the Lipschitz constants of sample functions, rather than a uniform bound. We propose a new reduction-based approach that enables us to obtain the first optimal rates (up to logarithmic factors) in the heavy-tailed setting, achieving error $G_2 \cdot \frac 1 {\sqrt n} + G_k \cdot (\frac{\sqrt d}{n\epsilon})^{1 - \frac 1 k}$ under $(\epsilon, \delta)$-approximate differential privacy, up to a mild $\textup{polylog}(\frac{1}{\delta})$ factor, where $G_2^2$ and $G_k^k$ are the $2^{\text{nd}}$ and $k^{\text{th}}$ moment bounds on sample Lipschitz constants, nearly-matching a lower bound of [LR23].
We then give a suite of private algorithms for DP-SCO with heavy-tailed gradients improving our basic result under additional assumptions, including an optimal algorithm under a known-Lipschitz constant assumption, a near-linear time algorithm for smooth functions, and an optimal linear time algorithm for smooth generalized linear models.

Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
Hilal Asi
Daogao Liu University of Washington liudaogao@gmail com
Kevin Tian University of Texas at Austin kjt tian@cs. utexas. edu
Apple Inc.
hilal. as19440a11000
Abstract
We study the problem of differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a 1th -moment bound the Lipschitz constants of sample functions, rather than uniform bound. We propose new reduction-based approach that enables us to obtain the first optimal rates (up logarithmic factors) the heavy-tailed setting, achieving emor
G2 1 + Gk ( (W²)1= under (e, -apprxxxiee differential privacy, up to a V mild polylog(?) factor, where G2 and G are the 2nd and 1:th moment bounds sample Lipschitz constants, nearly-matching lower bound of [LR23]. We further give suite of private algorithms in the heavy-tailed setting which improve upon our basic result under additional assumptions, including optimal algorithm under a known- Lipscchip constant assumption, near- linerr time algorithm for smooth functions, and an optimal linear time algorithm for smooth generalized linear models.
Introduction
Differentially private stochastic convex optimization (DP-SCO), where an algorithm aims to minimize population loss given samples from distribution, fundamental problem in statistics and machine learning. In this problem, given n samples from a distribution P over sample space S, our goal is privately find an approximate minimizer & X' C Rd for the population loss
(x)x) Egup s)),
where f(::s) convex function for all s E S. The quality of an algorithm measured by the excess population loss of its output é, that is Fp (.) min Fx(x*).
Extensive research efforts have been devoted to DP-SCO, resulting in important progress over the past few years [BITT19, FKT20, AFKT21, BGN21, ALD21, KLL21J. In important milestone, [BFTT19] developed optimal algorithms (in terms of the excess population loss) for DP-SCO under uniform Lipschitz assumption (i.c., where every f:: s) assumed have the same Lipschitz bound), and [FKT20] followed this result with efficient and optimal algorithms that run in linear time for smooth functions. DP-SCO has also been explored in other notable settings, including developing faster algorithms for non- non-smooth settings [AFKT21, KLL.11 23J+ different geometries imposed on the solution space [AFKT21, BGN21, GLL GLL++33) 23), and different notions of privacy (ALD21).
Most existing results in SC-SCO are based the assumption that the function f(; s) is uniformly G-Lipschitz for all s E S. This assumption is convenient for private algorithm design, because allows to straightforwardly bound the sensitivity of iterates of private algorithms, i.e., how far pair iterates defined via algorithms induced by neighboring datasets drift apart. Under the uniform Lipschitz assumption, the DP-SCO problem is relatively well-understood, optimal and efficient
Part of this work was done while interning at Apple.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

algorithms exist (sometimes requiring additional regularity assumptions) [BFTT19, FKT20]. State- of-the-art SCO algorithms satisfying (e, ( -diifeerettaal privacy (Definition 1) in the uniform Lipschitz setting result in excess population loss
(lg(()))
1 vn
GD
en
where D is the diameter of X. However, the assumption uniformly G-Lipschitz gradients is strong, and may be violated in real-life applications where the distribution in question has heavy tails (see e.g. discussion in |ACG+ 16]). As simple motivating example, consider mean estimation, where each ((; 1 I|- - sII2. so the minimizer of Pp is the population mean. The uniform Lipschitz requirement amounts to P having bounded support over X, whereas an algorithm that can handle heavy tails only posits the weaker assumption that P has bounded k-th moments. However, as pointed out by [WXDX20], many weal-world datasets [MM97, BDFS07, IIW1 especially those from biomedicine and finance, are usually unbounded or even heavy-tailed. As result, existing algorithms for DP-SCO may have overly pessimistic performance bounds when is large or even unbounded, necessitating the search for new private algorithms handling heavy-tailed gradients.
Motivated by this weakness of existing DP-SCO analyses, several papers studied the problem of DP-SCO with heavy-tailed gradients [WXDX20, ADF+21, KLZ222, LR23], formally defined in Definition 4. Rather than assuming uniformly Lipschitz gradients, this line of work builds on the more realistic assumption that the norm of the gradients has bounded h.th 4tth momments. In particular, [ADF+21] studied heavy-tailed private optimization for the related empirical loss, while [WXDX20] initiated an analogous study for the population loss. More recently. [KLZ22, LR23] also proposed algorithms to solve the heavy-tailed DP-SCO problem based on clipped stochastic gradient methods.
Despite the significant progress made in addressing heavy-tailed DP-SCO, it remains notably less understood compared to the uniformly Lipschitz setting. As benchmark, under notion called p-concentrated differential privacy (CDP, see Definition 3), which translates to (e, 8)DD for p R g² loooo' (t)), [LR23] established that the best excess population loss achievable scales as
1 Vn
vd
G₂
G&D.
(2)
nVP
where G.J is the jth moment bound the Lipschitz constant sampled functions, see Definition Note that - co, the rate in (2) recovers the uniform Lipschitz rate in (1).
Unfortunately, existing works on heavy-tailed DP-SCO assume stringent conditions on problem parameters and are suboptimal in the general case. For example, [KI.722] requires the loss functions be uniformly smooth with various parameter bounds order to guarantee optimal rates, while the
recent work [LR23] obtains a suboptimal rate scaling as G2D 1 + G (-va ) vā
which is
worse than (2) by polynomial factors in the dimension for any constant k.
1.1 Our contributions
Motivated by the suboptimality of existing results for heavy-tailed DP-SCO, develop the first algorithm for this problem, which achieves the optimal rate (2) up to logarithmic factors with no additional assumptions. Along the way, give several simple reduction-based tools for overcoming technical barriers encountered by prior works. To state our results (deferring a formal problem statement to Definition 1), we assume that for some k and all E [At, we have
[V < C.
Our results hold in several settings and are based on different reductions which allow us to apply strategies for DP-SCO from the uniform Lipschitz setting.
"One notable exception the lack of linear- time algorithms in the non-smooth setting. 'The rate in [LR23] is stated slightly differently (see their Theorem 6), as they parameterize their error bound via G2 despite assuming only & bounded moments. However, under the assumption that Gzu is finite (so the [LR23] result is usable), the optimal rate scales in (2) where & replaced with 2k, leaving polynomial gap.

---

Near-optimal rates for heavy-tailed DP-SCO (Section 3). We design an algorithm for the k- heavy-tailed DP-SCO problem, which satisfies p-CDP* and attains near-optimal excess loss
log (#t) n
[Vdlog (#) nVP
G2D
G+D-
This matches the lower bounds recently proved by [KLZ22, LR23] for p-concentrated DP algorithms up to logarithmic factors, stated in (2). Standard conversions from CDP to (e, 6)-DP imply that our
algorithm also obtains loss RJ G2D # G.D. ( (A/log"(1/)) ) 1- under this parameterization.
De
We note that our bound (3) holds with high probability 2 1-110. 8, whereas the lower bound (2) is for an error which holds only in expectation (see Theorem 13, [LR23]). Our lossiness in (3) is due to natural sample-spliting strategy used to boost our failure probability, and we conjecture that (3) may
be optimal in the high-rrobbiility error bound regime.
As in [LR23], to establish our result begin by deriving utility guarantees for a clipped stochastic gradient descent subroutine on an empirical loss, where clipping ensures privacy but induces bias, parameterized by dataset-dependent quantity 1 defined in (26). We give standard analysis of this subroutine in Proposition 1, a variant of which (with slightly different parameterizations) also appeared as Lemma 27, [LR23]. However, the key technical barrier encountered by the [LR23] analysis, when converting to population risk, was bounding Ebi over the sampled dataset, which naively depends on the 2h moment of gradients. This either incurs an overhead depending on G2s. or in the absence of such a bound (which is not given under the problem statement), leads to the aforementioned suboptimal rate in [LR23] losing a factor of L.a ) in the utility. We give a further discussion of natural strategies and barriers towards directly bounding Fly in Appendix G.
(npp (
Where we depart from the strategy of [LR23] is in the use of a new population-level localization framework we design (see Algorithm 2), inspired by similar localization techniques in prior work [FKT20] (discussed in more detail in Section 1.2). This strategy allows us to use constant-succet probability bounds on the quantity bp (which also bound (gg), which are easy achieve depending only on G₁. rather than Gz via Markov's inequality. This bypasses the need in [LR23] for bounding E6G. The motivation for population- level localization is that we wish aggregate empirical solutions to multiple datasets, some of which have small bp, and others which do not. However, each dataset has different empirical minimizer, so it unclear how to argue about convergence if we apply the empirical localization. Instead, we aggregate solutions close to the population-level minimizer and share them across datasets via simple geometric aggregation technique, showing that suffices for a constant fraction of datasets to have this desirable property for us to carry out our population-Ievel localization argument. We formally state our main result achieving the rate (3) as Theorem
Interestingly, as a straightforward corollary of our new localization framework, we achieve a tight rate for high-pro probbbbbbbbyyy stochastic convex optimization under bounded-variance gradient estimator parameterization, perhaps the most well-studied formulation of SCO. To our knowledge, this result was only first achieved very recently by [CH24]. 5 However, we find it promising groo-of--concepp that our new framework directly yields the same result. For completeness, we include a derivation in Appendix E (see Theorem 5) as a demonstration of the utility of our framework.
Optimal rates with known Lipschitz constants (Appendix B). We next consider the known Lipschitz setting, where each sample function f(::) () arrives with a value L, which is an overestimate
of its Lipschitz constant, such that EL2 is bounded for all j [k] (see Assumption 2). As motivation, consider the problem of learning a generalized linear model (GLM), where f(-;s) = o a(1s s)) for a known convex activation function a., Typically, the Lipschitz constant for f(;;s) is simply the Lipschitz constant of a times |||||. which can be straightforwardly calculated. Thus, for GLMs, our known Lipschitz heavy- assumption amounts to moment bounds on the distribution P.
*We state the privacy guarantee most of our results, save our algorithm in Appendix C which employs the sparse vector technique of [DNR* '09, 14], in terms of CDP, for simpler comparison to the lower bound (2). 'We mention that an alternative route obtaining a near-optimal high-probability rate was given slightly earlier in [SZ23], but lost polylogarithmic factor in the failure probability. We also wish to acknowledge that in an independent and concurrent work [JST24] involving the third author, the authors slightly sharpened and generalized the result of [SZ23], which inspired us to consider this application of our population level localization framework.
3

---

Our second result, Theorem 2, shows natural strategy obtains optimal rates in this known Lipschitz setting, eliminating logarithmic factors from Theorem 1. As mentioned previously, this result holds for the important family of GL.Ms. Our algorithm is based on straightforward reduction to the uniformly Lipschitz setting: after simply iterating over the input samples, and replacing samples whose Lipschitz constant exceeds given threshold with a new dummy sample, we show existing Lipschitz DP-SCO algorithms then obtain the optimal heavy-tailed excess population loss (2). Despite the simplicity of this result, to the best of our knowledge, it was not previously known.
Efficient algorithms for smooth functions (Appendices C and D). Finally, we propose algorithms with improved query efficiency for general smooth functions or smooth GL.Ms, with moderate smoothness bounds. Our strategy is to analyze the stability of clipped-DP Srreed-DD-GGDDDDD in the smooth heavy- tailed setting, and use localization-bast one [FKT20]. This results in linear-time algorithms for the smooth case with near-optimal rates. In order to prove the privacy of our smooth, heavy-tailed algorithm, we analyze a careful interplay of clipped stochastic gradient method with the sparse vector technique (SVT) [DNR + 09, DR14]. At a high level, our use of SVT comes from the fact that under clipping, smooth gradient steps no longer enjoy the type of contraction guarantees applicable in the uniform Lipschitz setting (see Fact 3), so we must take care to not clip too often. The SVT is then used to ensure privacy of our count of how many clipping operations were used. In Appendix F, we provide simple counterexample showing that the noncontractiveness of contractive steps after applying clipping is inherent. Our general smooth heavy-tailed DP-SCO result is stated Theorem 3.
reductions to transform a stable algorithm into a private
We believe the use of SVT within an optimization algorithm to ensure privacy may be of independent interest, as it is one of few such instances that have appeared in the private optimization literature to our knowledge; it is inspired by a simpler application of this technique carried out in [AL24].
On the other hand, we make the simple observation that for GLMs, clipping cannot make a contractive gradient step noncontractive, by taking advantage of the fact that the derivative of f(x; = a ((r, s)) a multiple of for any x E X' (see Lemma 14). We use this observation to give a straightforward adaptation of the smooth algorithm in [FKT20] to the heavy-tailed setting, proving Theorem 4, which attains both a linear gradient query complexity and the optimal rate (2).
1.2
Prior work
The best-known rates for heavy-tailed DP-SCO were recently achieved by [KLZ22, LR23]. As discussed previously, their results do not provide the same optimality guarantees as our Theorem 1. The rate achieved by [LR23] is polynomially worse than the optimal loss (2) for any constant k. On the other hand, the work of [KLZ22] uses different assumption which is arguably more nonstandard: in particular, they require that the 1:th -ohhorder central moments of each coordinate (z; s) is bounded. Moreover, their algorithms require each sample function f(; s) to be 3-smooth, and the final rates have strong dependence on the condition number ς = & where X is the strong convexity parameter (see Appendix C' in [LR23] for additional discussion).
the gradients than Assumption 1,
Our result in the heavy-tailed setting assuming B B-smoothness of sample functions, Theorem 3, is most directly related to Theorem 15 of [LR23]. These two results respectively require
B 3-0 GR
1.5
n2 V/
and
Ge D
EY1
omitting logarithmic factors in our bound for simplicity, to obtain near-optimal rates. These regimes are different and not generally comparable. However, we find it potentially useful that our upper bound on grows as more samples are taken, whereas the [LR23] bound degrades with larger n. is worth mentioning that [LR23]'s Theorem 15 shaves roughly one logarithmic factor in the error bound from our Theorem 3. On the other hand, Theorem 3 actually requires a looser condition than mentioned above (see (20)), which can improve its guarantees in a wider range of parameters.
Finally, we briefly contextualize our population-leve localization framework in regard to previous localization schemes proposed by [FKT20]. The two localization schemes in [FKT20] (see Sections 4.1 and 5.1 of that work) both follow the same strategy of gradually improving distance bounds to a minimizer in phases. However, their implementation is qualitatively different than our Algorithm 2, preventing their direct application in our algorithm. For instance, Section 4.1 1 of [FKT20] does not use strong convexity and, therefore cannot take advantage of generalization bounds afforded to

---

strongly convex losses (see discussion in (SSSS09]). On the other hand, the scheme in Section 5.1 of [FKT20] serves a different pupose than Algorithm 2, aiming to solve strongly convex optimization by reducing it to non-strongly convex optimization; our Algorithm 2, on the other hand, directly targets non-strongly convex optimization as its goal. We view our approach as complementary to these prior frameworks and are optimistic it will find further utility in applications.
2 Preliminaries
General notation. We use [d] to denote the set {i E ENJiS d}. We use sign(æ) E {=1} to denote the sign for E R, with (0gn(0) 1. We use (p, 2) to denote the multivariate normal distribution of specified mean and covariance. We denote the all-ones and all-zeroes vectors of dimension by 1a and Od- We use ||-]] to denote the Euclidean (l2) norm. We use Ia to denote the identity matrix on Rd. We use B(C)) to denote the E2 ball of radius C, and for E RR,, B(rr, C*) is used to denote {a' E RR || x|| & C}. For a set X' S R4, we let diam(X') == x | - æ'I,, and we let (x)x)) denote the Euclidean projection of x to X, i.e. argming'e.* || - zII. which exists and is unique when X' compact. We use fx to denote the restriction of function f to X, i.e.
[f(z) 100
E X
fx(x)
(4)
$ X
For x E Rd, we use [z()) as shorthand for (1), i.e. (X) denotes the clipped vector
-min ||z]| 1). We say two datasets D, D' are neighboring if they differ in one entry, and |D| [D'].
C
We say x E X is an e-approximate minimizer to f + IR if fa)) - inf f(x*) I e. For two
densities μ., V on the same probability space, and a > we define the a-Rényi divergence
Do = ax - log ( (B(c)) v(w)
du(ww)
For an event & on a probability space clear from context, we let Dg denote the 0-1 indicator of E. We
say f: X + R is L-Lipschitz if (xx f(x') < L ||x æ'll for all x, x' E X; if f is differentiable
and convex, an equivalent characterization is [[)] s L for all x E X. We say f X:X + R is μ
strongly convex if f fAxx' + (1 - A)z) - Af(z')+ (1-
aA(1-A) A) || z'I1 for all x' E X.
We say differentiable f X + R is 3-soohhh if for all x, E X, l1v - f s B || - z'|l
Differential privacy. We begin with definition of standard differential privacy.
Definition (Differential privacy). Let 2 O, E 1). We say a mechanism (randomized algorithm)) M: : Sth + Ω satisfies (E, 5) diffferentii privacy (altematively. M is (c, 5)-DP) if for any
neighboring D, D' E S", and any S S Z Pr [M(D) E 5] S exp(E) Pr [MM(') E 5 +5. 8.
More generally, for random variables X,Y E Ω satisfying Pr[x E e I exp(e) Pr[Y E S] + for all S C 22 we say that X,Y are (e, b)iiiiissiingusshaalle
Throughout the paper, other notions of differential privacy will frequently be useful for our accounting of privacy loss in our algorithms. For example, we define the following variants of DP.
Definition 2 (Rényi DP). Let 1, 2 O. We say a mechanism M S + Ω satisfies (a, differential privacy (RDP) if for any neighboring D,D' E SS", D, D.(M)))) <
Definition 3 (CDP). Let p 2 0. We say mechanism M - Ω satisfies p-concentrated differential privacy (alternatively, M satisfies p-CDP) for any neighboring D, D' E S", and any 1, (M(()))))((D)) < ap.
For an extended discussion of RDP and CDP and their properties, we refer the reader to [BS16, Mir17, BDRS18]. We summarize the main facts about these notions we use here.
Lemma 1 ([Mir17]). RDP has the following properties.
1. (Composition): Let M₁ : S -> Ω satisfy (a, (o,,1)-RDP and M2 S x Ω + S' satisfy (a, RDD for any input in algorithm which takes D to M2(D, (D)), satisfies (a,, S1 RDD.
Ω. Then the composition of M2 and M,, i.e. the randomized
2. (RDP to DP): If M satisfies (a,e)-RDD RDDP, it satisfies (E + - (, 6DD for all ō E (0, 1).
5

---

3. (Gaussian mechanism): Let f Shh + Rd be an L-sensitive randomized function for L 2 0, i.e. for any neighboring D, D', we have Il - f f(D'Il |I S L. Then for any o 0, the mechanism which outputs (D) + f.ror { ~ N (0a, 1a) satisfies 2/ -DP.
Private SCO. Throughout the paper, we study the problem of private stochastic convex optimization (SCO) with heavy-tailed gradients. We first define the assumptions used in algorithms.
Assumption 1 (k-beavy-tailed distributions). Let X C IRd be a compact, convex set. Let P be a distribution over sample space S, such that each convex, -Lppsccciizz loss function ([:8):: ;x - R, where L := maX || [(;; s)ll is unknown. For k IN satisfying k 2 say P satisfies the k-heavy tailed assumption for sequence of monotonically nondecreasing {G)]) we have Es>p([g] [T4] GJ oc for all j E [R.]
S induces a continuoustl-diffeeentddd
In Appendix B, we consider a variant Assumption where we have explicit access to upper bounds on the Lipschitz constants L., formalized in Assumption 2. Our goal is to approximately optimize population loss over sample functions satisfying Assumptions or 2, formalized in the following.
Definition 4 (k-heavy-tailes private SCO). In the k-heavy-tailed private SCO problem, X C Rd a compact, convex set with diam( X)) = D. Further, P a distribution over a sample space S satisfying Assumption I. Our goal is to design algorithm which provides an approximate minimizer in expectation to the population loss, Fp(x) := Egp [f s)}, subject to satisffyng differential privacy. We say such algorithm queries N sample gradients it queries V f s) for N different pairs (I, s) X x S. IfP further satisfies Assumption 2, we call the corresponding problem the known Lipschitz &-heavy-tailed private SCO problem.
We first observe the following consequence of Assumption 1, deferring a proof to Appendix A.
Lemma 2. Let P be distribution over S satisfying Assumption 1. Then Fp is Gi-Lipschitz.
We require the following claim which bounds the bias of clipped heavy-tailed distributions.
Fact 1 ([BD14], Lemma 3). Let and X Rd be random vector with E|||X|||]
S Gh. Then,
Gh
E [X)((X) - X|| < E||[ [ixnze] < (k - 1)CK-T
We also use the following standard claim on geometric aggregation.
Fact 2 ([KLL* 233]. Claim 1). Let S == fiilie C Rd have the property that for (unknown) 2 E R4 Hi E [b]] | - =|| S R]] 2 0.51 some R 2 0. There is an algorithm Aggregate which runs in time (dd-2) and outputs
S such that || 2|| < 3R.
Finally, given a dataset D E S* of arbitrary size, and À 2 O, we use the following shorthand to denote the regularized empirical risk minimization (ERM) objective corresponding to the dataset:
(D. == D
Σ f1;3) + 1 RED
(5)
When x = 0, we simply denote the function above by Fo(x)) = Do ELEDS(E;
3 Heavy-Tailed Private SCO
In this section, we obtain near-optimal algorithms for the problem in Definition 4 using new population-level localization framework, combined with geometric aggregation for boosting weak subproblem solvers to succeed with high probability (Fact 2). Our algorithm's 's main ingredient, in Section 3.1, is a clipped DP-SGD subroutine for privately minimizing a regularized ERM subproblem, under a condition on randomly sampled dataset holding with constant probability. Next, in Section 3.2 we show that our algorithm from Section 3.1 returns points near the minimizer a
'The assumed moment bounds shows that ((: has a finite Lipschitz constant, except for probability-zero set of Moreover, convex functions are differentiable almost everywhere. Therefore, if f(;:) is Lipschitz. perturbing its first argument by an infinitesimal Gaussian makes it differentiable there with probability and negligibly affects the function value. We thus assume for simplicity that f(; s) is differentiable every ehere This assumption is without loss of generality by Jensen's 's inequality.

---

regularized loss function over the population, using generalization arguments. Finally, we develop our population-level localization scheme Section 3.3, and combine it with our subproblem solver to give our overall method for heavy-tailed private SCO. Several proofs and generalization to strongly convex functions (Corollary 3) are deferred Appendix
3.1 Strongly convex DP-ERM solver
We give a parameterized subroutine for minimizing DP-ERM objective FD, (ar associated with dataset "D and regularization parameter À 2 0 (recalling the definition (5)). In this section only, for notational convenience we identify elements of DD with [n] where n [D], we will also write
1 Σ = TE (E(M)
(D))
fi(2)
|x||
i.c we let == f(=:s where E D is the element identified with E [n]. Our subroutine is clipped DP-SGD algorithm (Algorithm 1), which only clips the heavy-tailed portion of V.D.,. (i.e. the sample gradients), and leaves both the regularization and additive noise unchanged. The utility of Algorithm is parameterized by the following function of the dataset:
max bD
Σ Vi(()) (E(M)
1 Σ (c(V((())) TI
(6)
SEX
TI
iE|m
In other words, bn denotes the maximum bias incurred by the clipped gradient of FD when compared to the true gradient, over points in X; note the maximum achieved as X' compact.
We are now ready to state our algorithm, Clipped-DP-SGD, as Algorithm 1.
Algorithm 1: Clipped C, CT.
Input: Dataset D E S" clip threshold C E Rza, regularization À E Rgo, step sizes {m) he()) C R2o. noise o² E Rzo. iteration count T E N, radius r E Rzo, domain X' C B(r)
with X' 3 Da
2 Fp D₂
for 0 < 1 < T do
& ~ (oa,, I2
J. + +. Eie(n (V((V))(z))
I++1 + argmin, (n (g: + E,,2) + ne || + || xx.12
7 end
Return: & Losten(ttd)z
8
Eogrer((+4)
We provide the following guarantee on Clipped-DP-SGD, by modifying an analysis of [LSB12]. Proposition 1. Let 2 O, and be the output of DiippedDD--SGD SGD with n + x(++)) for all 2C-T
and T 2 max(n, =²²)). Clipped-DP-SGD satisfies p-CDP, and 0 o o² n²p
320 bg dn2p p
7A where x² == argmin Fp,)(a).
F(FD.)()) FD.()T))
+
For ease use of Proposition 1, we now provide a simple bound on bp which holds with constant probability from dataset drawn from distribution satisfying Assumption 1.
Lemma 3. Let D Pn, where P is a distribution over satisfying Assumption With probability at least 3. denoting bp as in (26), have
50
bp <
(k - 1)C
We therefore have the following corollary of Proposition 1 and Lemma 3.
7

---

Corollary 1. Let D ~ pm, where P is distribution over S satisfying Assumption 1, and let D.A argminzex (z), following (5). If we run Clipped-DP-SGD with parameters in Proposition I and C + -Gk (222d ) Clipped-DP-SGD is p-CDP, and there a universal constant Cer such that with probability 2 5 over the randomness of 'D and Clipped-DPP DoooddDP-.DD., 2, the output of Clipped- Seaedd-DD-GGD. sattisfis
3
Gk À
Vd nVP
| - zb,2ll S Corm
Clipped-DP-SGD queries at most max(n², a P) sample gradients (using samples in D).
Proof. Condition on the conclusion of Lemma 3, which holds with probability 3.- Therefore, Markov's inequality shows that with probability at least 5. after a union bound with Proposition I,
A | =bal2 FD,A(0) (D.A(ID,)))
2
160Cad
125G XC2(k-1) +
7A
320G 2
d
7Ap2
xn²p
n2pp
n2
where we used strong convexity the first inequality, and plugged our choice of the last. The conclusion follows by rearranging the above display, and using va² B a for a, Rzo- IT
3.2 Localizing regularized population loss minimizers
Here, we use generalization arguments from the SCO literature to show how that our algorithm SippeddDD-SSCI from Section 3.1 acts as oracle which, with constant probability, returns point near the minimizer of regularized population loss. We begin with a standard helper statement.
Lemma 4. Let À Z O, let P be distribution over S satisfying Assumption 1, let F X where X Rd is compact and convex, and let
FF(x) + 11xx - 1==1pp] where Fp(x)) = EguP [f(x:))]-
xx,² == arrgmin ZER
Then || - xx 2G,
Next, we apply a result on generalization due to [LR23] to bound the expected distance between restricted empirical regularized minimizer and the minimizer of the population variant in (7).
Lemma 5. Let 2 O, D p where a distribution over S satisfying Assumption 1, and let I E X where X C Rd is compact and convex. Following notation (4), (5), let
(Foiecamm (x) A
2G1 =13 for
y argmin zEX
X
and let a be defined as (7). Then with probability 2 0.95 over the randomness of pa,
90G₂ | - 23,0112 X/n"
Corollary 2. Let D ~ Pm, where P is distribution over S satisfying Assumption 1, and let z E X where X C Rd is compact and convex. Let 2 and define x²,2 as in (7). There is a p-CDP algorithm which queries max(n?, u²p)) sample gradients (using samples in D). With probability 0.55 over the randomness of A and D. A returns & satisfying, for universal constant Creg-pop-
1-
Gx x
Vd
G2
|| 1 S Oreg pop
2}
n
A
8

---

Proof. Condition on the conclusion of Lemma 5 holding for our dataset, which loses 0.05 in the failure probability. Next, consider the guarantee Corollary 1, when applied to the truncated and shifted functions, f(1;; 8) +- JB( E; 8), where is set as in Lemma 5. shows that with probability 5. 1| yll 0 ( (Arr for the point & returned by the algorithm, and the exact minimizer of the empirical loss restricted to B r). Therefore, the conclusion follows by overloading & å T. applying the triangle inequality with the conclusions of Corollary and and taking union bound over their failure probabilities.
3.3 Population-level localization
In this section, we provide a generic population-level localization scheme for stochastic convex optimization, which may be of broader interest. Our localization scheme largely patterned off of the analogous localization methods developed by [FKT200, but directly argues about contraction to population-level regularized minimizers opposed to empirical minimizers), which makes compatible with our framework in Section 3.1 and 3.2, specificially the guarantees of Corollary 2.
Algorithm Population--oocaizee(nn, P. P)
Input: Initial point Zy E X, distribution over samples in S, for X, inducing a k-heavy-tailed DP-SCO problem as in Definition 4, with population loss Fp == Es-ssf(: A 2 0, I for i E []] do
A + A 32
x; f any point satisfying
4
where 2 == argmin Fp(x)) + X 1|---10 x1-1
11: 2;1 5
(8)
A
2EX
end
6 Return: d7
We briefly discuss the role of the hyperparameters X, A in Algorithm for clarity. The parameter A scales with the error guarantee of our regularized ERM solver; in particular, it will be determined by the bound in Corollary 2. The parameter À specifies initial regularization amount that will later be tuned to trade off the terms in the following Proposition 2.
Proposition 2. Following notation of Algorithm 2, let x² == argminaex (x)) Then,
G
A
XD
F Fp(x*)
+
X8
4X
2
In particular, choosing X optimize this bound, we have
G
- S 2DD
g7 + DA.
Proof. We denote zb == x= throughout the proof. First, we expand
Fo(æ1) (z Fr(a)))Fr())) + Fr(z))
Fr(a))
- Fr(a)) + Σ Fo(x)) (x(
Moreover, for each E [7], since xt minimizes Fx(x) + A; || x ?? 2
Fイ(x)) < Fo(2;) + A || x--1ll (x + di || x;-1
2

---

Combining the above two displays, and using that Fp is G1 Gi-Lisschitz (Lemma 2), we have
X
Fp(x1) Fx(x*) - Gi ||,
xil
Σ
|
8z-1
2
kE(T
G
16
XD2
G
A
AD2
A8
2
18
4A
iE|r-1]
where we used the diameter bound assumption diam( = D, as Definition 4.
In particular, note that Corollary 2 shows that by using n samples from P and CDP budget of with constant probability, we can satisfy the requirement (8) with A4' O vd 1- vm
n.p By plugging this guarantee into the aggregation subroutine in Fact 2, we have our SCO algorithm.
Algorithm 3: Aggregate-ERM(iz A, J, { It)
Regularization center X, regularization À Rzo- sample split parameter J N, privacy parameter E Rgo, samples {se]eE[nJ] C S, distance bound E R2z
Input:
2 for j E [J]ds do
D + (5))))-) for [J]
ad + result of Corollary 2 using D', on loss defined by म., À with privacy parameter p. i.e., is a point satisfying, with probability 0.55, for a universal constant Creg-pop
1
G+ (7]
vd
G2 Avn
|| - x3,211 Creg-rop
nVD
5 end
6 x. <- Aggregate( )jE(J), R) (see Fact 2)
7 Return: x
Theorem 1. Consider an instance of k-heavy-tailed private SCO, following notation in Definition 4,
let x² argmin Fx(x), and let p ' 0, (0, Algorithm 2 using Algorithm 3 in Line
is p-CDP algorithm which draws 'D ~ Pn, queries C.co max(n?, "²()) sample gradients (using samples in foror universal constant Cxcor and outputs x E satisfying, with probability 2
(villog (t)
1-
log (t)
Fo(x) - Fp(x*) S Osco
GxD-
+G2
nVP
Conclusion
In this work, consider the DP-SCO with heavy-tailed gradients. When the k-th moments of gradients are bounded, we propose the population-level localization framework and attain near-
optimal excess loss G2D. log( GDD G.DD- (Vllog()) a/p ()) )1- with probability least - and satisfy p-CDP. We can achieve tight rate for high-probabilityy SCO under bounded-variance gradient estimator parameterization by applying the population-level localization framework. Moreover, we improve this basic result under additional assumptions, including an optimal algorithm under a known-Lipschitz constant assumption, near-linear time algorithm for smooth functions, and an optimal linear time algorithm for smooth generalized linear models, with interesting techniques adapted each setting.
n
leaves many intriguing open problems this direction. For example, can we design near-linear time algorithms for non-smooth functions? Can the population-level localization framework be applied to solve other problems? Can we establish high-probabiility lower bound or eliminate additional logarithmic term if we are only concerned with the excess bound in expectation? Can we evaluate the algorithm's performance through numerical simulations real-world datasets? We leave these questions for future research.
10

---

References
[ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 23rd Annual ACM Conference on Computer and Communications Security (CCS), pages 308-318, 2016.
[ACI+21] Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Stochastic bias-reduced gradient methods. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, pages 10810- 10822, 2021.
[ADF*21] Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adap- tive gradient methods for convex optimization. In Proceedings of the 38th International Conference Machine Learning (ICML), pages 383-392, 2021.
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in l geometry. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
[AL24] Hilal Asi and Daogao Liu. User-level differentially private stochastic convex optimiza- tion: Efficient algorithms with optimal rates. In International Conference Artificial Intelligence and Statistics, 2024, volume 238 of Proceedings of Machine Learning Research, pages 4240 4248. PMLR, 2024.
[ALD21] Hilal Asi, Daniel Levy, and John Duchi. Adapting to function difficulty and growth conditions private optimization. Proceedings of the 34nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 19069-19081, 2021.
[BD14] Rina Foygel Barber and John C. Duchi. Privacy: A few definitional aspects and consequences for minimax mean-squared error. In 53rd IEEE Conference on Decision and Control, CDC 2014, pages 1365-1369. IEEE, 2014.
[BDFS07] Atanu Biswas, Sujay Datta, Jason P Fine, and Mark R Segal. Statistical advances in the biomedical science. (No Title), 2007.
[BDRS18] Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated CDP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 74-86. ACM, 2018
[BFTT19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Proceedings of the 32nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), pages 11282-11291, 2019.
[BGN21] Raef Bassily, Cristobal Guzman, and Anupama Nandi. Non-cuclidean differentially private stochastic convex optimization. arXiv:2103.01278 [cs.LG], 2021.
[BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, ex- tensions, and lower bounds. In Theory of Cryptography- 14th International Conference, TCC 2016-B, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 635 6558, 2016.
[CH24] Yair Carmon and Oliver Hinder. The price of adaptivity in stochastic convex optimiza- tion. CoRR, abs/2402. 10898, 2024.
[C] Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, pages IEEE, 2023.
[DDXZ21] Damek Davis, Dmitriy Drusvyatskiy, Lin Xiao, and Junyu Zhang. From low probability to high confidence in stochastic convex optimization. J. Mach. Learn. Res,, 22:49:1- 49:38, 2021.
11

---

[DNR* 09] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 381-390. ACM, 2009.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends Theoretical Computer Science, 9(3 4):21 1 1-407, 2014.
[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. Proceedings of the 52nd Annual ACM on the Theory of Computing, pages 439-449, 2020.
[GLI,+23] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian. Private convex optimization in general norms. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5068-5089 SIAM, 2023.
[HRS16) Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In ICML, pages 1225-1234, 2016.
[HS16) Daniel J. Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. J. Mach. Learn. Res., 17:18:1-18:40, 2016.
[1W15]] Marat Ibragimov, Rustam Ibragimov, and Johan Walden. Heavy-tailed distributions and robustness in economics and finance, volume 214. Springer, 2015.
[JST24] Arun Jambulapati, Aaron Sidford, and Kevin Tian. Closing the computational-ques depth gap in parallel stochastic convex optimization. In The Thirty Seventh Annual Con- ference on Learning Thheory, COLT 2024, Proceedings of Machine Learning Research. PMLR, 2024.
[KLL21] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps. arXiv preprint vrXi:2213.153522 2021.
[3]]+ Jonathan A. Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, and Kevin Tian. Semi- random sparse recovery in nearly-linear time. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, volume 195 of Proceedings of Machine Learning Research, pages 2352-2398. PMLR, 2023.
[KLZ22] Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 10633-10660, 2022.
[Lia24] Jiaming Liang. Variance reduction and low sample complexity in stochastic optimization via proximal point method. CoRR, 0tos/2402.08992.. 2024.
[LR23] Andrew Lowy and Meisam Razaviyayn. Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses. In International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 986-1054. PMLR, 2023.
[LSB12] Simon Lacoste-Julien, Mark Schmidt, and Francis R. Bach. A simpler approach to obtaining an ((t/t) convergence rate for the projected stochastic subgradient method. CoRR, 1bs/1212.2002. 2012.
[Mir17] Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017, pages 263-275. IEEE Computer Society, 2017.
[MM97] Benoit B Mandelbrot and Benoit Mandelbrot. The variation of certain speculative prices. Springer, 1997.
12

---

[Sch14] Rolf Schneider. Convex bodies: the Brinn-Minkowski theory. Number 151. Cambridge university press, 2014.
[SSSS09] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT 2009 The 22nd Conference on Learning Theory, 2009.
(SSSSS09] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In Proceedings of the Twenty Second Annual Conference on Computational Learning Theory, 2009.
[SZ23] Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[WXDX20]] Di Wang, Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex optimization with heavy-tailed data. In Proceedings of the 37th International Conference Machine Learning (ICML), pages 10081-10091, 2020.
13

---

A Deferred proofs from the main body
A.1 Deferred proofs from Section 2
Lemma 2. Let P be a distribution over S satisfying Assumption 1. Then Fp is GL-Liscchizz
Proof. This follows from the derivation
max aeX
Espp
[V fx; $]]l|
max [f( $ Esp max ZEd Vf s)ll S &G.
max
zEx
A.2 Deferred proofs from Section 3
Proposition 1. Lel p 2 O, and it be the output of Clipped-DP-SGD with TJ < X for all _ and T 2 max(n, 2) Clipped-DP-SGD satisfies p-CDP, and 0 0 o² u'p'
320 by An?p +
7Ar2 where x=' := argmin FD,x(x). #Ex
((FDA) FD,(
n
Proof. For the privacy claim, note that each call to Line a postprocessing of a 2C -enssitivee statistic of the dataset D, since neighboring databases can only change n. EZeem) (V. by 2C in the &g norm, via the triangle inequality. Therefore, applying the first and third parts of Lemma 1 shows that after T iterations, the CDP of the mechanism is at most T We next prove the utility claim. For each < T, denote
x
20
n2 S.P p.
1
A := E [Z) (x.A(=))) ] 4, E
101 x
9: = VFD(a:),
where all expectations are only over randomness used by the algorithm, and not the randomness in sampling D. First-order optimality applied the definition of 1441 implies, for all ( < T,
(g: + Et. ox - -x") + (AXe+1, T++1 - x²) S
(I - x' 112 1 - =²1)²) + 2t ll.. + & 21)r
2
Adding (g: 9. Ee, x*) to both sides and rearranging shows
(x+) + X |k++||1 - (x)x + 2
| - x11
2
< (gt, - xx*) + (AT141, =x")
$ 2m (112) 1ora-x110 x²11 1-11-1111"""
Tt. ll + + [ge - E,, - x²))
-:
2
< 2m, (11e2 - x11 -11 - x² I²)) + C2 + m 115. + bn ||:0 - x=1l - (Ee, 30. - x²).
In the first line, used strong convexity of the function }/ ||~|| ? and in the last line, used ||a + b1l2 < 2 ||a]| + |]6| and the definitions of C and bp. Next, adding (1|x2]1 || 12) to both sides above and taking expectations over the first iterations yields
1 (Ø. A, + A _ 17t
b2 A
+.+1) + (C² + +Zd) +
T + 2
E - 2 (1t4+113)
where we used the Fenchel- Young inequality to bound by | x - 0p plugging in our step size schedule V)-
||, x= 11. Now,
x(tFI.. multiplying by + 4, and rearranging shows
(t+ +)44) v +(L+3)(1 + 4)
T X(l + 5) + 4)
Φe+1
4
4
4(1 4) (3C2Td)
(1 + 4)1
A(l 4)
(E [1| El 12),
+
+
+
X(t +1)
n?p
x
2
14

---

Then | xx,z < 2G:, A where plugged in the choice o² and T 2 n'p using that all iterates and x² lie in B(r), and dividing by Z := Eoster (t ++++) 2 shows
d, C² d'd Summing the above for 0 < T,
22
16C
1/
Σ (1+4)
+
Σ
E
Z
Z
2Zn²p
X
27
0S1KT
tE|T]
6Ar²
by
dr
b0
7Xr²
+
-
+
+
7
An?p
T
Xn2 p
A
T
The conclusion follows from convexity of FD.,, the definition of &, and T 2
Lemma 3. Let D ~ ph, where P is distribution over S satisfying Assumption 1. With probability least $ denoting bn as (26), we have
5G
bD S (k: 1)Ck-I
Proof. For every 8 S let x" (8) argmaax 2EX (lc s))
Then, we have
EDupa
FDuP
max sEt
Vf((z) Σ (c((((()))
iE(n)
1
E
EDupp
max xEN
fi) II. -Ic((
iE(n]
E [[V](( (k - 1)0k-1
Egup V -VVV
-k- 1)Ck--
The last line used independence of samples, used Fact on the random vector V (=(x=(()) (s); and applied Assumption I with the definition of x² (s). The conclusion uses Markov's inequality. I
Lemma 4. Let A 2 O, let P be distribution over S satisfying Assumption 1, let T E X' where X Rd is compact and convex, and let
Fo(x) + > 1| 1|x--il -=1]] where ('(xx) LEa [f(x;))]
xx, == arggmin zex
(7)
Proof. Letr = || x² By strong convexity and the definition of xx.==
2
Fr(x") > ||= =112 < Fr(T) Fr(x*) S Gir.
2 < (T)
Here, used that Fp is G Lipishhhiizz (Lemma 2), and rearranging yields the conclusion.
Lemma 5. Let 2 0, ler D ~ p where is a distribution over S satisfying Assumption 1, and let I E X where X C Rd is compact and convex. Following notation (4), (5), let
A || 212 for 2G 2
y argmin zEX
(Foie (x)
X
and let x3.2 be defined (7). Then with probability > 0.95 the randomness D pn.
90G₂
|| - x - A/n
15

---

Proof. For each s();s,, define restricted variant s(x;s) = (2; and let Fp = Es-sf(;;)) 8), Similarly, define FD to be the restricted variant of the empirical loss PD. Because Fp pointwise larger than Pp and xx, E r) by Lemma 4, it is clear that
X 1|. - E|| (F(()) + 2
2 xx,= = argmin =EA
and y is the minimizer of the empirical (restricted) variant of the above display. Moreover, each of the regularized functions f(x;; s) + + || - æ||² has a Lipschitz constant at most Ar = 2G larger than its unregularized counterpart in X' BB r), so these functions satisfy the moment bound in Assumption for j = 2 with a bound of 2G3 SG9. Now, applying Proposition 29, [LR23] yields
X PT(() + 2 1 - 01(? - F +
xx, -aaa==
2
(D(vV) + 11 - x|})
(D(()x.) + || =11²)
(T)(s)) + 2 11 - =1(²)
(D(w)) + 2
|1y - =|(²) 2
+
4G3 + 16G 4G3 + 16G +
20G3
0
An
An
An
The first equality used that 2x, is independent of sampling D, and the second used è is the empirical risk minimizer. The conclusion follows from Markov's inequality and strong convexity.
Theorem 1. Consider instance of k- t-heavy-tailed private SCO, following notation in Definition 4, let x² = argmin Fp(x), and let p 2 0, (0,1), 1). Algorithm 2 using Algorithm in Line
p-CDP algorithm which draws 'D pa, queries Cuco max(n?, =²²) sample gradients (using samples in D) universal constant Osco, and outputs x E X satisfying, with probability 2 1 8,
(Vilogg
(Vdlog (1) nVP
1-1
log (1)
- - Fp(x*)= S Cooo
GRD.
+ G2D
Proof. Throughout, we assume that at least large enough constant (where lossiness can be absorbed into Cıco), and that n is at least a sufficiently large constant multiple of log (because the entire range of Fp is < G2D). We first handle the case where is larger than polylog(n). deferring the case of small 1 à to the end of the proof. Let J E IN be chosen such that
n2 ]
400 log (1)
500 log )
logz
J
400
which is achievable with I = Olog n) and = Olog log") = O }). Let m := j. and assume without loss that is power of 2, which constant factor in the claim. For each i [4], let m, := m with samples, and subdivide each portion into I parts each with m, samples. For [J] and i [7], denote the samples corresponding to the 7th part of the j" portion by DJ, so
guarantee by discarding < 1 our samples, losing 2 We subdivide D into J portions, each
U U CD |d|| m; for all j [J], DJ D/ 0 for all (i. # (1,5). AE[s)
Next, show how to implement Line 5 in Algorithm 2, for iteration i [7]. by calling Algorithm with appropriate parameters. Let n <- mis p + p. and initialize Algorithm 3 with the dataset Djepj/D D/ and R = A4' where
A,
d mypp
G2 m
A = 3C pop
G
16

---

By Corollary 2, each independent run outputs x/ E A' satisfying, with probability 0.55,
1-
Creg.pop pop
va
G2 m
4
1 - 2.
Gk
(9)
X
mivP
3
3
6. at least 0.51J of the copies satisfy the X with the same probability. Union bounding over all iterations of Algorithm yields the failure probability. and so we obtain the claim from Proposition 2, after plugging in (m log( since the dominant term is DA. The privacy proof follows from the first part of Lemma since for each pair of neighboring databases, exactly one of the datasets D. are neighboring, and Corollary guarantees privacy of the empirical risk minimization algorithm using that dataset; privacy for all other datasets used is immediate from postprocessing properties of privacy. The gradient complexity comes from aggregating all of the IJ calls to Corollary 2, where we recall the sample sizes decay geometrically.
Therefore, by a Chernoff bound, with probability 2 above bound, so Fact 2 yields x; satisfying ||,; =1|l R A4'
Finally, if is smaller than polylog(n). for the 1th iteration of Algorithm 2 we instead set J: [400 log( {,) 500 log( } where 6; := 5. Then subdivide consecutive batch of zt samples into Jj portions, and follow the above proof. It is straightforward to check that (9) still holds with the new value m, = _ because the 4' factor growth on the right-hand side continues to outweigh the change my The error bound follows from Proposition 2, and the privacy proof is identical. C
A.3 Strongly convex heavy-tailed private SCO via localization
Finally, by following the template of standard localization reductions in the literature (see e.g. Theorem 5.1, [FKT20] or Lemma 5.5, [KLL21]), Theorem I obtains an improved rate when all sample functions are strongly convex. For completeness, we state this result below.
Corollary 3. In the setting of Theorem 1, suppose fI;;) s) is u-stroogly convex for all E S. There an algorithm which draws D P", queries Cwco max(n?, " sample gradients (using samples in 'D) for universal constant C and outputs X satisfying, with probability 2 -11. 5,
1-
G /
ddlog" (t) n2pp
G2 log (4)
((a))=F(xx)) S Coso
11
Proof. This is immediate from the development in Section 5.1 (and the proof of Theorem 5.1) of [FKT20], but we mention one slight difference here. Our guarantees in Theorem 1 do not scale with the initial distance bound to the function minimizer, and instead scale with the domain size, which makes less directly compatible with the standard localization framework [FKT200. However, because Theorem holds with high probability, we also have explicit bounds on the domain size via function error, as seen in the proof Theorem 5.1 in [FKT20], so we can explicitly truncate our domain to have smaller domain without removing the minimizer. With this modification, the claim follows directly from Theorem 5.1 in [FKT20].
B Optimal Algorithms in the Known Lipschitz Setting
Compared the standard Lipschitz setting (i.e. the oo-heavy-tailed private SCO problem), algorithm in Section 3 has two downsides: it pays polylogarithmic overhead in the utility, and requires extra aggregation step. In this section, assuming are in the known Lipschitz k-heavy- tailed setting (see the following Assumption 2, and Definition 4), we provide a simple reduction to the standard Lipschitz setting, resulting in optimal rates.
Assumption 2 (Known Lipschitz h-heavy-tailed distributions). In the setting of Assumption 1,
suppose that for each S we know a value I., 2 L,- For k E N satisfying k 2 2, we say P satisfies the known Lipschitz k-heavy tailed assumption if. for sequence of monotonically nondecreasing (Gy}sE(H) have Es-p [[]] < G3 < so for all j [k].
17

---

Note that Assumption 2 clearly implies Assumption 1, but gives us additional access to Lipschitz overestimates with bounded moments. We require some additional definitions used throughout the section. First, we augment 8 with designated element so & S, and define
fz; su) 0 for all X.
(10)
We also define a truncated distribution parameterized by C 2 O, where we use f(; 80) in place of sample functions with large Lipschitz overestimates, following notation of Assumption 2:
f(z))) L, SC (1;;8) = (z( I, > C (0) = f(2; (1; 8) = Espp [ (x; (x: (11)
We denote So U {so}, and for D S", the dataset DC Sjj replaces all s E satisfying L, > C with sp- We additionally provide second reduction the known Lipschitz heavy-tailes setting, when all sample functions are assumed to be j--ttronlyy convex. Because our treatments of these cases are slightly different, we use different notation when μr and μ > 0, for convenience of exposition. Fixing an arbitrary point E E X, for 0, instead of using the constant 0 function as in (10), we define a strongly convex alternative I sp), for designated element sy:
f(z; = 11 1 =|| for all x E E
(12)
The truncated distribution parameterized by C 2 pD, is defined in a similar way:
(x; (f(z;) IC (p()sp) Lg >00'
= [1x; (x; 8) = EsNp [1 (2; s)]
(13)
We denote Sp = S UUSUUU (sp). and for D S", the dataset D E Sp replaces every s E such that
Ig > C with Sμ- Our foeus the regime C #D is motivated by the following well-known claim.
4
Lemma 6. Let X C Rd be compact and convex satisfying diam(X) D, and suppose f X R L-Lipschitz and p-strongly convex. Then, > HD
Proof. Let x* = argmin f(x). By strong convexity, for all E X.
1 o x=1
- f(x')( -| x=1
2
Now, choose such that || x11l 2 2 To see this is always possible, let a, E X' realize || - x'Il D; then least one of x. x' must have distance > D from xt by the triangle inequality. The conclusion follows by rearranging after using our choice of x.
In other words, Cf < nD then no sample function will survive the truncation in (13). Finally, we parameterize the performance of algorithms in the standard Lipschitz setting.
Definition 5 (Lipschitz private SCO algorithm). We say A is an L-Lipschitz private SCO algorithum if it takes imput (D, p. X), where D E S" is drawn i.i.d. from P. distribution over S where every E S induces L-Lipschitz f(;s) over C Rd, A(D, p, X) X, and A satisfies p-CDP. We denote == EA (A(D,
min Fp(x),
ZEX
where Fx(2) ;= := ((; and denote the number of sample gradients queried by A by N(A). Moreover, if each Lipschitz function f(; s) is u-strongly convex over the convex domain X, we say A is an L-Lipschitz, p-stroongy convex private SCO algorithm, and define Err(A),, N(A) as before.
With this notation place, we state our reduction.
We begin with simple bound relating F and Fp.
Lemma 7. Let Fp be defined in Definition where satisfies Assumption 2, and define F& as at 4G
Gt in (11). Then, Fp- FS is (R-1)C I -Lipschitz and Fp F.C. is Tk-1)04 + -Lipschitz.
18

---

Algorithm 4: KnownLipReductionn,.C./
Input: Dataset D E S", clip threshold C E R20, strong convexity parameter E R2o, privacy parameter p E R>o. domain X' E R", C-Lipschitz private SCO algorithm A (if 0), or C-Lipschitz p-strongly convex private SCO algorithm (if μ >> 0)
if J ( then
Return: A(DC, P, X) end
5 else
Return: A(D P.)
7 end
Proof. For Se = su if Lg C, and otherwise let i(s)) s. For any x, x, E X, we
have
(Fp(x) FFF (Fp(z') Ff(x') = Esup [f(;;)) f(); - f(a';)) + f(a;;
EaND [[[();) - f()';s)) 1,,
G
< F spp TT. || x'll TT,cl S (I: (1-1)C | I'll
In the second line, used that (s)) unless I,, C. in which case f(; (s)) uniformly. The last line used the definition of L, and Fact 1 with X I,, recalling Assumption 2.
Next, analyze F Overloading л (s) 8y if T. C, and letting (()) otherwise,
( - (x)) - (Fpx')) -F = Empplf(x;>) f(;; T (s)) - f(';;s) + f(z'; (s))
= ESPP ([f(r;)) f(x;;)) s) + f(d::8p) - f(x; sp)) T
s EgNp [. || x' |z,acl + ESSNP |4Gx ||0 - x' I,>c
4G
|| | 2'1l
(k - 1JC O
In the third line, we used that μD < 4G, S 4Gr by Lemma and Lemma to show that f(; s,) is 4Gp-Lippchitz over X. Finally, the last line used Markov's incquality to bound Ellz,>c!- [
Using Lemma 7, provide straightforward analysis of Algorithm 4.
Proposition 3. Consider an instance of known- known-Lipschitz k-heavy-tailed private SCO (Definition 4), and let p 2 If A is C-Lipschitz private SCO algorithm (Definition 5) and μ Algorithm using A is p-CDP algorithm which outputs x E X satisfying
GRD
E (F)(x) Fp(x')] Err(A) + (k. 10)1)) where x² argmin Fz(x).
2EX
Further, if f(;;)) is p-strongly convex for all s E S and A a C-Lipschitz, p--strongyy convex private SCO algorithm for > 0, Algorithm 4 using A p-CDP algorithm which outputs x E X satisfying
[x)( Fz Err(A)
G
4G Ch
(
2G ju(k
8G PCk
2 V
+
Err(A) 1
(k: 1ICk-T
where x² = argmin (x) ZEX
In either case, Algorithm 4 queries N(A) sample gradients (using samples in D).
19

---

Proof. For the first utility claim, letting = = argmin (x()), we have
E [[F(()) - Pr(x*)]
= [ (x) - [x((1"]
+ [(Fp(1) Ff(x)) - -Fr((*)
Gk
s E (x) 1f(('00]] (k -k-I)C=- L |||e x01l
(14)
1)
G (k: 1)C
< Em((A)
where the first inequality used the definition of x²cC C and Lemma 7, and the second used the definition of Err and tiam(()) D. For the second claim, we first have
M x
00 S Err(AA
E
x
by the definition Err(AA and p-strong convexity of FF so that E[||== x-1 s (r)()))) (( by Jensen's inequality. Moreover, we also have
1 2 | -x00-x100 x²1 < Fr(x**) - Ff(x*)
s (Pp(x* Fg (zx,O0)
G 4G (k 1)C
|
-x'll,
where we use optimality of C in the second incquality, and Lemma 7 in the third. Combining,
(
G
4G
2
E x - x+1 S
+
+ V Err(A),
C
and then the claim follows by substituting this bound into (14).
We can use any existing optimal algorithms for DP-SCO to instantiate our reduction. In particular, use the algorithm of [FKT20], denoted by ALip. which has the following guarantees. For simplicity of exposition, we focus on the case where our functions do not possess additional regularity properties e.g. smoothness, and also focus the simplest ALip which attains the optimal utility bound. Because of the generality of our reduction, however, improvements can be made by using more structured faster subroutines ALip: such the smooth DP-SCO algorithms of (FKT20) or the Lipschitz DP-SCO algorithms of e.g. [AFKT21, KLL21, CJJ+ which are more query-efficient, sometimes at the cost of logarithmic factors in the utility (in the case of [CJJ 23]).
Proposition 4. Let P be a distribution over S such that [c; is L-Lipschitz and convex for all S. There exists a constant CLip such that given D S" the algorithm ALip is p-CDP and outputs pev such that, for a universal constant CLip- letting x= == -argningexx Fp(x).
(GoD
LDVA nVp
E[Fp( Fp(x*)] CCip
and ALip queries < CLip max(n? x² sample gradients (using samples D), where Gy is defined as in Assumption 1. Moreover, if f(: is u-strongly convex for all E S, then
G2 {
L2d pn?
E[Pp(uppiv)) [x(x*)] CLip
pm
and Aup queries S CLip max(n?, = sample gradients (using samples in D).
Proof. This follows from developments in [FKT20), we briefly explain any discrepancies. The case applies Theorem 4.8 in [FKT20], where for simplicity consider the full-batch variant
20

---

which does not subsample." & Moreover, Theorem 4.8 in [FKT20] is stated with dependence on L rather than G2 on the n 1/2 term, but inspecting the proof shows it only uses second moment bound. The μ 0 follows from Theorem 5.1 of [FKT20], using Theorem 4.8 subroutine.
We are now ready to present our main result in this section, using our reduction with ALip-
Theorem 2. Consider an instance of known-Lipschitz k-heavy- taillyt private SCO (Definition 4), let 2 O, and let x² == argmingex Fp(x). Algorithm 4 with C < G1 (2x/)) using ALip in Proposition 4 is p-CDP algorithm which outputs x E X satisfying, for a universal constant CHT,
(">/2)
GzD Vn
vd
((Fp(z) - FT(x*)] S CHT
G
nVP
=) sample gradients (using samples in D). Further, if f(;;8) is p- strongly convex for all E S, Algorithm with C + Gx( (n²0) ) ) using ALip in Proposition 4 is p-CDP algorithm which outputs X satisfying
querying < OHT max(n²,
d
G um
G
E [[F((x) Fx(x")) S CHT
querying S CHT max(n?, n²)) sample gradients (using samples in DD.
Proof. Throughout the proof, assume without loss generality that d S n²p, as otherwise all
4G by
stated bounds are vacuous since the additive function value range over X' is at most G2 < P
Lemma 6 and Lemma 2. This also implies that C 2 Gş in either case.
In the μ = case, Proposition 3 and the guarantees of ALip in Proposition 4 imply that
E [[Fp(+) - Fp(x*)] Err(Aup) + G
Ck-1
G2D Vn
+ CDVd
+ G Ck-
s CLip
nVP
GoD Vn
Vd nVp
< (CLip +)
+ GtD
where the last inequality follows from our choice of C. Next, we consider p. Proposition 3 and the guarantees of ALip in Proposition 4 for this case imply that, assuming CLip 2 2 without loss,
5G
DEp,,n,d,,,C...
10G MC
E (F) - Fx(x')) S Err(Auip)
CK-1
G2
Cdd
5G
106k (uVn
G2
unvp p.n-1)) ))
Ovd
s CLip
+
pn
um2p
Ck-1
G2
G
d 1-t
< (Clip + +1)
+
um
n2p
where we used C' 2 G3 to simplify bounds, and applied our choice of C',
'The subsampled variant only satisfies weaker variant of CDP called truncated CDP, with an upside of using times fewer sample gradient queries, but this less comparable the lower bounds in [LR23].
21

---

C Fast Algorithms for Smooth Functions
In this section, we develop a linear-time algorithm for the smooth setting where we additionally assume {(; 8) is 3-smooth for all 8 8. Our algorithm attains nearly-optimal rates for sufficiently small value B, and is based on the localization framework of [FKT20]] To apply this framework, we show that variant of clipped DP-SGD (see Algorithm 5) is stable the heavy-tailed setting with high probability. We then ensure that stability holds for any input dataset (not necessarily sampled from distribution P), by using the sparse vector technique [DR14] 14] to verify that the number of clipped gradieets is not too large. In Appendix C.I. we provide some standard preliminary results from the literature. We use these results in Appendix C.2, where we state our algorithm full as Algorithm 7 and analyze it in Theorem 3, the main result of this section.
C.1
Helper tools
First, we state a standard bound on the contractivity of smooth gradient descent iterations.
Fact 3 (Lemma 3.7, (HRS16)). Let f X + IR be 3-smooth, and let r S z. Then for any I. x/ X,
(x - -²)=x) n V VV(x()) < || r'1l-
Next, we provide a standard utility bound on one-pass SGD algorithm using clipped gradients.
Algorithm 5:
Input: Dataset D = {>tere E S", clip threshold C E Rgo, step size E Rgn, iteration count
T N, domain C B( D) for 24 X
for 0 S t T do
Ft+1 & argmin (n (V + || x,112}
end
Return: 8 + EoSee
Lemma 8. Consider an instance of ke-hevy-tailed private SCO. following notation in Definition and let u E X be independent of DD. Assuming ' ~ PT i.i.d., Algorithm 5 outputs it X satisfying
|20 u|1
G
G
[[Fp(#) - FP(u)] <
+
2n7T
2
(A:
1)CK-T
Proof. To simplify notation, let 9: (((58441) for all 0 < < T, and let Tc(g). 8141 P is independent of Ie, we have that Egt = FFp Therefore, in iteration t,
Because
Fr(æ.) (Tp(u) = E Kgr, Te - -u]
< F [0t, Ht u) + 11g. rzll D]
(15)
1
u|| + G2
G (A: - 1)
S [r - u|l |
where all expectations are conditional on the first iterations of the algorithm, and taken over the randomness of 8t+1. 1. In the third line, we used the first-order optimality condition T1+1, applied Fact bound l[ge Gell. and used
E | < E 11g:1 G.
(16)
Summing across all iterations and dividing by yields the result upon iterating expectations.
We also the following straightffrrwrdd generalization of Lemma the case of randomized clipping thresholds, which is used in our later development.
Corollary 4. For C, Ć 2 and E IRd, define the operation
(I(())
| 2 C
Tc.c(9)
else
22

---

If Algorithum is run with II (z) s4+1)) replaced by c,e, (Vf St41)) where Cj is inde- pendent of S14.1 and satisfies Õ₂ 2 & for all 0 S < T, then following notation in Lemma 8,
[(F((#) - Pr(u)] 100 ull 2n7T + 2n/ + (h: - (
G
Proof. For fixed iteration 0 T. the calculation (16) changes in two ways. First, in place of the variance bound (16) (which used @e S |19.1 deterministically, when using the modified clipping operators require the modified deterministic bound
0l < 2 Il9ell,
which follows because ||
|| * ||9a|1 (which implies = || only if ||9a]] 2 - Moreover, in place G 1)0t-r which followed from Fact 1, we instead have
of the bias bound E 119: rell I [k-
T.c. (9:) ge E C
G
IIaell 119.112 s EE
| 11
gell
(k: - ())
The conclusion follows by adjusting these constants appropriately in Lemma 8.
Next, for R, r 2 O, we let BLap(R. denote the bounded Laplace distribution with scale parameter R and truncation threshold T be defined as the conditional distribution & Lap(R) on the event [sl S (recall that Lap(At) (t) has density function exp( R I())). It is standard calculation that
| S Rlog ()) -1 -
Pr {nLaa((R)
(17)
so that the total variation distance between Lap( and BLap (R, R log(H)) 6. We hence have the following bounded generalization of the privacy given by the Laplace mechanism.
Lemma 9. Let 6 1). If S(D) R is A A-sensitive statistic of the dataset D, i.e. for neighboring datasets D we have that (S(D) S(D)) I A, then the bounded Laplace mechanism which outputs S(D) + & where & B for any 2 A log(3) satisfies (e, DDP
Proof. For notational simplicity, let denote the Laplace mechanism (which samples & ~ Lap( A instead of BLap( A T)), let A denote the bounded Laplace mechanism, and let & C IR be an event in the outcome space. By standard guarantees (e, D)- of A (e.g. Theorem 3.6, [DR14],,
Pr A(D) E E] < Pr(A(D) E E]
(18)
8 S exp(e) Pr [A(D') E E +
< exp((s Pr [r(D'') E E]
for any neighhoring datasets, where we used exp(e) < 3 and that the total variation distance between (A(D),A(D)) and (A(D').A(D') are bounded by 4 by (17).
We also use the sparse vector technique (SVT) [DR14]. which has been used recently in private optimization in the user-level setting [AL24]. Given an input dataset = {s:lie(n) E S". SVT takes stream of queries (11, .2.............................. 4T D - R in online manner. We assume each yi is A-sensitive, iee. 14: (D) - (D") S for neighboring datasets D, D' E S One notable difference that our SVT algorithm will use the bounded Laplace mechanism, rather than the Laplace mechanism, but this distinction handled similarly to Lemma 9. We provide a guarantee on this variant of SVT in Lemma 10, and pscudocode is provided as Algorithm 6.
Lemma 10. Let 8, (0,1) 1) and suppose
6A
10T
R
2
clog 8
T 2 Rloog 8
(19)
Algorithm 6 outputs sequence of answers {a, E {1, THE for some k [T], and is (),8)-DP
23

---

Algorithm 6: (D, f0 My L, T)
Input: Dataset D = ha(n) S", A-sensitive queries {% 8 - [ count threshold
E I,, query threshold L E R, scale parameter R E Rgo, truncation threshold E R2o
2 i < 1, count + 0
b f L + & for BLap(R,
while i E [2] and count < coo
E~ R2,, 2r)
if qf (D) + < then
Output: a; f 1
i 1+1
end else
11
Output: a; f- T
i- 1, count count 1
13
b b L + for ~ BLap(R,
14
end
end
16
Halt
Proof. The proof is analogous to Lemma 9. Let A denote SVT run with Laplace noise in place of bounded Laplace noise (i.e. T = oo), and let A denote SVT run with bounded Laplace noise. We first claim that is (e, -DP, which is immediate from Theorem 3,23 and Theorem 3.20 in [DR14].
Next, by union bound on all of the 2T random variables sampled, the total variation distance between (A(D), A(D)) for any dataset D is bounded by S Then, for neighboring datasets D, D and some event & in the outcome space, repeating the calculation (18),
Pr [A()) E E < Pr[A(D) E E]
8
exxp(e Pr (A(D') E E]
+
+ S
exp(E) Pr [A(D") E EE] +
5 5
C.2 Algorithm statement and analysis
In this section, we present the full details of our algorithm (see Algorithm 7) and prove corre- sponding guarantees, separating out the privacy analysis and utility analysis.
24

---

Algorithm 7: Localized- Sttpii/dd-Cippee-D---SS-- 20. 77, c,
Input: Dataset DD E S", initial point zo E A', step size E Rso, parameters C, w E Rso.
privacy parameters (s, 6) E 50
2 I + [ogg n2,. n t 2 for 7 do
f 2 t 2. wi t w 6Cr33
Ö C+ ( wi log( 30m, )), c BLap( f). count
24,1 f- 24-1
for j E [nd] do
Bij f (Ere(s) ny + 1)th element of
Mij BLaappppuut 2wi; 2w; log( 30m,
10
( + V.j 2 C then
count count +
12
D.j - (Vc(Vf( si.s))
C BLap(u wi, wi log( 30m. ))
13
14
end else
15
9b.j (f(
17
end
if count
2 é then
19
Return:
20
end
Zijt1 + 11x(x10 T(9ts)
22
end
1 ni EjE(m)) Vig
23
I, + Si. where & NN with o; 30C', y (3/(3/8)
end
26
Return: 27
The following theorem summarizes the guarantees of Algorithm 7.
Theorem 3. Consider instance of k-heavy-tailed private SCO, following notation in Definition
and let x* == argmin,ex FT(x), and e, E (0, 1). Algorithm run with parameters
4
D
DI
2²
24
1 - min
V n
G2
Ggn
14400d log 2( 15m
DTn= 14400dn log ( (15))
KFI
240
15n
18
15
C 2
c
2clog
E
8
(e, 8D and outputs x, that satisfies, for universal constant Csmoothr
(Valoge(s)
1-1
G₂D
[[Fp(x)) - Fx(x")] S Csmooth
+G,D
Vn
NE
assuming f(:8) is 9-smooth for all s E S, where
1.5
<
24000
30m
k-1
(20)
G2
Vns 15
G
02.5n n
(doog(()) n?g2
max
Vd (g)
D Vdlog(n) log (%)
We now proceed to prove Theorem 3.
25

---

Privacy proof overview. We first overview the structure of our privacy proof. Consider two neighboring datasets D, D' that differ on a single sample $1,o # 5' The core argument used to prove privacy is controlling the total number of times when gradients are clipped, so we introduce the variable "count." Note that we have | 2 s = O(Cn) due to the clip operation. If no clip ever happened afterward, then we know I| - _n__ |l S || - 5o = O(Cr) due to our smoothness assumption (see Fact 3), which means the algorithm is private. When count is not too large, we can still bound the sensitivity between || - ''I,,,1 ll by O(Cr). However, when the value of count is larger, there is a risk that the sensitivity of si,,; not bounded as before, and hence we halt the algorithm when count exceeds some appropriate cutoff point éq
One subtle difference between our algorithm and standard uses of SVT is that we add Laplace noise to the cutoff point e to obtain a randomized cutoff é. This is because the sensitivity of the count increment at the je iteration of phase i is bounded by one, even though |/ f ( ( f $1.io ]| can be arbitrarily large. The guarantees of the bounded Laplace mechanism imply that the noise added in é₁ hence suffices to privatize count.
In summary, we can control the sensitivity between | - و',gن for all j due to the termination condition in Line 18 and our use of bounded Laplace noise, and hence can control the sensitivity of the query for [ st,))l [ ا(,ي) for all j # jo. By adding Laplace noise on the cutoff c, we handle the issue of the sensitivity of the 1oth query || [ $1,50) being unbounded. If the algorithm succeeds and returns 2g, know the sensitivity || Li is O(Cr,)) and the privacy guarantee follows from the Gaussian mechanism. If the algorithm fails and outputs I, the privacy guarantee follows from the bounded Laplace noise on the cutoff point and the guarantees of SVT.
Privacy proof. We now provide our formal privacy analysis following this overview. To fix notation in the remainder of the privacy proof, we consider running Algorithm 7 on two neighboring datasets D, D' that differ on a single sample $i.jo # s' for some E [T]. By standard postprocessing properties of differential privacy, it suffices to argue that the 7th phase (i.e. the run of the loop in Lines 3 to 25 corresponding to this value of is private, so we fix E [T] in the following discussion.
We let { and { be the iterates of the 7th phase of Algorithm 7 using D and D', and we let Yú, and Yi be the respective 0-1 indicator variables that count increases by 1 in iteration j. We also let county and count', denote the values of count at the end of the j"h iteration, and abusing notation we let č,, E² be the values of é in the 7th phase when using D or D' respectively. Finally, we denote x; := 2.
m. Eje(n.) Fi.j and let x' denote the average iterate using D'' similarly.
We first bound the sensitivity between the iterates {uig) (eEm)) and (xt. in the following lemma, assuming count, and county are bounded. The proof is deferred to Appendix H.
Let E [na], and suppose that 1921,Bc S and C 2 Swi log( 30p=). l0g( If ooountt C count' Er and Yi,- YY,, for all j < with j * jo. then
Lemma 11.
|| - 2ا Il S 60mp
Using this bound on the sensitivity, we are now ready to prove privacy of the algorithm. Lemma 12. Algorithm 7 is (e, 6) if it is run with parameters satisfyyng
30n, 8
6
12 5
18
15
C' > Sw; log
log
2c log
192n; < 1. (
Proof. Recall our assumption that D and D' only differ in $i.jo- the jith sample used in the 7tth phase of the algorithm. The privacy of all phases of the algorithm other than phase i is immediate from postprocessing properties of DP, so it suffices to argue that phase is (e, 6)-DP. Note also that the conditions of Lemma 11 are met after reparameterizing 5 < 3. We split our privacy argument into two cases, depending on whether the algorithm terminates on Line 18 or Line 26.
Termination on Line 18. We begin with the case where the algorithm outputs 1. We introduce jES to be the 0-1 indicator some simplifying notation. For iterations S C [ni], define Ws == (Yi,g) F
variables for whether count incremented on iterations j S (when run on D), and define [W]s :=
26

---

Ejes Yij to be their sum. Similarly, define W's and [W"]s for when the algorithm is run on D'. Observe that the algorithm outputs 1 iff the following event occurs:
Yijo + [IJMM5 2 & > (YiJo - ()) + [m]mao 2 - -
The right-hand side -IW] [io-1] is independent of whether the dataset used was DD or D'' so it suffices to argue about the privacy loss of the random variables YiJo è and W WnniNobol as a function of the dataset used. First, Yi is clearly a 1-sensitive statistic, so Lemma 9 implies (5: >iiniistnnguihhall as function of the dataset used. Next, conditioning value of i. G. the random variable WinlNNool is an instance of Algorithm run with a fixed threshold é Yi.io - [bo-11 I 2c, where we rename the output variables {L, Т} to {0, 1}. Moreover, Lemma I and smoothness of each sample function implies that the sensitivity of each query [vV[(=;,,) st,)) is bounded by == 6Cn,,3 Therefore, Lemma 10 shows that Win.MBal is ($. 3 "---ddstiinuishablle where we note that we adjusted constants appropriately in w and the failure probabilities everywhere. By basic composition of DP, this implies Yi é; + [W]]o (a
Yi,ja é is
the
postprocessing of Yi.oo - è and Win])bol Vi.jo è is (3 3) )DP, as required.
Termination on Line 26. Finally, argue about the privacy when the algorithm does not terminate on Line 18. As before, the sensitivity of T; is bounded by 6C'r, via Lemma 11 and the triangle inequality, conditioned on (33 26) >-indistinguishable event (i.e. the values of Yijo è and W Wir.].Go
Yi.jo a3). Then I; is (5: J-iindstinguuisable by standard bounds on the Gaussian mechanism (Theorem A.I, [DR14]), which completes the proof upon applying basic composition.
Utility proof. The utility proof follows the standard analysis of localized SGD algorithms and a specialized analysis of clipped SGD (Corollary 4). We first state a utility guarantee in each phase.
Lemma 13. Following notation in Algorithm 7, fix i E [1]. and suppose D ~ p i.id where P
satisfies Assumption 1. For any x E X, if C 2 Sw; log( 20nx) ) and 2 max(n 2G ) Glog())),
| x1-1 Gm
G (k 1)((t11 n²
G2D
E[Fp(x.) - (())) S
27:
Proof. By Markov's inequality, EspplL,, S (2 )h, so the total number of expected samples with Te E is most q. Hence by applying Chernoff bound,
Pr Dapp
E1
1r,
2 1 n²
Conditional E, the algorithm will not halt (i.e., return 1.) and is running one-pass clipped-SGI) (Algorithm 5) using the modified clipping operation defined in the precondition in Corollary 4. Then, the statement follows from Corollary 4 follows: letting & denote the complement of E,
(x.) (x) ((F)(z;) Fxx E] Pr[E] + E(Fr(z,) FF())) Pr(E9
x 21-11
G
+ 2m, G2 +
(k (k-1)(() +[[P Fr(x) | Pr(e9
2mp
||0
11-1
GLD
+ G2,, +
+ +GDDPTET
(k (k-1)(g)*= 1)(
11-1
G
+ G2D
+ 2n: + (k 1)( n²
27:
where we used that Fp is G1 S -ipschhtt by Lemma 2.
Combining our privacy and utility guarantees, are ready to prove this section's 's main theorem.
27

---

Proof of Theorem 3. For simplicity, let Tu := xx" and Co := To -". | S D by assumption. Also, suppose that n is a power of 2, as the adjustment on Line only affects n (and hence the guarantees) by constant factors. The privacy claim follows immediately from Lemma 12 assuming its preconditions are met, which we verify at the end of the proof. By applying Lemma 13 each phase i [7] to z t 24, assuming its preconditions are met, we have
E [|G-=211]
GED
G2D1 n²
E [[p((1)) Fp(x*)]
Σ
21,
+ +m
(2)
+
iE(1]
+ E (Fx) FT
4D
n
G
G2D
+ G2ørVd
nm
2
(2)
Vn
3600C log(
n.
Σ
n,e²
2
iE[r-1]
In the first inequality, used G1 Cg-LLipchitzness of Pp by Lemma 2, and in the second inequality, we pulled out the = 1 term and adjusted indices, and bounded I S n and used Jensen's inequality to bound (E IK)/ < || = ofd. Now using that "i and Y/ are geometrically decaying sequences, we continue bounding the above display using our choice of C::
4D
14400
C. 2dn log (
GRDI (g)
G2D vn
E [(Fp(z)) Fx(x")
+ nG
2
+GzrrVd
17n
n=²
41
+ n + 2(AA))
Aो (G k+1
G2D
Vn + G2orVd,
1Jn
14400d log ( 15m
GDD!
841
for A =
C=
ns2
An
Next, plugging in our choice of
D
DT
n
2
= min
(21)
G2 Gkn
n
G2
we have the claimed utility bound upon simplifying, and using that G2ø, / is low-order term.
We now verify our parameters satisfy the conditions in Lemma 12 and Lemma 13, which concludes the proof. First, it is straightforward to check that both sets of conditions are implied by
36n3c VE
30n 8
2Gk k
26
15n 5
log
11 c 4n (c)
and c 2 log
(22)
given that we chose
2c log( 13) S c. Indeed, C Sw, log( 30m.
2n log( 30n
Ve'
1 which is subsumed by the first condition in (22). Clearly, 26 log( 15n ). giving the third condition in (22). Next, direct computation with the definition of 172 in (21) yields
4n (Gi=
Anz
k+1
2=2VAn An 4n V
c c=
G
Now because C depends inversely on 17 S 722 defined in (21), the second condition in (22) holds:
4n
Gx
Arp Gk
> 4n (Gx
An
4n
2G
DT
G DT
C
Finally, the first condition in (22) now follows from our upper bound on 3.
28

---

D Improved Smoothness Bounds for Generalized Linear Models
In this section, we give an improved algorithm for heavy-tailed private SCO when the sample functions f(x; s) are instances of smooth generalized linear model (GLM). That is, we assume the sample space S _ R and that for convex function IR R,
f ((s,)))
(23)
We also assume that all f1;; are B-smooth. Observe that
Vf(=;s) o' ((s,)))s
(24)
that for all x E X, (s; 8) are all sealar multiples of the vector We prove that under this assumption, clipped gradient descent steps can only improve contraction, in contrast to Fact 16.
Lemma 14. Let 8, IR and let x, x', Rd. Assume that
I| sg) (x' s'g)ll S -
Then for any C 2 letting sign(s 5) min[ C) and == sign(s') min([s'), C), we have ( tg) (s' |' S | x'|l-
Proof. Note that the premise is impossible unless sign(s - 5') = sign (x - g)). Without loss of generality, assume they are both nonnegative, else negate s, s', 9. In this case,
[ x') - (s =s'ggl - I x'll = (s' - z)² ||l|| - 2(s - s') (x - z'.9)
s' 2 (xr x'.g) g))
||
Now, observe that t t- 1'''s s' and st t < 2(v.g) as well, and we can reverse the above chain implications. |
(f- +))
sign(s ) for any value of C 2 0. Therefore,
Note that the premise of Lemma 14 is exactly an instance of Fact 3 where V (zx)) and Vf(x') are scalar multiples the same direction, which is the case for GLMs by (24). Hence, Lemma 14 shows the contraction property in Fact is preserved after clipping gradients (again, for GLMs).
We can now directly combine Lemma 8 and our contraction results, used to analyze the stability of Algorithm 5, with the iterative localization framework of [FKT20), Section 4.
Algorithm 8: OheePassCllipeed-D--SDD0...
Input: Dataset D (8:)ae(n) E S", domain X' c B(xo, D) for un E X
<- [og](n)]
+-2 2'
+ min(
8 D
2 D C Gt
Dpn I 32yd
G2
32d
for i [ do
M4 2n,,, T/: 1 C. 2'C, 21p0
D; first n, elements of D. D D (D,
8
I; & SheePassCClipped-SGee
C; Mii nl; X,Ti-1)
& ~ ((d,,oFT.)
10
24 + I & &
end
12 Return: TT
Theorem Consider an instance of h--heavytailed private SCO, following notation in Definition let x² = argmingex Fr(x), and let p 2 0. Further, assume that for convex function the sample functions f(x; s) satisfy (23) for all S C Rd. Finally, assume f(z; 3) is 3-smooth for all e S,
29

---

where B S m n. (2 F). Algorithm 8 is p-CDP algorithm which draws D ~ pn, queries sample gradients (using samples in D), and outputs xı E X satisfying
1-
I
vd nyP
E [[Fp(ær) - [p(x)) S 4G2DV 26G
Proof. We begin with the privacy claim. Consider neighboring datasets D, D', and suppose the datasets differ on the fth entry such that 8j E "D (if the differing entry is not in Use(r] D; Algorithm 8 clearly satisfies O-CDP). Let F3 and o be the outputs of Line 8 when run with the same initialization 14-1, and neighboring D, D/ By the assumption on B, since тO I 1) for all E [7], we can apply Fact 3 and Lemma 14 (recalling the characterization (24)) to show [ - All S 2n,C, with probability 1. Therefore, by our choice of a; and the first and third parts of Lemma 1, the whole algorithm is p-CDP regardless of which Dj contained the differing sample, since all other calls to OnePass- Laass-ClippedSGGi are O-CDP as we can couple all randomness used by the calls.
Next, we prove the utility claim. For simplicity, let žo == xx and Eo == x², so ||Eo| S by assumption. By applying Lemma 8 for all i [4] with xo f- 24-1 and + T4-1, we have
E [[Fp(x)) Fx(x*)]
Σ EE[1]
E (T.) FF( [Fp((z)) Fx()))
11
G
E
+
+ +GE Ey
277
2
(h:
1)Ck-1
4D
Σ
2-1
13ddnC2
n2
G
+ |V p
8d
G.n..
Ck-1
pn
1-
4D2 32dn
n22
GinC Ch-1 + + n63
G
d
1/2
pn
where the second line applied Lemma 2, the third used Jensen's inequality bound El[o, Fy ||]
E[[|2, 1 and our assumption 1: 2, and the last used the geometric decay of the different parameters. Finally, by plugging in our choices of C, we have
4D
GG
32dnC²
G
4D
n
32dd
+
2m
k+]
(G
D)
m
pn
CK-1
mm
pm
1-t
g +
Vd
S GzD
&G&D
n
nVP
We can also check that the final summand is low-order term, by using 1j S
32d
Ga
d
GinC 5G
24
n3
n²
The conclusion follows by adjusting n, since Algorithm 8 is run with sample count in [2, n).
E High-probability stochastic convex optimization
In this section, to highlight another application of our population-level localization framework, we show that it obtains improved high-probability guarantees for the following standard bounded-variance estimator parameterization of SCO in the non-private setting.
Definition 6 (Stochastic convex optimization). Let X C Rd be compact and convex, with diam(X') D. In the stochastic convex optimization (SCO) problem, there is a convex function f X + R, and we have query access stochastic oracle g X - Rd satisfying, for all X,
E [g(4]] @z()). E ||{( G
For convex function v X + R, goal in SCO is optimize the composite function f + vb
30

---

For instance, one can set y to the constant zero function to recover the non composie variant of SCO. We include the composite variant of Definition 6 as it standard extension in the SCO literature, under the assumption that the function vé is "simple." The specific notion of simplicity we use is that vb : X + IR admits an efficient proximal oracle (Definition 7).
Definition 7 (Proximal oracle). Let X C Rd be compact and convex. We say O is proximal oracle for a convex function X R for any imputs v E R ry R2o. Ovu) returns
ull + ((0)
argmin #EX
||
2m
In Theorem 5, we give an algorithm which uses n queries to each of and proximal oracle for 4, and achieves an error bound for f + tp of
o (GD
log 1 8
GD. n
(25)
with probability 2 1 - 6. Similar rates are straightforward to derive using martingale concentration when the estimator g is assumed to satisfy heavier tail bounds, such as a uub-Gaussian norm. To our knowledge, the rate (25) was first attained recently by [CH24], who also proved matching lower bound. Our Theorem 5 gives an alternative route to achieving this error bound. As was the case in several recent works in the literature [HS16, DDXZ21, Lia24] who studied gig-probbbbility variants of stochastic convex optimization, our Theorem 5 based on using geometric aggregation techniques within a proximal point method framework (in our case, using Fact 2 within Algorithm 2). However, these aforementioned prior works all assume additional smoothness bounds on the function f.
We use the following standard result in the literature as a key subroutine.
Lemma 15 (Lemma 1, [ACJ+ 21)). In the setting of Definition 6, assume t is X-strongly convex, let x² := argmin f(x) + (xx, and let T E N. There is an algorithm which queries the stochastic oracle g and a proximal oracle for vl each times, and produces & satisfying, with probability 2 z.
30G
| --'' AvT
We combine Lemma 15 with Proposition 2 obtain the following high-probability SCO algorithm.
Theorem 5. Consider an instance of SCO. following notation in Definitton 6, let n E N, x²x := argminzex f(x) + (xx), and 8 (0. }). There is algoritlum using queries to and proximal
oracle for vb and outputs x E X satisfying, for a universal constant Owe. with probability 2 1 - 5,
log
f(x*) - xxxx)) S Csco GD GD.
Proof. Assume without loss of generality that & is sufficiently large constant (else we can adjust the constant factor Csco), and that is sufficiently larger than log \ (else the result holds because the range of the function is bounded by GD). We instantiate Proposition with Fp + f + v, I с- log, n, and in each phase i [T] of Algorithm 2, we let n; proof, we describe how implement (8) in the 7th phase, where Fp <- vh, splitting into cases.
In the remainder of the
If is bounded by polylog(n) and n is sufficiently large, suppose that n is a power of 4, else we use fewer queries and lose constant factor in the guarantee. Then consecutive queries, divided into 48 log(
a batch of n. 5, portions, where 6; := zt- We then use Lemma 15 on each portion of queries, with f + f and db + ن + b ||- 11= is straightforward to see that Definition 7 generalizes to give a proximal oracle for this new vb. A Chernoff bound shows that at least & of the portions will return a point satisfying the bound in Lemma 15 except with probability
8,, so Fact 2 returns us point at distance at most 90G from 27, where A
f4
n
T =
log
=
Ω
1 5 2 (log
+
31

---

(accounting for rounding error). Therefore, (8) holds with
Cuo
log 1
A G.
V
n
for sufficiently large Csco- Proposition 2 then implies that Algorithm 2 outputs x satisfying
A n
C.co
log .D.VV
log ]/
+ +())+((())) --====((xxxx) S 2GD
-
V
2 .GD.
I C GD
V
n
where we use that G₁ v G by Jensen's inequality and our second moment bound Definition 6. The failure probability follows from union bound because we ensured that Σie( ō; S 5.
Finally, if 3 larger than (nlylog(n), then we let I, J E IN be chosen such that
loga (") J 48 log (0)-
which is achievable with (log n) and (log Log - (log t). Let m := g. and assume without loss that m is power of which we can guarantee by discarding S our queries, losing a constant factor in the error bound. The remainder of the proof follows identically to the first part of this proof, where we union bound over 7 phases, the 7th of which uses J batches of m unused queries. 2
Again we may apply Lemma 15 and Fact 2 with T gr so (8) holds with
Cuco G.
log
A
V
except with probability j. The conclusion then follows from Proposition 2.
F
Non-contraction of truncated contractive steps
In this section, we demonstrate that a natural conjecture related to the performance of clipped private gradient algorithms in the smooth setting is false. We state this below Conjecture To motivate suppose is the difference between a current pair of coupled iterates of a private gradient algorithm instantiated neighboring datasets, and suppose the differing sample funetion has already been encountered. If we take coupled gradient step in sufficiently smooth function, Fact 3 shows that the step is contraction. However, to preserve privacy in the heavy-tailed setting, is natural to ask whether such a contractive step remains contractive after the gradients are clipped. i.e. the statement of Conjecture (which gives the freedom for to lower bounded).
Conjecture 1. Let ||ul| & for a sufficiently large constant C, and let ||I 1u--6 (g A)]l S g' = 11 (g) and h' = (h).. Then, 1 (g' S C.
||0|| Let
We strongly refute Conjecture 1, by disproving it for any C 2 0. We remark that Lemma 16 does necessarily rule out this approach to designing heavy-tailed SCO algorithms in the smooth regime, but demonstrates an obstacle if additional structure of gradients is not exploited.
Lemma 16. Conjecture is false for any choice of C 0.
Proof. We give a 2-dimensional counterexample. Let
. 9 )==
()) h= CV2041
2C+1
224+1 CfT
=
C+1
= V2
C+1
N=M
Observe that
((C+ +
2C+1
C2
11)
C+1
C+1 CV2C+1
CV2C+1 C+1
V2C-1
C+1
By of the claim, the assumption that the truncation threshold is 1 is without loss of generality.
32

---

It is easy to verify ||0 - [g -h]ll C' at this point. Moreover,
(C 1C+ V2++1
(g' h²)
C+1
For C 0, the first coordinate of this vector is already less than C.
G Non-decay of empirical squared bias
In this section, we present an obstacle towards a natural approach to improving the logarithmic terms in our algorithm Section We follow the notation of Section 3.1, i.e. for samples {i S)be[n) pm, define sample functions [(;3 (z), and let
bD
max aEX
1 Σ V((c) T (E(M)
Σ Tc((V((()) EE(M]
(26)
n
basic bottleneck with known approaches following SCO-to-ERM reductions is that they require strongly convex ERM solver as primitive, due to known barriers to generalization in SCO without strong convexity (see e-g. discussion [SSSSS09]). This poses an issue in the heavy-tailed setting, because standard analyses of strongly convex clipped SGD (see e.g. our Proposition 1) appear to suffer dependence by the utility bound, which upon taking expectations requires bounding
1 Σ (c(()(()) IE(M
F D 18 = EDupp
max xEX
V((()) :E|m]
(27)
n
G due to Fact 1. Bounding Ebj
Recall from Lemma 3 that it is straightforward to bound Eby more problematic; in [LR23], requiring this bound resulted in a dependence on G2x as opposed to G2 (see the proof of Theorem 31), which avoid (up to polylogarithmic overhead) via population- localization strategy. We now present an alternative strategy to bound (27), avoiding G2k dependence. Observe that, by using (a b+ c)2 s 3(a² + 12 + e²).
EDapa bpp 3 EDupp
Vf((z) -PP())))pp(
max BEλ
TI
sE|n]
=i
+ 3 max ZEX
[V)(v> E,pp [I s))]1
(28)
:=22
+ 3 EDwpP
Ie (V((((()) Eswp (V)(((2
RE|M]
We focus on Ti, as T3 be bounded by similar means (as truncation can only improve moment
G2t bounds), and Te < δमÉ via Fact 1. Hence, if we can show that Ti O C under the moment bound assumption Assumption 1, can avoid the logarithmic factors lost by our population localization approach. We suggest the following conjecture as abstraction of this bound.
Conjecture Let be a distribution over S. For each X, let g(x; s) Rd be random vector, indexed by ~ S. satisfying Es-p [g(x; s)] = Oa and (Ewp[supaex [1g(2; s) < 1. Finally for S ~ Pd and x E X. let g(2; S) = 1 E.es g(z; s). Then,
sup g( 5)2 0 (1)
E Esupa
zEX
33

---

Note that the bound in Conjecture 2 exactly corresponds to 7i in (28), after rescaling all sample gradients by क. and centering them by subtracting (x) Hence, if Conjecture 2 true, it would yield the following desirable bound in (28):
2 (0/))
G
EDupuly = 0
(k- 1)Ck-1
n
Moreover, it is simple prove bound of ((1) on the right-hand side of Conjecture and as + oo it is reasonable to suppose g(æ; S) - 0g for all x E X. Nonetheless, we refute Conjecture 2 in full generality with a simple 1-dimensional example.
Lemma 17. Conjecture 2 is false.
Proof. Let S = 00, 1] and let P be the uniform distribution over S. Let X' index set of random g(x: : [0, 1] [0. which are nonzero at finitely many points. Then (a; for all
E N. and (z; s)² - < for all X. E S. However, for any S E [0, 1]",, we have
sup S)² =1 zEx
While Lemma 17 does not rule out the approach suggested in (28) (or other approaches) to improve the analysis of strongly convex ERM solvers in heavy-tailed settings, it presents an obstacle to applying the natural decomposition strategy in (28). To overcome Lemma 17, must either use more structure about the index set X' or the iterates encountered by the algorithm, or consider a different decomposition strategy for bounding the squared empirical bias.
H Proof of Lemma 11
In this section, we prove Lemma 11. We first require the following standard fact (see e.g. [Sch14]).
Fact 4, Let X S Rd be a convex set. for any x, y E Rd, we have
[[ 1lx s | w|l-
We now set up some notation. Let {uyy :X + X'e jE and {Øz : + X heem be two sequences of operations. We say that an operation pair (1/, Φ) is contractive if for any two points x, E X,
[|+(2)) - ا(v)1 S ||x - y/l-
We say operation pair ()) is -Conttccota if for any x. y where ||x yll I C, we have
[xb(z) - <(v))l - | vil + c. Let 1 (x) Vi 41-11 ... s (x), and define s similarly, for all [T].
We prove Lemma 11 as a consequence of the following more general result.
Lemma 18. Let xo = = E X, and consider two sequences of operations {w/ X + X} and
Eut X X) ber satisfying the following conditions, for := L$)-
1. For least T 1 indices j [T], (1)y 0z) is contractive.
2. At most one operation pair, (1/k, vhb). ) is (oc, -')ccottractive
3. For at most e indices j E [T), (1b5, is (2C, -contraacee
Then for all; j E [T', we have that || (xx) の (vo)l < 2C'
We note there is a bijection between X and any convex subset X' of containing a ball with nonzero radius. To see this, it is well-known that there is a bijection from [0, 1] to R2 and we can simply construct bijection between Rgo
by mapping the interval the nonzero points, and the next coordinates specify their values) for all i E N. Finally, it is well-known there is a bijection between [0, 1] and Rd, and we can construct a bijection between X' and Rd by considering each 1 1-dimensional projection separately.
1, [0, 1]2i (where the first coordinates specify
34

---

Proof. Define A = (T)) / (zar for j E [T]. Let aj I c be the total number of (2C, ()- contractive operation pairs (4); o,) where $ j. and let b, be the 0-1 indicator variable for J. We use induction to show that Aj S 0, C.C. When j 1, the claim holds. Now if the claim holds for then A S a--1 { b- v 2C. Hence, by definition,
A A - (a, - 4n- i)c (bz bj-1)C a
which completes our induction. This also implies År S 2C as claimed.
Proof of Lemma II. Throughout the following proof, note that é, 2c deterministically (due to use of B c) noise), and under the stated parameter bounds,
TC 9C
C and |sss for all j E [na]]-
ČE
8
Let (gi, = IVV(( st.))) je(n.) and (ol, ITc ( be the two truncated gradi- ent sequences in the 7th phase corresponding the two datasets, and ( (een)) and (e))))))n)) be the corresponding iterate sequences. We set the operation sequences thy (a) == xxx= - (TBk..) and (x) ;= 1x m...,)) We bound the contractivity of these operation pairs and apply Lemma 18.
First, note that because count,, count, < é < 2c, the operation pair (1) is an identical untruncated gradient mapping for least 2c indices [t]. Because we assume each sample function f(:: s) is 8-smooth, it follows that for these indices j E [t]. the operation pair (ehy, Qy) is contractive, by applying Fact 3, Fact 4, and n7,3 1.
Next, recall the assumption that the datasets D, D' differ in the jb sample only. Because ||gr,ool ll s C
9C
8
T
<
UC by assumption, and similarly [19f,,,11 < UC it follows that the operation pair g
(155. Pio) is (oc,3Cn)) --ontractive by applying the triangle inequality and Fact 4.
For all remaining indices j E [t]. count, and count', both incremented (under the assumption that Yr, = Yi, for these indices). We claim that (Vi, 0,) is (6n,C, conttratvee for these iterations. To see this, we bound
(,,)( (,,
- [[ 7:gis) - (2'2 - -m
< [| Th V ( st.)) - (2'1 - - Vn st.)))))))))))
+ mi [ (4.e V.(a' st5يي T 9 ار,د
< || - و 12 C.S.
The first line used Fact 4, the second used the triangle inequality, and the last used Fact 3, Fact and the fact that | ( - Vs(4 si,;)l 6n,BB by smoothness, when || x < 6C1).
Finally, it suffices to apply Lemma 18 with C' < 3C'n, Ç + CB, and c t 2c, which we can check meets the conditions of Lemma 18 under the stated parameter bounds.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide new algorithms with improved guarantees for heavy-tailed private SCO in several settings, which is what claim in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not 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]
The paper discusses places where the main result lossy, providing an appendix section dedicated towards improving it to be optimal. It also compares its results to another similar bound in the literature, discussing regimes where our bound weaker.
Justification:
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 a separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex. system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency 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 as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
36

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide full of verifiable details for all of theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in 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 information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions 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 include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
37

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/ /twpgdde//oeeuuuniistttteeeeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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: / //nip/ httpppscccpuullc/guuddeee httgg/dddd//oeeuumiiiiieeee https//ooooeuuuoiiiiooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
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 the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
38

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httt:::://errrrg...pppiie///eeee httpppppwwpppppittttttccceeeeeee
39

---

Answer: [Yes]
Justification:
We read the ethics guidelines and believe meet them.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We do not believe our paper poses a significant negative societal impact, as it is about making existing learning algorithms differentially private under less stringent distributional assumptions, which we do not foresee being used in any significant malicious cases. We do believe that our algorithms can have positive societal impacts, but do wish to overclaim to this effect because our results are primarily theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate 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 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper 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 does not release data or models.
Guidelines:
The answer NA means that the paper poses such risks.
40

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and 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 used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
41

---

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 research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
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 research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
42


Reviews:
[{"review_id": "5KIrKv8kzv", "reviewer": "Reviewer_UUcG", "summary": "This paper studies the problem of differentially private stochastic convex optimization with heavy-tailed gradients. This paper points out that in typical optimization research, the assumption of uniformly G-Lipschitz, while convenient for bounding sensitivity, does not always hold. Based on this weakness, the authors studied k-heavy-tailed DP-SCO. The author obtains near-optimal algorithms that lie in the clipped DP-SGD subroutine and ensure the private minimization of a regularized ERM problem under k-heavy-tailed DP-SCO conditions. This method yields points that closely approximate the minimizer of population loss, verified through Markov’s inequality.\n\nUpdates post response:\n\n- I find the lack of experiments a bit underwhelming, and the authors' response didn't really convince me why this should not be part of this paper. Data privacy is a highly practical question that should be of strong interest to practitioners. The lack of practical implications is thus concerning.\n\n- The paper does not have a conclusion section, which is very strange for a NeurIPS paper. I have been reviewing NeurIPS submissions for many years; It is really awkward for a paper to not have a conclusions section. Not having a conclusions section also means that the authors did not carefully think about the \"Limitations\" of their work, which is a requirement as per NeurIPS submission guidelines.\n\n- Lastly, I wonder what are some of the broader impacts/implications of this work. It would be helpful if the authors could add some discussions about this. Again, I feel like this would require a proper \"conclusions\" section added to the paper.\n\n- While reading through the paper I noticed many notational inconsistencies and concepts that have not been clearly explained (please see concrete examples under the list of questions below), I suggest the authors to carefully proof read their paper and making improvements on explaining their work. This will help broaden the impact of this research.\n\nDisclaimer: Please be aware that due to the rather short reviewing time, I have not been able to check all the proof details in the appendix.", "questions": "- Why is the k-heavy-tailed assumption more common than the uniformly G-Lipschitz assumption? Intuitively, the uniform is indeed a weaker assumption, but I would like more direct evidence to prove the necessity of using the k-heavy-tailed assumption.\n\n- What are the comparisons between the bounds under the k-heavy-tailed assumption with those of prior work? Please comment on this\n\n- Is it possible to provide the convergence analysis of the proposed algorithm?\n\n- From equation (1) to equation (2), what's the difference between $G$ and $G_2$?\n\n- In line 45, can you give a specific example of what you mean by \"heavy-tailed gradients\"? When might readers expect this condition to hold in practice (e.g., in the training of a neural network)?\n\n- While citing a paper, can you please properly cite the author's name(s) using \\cite{}, as opposed to things like [LR23]?\n\n- In the introduction, can you please clarify exactly under what notion of DP your results will hold? Note: I'm seeing multiple versions of DP definitions in section 2, page 5, thus prompting this question.\n\n- Is Theorem 1 (at the bottom of page 9) supposed the main result in your paper?\n\n- What are some of the broader impacts/implications of your work? Please comment on this.", "limitations": "Limitations are discussed on page 32.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- This paper provides a comprehensive analysis of prior work, enabling readers to quickly understand the limitations of previous research on DP-SCO and why the authors believe this work is necessary.\n- This paper conducts solid theoretical research and has a profound understanding of the k-heavy-tailed DP-SCO problem. The entire paper is filled with rigorous derivations, providing a theoretical foundation for future research.", "weaknesses": "- Experiments could be added to validate the proposed algorithm for readers to better understand the key takeaways.\n\n- The paper's organization could be improved, and the contribution can be better highlighted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback. We answer your questions below.\n\n\nExperiments: The focus of our work is theoretical in nature: developing algorithms that address known gaps in the literature on DP-SCO, a problem of interest in both theory and practice. We believe this goal has significant merit in its own right, as it provides insights that lay the groundwork for future research, both theoretical and experimental. We absolutely agree with the reviewer on the complementary importance of experimental evaluation of theoretical derivations. We chose to restrict our focus, but think that transferring our insights to practice is an exciting and promising direction for future research.\n\nOrganization: We take the organization of our paper and presentation of our contributions seriously as concerns, and appreciate the feedback. We would like to kindly request that the reviewer provide some more specific feedback on our organization and presentation. Re: our contributions, all of our key results are described in Section 1.1 (with corresponding formal statements as Theorems 1-4), and compared to prior work in Section 1.2.\n\nQ1: Indeed, the k-heavy-tailed assumption applies to more situations than the uniform Lipschitz assumption, as a distribution can be $k$-heavy-tailed but not $\\infty$-heavy-tailed. However, there is a tradeoff in the gains achievable for finite $k$. Our work is the first to obtain an algorithm that gives the best possible tradeoff up to logarithmic factors.\n\nIn practice, differentially private neural networks are trained with clipped gradients (see [ACG+16]), due to outliers which create undesirable tail behavior. For more problems in practice where the $k$-heavy-tailed assumption is a more appropriate model than the uniform Lipschitz assumption, we refer the reviewer to the reference [WXDX20], which discusses how biomedicinal and financial research often use heavy-tailed modeling. More generally, power laws are heavy-tailed, and used to model many phenomena in the sciences. We will add additional discussion of this motivation; thank you for raising this point.\n\nRegarding the relative strength of these assumptions, for $k’ > k$, the $k’$-heavy-tailed assumption is stronger than the $k$-heavy-tailed assumption (with appropriate parameters), as a variable can have a finite $k$-th moment but not a finite $k'$-th moment. In this sense, as uniform Lipschitzness is an $\\infty$-heavy-tailed assumption, it is the strongest.\n\nQ2: We compared our bounds to existing work in Lines 57-61 of the submission, as well as more in depth in Section 1.3. The heavy-tailed DP-SCO problem is relatively new, and few theoretical guarantees are provided by the literature. The two most relevant works are of [KLL22] and [LR23]: the first requires stringent conditions (such as uniformly smooth loss functions) to guarantee optimality, whereas the former obtains sub-optimal rates that can be polynomially worse than ours. We close the gap left by these prior works, achieving the first near-optimal rate, as well as generalizations in many settings (smooth and/or GLM).\n\nWe were not sure if the reviewer meant how our Assumption 1 compared to previous definitions of the problem. Our problem statement is the same as in [LR23]. The problem definition is phrased slightly differently in [WXDX20, KLL22], using a (in our opinion, less natural) coordinatewise bound; we chose the definition consistent with more of the literature, e.g. previous works on private mean estimation [BD14], and uniform Lipschitz DP-SCO.\n\nQ3: We believe all of our algorithms have complete analyses and proofs. For example, Theorem 1 is proven in Section 3 and Appendix A, with a fully specified algorithm description. We are happy to address your concerns, but we would like to again kindly request that the reviewer be specific about which missing convergence analyses they refer to.\n\nWe appreciate that you found our research solid and our descriptions comprehensive, providing a good foundation for the problem. We hope our response was clarifying, and that it elevates our contributions from your viewpoint. Thank you for your feedback again.", "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": "V7aCE0Jbmw", "reviewer": "Reviewer_S4Vx", "summary": "This paper gives three main results.\n\nThe first is a nearly optimal (losing a few logarithmic factors) excess loss rate for differentially private stochastic convex optimization (DP-SCO) when the gradient norms have $k$ bounded moments. In particular, they achieve the optimal excess loss under $\\rho$-concentrated differential privacy (CDP) of\n\n$\\frac{G_2 D}{\\sqrt{n}} + G_kD \\cdot \\left(\\frac{\\sqrt{d}}{n\\sqrt{\\rho}} \\right)^{1-1/k}$\n\nwhere $G_i$ denotes the uniform upper bound on the $i$th moment of the gradients and $D$ is the diameter of the domain. This improves over the prior state of the art [LR23] by a factor of $G_kD \\cdot \\left(\\frac{\\sqrt{d}}{n\\sqrt{\\rho}} \\right)^{1/k}$. This improvement is increasingly pronounced as we decrease the number of gradient moments that we assume are bounded, which is probably the important regime in this work.\n\nAs I understand, the main technical innovation is a \"population-level localization framework\", through which the authors are able to control the population excess risk without having to argue about the variance of the bias term arising from gradient clipping.\n\nThe second main result is an algorithm that achieves the optimal excess risk when each sample function arrives with a known Lipschitz constant. This yields algorithms for privately learning a generalized linear model with the optimal excess risk. This follows from a clean reduction to the case where we know that our losses are uniformly Lipschitz.\n\nThe third main result is an improved query complexity for optimizing smooth functions. The algorithm follows from an application of the sparse vector technique.", "questions": "N/A", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The algorithms seem very natural, the analysis looks clean, and the results yield quantitative improvements over prior work. Therefore, I think this work is an important contribution to private convex optimization.\n\nThe ideas are cleanly explained and at least on a surface level make sense to a complete outsider to the field (such as myself).", "weaknesses": "Can't really think of anything significant. A natural criticism I anticipate is that the improvement over [LR23] is pretty minor when $k$ is large, but given that the authors get the optimal result and [LR23] doesn't, this doesn't seem like a real issue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your reviewing efforts, and we appreciate your positive feedback. Please feel free to let us know if you have any questions or suggestions.", "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": "h5c3j65UOR", "reviewer": "Reviewer_8sRE", "summary": ".The paper studies DP-SGD under the assumption that the gradients have heavy-tailed phenomenon. This has been recently motivated and studied a lot by recent works. The authors claim to achieve optimal rate for this problem.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "They obtain the first optimal rates (up to logarithmic factors) in the heavy-tailed setting, achieving error that depends on $\\frac{G_1}{\\sqrt{n}} + G_k(\\sqrt{d}/nk)^{1-1/k}$ under approximate-DP guarantee. \n\nThey additionally study this problem under well-studied assumptions: Lipschitz constant assumption, smooth convex functions, and smooth generalized linear model.\n\nI haven't checked the proof, but the paper is definitely an accept considering it solves a problem in this domain.", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your reviewing efforts. We appreciate your positive feedback. Please feel free to let us know if you have any questions or suggestions.", "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": "88ibN8MLX4", "reviewer": "Reviewer_KReZ", "summary": "This paper addresses differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where previous assumptions of uniform Lipschitz constants are relaxed to bounded k-th moments. The authors introduce a new reduction-based framework that adapts strategies from the uniform Lipschitz setting, enabling optimal rates up to logarithmic factors under (ε,δ)-approximate differential privacy. They propose several algorithms, including an optimal algorithm for known Lipschitz constants, a near-linear time algorithm for smooth functions, and an optimal linear-time algorithm for smooth generalized linear models. A novel population-level localization framework is also presented, overcoming technical barriers and providing robust bounds on excess population loss without stringent gradient moment assumptions. This work advances the theoretical and practical understanding of DP-SCO with heavy-tailed gradients, outperforming previous approaches in handling real-world data challenges.", "questions": "1. To solve population-level localization, could one use the same (or slightly adjusted) method for the localization of the empirical minimizer?\n2. How does the sample split parameter $J$ affect the utility of Algorithm 3?\n3. Should $G_2^2$ and $G_k^k$ on line 7 be $G_2$ and $G_k$?", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel reduction-based framework for handling heavy-tailed gradients in differentially private stochastic convex optimization (DP-SCO). This innovative approach enables the achievement of near-optimal rates and overcomes limitations of previous methods, marking a significant advancement in the field.\n2. The proposed method bypasses the need for bounding $\\mathbb{E}b_{\\mathcal{D}}^2$", "weaknesses": "1. Referring to Corollary 2 in Line 4 of Algorithm 3 reduces readability. To enhance clarity, it would be beneficial to specify the algorithm $\\mathcal{A}$ (from Corollary 2) clearly, at least within the proof. While leaving the optimization oracle as a black box might help generalize the framework, it makes the algorithm harder to follow if the instantiations are not highlighted.\n2. The motivation of the population-level localization could be further clarified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading; we address your questions here.\n\nRe: clarity, we agree with your suggestion, and will add a description of the algorithm and the specific guarantees we are using about it to help the reader. Thanks for pointing this out. \n\nRe: population-level localization, we will add an additional description after Line 85. The motivation for population-level localization is that we wish to aggregate empirical solutions to multiple datasets, some of which satisfy assumptions of Corollary 1 (i.e., have small $b_{\\mathcal{D}}$), and some of which do not. However, each dataset has a different empirical minimizer, so it is unclear which to argue about convergence to. We instead aggregate solutions close to a population-level minimizer, shared across datasets. Previous localization frameworks could not handle the setting we consider, as described in Section 1.2, prompting our new development. In particular, previous localization frameworks used non-strongly convex losses, which have known difficulties in generalizing to population-level objectives [SSSS09].\n\nQ1: Our population-level localization is inspired by and closely related to frameworks used to minimize an empirical loss. Both rely on stochastic access to the input, but a key difference is that we cannot verify our empirical dataset actually satisfies a key assumption used to get the optimal rate (bounded $b_{\\mathcal{D}}$), so the empirical solution could be meaningless. This is why we target population-level objectives, which can aggregate multiple datasets. \n\nQ2: Suppose that we can get $x_{i,j}$ such that $\\|x_{i,j}-x_i\\|\\le R(i,J)||$ with probability at least 0.55. Then $J$ can not be too small, to make use of a Chernoff bound to show at least half of the $x_{i,j},j\\in [J]$ are close to $x_i$. On the other hand, the larger $J$ is, the smaller the privacy budget we can use to generate $x_{i,j}$, since we need to compose over $J$ instances, which hurts our final utility bound. Hence $J$ can not be too small, or too large.\n\nQ3: We believe Line 7 is correct as stated. As assumed in Line 67, $G_j^j$ is the $j^{\\text{th}}$ moment.\n\nWe appreciate you found our approach innovative, and that our result was a significant advancement. We hope our response was clarifying, and that it elevates the merits of our paper in your view.", "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": "w7tVG6DAeo", "reviewer": "Reviewer_1QCz", "summary": "The paper investigates the problem of differentially private stochastic convex optimization (SCO) under the heavy-tailed setting and achieves a nearly optimal rate of $G_2 \\cdot \\frac{1}{\\sqrt{n}}+G_k\\left(\\frac{\\sqrt{d}}{n \\varepsilon}\\right)^{1-\\frac{1}{k}}$. Specifically, it first provides results using Clipped-DP-SGD in the differentially private empirical risk minimization (DP-ERM) framework and then utilizes generalization techniques to offer similar results in the population case. Finally, it explores the heavy-tailed DPSCO.", "questions": "NA", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The paper provides a nearly optimal bound for DPSCO in the heavy-tailed setting.", "weaknesses": "1. Section 3 is not very clear. The connection between Sections 3.1 and 3.2 is not well explained.\n2. The presentation needs improvement. One of the most important parts, Population-level Localization, is placed on the last page and is only briefly introduced and discussed. For example, how to choose parameters like $\\lambda$ in Algorithm 2 and what $\\Delta 4^i$ in Equation 8 represents should be explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your reviewing efforts and feedback.\n\nSection 3: We apologize for the lack of clarity in Section 3. In Section 3.1, we propose Algorithm 1, which achieves good performance on an empirical loss assuming the dataset satisfies a property (bounded $b_{\\mathcal{D}}$, see (6)). In Section 3.2, we show we can use Algorithm 1 to get a solution with respect to the population function if the dataset is drawn from a heavy-tailed distribution. We included a description of this relationship at the start of Section 3 (Lines 226-235), but will include more connective tissue between Sections 3.1 and 3.2.\n\nPresentation: Due to page limitations, we did not add many details about the population-level localization in the main paper (some details were deferred to the appendix). We will revise our final version and add more details and intuitions to clarify it. Currently, a short description is given in Lines 85-92, and full proof of its guarantees is given in Proposition 2 in the main body. We provided additional intuition of why we developed this technical tool and its comparison to prior work in our response to Reviewer KReZ, and will incorporate this response into our revision. For your other questions, $\\lambda$ is a hyperparameter that we optimize in Line 295 to minimize the expression on the previous Line 294, and $\\Delta$ is a scaling of the objective error defined in Line 301.\n\nWe hope this discussion was clarifying, addressed some of your concerns, and elevated the merits of our paper in your view.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work studies differentially-private stochastic convex optimization (DP-SCO) under heavy-tailed (stochastic gradient) settings. Its main results are in closing the gap between upper and lower bounds for this problem. At the technical level the work puts forth some nonstandard ideas in this literature, such as using a population-localization approach (whereas it is far more typical to use empirical localization which is also simpler), and SVT as a privacy budget control under clipping. There were some concerns about the paper not containing a conclusions section or numerical experiments.

Overall, I think this paper makes enough contributions and merit to warrant publication at NeurIPS.
Decision: Accept (poster)