Faster Algorithms for User-Level Private Stochastic Convex Optimization
Authors: Andrew Lowy
Daogao Liu
Hilal Asi
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
user-level privacy
stochastic convex optimization
private optimization
Primary area: privacy
TL;DR: We provide new user-level private algorithms with improved runtime and less restrictive assumptions vs. the prior state-of-the-art.

Abstract: We study private stochastic convex optimization (SCO) under user-level differential privacy (DP) constraints. In this setting, there are $n$ users (e.g., cell phones), each possessing $m$ data items (e.g., text messages), and we need to protect the privacy of each user's entire collection of data items. Existing algorithms for user-level DP SCO are impractical in many large-scale machine learning scenarios because: (i) they make restrictive assumptions on the smoothness parameter of the loss function and require the number of users to grow polynomially with the dimension of the parameter space; or (ii) they are prohibitively slow, requiring at least $(mn)^{3/2}$ gradient computations for smooth losses and $(mn)^3$ computations for non-smooth losses. To address these limitations, we provide novel user-level DP algorithms with state-of-the-art excess risk and runtime guarantees, without stringent assumptions. First, we develop a linear-time algorithm with state-of-the-art excess risk (for a non-trivial linear-time algorithm) under a mild smoothness assumption. Our second algorithm applies to arbitrary smooth losses and achieves optimal excess risk in $\approx (mn)^{9/8}$ gradient computations. Third, for non-smooth loss functions, we obtain optimal excess risk in $n^{11/8} m^{5/4}$ gradient computations. Moreover, our algorithms do not require the number of users to grow polynomially with the dimension.

Faster Algorithms for User-Level Private Stochastic Convex Optimization"
Andrew Lowy Wisconsin Institute for Discovery University of Basconsin-Madisee alouy@xisc.edi edu
Daogao Liu
Department of Computer Science University of Washington
1 iudaogao@gmail.. com
Hilal Asi
Apple Machine Learning Research
hilal. asi94@gmail.com com
Abstract
We study private stochastic convex optimization (SCO) under user-level differential privacy (DP) constraints. this setting, there are n users (e.g., cell phones), each possessing m data items (e.g., text messages), and we need to protect the privacy of each user's entire collection of data items. Existing algorithms for user-level DP SCO are impractical in many large-scale machine learning scenarios because: (i) they make restrictive assumptions on the smoothness parameter of the loss function and require the number of users grow polynomially with the dimension of the parameter space; or (ii) they are prohibitively slow, requiring at least (mn) /3/2 gradient computations for smooth losses and (mn)² computations for non-smooth losses. To address these limitations, we provide novel user-level DPP algorithms with state-of-the-ard excess risk and runtime guarantees, without stringent assumptions. First, we develop linear-time algorithm with state-of-ther -fet----t-et-tttt excess risk (for a non-trivial linear-time algorithm) under a mild smoothness assumption. Our second algorithm applies to arbitrary smooth losses and achieves optimal excess risk in 9/8 gradient computations. Third, for non-smooth loss functions, we obtain
= (m optimal excess risk in n 1/1 m/ 5/4 gradient computations. Moreover, our algorithms do not require the number of users grow polynomially with the dimension.
Introduction
The increasing ubiquity of machine learning (ML) systems in industry and society has sparked serious concerns about the privacy of the personal data used to train these systems. Much work has shown that ML models may violate individuals' privacy by leaking their sensitive training data (SSSS17] LLL+24a L For instance, large language models (LLMs) are vulnerable to black box attacks that extract individual training examples (CTW+21). Differential privacy (DP) [MNS06 prevents ML models from leaking their training data.
The classical definition of differential privacy-item-level differential privacy DMNS06) is ill- suited for many modern applications. Item-level DP ensures that the inclusion or exclusion of any one training example has negligible impact on the model's outputs. If each person (a.k.a. user) contributes only one piece of training data, then item-level DP provides strong guarantee that each user's data cannot be leaked. However, in many modern ML applications, such training LLMs on users' data in federated learning, each user contributes a large number of training examples [Z24)
Authors are listed reverse alphabetically.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In such scenarios, the privacy protection that item-level DP provides for each user is insufficiently weak.
User-level differential privacy is a stronger privacy notion that addresses the above shortcoming of item-level DP. Informally, user-level DP ensures that the inclusion or exclusion of any one user's entire training data (m samples) has a negligible impact on the model's outputs. Thus, user-level DP provides a strong guarantee that no user's data can be leaked, even when users contribute many training examples.
A fundamental problem in (private) machine learning is stochastic convex optinization (SCO): given a data set = (Zi..... Zn) from n i.idd users, each possessing m ii.d. samples from an unknown distribution Zi pm our goal is to approximately minimize the expected population loss
F(x) == Eg~plf(x: ()).
Here, f: X' x - R is a loss function (e.g., cross-entropy loss), X C R is the parameter domain, and 2 is the data universe. We require that the output of the optimization algorithm A 2mm -+ X satisfies user-level DP (Definition 1.3). We measure the accuracy of AA by its excess (population) risk
EF(A(D)) F = Pm F(A(D)) - min F(x). #EA
Given the practical importance of user-level DP SCO, it is unsurprising that many prior works have studied this problem. The work of [LS 21) initiated this line of work, and provided an excess risk lower bound 22(1 22(1//nm + vd/ (e)) where & is the privacy parameter. However, their upper bound was suboptimal and required strong assumptions. The work of (BS23) gave an algorithm that achieves optimal risk for 3-smooth losses with 3 < (n/Vmd A n (ddm)), provided that 2 vdje and m I max(Vd, NE² /Vd). These assumptions are restrictive in large-scale applications with a large number of examples per user m or when the number of model parameters d large. For example, in deep learning, we often have d >> n and an enormous smoothness parameter > 1. Moreover, their algorithm requires mm/3/2 gradient evaluations, making it slow when the number of users n is large The work of [KKK= gave another user-level DP algorithm that only requires log(d)/s, but unfortunately their algorithm does not run in polynomial-time.
To address the deficiencies of previous works on user-level DP SCO, the recent work [AL24] provided an algorithm that achieves optimal excess risk in polynomial-time, while also only requiring n 2 (og(m))/ e users. Moreover, their algorithm also works for non-smooth losses. The drawback of [AL24] is that it is even slower than the algorithm of [BS23] for 3-smooth losses, their algorithm requires 9 (nm) 3/2 gradient evaluations; for non-smooth losses, their algorithm requires (nm)² evaluations.
Evidently, the runtime requirements and parameter restrictions of existing algorithms for user- DP SCO are prohibitive in many important ML applications. Thus, an important question is:
Can develop faster user-level DP algorithms that achieve optimal excess risk without restrictive assumptions?
Question 1.
Contribution 1. We give a positive answer to Question 1, providing a novel algorithm that achieves optimal excess risk using max{ (////((mm)mmmm )//8, 31/2,,/4m gradient computations for 3-smooth loss functions, with any 3 oc (Theorem 3.2 For non-smooth loss functions, our algorithm achieves optimal excess risk using n m/ gradient evaluations for non-smooth loss functions (Theorem (.T).. 4. Our runtime bounds dominate those of all prior works in every applicable parameter regime, by polynomial factors in n. m, and d. Moreover, our results only require - > >logdd)/ comparison of our results vs. prior works. For example, for non-smooth loss
5/4
users. See Table functions. our optimal algorithm is faster than the previous state-of state-of-the- factor of n. m 7/4 For smooth loss functions, our optimal algorithm is faster than [AL24] by factor of (nm) 3/3///33/ /3/1 (in the typical parameter regime when n² 2 m).
(AL24] by multiplicatiiv
In the introduction, whenever e does not appear, we are assuming = 1 to ease readability. For runtime bounds, we also assume = d to further simplify.
2

---

Loss Function
Reference
Gradient complexity
Assumptions
[BS23]
mn
B S V n/m & m vd
/-Smooth
[AL24]
B (mm) )312
None
Our Algorithm
BIA, (mn) 9/8 + f112 m
None
[AL24]
(mn)²
None
Non-Smooth
Our Algorithm 3
1/8
m 5/4
None
(smoothed)
Figure 1: Optimal algorithms for user-level DP SCO. We omit logarithms, fix L R = = and n d.
Linear-Time Algorithms The "holy grail" of DP SCO is linear-time algorithm with optimal excess risk, which is unimprovable both in terms of runtime and accuracy. In the item-level DP setting, such algorithms known exist for smooth loss functions (FKT20 ZTOH22 [AL24 posed an interesting open question: is there a user-level DP algorithm that achieves optimal excess risk in linear time for smooth functions? For second contribution, make progress towards answering this question.
Existing techniques for user-level DP SCO are not well-suited for linear-time algorithms. Indeed, the only prior non-trivial linear-time algorithm is the user-level LDP algorithm of [BS23 Algorithm
5] Their algorithm can achieve excess risk ss 1/ynmm + vd/( (nmm)) Unfortunately, however, their algorithm requires a very stringent assumption on the smoothness parameter 3 < /n²² (mm//m")), which unlikely hold for large-scale ML problems. Further, the result of [BS23] requires the number of users queried in each round to grow polynomially with the dimension d, and it assumes
m n. These assumptions severely limit the applicability of (S23 Algorithm 5/ in practical ML scenarios. This leads us to:
Question 2. Can we develop linear-time user- level DP algorithm with state-of-the-an art excess risk, without restrictive assumptions?
answer Question affirmatively in Theorem 2.1 under a very mild requirement on the smoothness parameter < Vnumd, our novel linear-time algorithm achieves excess risk of 1////nm + vd/( (V/mm)... Moreover, our algorithm does not require the number of users to grow polynomially in the dimension d, and our result holds for any values of m, d, and Thus, algorithm has excess risk matching that (BS23), but is much more widely applicable.
Contribution 2.
1.1 Techniques
We develop novel techniques and algorithms to achieve new state-of-the-ar results in user-level DP SCO. Before discussing our techniques, let us review the key ideas from prior works that we build on.
The goal of prior works [BS23 AL24 was to develop user-level analogs of DP-SGD [BFTTI9],
which is optimal in the itee-level setting. To do so, they observed that each user i's gradient m EØ= (f(x, Zuz) lies in ball of radius 1//m around the population gradient F())) with high probability, if the data is i.i.d (Z₁ pm). Consequently, if the data is i.i.d., then replacing one user Z, E D by another user Z E DD' will not change the empirical gradient VF)(x)) by VF (x)] S 1/(n/m) with high probability. Thus, one would hope for a method to privatize VFp (z) by adding noise that scales with 1/(ny/m)-nn rather than 1/n which would allow for optimal excess risk. [AL24] devised such method, which was inspired by FriendlyCore [TCK+22] Their method privately detects and removes "outlier" user gradients, and then adds noise the average of the "inlier" user gradients. This outlier-removal procedure ensures privacy with noise scaling with 1/ (m), provided n Z 1/e. Moreover, when the data is i.i.d., no
1
too much: (x))
IIt is trivial to achieve excess risk z 1/ nmm + vd((en) with (e, 8) user-leeeel, e.g. by applying group privacy to an optimal item-level DP algorithm such as [KT20 The error due to privacy in this bound does not decrease with

---

outliers will be removed with high probability, leading to a nearly unbiased estimator of the empirical gradient.
Our algorithms apply variations of the outlier-removal idea of A1.24 in novel ways.
Our linear-time Algorithm|] | takes a different approach to outlier removal, compared to prior works. Instead of removing outlier gradients, we aim to detect and remove outlier SGD iterates The high-level idea of our algorithm is to partition the n users into C' z 1/e groups, with each group containing & ne users. For each group of users, we run T & mne steps of online SGD using the samples in this group and obtain the average iterate of each group: { 15-1- We then privately identify and remove the outlier iterates from { {=
order to successfully do so, we need to argue that if we run online SGD independently on user Z and user Z' to obtain and i' respectively, then || - i'll I ny' with high probability, where 1j the SGD step size. We prove such a stability bound in Lemma 2.3] which we hope will be of independent interest. By repeating the above process log(n) times and using iterative localization [KT20). result.
we obtain our state-of-the-arr linear-time
Our second algorithm, Algorithm builds on AL244] in different way. In Algorithm we apply an outlier-removal procedure to users' gradients. However, unlike [AL24]. we draw random minibatches of users in each iteration and apply outlier-removal to these minibatches. To make this procedure private while also achieving optimal excess risk, we combine AboveThreshold (DR14) with privacy amplification by subsampling [BBGI8] We then develop an accelerated DP algorithm that solves a carefully chosen sequence of regularized ERM problems, and applies localization in the spirit of [KLL21 [FFTTT]] An obstacle that arises when we try to extend the ERM-based localization framework to the user-level DP setting is getting tight bound on the variance of our minibatch stochastic gradient estimator that scales with 1 m. We overcome this obstacle in Lemma 3.5 by appealing to the stability of user-level DP [BS23]. To handle non-smooth loss functions, we apply randomized smoothing to our accelerated algorithm.
[GL22 user-level
1.2 Preliminaries
We consider loss functions f: X' x Z + E. where X' is a convex parameter domain and Z is data universe. Let be an unknown data distribution and F(x) == [x, 2)] be the population loss function. Denote F* == min F(x). The SCO problem is minzex Fzz). Let || denote the lg
norm. (u) == segminnexx1e x|| denotes projection onto X.
Assumptions and Notation. Function X' + R is L- L-Lipschitz if (9(x) - g(x')l S L| x' z'Il2 for all x, x E X. Function g X + is 3-smooth if g is differentiable and has B-Lipschitz gradient: [V]) - Vg(æ') Il S B||æ - x' Function g : X - R is p-strongly convex if glocr + (1 ar) aa)²) ag(#) (1 a)g(x') a(1 a(l_a)m | x'12 for all a E [0, 1] and all x X.
If μ = 0, we say is convex.
Assumption 1.1.
1. The convex set is compact with ||I 2' $ for all x, x' e eX
2. The loss function f(,,2) is L-Lipschitz and convex for all E Z. In all of the paper except for Section 4 we will also assume: Assumption 1.2. The loss function [(, z) is 9-smooth for all = E 2.
Denote a A b == min(a, b). For functions f and of input parameters f, we write f S g if there is an absolute constant C > such that f(f) < Cg(() for all permissible values of f. We use Õ to hide logarithmic factors. Write a S poly(b) if there exists some large J > 1 for which a < b².
Differential Privacy.
Definition 1.3 (User-Level Differential Privacy). Let & 2 0, ô E [0, 1). Randomized algorithm A 2 gum X is (s, -euueer-level differentially private (DP) if for any two datasets D (2) .Z,..... Za) and D' ..,, Z2,) that differ in one user's 's data (say Z; # Z but Z, = Z for j * i). we have
P(A(D) E S) S eP((D) E S) + 5,
'The reason that this innovation is necessary is discussed in the last paragraph of Section 2

---

for all measurable subsets S C X.
Definition 1.3 prevents any adversary from learning much more about individual's data set than if that data had not been used for training. Appendix A contains the necessary background on DP.
1.3 Roadmap
We begin with our sfat-of-the-aie linear-time algorithm in Section 2 In Section 3 error-optimal algorithm with state-of of-thh-art runtime for smooth loss functions. Section extends our fast optimal algorithm to non-smooth loss functions. We conclude in Section with a discussion and guidance on future research directions stemming from our work.
we present our
2 A state-of-the-art linear-time algorithm for user-level DP SCO
In this section, we develop a new algorithm (Algorithm 1 for user-level DP SCO that runs in linear time and has state-of-the-art excess risk, without requiring any impractical assumptions. The algorithm can be seen as a user-level DP variation of the localized phased SGD of [FKT20]: we execute a sequence of SGD trajectories with geometrically decaying step sizes, shrinking both the expected distance to the population minimizer and the privacy noise over logarithmic number of phases.
In each phase i, we first re-set algorithmic parameters and draw a disjoint set of n, users Dj C D (lines 4-5). We further partition D; into C' disjoint subsets {D., ) For each j [C]. we pool together all of the n,m samples in Di,j and run one- mee-pass online SGD on Di,j with initial point x;-1 given us from the previous phase. Next, in lines 10-20, privately detect and remove "outliers" from (#t,) 19 That is, our goal is to privately select a subset S, C { ),- such that for any two
points Ci,, Hi.5' E S,, | - o S T. = LVT... This will enable us to add noise scaling with r; in line 22, rather than with the much larger worst-case sensitivity (that scales linearly with T:). In order to privately select such a subset S,, we first compute (and privatize) the concentration score for (Ti,) )=1 in line 10. A small concentration score indicates that outlier removal is doomed to fail and we must halt the algorithm to avoid breaching the privacy constraint. A large concentration score indicates that ( is nearly 7--Concentrated and we may proceed with outlier removal in lines 12-15.
j=1
Theorem 2.1 (Privacy and utility of Algorithm I Informal). Let & 10, 1-o1111 2 log(n/8)
s (L/ Hty/Ryydnn dmne, and m S poly(n). Then, Algorithm / is (c, --see-ree-lleel DP. Further,
Vnme + vdlog(1/0)
EF(x) F LR.
vnevmm
The gradient complexity of Algorithm 7 is S nm.
Remark 2.2 (State-of-the-ar excess risk in linear time, without the restrictive assumptions). Under the assumptions that 8 < (Le R)) 1D3//mmm and m < d/e² < n. (BS23) gave a linear-time algorithm very restrictive in practice:
with similar excess risk to Algorithm However, their assumptions For example, in the canonical regime n x d, their assumption on 3 rules out essentially every (non-linean, loss function. By contrast, our result holds even if the smoothness parameter is huge (3 / /nmd) and we only require: a logarithmic number of users. Thus, our algorithm and result is applicable to many practical ML problems.
To prove that Algorithm is private, we essentially argue that for any phase i, the l2 le-seiitty of ã; is upper bounded by O(r/C') with probability at least 1 1 1- 5/2. The argument goes roughly as follows: First, the Laplace noise added sı(Te) ensures that (T.)) e/4-user-level DP. Now, suffices to assume (T,)) 2 4C/3, since otherwise the algorithm halts and outputs 0 independently of the data. Next, conditional on the high probability event that the Laplace noise is smaller than
sT,7,) > 2C/3 with high probability by our choice of C. In this case, argument along the lines of [AL24] Lemma 3.5] shows that ã; has sensitivity bounded by OTr/CC) with probability least 1 8/2. See Appendix B for the detailed proof.
((1/E), we know that (T,) 2 4C/5 =
To prove the excess risk bound in Algorithm T the key step is show that if the data is i.i.d., then with high probability, points removed from {āt,, 10 during the outlier-removal phase
5

---

Algorithm 1: User-Level DP Phased SGD with Outlier Iterate Removal and Output Perturbation
Input: Dataset DD 71 ...... 7n privacy parameters (c, 6), parameters p.g O, stepsize y):
Set / = [log2 ( [n]], C = 100 (alllo((mmm)))) (20mme /8)/E;
3 for i = 1........ do
Set n4 (1 (1/2)9)m/2"4 1/ n/221 N₂ n4/C, Nem, Ti 1000m:LyT, (nd():
Draw disjoint users D, of size from D;
Divide D; into C' disjoint subsets (Di ) each containing |Dul = N₂ users; for j 1, C. do zi, - SGD(D,, Thy Te, x;,1) = average iterate of Ti steps of one-pass projected SGD with data D.j. stepsize The and initial point 2;-1
end
10
Compute the concentration score for Dj:
si(Ti)
= C
1
Σ
1([3
T. S Ti)
J.J'E(C
Let (T.)) = sT())) L20(2//s):
11
(T)
4C then
5
12
S 0
13
for j = 1......... do
14
Compute the score function of Tigs big = ES
1(1āig
- -ipyll < 2T:);
h4s
C/2
15
Add a S, with probability Ptù for Pig
hij 2 20/3
C/2
C76
o.w.
16
end
17
end
else
19
Halt; Output 0
end
Let i; [5. Esnjes, Tij
+ 3, + Si, where S ~ ((0, with 100r, log (n/8)
22
EC
23 end
Output: 2/-
(i.e. - C). |S = C holds, then can use the convergence guarantees of SGD and the localization arguments in [FKT20 to establish the excess risk guarantee. In order to prove that need the following novel stability lemma:
| C' with high probability,
Lemma 2.3. Assume f(,,2) is convex. L-Lipschitz, and 3-smooth on X' with < 1/3. Let < SGD(D, n, T, xo) and t SGD(D', n, T, To) be two independent runs of projected SGD, where D, D' ~ PN are i...d. Then, with probability at least 1 - -,, we have
| - 5ll S 1 I Tog(dT//C
We prove Lemma 2.3 via induction I, using non-expansiveness of gradient descent on smooth losses (RSS6)) subgaussian concentration bounds, and a union bound.
Lemma 2.3 implies that if the data is ii.d., then the following events hold with high probability: | - Ti,y' < Tj for all j.j E [C2] and hence s,(T,) = C. Further, conditional on s,(T)) = C. that the algorithm does not halt. Also, | Tr S Ti for all j.j' implies pi.; = for all j and hence [S|| = C for all j. The detailed excess risk proof is provided in Appendix
know that (T,)) 2 4C/5 with high probability,
Challenges of getting optimal excess risk linear time: In the item-level DP setting, there several (nearly) linear time algorithms that achieve optimal excess risk for smooth DP SCO

---

under mild smoothness conditions, such as snowball SGD [FK220], phased SGD [FKT20], and phased ERM with output perturbation [ZTOH22] Extending these approaches into optimal nearly linear-time user-level DP algorithms is challenging. First, the user-level DP implementation of output perturbation in [GKK 23 is computationally inefficient. Second, snowball SGD relies on privacy amplification by iteration, which does not extend nicely to the user-level DP case due to instability of the outler-detection procedure in [AL24]. Specifically, since amplification by iteration intermediate only provides DP for the last iterate æT but not the intermediate iterates x₃ (t < T'), the sensitivity of similar instability issue arises if one tries to naively extend phased SGD to be user-level DP by applying [AL24] to user gradients. This issue motivates our Algorithm| ! which extends phased SGD in an alternative way: by applying
the concentration score function is not O(1), which impairs DP outlier-dttccion..
to the SGD iterates instead of the gradients, we can control the sensitivity of the concentration score and thus prove that our algorithm is DP. However, since the bound in Lemma 2 scales polynomially with T (and we believe this dependence on T is necessary), Algorithm| T adds excessive noise and has suboptimal excess risk. We believe that obtaining optimal risk in linear time will require fundamentally different user-level DP mean estimation procedure that does not suffer from the instability issue.
3 An optimal algorithm with ~ (mm))%/ gradient complexity for smooth losses
In this section, we provide an algorithm that achieves optimal excess risk using z (mn) 9/8 stochastic gradient evaluations. Our Algorithm Bis inspired by the item-level accelerated phased ERM algorithm of [KLL2]]. It applies iterative localization [FKT200 to the user-level DP accelerated minibatch SGD Algorithm Algorithm 2 is a user-level DP variation of the accelerated minibatch SGD
of GL GL13
Our Algorithm applies a DP outlier-removal procedure to the users' gradients in each iteration. We use Above Threshold [DR14] to privatize the concentration scores s(t) and determine whether or not most of the gradients users in minibatch D are 2r-close to each other. If 3 2 Å., indicating that the gradients of users in D are nearly 2r-concentrated, then proceed with outlier removal in lines 8-12. We then invoke privacy amplification by subxampling [BBG18] and the advanced composition theorem KOV15) to privatize the average of the "inlier" gradients with additive Gaussian noise. By properly choosing algorithmic parameters, we obtain the following results, proved in Appendix C
Theorem 3.1 (Privacy of Algorithm 3). Let e S 10, q > such that n--9
100 log (20nmdee (5). e(1 (1-(1/2))
Then, Algorithm 3 is (E,5)-DP.
Theorem 3.2 (Utility & runtime of Algorithm 3 Informal). Let S 10 and 8 < 1/(mn). Then,
Algorithm 3 yields optimal excess risk:
1
v /llog(1/0)
EF(x)) - F S LL.
+
Vmn
en/m
The gradient complexity of this algorithm is upper bounded by
(3R 1/4
(-111) )))
E (en2mm 1/8
BR nn 2/434/3/
n2/22m3/4
(mm))/8 1/8 A
mn 1+
T.
d2/4g1/2
If n. = d, E 1, and 3R = L then the gradient complexity bound in Theorem 3.2 simplifies to (mn))// + m///4m/// Typically, n² 2 m, so that the dominant term this bound is (mn) 9/8
Remark 3.3 (State-of -ote----thhhhaaeee art runtime). The gradient complexity bound in Theorem 3.2 is superior to the runtime bounds of all existing near-optimal algorithms by polynomial factors in n. m, and
[BS23 GKK+ AI.24). Note that while the mn3/2 gradient complexity bound of [BS23) may
appear to be better than 11/4 (nm))9
31/4(nmm) 9/88 in certain parameter regimes (c.g. m > n² or > nm), this
is not the case: the result of [BS23] requires m < Ft and 3 < /n//m.
Remark 3.4 (Mild assumptions). Note that Theorems 3.1 and 3.2 do not require any bound on the smoothness parameter 3, and only require the number of users to grow logarithmically: n !=o(1) >
((1/E). Contrast this with the results of previous works (c.g. (BS23]).
7

---

Algorithm 2: User-Level DP Accelerated Minibatch SGD F,, Tú K2 T4 T,6,6)
Initialize 2! 2;-1: for t 1, . do
Draw K2 random users D [Z 1 from D; uniformly with replacement;
Set noisy threshold A = 1K, + E,, where & ~ Lap (e);
Let qr (2) fr E ff 2) for user Z;
Compute the concentration score of D::
st(T) = K
Σ
- ((1x(2))2(())
s 2r)
Z
Let (T) (T,) + of. where of Lap it A, then = for Each User Z E D do Set (Z) Ex'ep; (Z) -z(Z'))l s 2T);
(:)
0
M((Z) < K4/2
11
Add Z to S with probability p!(Z) =
h((Z) Z 2K,/3
(((Z)-K.77
K,/G
0.w.
12
end
g: [87 Ezes; (i Z):
Ø. of + C. where 4 ~ NNO, with 0; 1000>v/i log(nde" 18).
14
271;
15
Do 1 iteration of Accelerated Minibatch SGD (AC-SA) [LL12 on Fg, using gradient 1+1 estimator 0 Ax(15_1 fi-1) to obtain - 4;-1
16
end
17
else
18
Halt; Return 0
19
end
end
21
Output 1
Algorithm User-Level DP Accelerated Phased ERM with Outlier Gradient Removal
Input: Dataset D (Zi...., Zn), privacy parameters (c, 5), parameters p. 9, À > 0:
Set [ [nog2(n) and O(L log(ndm)) /m), choose any initial point øg X;
3 for i = 1,... 1 do
Set n. (1 (1/2)9)m/2ia, >, = -- 2n ; T, = Ō(1 + (B/a),
K; = 500 log(n?m2² 18) Io (1/())
nes
Draw disjoint users D, of size n4 from D; Let [x(x) = A., EZ, F(x, Zi,)) d - where F(x, Zis) is user Zig's
empirical loss;
F; User- DP Accelerated Minibatch SCD(F,, T,, K,, 2z T,E,))))
end
9 Output Zi-

---

A challenge in proving Theorem 3.2 is getting tight bound on the variance of the the noisy minibatch stochastic gradients 9. that are used in Algorithm (lines 12-14). Conditional on S Dj. it is easy
to obtain variance bound of the form Bl (x 2 do? + K. since we are sampling K; users uniformly at random. However, this bound is too weak to obtain Theorem 3.2 since it does not scale with m. To prove Theorem 3.2 we need the following stronger result:
L
Lemma 3.5 (Variance Bound for Algorithm 2 Les S 1/(nm), S 1. Denote F.(x) =
1 2z,EED, F(e, Z.z). Then, conditional on S for all i [1, [Ti]. we have
L log(ndm)
Blgg V.
Km
for all i 11 E [Ti], where the expectation over both the random i.i.d. draw of D. (Zi...., ..n)== pum and the randomness in Algorithm 3
The difficulty in proving Lemma comes from the fact that the iterates ot and the data not independent. To overcome this difficulty, we use the stability of user-level DP [BS23] to argue that for all Z E D., (x 7) is x ////mlclose to V (=( with high probability, since x! is user-level DP. A detailed proof is given in Appendix C
Remark 3.6 (Strongly convex losses: Optimal excess risk with state-of-the-art runtime). f(,, 2) is ju-strongyy convex, then Algorithm can be combined with the meta-algorithm of (FKT20) Section 5.1] [] to obtain optimal excess risk
L? L..0 /
1 nm
dll(11/)
22n2m
with the same gradient complexity stated in Theorem 3.2 This improves over the previous state-of-
the-art gradient complexity ~ B(mm)3/2 of [AL24).
4 An optimal algorithm with subquadratic gradient complexity for non-smooth losses
In this section, we extend our accelerated algorithm from the previous section to non-smooth loss functions. To accomplish this with minimal computational cost, we apply randomized (convolution) smoothing (NSI22 DBW12 approximate non non-smooth f by 3-smooth f. We can then apply Al- gorithm
3 to Since convolution smoothing is by now a standard optimization technique, we defer the details and proof to Appendix [
Theorem 4.1 (Privacy and utility of smoothed Algorithm 3 for non-smooth loss informal). Let E S 10, 8 < 1/(m)), and q > 0 such that n 2-- > log (20mmde 18), Then, applying Algorithm
e(1-(1/2)²)
to the smooth approximation of yields optimal excess risk:
/dlog(1/0) en/m
EF(x:) F LR.
Vmn
The gradient complexity of this algorithm is upper bounded by
mi (1 [1 3/8
3/8 m 1/4g1/4)
Remark 4.2 (State-of-ther art gradient complexity). The only previous polynomial time algorithm that achieve optimal excess risk for non-smooth loss functions is due (AL24). The algorithm of [ required (nm)3 + (mn)² 2 2d gradient evaluations. Thus, the gradient complexity of the smoothed version of Algorithm 3 offers a significant improvement over the previous state-of-the-ar.. For example, if 1, then algorithm is faster than the previous state-of-the-an by multiplicative factor of at least n 7/4
5 Conclusion
In this paper, we developed new user-level DP algorithms with improved runtime and excess risk guarantees for stochastic convex optimization without the restrictive assumptions made in prior

---

works. Our accelerated Algorithm 3 achieves optimal excess risk for both smooth and non non-smooth loss functions, with significantly smaller computational cost than the previous state-of-the-art. Our linear-time Algorithm achieves state-of-the-ard excess risk under much milder, more practical assumptions than existing linear-time approaches.
Our work paves the way for several intriguing future research directions. First, the question of whether there exists a linear-time algorithm that can attain the user-level DP lower bound for smooth losses remains open. In light of our improved gradient complexity bound (*2 (nm))/8), optimistic that the answer to this question is "yes." key the development of optimal linear-time algorithm. Specifically, utilizing Lemma 2.3 to apply outlier removal to the iterates instead of the gradients appears to be pivotal. Second, the study of user-level DP SCO has been largely limited approximate (e, o)-D. What rates are achievable under the stronger notion of pure e-user-level DP? Third, it would be useful to develop fast and optimal algorithms that are tailored federated learning environments [MRTZI8] GLZW24), where only small number of users may be available to communicate with the server in each iteration. We hope our work inspires and guides further research in this exciting and practically important area.
now " We believe that our novel techniques will be
Acknowledgements
AL's research is supported by NSF grant 2023239 and the AFOSR award FA9550-21-1-0084 We thank anonymous NeurlPS reviewers for their helpful feedback.
10

---

References
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in l geometry. In ICML, 2021.
[A1.24] Hilal Asi and Daogao Liu. User-level differentially private stochastic convex optimiza- tion: Efficient algorithms with optimal rates. In International Conference on Artificial Intelligence and Statisties, pages 4240-4244. PMLR, 2024.
[ALT24] Hilal Asi, Daogao Liu, and Kevin Tian. Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions. arXiv preprint arXiv:2406.02788) 2024.
[BBG18] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Processing Systems, volume 31. Curran Associates, Inc., 2018
and R. Garnett, editors, Advances in Neural Information
[BFTT19] Racf Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances Neural Information Processing Systems, volume 32, 2019.
[BS23] Raef Bassily and Ziteng Sun. User-level private stochastic convex optimization with optimal rates. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardr, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 1838-1851, PMLR, 23-29 Jul 2023.
[CTW+21] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagiclski, Ariel Seerbert-Voss. Katherine Lee, Adam Roberts, Tom B Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In USENIX Security Symposium, volume 6, pages 2633-2650, 2021.
[DWW12] John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[DR14] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy, volume 9. Now Publishers, Inc., 2014.
[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439-449, 2020.
[GKK+23] Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, and Chiyuan Zhang. On user-level private convex optimization. In International Conference Machine Learning, pages 11283-12999 1299. PMLR, 2023.
[GL12] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization generic algorithmic framework. SIAM Journal on Optimization, 22(4):1469-1444 2012.
[GL13] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: Shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4):2011-2089 2013.
[GLZZ244] Changyu Gao, Andrew Lowy, Xingyu Zhou, and Stephen Wright. Private het- erogeneous federated learning without a trusted server revisited: Error-optimal and communication-efficeenn algorithms for convex losses. arXiv preprint arXiv:240..06690) 2024.
11

---

[HRS16] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Maria Florina Balcan and Kilian Q. Weinberger, editors. Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1225-1234, New York, New York, USA, 20-22 Jun 2016. PMLR.
JNG 19] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv: 100X0::1000.033366, 2019.
[KLL21] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in subquadratic steps. Advances in Neural Information Processing Systems, 34:4053-4064, 2021.
[KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy, 2015.
[LJCJ17] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Non-convex finite-sum optimization via sesg methods. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 2345-2355 2017.
ILLL 24a] Zhuohang Li, Andrew Lowy, Jing Liu, Toshiaki Koike-Akino, Kieran Parsons, Bradley Malin, and Ye Wang. Analyzing inference privacy risks through gradients in machine learning. arXiv preprint arXiv:2408. 16913, 2024.
[LLI,+24b] Andrew Lowy, Zhuohang Li, Jing Liu, Toshiaki Koike-Akino, Kieran Parsons, and Ye Wang. Why does differential privacy with large epsilon defend against practical membership inference attacks? arXiv preprint arXiv:2402.0995 2024.
[LR22] Andrew Lowy and Meisam Razaviyayn. Private stochastic optimization with large worst-case lipschitz parameter, 2022.
[LSA+21] Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. Advances in Neural Information Processing Systems, 34:1 12466-12477, 2021.
[LUW24] Andrew Lowy, Jonathan Ullman, and Stephen Wright. How to make the gradients small privately: Improved rates for differentially private non-convex optimization. In Forty-first International Conference on Machine Learning, 2024.
[McS09] Frank D McSherry. Privacy integrated queries: an extensible platform for privacy- preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 19-30, 2009.
[MRTZ18] Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differ- entially private recurrent language models. In International Conference on Learning Representations (ICLR), 2018.
[SSSS17] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[SSSSS09] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, volume 2, page 5, 2009.
[TC Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Friend- lycore: Practical differentially private aggregation. In International Conference on Machine Learning, pages 21828-21863. PMLR, 2022.
[U111]] Jonathan Ullman. CS7880: rigorous approaches to data privacy, 2017.
[XZ24] Zheng Xu and Yanxiang Zhang. Advances in private training for pro- duction on-device language models. https://research.ogg.../ advances -ireees-i-irvvvte-teeeee trainin- foree--orrrrrrooee httpapaww...ppppccoccooooooaaaar
2024. Google Research Blog.
12

---

[YNS12] Farzad Yousefian, Angelia Nedić, and Uday V Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56-67, 2012.
[ZTOH22] Liang Zhang, Kiran K Thekumparampil. Sewoong Oh, and Niao He. Bring your own algorithm for optimal differentially private stochastic minimax optimization. Advances in Neural Information Processing Systems,
2022.
13

---

Appendix
A More Preliminaries
A.1 Tools from Differential Privacy
Additive Noise Mechanisms Additive noise mechanisms privatize a query by adding noise to its output, with the scale of the noise calibrated the sensitivity of the query. sup D-D
Definition A.I (Sensitivity). Given a function q Z R and norm ||-Ilp on IR. the e--seniitivity of is defined as
(1) (D')
where the supremum is taken over all pairs of datasets that differ in one user's data.
Definition A.2 (Laplace Distribution). We say X Lap(b) if the density of X is f(X = x)
25 )
Definition A.3 (Laplace Mechanism). Let > 0. Given function q 2 R on R with l-sensitivity A, the Laplace Mechanism M is defined by
M(D) (D) + (Y....., Ya),
where {Y))_. are i..d. Y, Lap (2) Lemma A.4 (Privacy of Laplace Mechanism DR
The Laplace Mechanism is s-DP.
Definition A.S (Gaussian Mechanism). Let e 0, (0, 1). Given function q ZN - R with fg-sensitivity A, the Gaussian Mechanism M is defined by
M(D) == (D) GG
where Ng (II) and 0² 24 log(2/6)
Lemma A.6 (Privavey of Gaussian Mechanism (R14)..
The Laplace Mechanism is (c, 8)-DP.
Advanced Composition If adaptively query a data 7" times, then the privacy guarantees of the T-th query is still DP and the privacy parameters degrade gracefully:
Lemma A.7 (Advanced Composition Theorem [DR14). Let
0,5.8 E 10. Assume
A1 .A, with A, n x + X, are each (e, (e, AI = 1,... T. Then, the adaptive composition A(D) == Ar (D 1}) is (e', T8 DD for
é' 22T + Te(e 1).
Privacy Amplification by Subsampling
Lemma A.8 ((UII7)). Let M: ZM + X be ().8)-DP. Let M' 2N + X that first selects random subsample D' of size M. from the data set NN and then outputs M(D'). Then, M' is (5',8')-De where e' (6' (1'- and 8'
5M N
AboveThreshold algorithm DD14 which is key tool in differential privacy to identify whether there a query 2 threshold A. The AboveThreshold Algorithm Tass the following guarantees:
AboveThreshold:
a stream of queries q1...., Qr that above a certain
Lemma A.9 ([DR14), Theorem 3.24). Let > and a 8log(2T/n). k [T+ 1]. AboveThrrshold (e, D)P Moreover, with probability at least 1 - 7, for all & k, we have:
if 0z = T, then q: (D) 2 og and
of L. then q: (D) < A a
14

---

Algorithm 4: AboveThreshold
Input: Dataset
(Z1,..., 7n), threshold A E R, privacy parameter E; sequence of queries
01.". 2r 2 - IR, each with & -ssesiiityy 1;
2 Let 7 = A + 2)p(
for
do Receive new query 9: 2n - R;;
Sample Lap(
if q: (D) + 14 2 A then
Output: a₂ T;
Halt:
end
10
else
11
Output: a; 1;
12
end
13
end
A.2 SubGaussian and Norm-SubGGuassin Random Vectors
Definition A.10. Let >> O. We say random vector X is SubGaussian (SG(() with parameter if Efe((r.X-Ex) S e /0 for any Rd. Random vector E Rdd is Norm-SubGaussian with
parameter Ç (nSG(()) if EX] 2 1 2e
2e 22 for all t 0.
Theorem A.11 (Hoeffding-type inequality for norm-subGiaussinn x.) ",
19) Let XI.... X
for [k] be the corresponding filtration. Suppose Rdd be random vectors, and let J; a ( for each E [k)], X; Fi-1 is zero-mean mSG(G). Then, there exists an absolute constant > 0, for any y > 0,
X 2 log(d/7) [E
Σ ? iE(R]
ST.
There exists an absolute constant e, such that if X is nSG((), then for any fixed unit vector E IRd (v, X) is of norm-SubCaussian.
Lemma A.12 (JNG+ 19
B Proof of Theorem 2.1
Theorem B.1 (Formal statement of Theorem 2.1 Suppose n 1 (100/(1-1/21) log(n/8)
some small q > O, and m S nd for some large J O. Choose p = J 3/2 and n
R/ (LV dmne).
in Algorithm 7 Then, Algorithm 7 is (8, -user-elelll DP and achieves excess risk
(Vinne
(iime + Vdlog(1/0)
EF(x)) F LR. Ō
Vne /m
using nm gradient evaluations, provided 3 S (5/R)ddmaa
The gradient complexity is clear by inspection of the algorithm: The number of stochastic gradients computed during the algorithm is
Σ T.C = Σ NamC Σ nmm S am.
Next, we will prove the privacy statement in Theorem B.I The following lemma ensures that if the Laplace noise added in Algorithm i is sufficiently small and outlier detection succeeds, then the sensitivity of ē; is O(T/C)) with high probability.
15

---

Lemma B.2. |A224
Slight modification of Lemma 3.5] Let i E [1] and C > O. Suppose D; and D' differ in the data of one user and we are in phase of Algorithm I Let E, be the event that the Laplace noise added to the concentration score (T(T.) for D2 has absolute value less than 2C/15 and define F similarly for data D'. Denote 0; == (T) 2 4C/5) and af == (T((TT) 2 4C/5), where (T( and (T,) are the noisy concentration scores that we get when running phase of Algorithm ! on neighboring Dj and D' respectively. Then, conditional on a, = am and E, . E there is coupling I over T; and T such that for (yi, v13 drawn from I' we have
log(1/() C
ly: 1/1l 2
with probability at least 1
Ç.
With Lemma B.2 in hand, we proceed to prove that Algorithm Iis (c, 80-user-level DP:
Proof of Theorem B.7 Privacy. Privacy:
Since the {D:Y are disjoint, parallel composition of DP McS09] implies that it suffices to prove that phase is (s, -jsuer--eeee--DP for any fixed and fixed T--1. To that end, let D and D' be adjacent datasets differing in the data of one user, say 2, * Z without loss of generality. We will show that the outputs of phase i when run on and D'. x, == (D) and ot == (D') respectively, are (E. -iidistinnuuisaable.
Let E, be the event that the Laplace noise added in phase (for data set 'D) has absolute value less than 2C/15 and define E analogously for data set D'. Note that E, and E are independent and 3/10ef. Denote Ç == 5/ 5/10e Let 4C/5). where (T,)) and (T:) are the noisy concentration scores that we get when running phase i of Algorithm|| I on neighboring D; and Dj, respectively. By Lemma B.2 and our choice of C, we know that, conditional on E, A E and on a; a/e there exists a coupling I over (Z,, F() such that for (y,. v drawn from r, we have
P(E,, Ey) 2
(T; 2 4C/5) and af := (3, 2
1y: v/ll S log(1/))
C
with probability at least 1 C.
Note that the sensitivity of 8; is less than or equal to 2. Thus, by the privacy guarantees of the Laplace mechanism (Lemma A.4), we have
P(a, = 6) S </
(2)
for any b E 1). Further, this implies
P(a: = b, E ///4 c//4 [P(c = b, EA) + 51
(3)
By the bound (I. the privacy guarantee of the Gaussian mechanism (Lemma A.6). our choice of os and independence of the Laplace and Gaussian noises that we add in Algorithm we have
P(x; E O Eg a = 1) e "P(c) E E E, of = 1)
n +
(4)
for any event O X Moreover, since the algorithm halts and returns = if a; 0,, we know that
P(z, E E,, a; 0) PPx E O E af = 0)
(5)
for any event O C X. Therefore,
P(x, E 0) P(z, E O (.) e 0 E;)((E))
P((,, 0 E, a; =
0 -
I e/ e O =[
+P(z) e 0 E, af = [FE, +
16

---

S e O,E,) + & ( +1)
S 0) +
where (i) follows from inequalities the privacy proof.
and (5) Thus, Ty is (usee--uee--l This completes
Next, we turn to the excess risk proof. The following lemma is immediate from KK20 Lemma 4.5]: Lemma B.3. Let 7i 1/B. Then, for any X and all i. we have
Blyy ri-1 1|
B[F(E.,) - F(v))
n:Ti + 1,
The next novel lemma is crucial in our analysis:
Lemma B.4 (Re-statement of Lemma 2.3 Assume f(.,z) convex, L-Lipschitz, and 3-smooth on X with 1/8, Let ā + SGD(D D n, I, xo) and y SGD(D', ,,, be two independent runs of projected SGD, where D' PM are ii.d. Then, with probability at least C, we have
| أll S
Proof. Let Gr = V (a ze) for drawn uniformly from D without replacement and gf == Vf(n,, z() for z/ drawn uniformly from D' without replacement. Let F(x) == Ez= =)].
We will prove that ||=r, - yel S (og(dT//) with probability least 1 - Ç/tt for all E [7].
Note that this implies the lemma. We proceed by induction. The base case, when / = 0, is trivially true since xo = Yo. For the inductive hypothesis, suppose there is an absolute constant e >> such that with probability at least 1 - tC/T,, we have
||=;
3ill S en log (dT/(c) 2T
Vi < Then, for the inductive step, we have by non-expansiveness of projection onto convex sets, that
|
31-1/12 S Iz 79: (ye ng()il²
11= - v/ Fxx+) (y/ VV(() 7(9 VF(x,) VF
||2, - 77 F(x)) - (ye F)F)()))
-2n(xre - f),)(x; (vi - ,)VF(())) -F(x) 9/ + VF()))
+ 1721gg VF(x,) g. VF()))12
2 ||,, - vell - 2 F,,)) (y:- (V.-VFFF(.)). VF(x.) g. + VF(v.)
2
(6)
where (i) follows from the non-expansive property of gradient descent on smooth convex function for 17 S 1/3 [HRS16).
Define 0 = 2 - (v:-n)V((r))) - VFF())F())) By Inequality (6) and the inductive hypothesis, we obtain
| 11 4n L
a2
remains to bound Σ
=1 ag Note that Eia; a1. 0; = 0, and by Lemma A.12 we know
there is constant such that a; is nSG(cn y: [)) for all i. Hence by Theorem A.11 know
Σ a 2 en
1og(dT/>)
Σ ||
11
$1
151
17

---

Conditional on the event that - vill I /V/oo((TT((nnVV for all S t (which happens with probability - by the inductive hypothesis), we know
P
(c 1)23, log(d//C)) (og( ||=;
will s clog(ct/((nLLv, -1-
Hence know
P ||02+1 Mc+1ll 2 log(dT/()n 11 ( vill s clog(dI vi S S C/T.
Combining the above pieces completes the inductive step, showing that || y S
</ + (t
()ood))lg(T//) 2nL with probability at least - (t + 1)/TT. This completes the proof.
By combining Lemmas 2.3 and B.3 with the localization proof technique of [FT20) we now prove the excess risk guarantee of Theorem B.I
Proof of Theorem 2.7 Excess risk. Excess Risk: First, will argue that 5; = - 2 Fig for all
i with high probability 3/nm. Lemma 2.3 implies that
| i S T,
for all i E J.J E [C] with probability at least 1 - 1/mm. Thus, s; (T;)) C' with probability at least 1/nm. Now, conditional on (T, = C. we have (T,) 2 4C/5 for all i with probability at least 1 1/nm by Laplace concentration and a union bound. Moroever, if ||ā.,j &igell S for all j.J'. then Pi.j for all j and hence there are no outliers: S; ( By union bound, we conclude that S; = {Ā., bjjej and hence ă; = s. ED.,ES, सt.5 for all i with probability at least 2 - 3/mm. By the law of total expectation and Lipschitz continuity, it suffices to condition on this high probability good event that ã; En= ã. for all i: the total expected excess risk can only be larger than the conditional excess risk by an additive factor of most 3.RRnnm
Now, conditional on ã; = 3. ED,YsS, Tig. Lemma B.3 and Jensen's inequality implies
E
x--1 11?
do;
E(F F(
+ n2L
m,Ti + moLL
n.
Next, let 2 == x- argmin EE F()) and write
B[F(1) F B[F(x;) -(x+-)))+ F(z?)]
R²
+ nI² + [m n.L3 + I² Van V
T/Ti
i=2
R²
n/ii + dnL + LL2 L2 /n.
Plugging in the prescribed algorithmic parameters completes the excess risk proof.
C Proofs of Results in Section 3
Theorem C.1 (Re-statement of Theorem 3.1. Let S 10, q such that m
100 (20rmmde 18), Then, Algorithm is (e, DD.
c(1 <(1-(1/2)))
We require the following lemma, which is direct consequence of AL24 Lemma 3.5]:
18

---

Lemma C.2. Consider Algorithm
2 Let Dj and D be two data sets that differ in the data of one
user. Let E, {lut] & K:/20 vt [T]] n I K, K2/200. Define E similarly for independent
I K2/20 VI E [T:] S K2/20]. Let ož 4K,/5 denote the concentration scores iteration t. Then, conditional on E. (4 and conditional on of b/. there exists coupling 1 over g) (D,) and
draws of random Laplace noise: E = (1(
1 (D. 2 4K2/5) and bj (D)
gi (D)) such that for (h, drawn from 1 we have
(1/S)
|| 11 S
K;
with probability at least 1 1-6 Ç.
Proof of Theorem C.1 Note that our assumption on n 12--9 being sufficiently large implies that n, 2 log (1mdd66) for all E [1]. By parallel composition [McS09] and post- post-processing. it suffices to show
[4] and let D and D be adjacent datasets that differ in the data one user such that D; * D. We will show
that (gt Jt= satisfies (s, d-user-elell DP for any [4] To that end, fix any
T
that (or (D) T. and (D')) are (e, d)-inndisingguishalle which will imply that Algorithm is (e, 5) userr-eeve DP.
Let E, = { & K2/20 Vt E [T] n & S K,/20). Define E similarly for independent draws of random Laplace noise: EN (I(ett
K, vt [T.] n [ s Kz/20). Our choice of K, 2
500 loginmdee (0) ensures that
P E. Ex 2 - 6/(10e().
by Laplace concentration and a union bound. Let ( == (/
Let a: 1 (3 (D) > 45, and bf = (3 2 4K./5). Note that if of = bj. = 0, then
(D) = g
Conditional on the good event that of = by for all and conditional on E. E.n EY, we can bound the fz-sensitivity of of with high probability, via Lemma C.2 and a union bound:
(D) ( < (L)( T log(nme" 18)
(8)
K,
K:
for all t E [23] with probability at least 1 - T:C = 1 61(00
Note that (D)) and (D') are e/2-indistinguihhal old in Lemma A.9 since the sensitivity of st is upper bounded by 2. Therefore,
by the DP guarantees of AboveThresh
P( = u. U.F)) Fb)) S e2 [P(C))
E7) +
for any a E 1)
Now, by the sensitivity bound (8) the privacy guarantee of the Gaussian mechanism (Lemma A.6 and our choice of o,, the advanced composition theorem (Lemma A.7, and privacy amplification by subsampling (Lemma A.8), we have
(D) E EO1
v) S ( E E, (b u) (T++ 1)ç. (10)
for any event O C X. Here we also used the fact that K; >
nyc VT.
For short-hand, write {a/] = if of = 1 for all t E [T:] and {a = 0 if Ø = 0 for some
t E [7:]: similarly for if. Then since the algorithm halts and returns (0( T, if (a)) 0.
we know that
((IO E E E,, (a 0) = =) -
0 E 0), (1I)
for any event O X.
Combining the above pieces, we have
(D)) e 0) (()) E 0 (0)))))+++++))))))))0)00
0 (EEE)()
19

---

1)PEE, fa =
[0 - ()]( (a. =0)
E0 1) P(E 16.11 = 1) + TT)
- =(0 = 02 [P(E), (b)) 0) + +Tc] + TC
S E + 4TC (26 +1)
S ((
where (i) follows from inequalities and which implies the result.
Thus, (D)) is (e, ueeee--Dee-.
Theorem C.3 (Formal statement of Theorem 3.2 Let e S 10 and å < 1/(mn). Then, choosing
=
n
Vnm
En/m
and 3q + 2.5 + loga (vm) in Algorithm 3 yields optimal excess risk:
1
/dlog(1/5)
BF(m) - F S LR
mmn
enym
The gradient complexity of this algorithu upper bounded by
(3RR)
1/4
(mmn)1/ A (22n'm) (F(dm)
)²) + +)++
1/8
+ + (d//4/1122
BR 12/4m3/1 3/1
(nh/3m8//1
(1+E
d
will need the following bound on the excess empirical risk accelerated (noisy) SGD for the proof of Theorem C.3
Proposition 7] Let x be computed by T steps of (multi-stage) Accelerated Minibatch SGD on A-strongly convex, B-smooth with unbiased stochastic gradient estimator g' such that E Eggg VF(x') < 22 for all E [T). Then.
Lemma C.4. GL13
V2
E B(F(2T) min ((x) [F(0)
min (xx) exp =Ex
-T
XT
Remark C.5. As noted in Lemma C.4
we technically need to call multi-stage implementation of Algorithm 2 in line 7 of Algorithm (as in (GLI3)) get the desired excess risk bound for minimizing the regularized ERM problem in each iteration. For improved readability, we omitted these details in the main body.
Next, obtain bound the variance of the noisy stochastic minibatch gradient estimator øl in Algorithm which can then be plugged in for 12 Lemma C.4
Lemma C.6 (Re-statement of Lemma 3.5 Let 8 < 1/(nm), & 1. Denote F((x)
n4 Ez, F(x,Zr,)) Z. Then, conditional on S D all E [1, E [TT, we have
L log(ndm)
E| g (F
Km
for all i 11,t [T]]. where the expectation is over both the random i...d. draw of D (Z,...., 2n) pum and the randomness in Algorithm
Proof. By (LCI1Z Lemma A.1], know that, conditional on the draw of the data D and for fixed xi_ y the variance of the minibatch estimator of the gradient of the empirical loss is
9f VF((ot )) >
K
m
Dj, xf_
= E (i) (x))((r))
vf(a(_11 21,9)) -
(F((fa)))
Dr
Km
20

---

1(K = n) 1 K
V (z
(12)
Recall (x)x) - Now, for any fixed x and any Z E D. Hoeffding's s inequality implies that
n, EeED, (x, 2) is the empirical loss of Dj.
Tr (TyTog (og(nd/7) vm
Fv 2) VF(=) TT=
with probability at least 7, where F(x., 7) -
-1E22 far 2) is user Z's empirical loss. Thus, by the stability of user-level DP (see [BS23 Theorem 3.4J), for any i E [1] t [t], we have that
|VF 2) VF
(13)
for all DD with probability at least - - n((=2 + 8), since xi-1 is (c, -user-eellll DP. To make y S 1/m, we choose y = 1/mn and use the assumptions that S and ô S 1/mn, Thus, for any fixed i, f we have
L logo(n2mmd vm
V -) VF(
for all Z E D with probability at least 1 1/m, which implies
L log(nmd)
E/ -
This also implies
E E - VF L log(nmd)
m
by Jensen's inequality, where (r(x) is the empirical loss over the entire data set D. Plugging the above bounds into then yields
L log(ndm)
K
Bllof - ViGGL-DI1
EDwpam Ate Unif([n])
V
(((f-11><h)) -
Km
Km
j=1
1(K n) L log (nmd)
m
completing the proof.
We are now ready to prove Theorem C.3
Proof of Theorem C Excess risk: Note that the assumption in the theorem ensures that K; S n;
for all i. By similar arguments to those used in [A224] Proposition 3.7], we will show that with high probability 2 - 2/(mm), for all i [4) E [T,]. S = DŁ and hence of an unbiased estimator of v F (zt). To show this, first note that for any >> and any fixed x,
V VF 2,) VF(x)] Llo((nd/7) vm
with probability at least 1-7/K, by Hoeffding's inequality (see AL24 Lemma 4.3]). Next, we invoke the stability of differential privacy to show that for all [T)), ((( (Z,,x,) ))
is r-concentrated (i.e. there exists 9* E Rd such that [g (Zt, d0ll < 7) with probability at least 25 + 6) (see [BS23 Theorem 4.3l). By union bound and the choice of
21

---

1/((m))) log(ndm)e"9 we have that (0.2).)......(2Z.... (e((Z, is 7-concentrated for all e [0,,t e [T]] with probability at least 1- 1/nm. Now, 7-concentration of (q:(Z),) ............... (4, implies (T) = K, Further, (T) K2 implies (7) 4K,/5 with probability least - ( if k).br by Laplace concentration and union bound. Next, note that 7-concentration of ((.. qr (2,),,,)) implies ( for all j E [K and S D Thus, S D for all i,t with probability at least 1/nn. Setting 1/nm and using union bound shows that with probability at least 2/m,, we have S = D and g = v D (xt) for i,
K, 2 500
Now, Lemma C.4 implies that, if the outier--rmoval procedure in Algorithm Iledds to an unbiased gradient estimator g (line 12) for E [T. = O(1 + 33/X,), then
V?
E E[F(x,)))
min F((x)) v
(14)
X.T.
(unconditionally, after taking We have shown that the event [1], E [T:]] occurs with probability at least 2/nmm. We will condition GOOD for the rest of the proof: note that the Lipschitz assumption implies that the total (unconditional) excess risk will only by larger than the conditional (on GOOD) excess risk by an additive factor of at most 2LR/ /nmm
where V/2 [( - (=(2111 S do +
log(ndm) L
K.m.
expectation over the random draw of D pum. by Lemma 3.5
GOOD {o} V F D. (1r5) for all
By stability of regularized ERM (see ) we have
L
B(F(x;) - F(v)] $ A,,mm
+ A - y|l²]
(15)
for all i, where 2 == argmin F.(x). By strong convexity and (4). we have
do? La Pog(ndd)
(A,/2)Bllz; 1| < BF((2)) Fr
(16)
X.T.
X,T.Kim
Thus,
d L (og(mmd))
dr Log(111)))
+ La log(ndm)
-1 - 21 S
(17)
A,T; A.T.K.m
X3e2n?
XTT.Kim
Now, letting 20 = x= argmin EE
F(x) and hiding logarithmic factors, have:
E[F(z)) - F == = ((F(())) - F F(z 1]] + - F(a7)]
1m1
L
L
AR
E
+ Aellx - 112111
LIE [x)
x1
X
Axnmm
i=2
L
L
(og(/0)(1/6)
L
XR2
+ >₂
Anm
Amnim
X? T K
1=2
dd / Ti log(1/8)
A
where the first inequality used (15) and Lipschitz continuity, the second inequality used (17)
Note that K,T. 2 ni. Further, our choice of sufficiently large p makes A large enough that
Vdr I: log(1/5)
LRVd Therefore, upper bounding the sum by it's corresponding geometric enym
Areni series gives us
LRVd 1 + d= log(1/0)) en/m m
((F( - S
+ AR
(18)
nm
e?n²
Plugging in À completes the excess risk proof.
Gradient Complexity: The gradient complexity is Ei= T.Kmm. Plugging the preseribed choices of T, and K, completes the proof.
22

---

D Details on the non-smooth algorithm and the proof of Theorem 4.1
For any loss function 2(; define the convolution function f+(+,2) f(;,2) my where Mr is the uniform density in the & ball of radius centered at the origin in R. Specifically, n.-(y) = [(++1) for Ilyll S and (v) = 0 otherwise. For simplicity, we omit the dependence on x nd
2 in the following Lemma:
Lemma D.1 (Randomized Smoothing, YNSI2 DBW12)). For any O, let X, == X + {x E E |||||| <r). If f is convex and L-Lipschitz over &r, then the convolution function fr has the following properties:
fx()) & f(x) S
= fx(a) + for all X.
fr is L-Lipschitz and convex.
is Lyd. L.A. smooth.
For random variables ny. have Ey LL v)] fz).
The following lemma can be easily seen from the proofs of Theorems and 3.2
Lemma D.2 (Privacy and utility of Algorithm 3 for general K, T.). Let & 10, 0 such that n 100 log 220mmde /6)
(1/29))
If Ki 2 VT.
log log(mnnde (nundee (6)
then Algorithm is ( -)seer--eell DP.
IfT,K; n, and T; 2 (1
for all then Algorithm achieves optimal
excess risk.
Theorem D.3 (Formal statement of Theorem 4.1) Let E S 10, 8 < 1/(mn), and q > such that n log (20nande /6) Suppose that for any 2, f(,2) is convex and L-Lipschitz over X, for
(1/2)9) X, = X (x R | S r where vd R. Then, running Algorithm 3 with functions cnym
{fr (z: >ED yields optimal excess risk:
(
Vin + dllog(1/6)
EF(x) F LR.
enym
The gradient complexity of this algorithm is upper bounded by min (1+n s/ag2/))
Proof. By Lemma D.I and our choice of r, we have [r(x, 2) - f(x, S Lr OLR vd) Set
Vmn Then know that
Vd EF(x) F ( - - en
Further, F, is 3-smooth for S henym. Set T; (1 + v /B(x,) log(ndm)
3/4 1/2 log(ndm) and K; VT. + log(nmde" /8). Then Lemma D.2 implies that Algorithm n. (e, 6) user-level DP, and yields the excess risk bound
EF,(a) - F" < ò
1 Vinm
lolo/(1/0) enym
as desired. The number of gradient evaluations is
Σ
T.K.m mn (1 n3/8 m/4
1=1
This completes the proof.
23

---

E Limitations
Our work weakens the assumptions on the smoothness parameter and the number of users that are needed for user-level DP SCO. Nevertheless, our results still require certain assumptions that may not always hold in practice. For example, we assume convexity of the loss function. In deep learning scenarios, this assumption does not hold and our algorithms should not be used. Thus, user-level DP non-conver optimization is an important direction for future research [LUW24]. Furthermore, the assumption that the loss function is convex and uniformly Lipschitz continuous may not hold in certain applications, motivating the future study of user-level DP stochastic optimization with heavy tails R222 ALT24].
Our algorithms are also faster than the previous fate-of-the-ane including lincar-time Algorithm | with state-of-the-art excess risk. However, our error-optimal accelerated Algorithm runs in super- linear time. Thus, in certain applications where a linear-time algorithm needed due to striet computational constraints, Algorithm| I should be used instead.
runs
F Broader Impacts
Our work on differentially private optimization for machine learning advances the field of privacy- preserving ML by developing techniques that protect the privacy of individuals (users) who contribute data. The significance of privacy cannot be overstated, as it is a fundamental right enshrined in various legal systems worldwide. However, the implications of our work extend beyond its intended benefits, and is essential to consider both potential positive and negative impacts.
Positive Impacts:
1. Enhanced Privacy Protections: By incorporating differential privacy into machine learning models, provide strong privacy guarantees for individuals, mitigating the risk of personal data being exposed or misused.
2. Ethical Data Utilization: DP ML enables organizations to leverage data while adhering to ethical standards and privacy regulations, fostering trust among users and stakeholders.
3. Broad Applications: The techniques we develop can be applied across diverse domains, including healthcare, finance, and social sciences, where sensitive data is prevalent. This broad applicability can drive innovations while maintaining privacy.
4. Educational Advancement: Our research contributes to the growing body of knowledge in privacy-preserving technologies, serving valuable resource for future studies and fostering an environment of continuous improvement in privacy practices.
Potential Negative Impacts:
1. Misuse by Corporations and Governments: There is a risk that our algorithms could be exploited by entities to justify the unauthorized collection of personal data under the guise of privacy compliance. Vigilant oversight and clear regulatory frameworks are necessary to prevent such abuses.
2. Decreased Model Accuracy: While DP ML provides privacy benefits, it can also lead to reduced model accuracy compared to non-private models. This trade-off might have adverse consequences, such less accurate medical diagnoses flawed economic forecasts. For example, an overly optimistic prediction of environmental impacts due to lower accuracy could be misused weaken environmental protections.
While recognizing the potential for misuse and the trade-off's involved, we firmly believe that the advancement and dissemination of differentially private machine learning algorithms offer net benefit to society. By addressing privacy concerns head-on and advocating for responsible use, we aim to contribute positively to the field of machine learning and uphold the fundamental right to privacy. Through ongoing research, collaboration, and education, we strive to enhance both the capabilities and ethical foundations of machine learning technologies.
24

---

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 state our results in Sections 2-4 and prove them in the Appendix.
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
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or 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 images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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 set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification: All assumptions are provided in theorem statements and proof' are provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's 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 properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This is theoretical paper without experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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 (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer:
[NA]
Justification:
This is a theoretical paper without experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
cessionnPlccyy 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 NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuiu wwwiiicgguie///eeeeeeeeic CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is a theoretical paper without experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can 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: [Yes]
Justification: This is theoretical paper without 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, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
27

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
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: [Yes]
Justification: This is theoretical paper without experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: h/tp::///euipp..eeeee http://........i.ttttttssootto..
Answer: [Yes]
Justification:
The research conforms to the Code of Ethics.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a 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: [Yes]
Justification: See Appendix
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 to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
28

---

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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is theoretical paper without experiments.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards 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
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
This is a theoretical paper without experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, wwppppswpptseeee whw.ree.wthhhe....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are 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 is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
29

---

Answer:
[NA]
Justification:
This is theoretical paper without experiments.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This is theoretical paper without experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is theoretical paper without experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "71kg7dt1qN", "reviewer": "Reviewer_JSLp", "summary": "This paper proposes new algorithms for stochastic convex optimization under user level differential privacy. This paper improves the computation complexity. The first algorithm achieves linear time complexity with suboptimal risk bound (the risk is SOTA among all linear time algorithms). The second algorithm achieves optimal risk with suboptimal time complexity (the time complexity is SOTA among all risk-optimal algorithms).", "questions": "1. Can the authors provide more intuitive explanations of the design of algorithms, especially the second one? \n\n2. I wonder what will be the risk bound for strong convex loss functions. The case with strong convex loss function has been discussed in \n\nKamath et al. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. ICML 2022.\n\nThis holds for item-level case. I wonder if one can derive the user-level counterparts.\n\n3. Can the authors please provide more discussions on why it is hard to achieve linear time with optimal risk?", "limitations": "The authors have addressed limitations well in the conclusion.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors have addressed an important problem. The method improves over Bassily et al. ICML 2023 and Liu et al. AISTATS 2024 on the time complexity. Moreover, this paper removes the assumption n\\geq \\sqrt{d}. I think that this paper makes a solid and interesting contribution.", "weaknesses": "1. I feel that the second algorithm (Section 3 in the paper) is hard to follow. I do not understand the main ideas of the design. \n\n2. Based on my own understanding, it seems that this paper requires $\\epsilon<1$, since it divides users into $1/\\epsilon$ groups. When $\\epsilon>1$, there is only one group. Following the remainder of this paper, I feel that the bound with $\\epsilon>1$ may not be optimal. Please correct me if it is wrong.\n\n3.In item-level case, optimal rates with linear time has been achieved in\n\nFeldman et al. Private stochastic convex optimization: optimal rates in linear time. STOC 2020.\n\nAlthough this paper has cited the above paper, it would be better if the authors can provide more explanations on why achieving linear time with optimal rik is hard for user-level cases. In other words, why does the methods in Feldman et al. can not be simply extended to user-level case. My feeling is that using something like two-stage approach (such as Levy et al. Learning with user level privacy. NeurIPS 2021), the item-level methods can be converted to user-level ones with optimal rate.\n\n\nMinor issue: The statements of three algorithms are not with the same font. The algorithm 2 is different with algorithm 1 and 3.\n\nIn general, I think that the paper indeed makes a solid contribution. However, the writing needs to be further improved and details need to be further polished.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful feedback and your positive assessment of our work. We respond to your comments below. \n\n\n>*Main ideas of the second algorithm (Section 3 in the paper)*\n\nOur second algorithm is **inspired by the item-level accelerated phased ERM algorithm of [KLL21]**. Their algorithm runs in $\\log_2 (n)$ phases. In each phase $i$, a disjoint batch of $n_i$ samples is used to define a regularized empirical loss function, $\\hat{F}_i(x)$. The main ideas of the algorithm are:\n \n- A noisy DP variation of **accelerated** SGD is used to efficiently find an approximate DP minimizer $x_i$ of $\\hat{F}_i(x)$. This approximate minimizer $x_i$ is then used as the initial point in phase $i+1$. \n\n- By **stability** of regularized ERM, $x_i$ is also an approximate minimizer of the underlying population loss function $F$. \n\n- **Iterative localization**: As $i$ increases and $x_i$ gets closer to  $x^* = argmin_{x} F(x)$ , we increase the regularization parameter (geometrically) to prevent $x_i$ from moving too far away from $x_{i-1}$ and hence from $x^*$. We also shrink $n_i$ geometrically. \n \nOur algorithm is a **user-level DP variation of the algorithm described above**: Our **Algorithm 2 uses outlier-detection and outlier-removal procedures to get a low-variance noisy *user-level DP* estimate of the gradient** (with sensitivity scaling with $\\tau \\approx 1/\\sqrt{m}$) in each iteration. This noisy user-level DP gradient is then used to take a step of accelerated SGD. Algorithm 3 uses Algorithm 2 as a subroutine to get a **stable**, user-level DP approximate solution of a regularized ERM problem in each phase, and applies **iterative localization**. \n\nPlease see **Section 1.1 and lines 219-225** for a more detailed description of our algorithmic techniques. \n\n>*it seems that this paper requires $\\varepsilon <1$, since it divides users into $1/\\varepsilon$ groups…I feel that the bound with $\\varepsilon >1$ may not be optimal. Please correct me if it is wrong.*\n\n\nGood question. In fact, **we do not require  $\\varepsilon <1$**.\n\n**For Algorithm 1, we do not necessarily need $\\varepsilon < 1$:** it suffices that $\\varepsilon < 50 \\log(20 n m e^{\\varepsilon}/\\delta)$, so that  $C \\geq 2$. This condition is not practically restrictive.  \n\n**Algorithm 3 is also optimal for $\\varepsilon > 1$:** This algorithm does not divide users into groups that depend on $\\varepsilon$.  \n\n>*More explanations on why achieving linear time with optimal risk is hard for user-level cases…why the methods in Feldman et al. can not be simply extended to user-level case?*\n\nExcellent question! Note that even obtaining user-level DP algorithms with *polynomial* runtime was challenging and only recently solved by the work of Asi & Liu (2023). \n\nIn the item-level DP setting, Feldman et al. give two optimal linear-time algorithms: snowball SGD and phased SGD.\n\nIt is not at all clear how to extend snowball SGD into an optimal linear-time user-level DP algorithm. \n\nTherefore, we aimed to extend their phased SGD algorithm into a user-level DP algorithm with our Algorithm 1. The key challenge in obtaining optimal user-level DP excess risk with this algorithm is controlling the **user-level sensitivity of the iterates of one-pass SGD**. In the item-level case, the sensitivity of the iterates is $O(\\eta L)$ [Feldman et al., Lemma 4.3], independent of the number of iterations $T$. However, in the user-level case, the sensitivity is $O(\\eta L \\sqrt{T})$ (our Lemma 2.3), and we believe this bound is tight. Hence the additive Gaussian noise that is needed to privatize the iterates is too large to obtain the optimal rate in the phased SGD framework. Thus, a fundamentally different algorithmic framework that leverages Lemma 2.3 in a more effective way may be needed to obtain the optimal rate in linear time. \n\nA second challenge in designing user-level DP variations of phased SGD is **instability of the outlier-detection scheme**: If the initial point $x_{i-1}$ changes by a small amount and we do outlier-detection, then the output can change greatly. Moreover, outlier detection seems to be necessary for any optimal user-level DP algorithm. Thus, another direction for future work could be to develop a new, **more stable outlier detection method**.  \n\nWe will add a discussion of these challenges and potential ways to overcome them in the final version of the paper.\n\n>*My feeling is that using something like two-stage approach (such as Levy et al. NeurIPS 2021), the item-level methods can be converted to user-level ones with optimal rate.* \n\nFirst, recall that the approach of Levy et al. does not obtain optimal rates. Moreover, their two-stage approach is similar to our outlier removal procedure. Their approach  suffers from similar instability as our outlier removal approach. Thus, we do not see any way for their approach to allow for improvements over our algorithms. Please let us know if you have any ideas for how to leverage Levy et al. that we might be missing.  \n\n>*What will be the risk bound for strong convex loss functions?* \n\nGreat question! The risk bounds for $\\mu$-strongly convex loss functions will essentially be **the square of the convex risk bound** (but with the scaling factor $LR$ replaced by $L^2/\\mu$). This follows from a reduction in [FKT20]. In particular, **Algorithm 3 can easily be converted into an optimal algorithm for strongly convex functions with state-of-the-art runtime**. We will comment on this in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qRLu6D5fVK", "reviewer": "Reviewer_W7xk", "summary": "This paper considers stochastic convex optimization under user-level differential privacy.\n\nAlgorithm 1 achieves the previous state-of-the-art excess risk of the linear-time user-level DP algorithm with milder assumptions. The algorithm is based on item-level DP-SGD algorithms. Previous paper AL24 shows that when the data of one user changes, the empirical gradient will not change too much, hence they remove outlier gradients to ensure privacy. Instead of removing outlier gradients, this paper removes outlier SGD iterates. This technique relies on a novel stability bound of SGD iterates proved in this paper.\n\nAlgorithm 3 improves the run-time for both beta-smooth and non-smooth loss functions. It applies outlier-gradient removal to random mini-batches and implements previous subroutines to reach a good performance.", "questions": "The questions are asked in the 'Weaknesses' part.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper makes concrete improvements from the previous work. Algorithm 3 has a faster run-time under milder assumptions while achieving optimal excess risk and user-level DP. Algorithm 1 improves the previous state-of-the-art excess risk of the linear-time user-level DP algorithm. Novel techniques and analysis are put forward which may be of independent interest.", "weaknesses": "Section 1.1 may contain more information about the intuition of the novel techniques (e.g., what may be the key reason that outlier-iterate removal is better than outlier-gradient removal?).\nContribution 2 of this paper lacks a comparison table to previous results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful feedback and your positive assessment of our work. We respond to your comments below. \n\n\n>*Section 1.1 may contain more information about the intuition of the novel techniques (e.g., what may be the key reason that outlier-iterate removal is better than outlier-gradient removal?)*  \n\nGreat suggestion. We will elaborate on the intuition behind our techniques in the final version.\n\nSince the item-level DP phased SGD algorithm [FKT20] adds noise to the iterates, removing outlier iterates is a natural approach for extending this algorithm to be user-level DP. If we instead attempt to remove outlier gradients, one issue is that large batch sizes lead to a severe restriction on the smoothness parameter. \n\n\n>*Contribution 2 of this paper lacks a comparison table to previous results.* \n\nThis is a very good suggestion. The only previous linear-time algorithm for user-level DP SCO is due to [BS23]. We compare our result against [BS23] in lines 80-93 and Remark 2.2. We will put this comparison into a second table in the final version.", "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": "QtiJEk4Rdz", "reviewer": "Reviewer_jGa8", "summary": "This paper proposes new mechanisms for private SCO with user-level DP.  Their approach extends prior work on this topic, and reduces the gradient complexity while attaining optimal excess risk.  Three algorithms are proposed (1) a linear time algorithm that pushes state of the art (but does not achieve optimal excess risk), (2) a (m n)^{9/8} time algorithm that does achieve optimal excess risk (improving over prior work which required (m n)^(3 / 2) gradient evaluation, and (3) an optimal algorithm for non-smooth losses that requires < (m n)^2 gradient computations.  Extensive theoretical results give expressions for the expected excess risk under various assumptions for each mechanism.", "questions": "* In what ways does your algorithm exploit the user-structure of the problem (the fact that each user holds m items)?\n\n* The noise multiplier seems humongous, am I missing something?  It's hard to believe this algorithm doesn't diverge --- do you have any empirical evidence (even on synthetic data satisfying all your required assumptions) to confirm / augment your theorem statements?  Note I have not checked your proofs at all.\n\nepsilon = 10\ndelta = 1e-6\nstep size = 1\nn = 10 million\nm = 100\nd = 1 billion\nL = 1\n--> C = 475\n--> T = ? >= 100\n--> tau = 400,000\n--> sigma = 250,000", "limitations": "Limitations are discussed in the appendix.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The paper improves state of the art on an important problem, reducing gradient complexity while also relaxing assumptions. \n* The theoretical results are strong, and clearly stated, presented, and discussed.\n* The work is well-motivated and the authors make a compelling story.", "weaknesses": "* One of main claims is not supported by the evidence given.  The work is motivated by \"modern ML applications, such as training LLMs...\" and it claims that \"our algorithm and result is applicable to many practical ML problems.\"  However, looking at Algorithms 1-2 it is not clear that this statement is true.  I believe modern LLMs are pretty big (> 1B parameters) and typically saturate GPU memory, and Alg 1 requires storing C different settings of those parameters to compute the concentration scores -- is that feasible?  From what I can tell, for reasonable values of n, m, epsilon, and delta, C ~ 500.  \n\n* The proposed algorithms seem quite complicated.  Is that complexity necessary?  The paper is missing a description + summarization of simpler approaches and their limitations.  E.g., what about plain-old DP-SGD?  What happens when you try applying optimal item-level DP mechanisms to the user-level setting (with appropriate modifications).  What are those modifications (I can think of a few natural ways to extend them).  It would be nice if your mechanism reduced to a known optimal item-level DP mechanism when m=1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful feedback and assessment of our work.  \n\nFirst, we would like to kindly remind you that our work focuses on understanding theoretical complexity bounds for a fundamental problem. This is both an important goal in its own right and also lays the foundation for future works focusing on practical aspects of user-level DP SCO. We did not intend to give the impression that our algorithms are ready for large-scale practical deployments yet. For example, we did not optimize for constants in our algorithms (e.g. in $\\sigma$ and $C$), since our results are stated in big-O.  \n\nWe respond to your specific comments below. \n\n>*Evidence for the claim \"our algorithm and result is applicable to many practical ML problems.\"*\n\nThank you for raising this important point. \n\nWe stand by this claim, which refers to the applicability of our theoretical result. Theoretically, our Algorithm 1 is applicable whenever $\\beta < \\sqrt{nmd\\varepsilon}$ and $n \\gtrsim \\log(n/\\delta)/\\varepsilon$. Typically, $\\varepsilon$ is a small constant in practice and $n$ is quite large so that the second condition is easily satisfied. Moreover, $d$ is often large in practice and the smoothness condition holds (e.g. for linear/logistic regression). **For such problems, our algorithm and result is (theoretically) applicable**. We will revise the wording in the final version of our paper to clarify that we are referring to **theoretical applicability** of our result/algorithm to practical ML problems, in contrast to the result/algorithm of [BS23] which does not apply theoretically to these problems.  \n\n\nThat being said, you raise a valid point about GPU memory and applicability in practice. An important direction for future research is to develop practical implementations of our algorithms that are well suited for large-scale tasks like training LLMs, e.g. by parallelizing computations and optimizing for constants to allow for smaller $C$.  \n   \n>*The work is motivated by \"modern ML applications, such as training LLMs...\"*\n\n We only mentioned LLMs in order to motivate the importance of user-level DP. The full quote reads: *“in many modern ML applications, such as training LLMs on users’ data in federated learning, each user contributes a large number of training examples [XZ24]. In such scenarios, the privacy protection that item-level DP provides for each user is insufficiently weak.”* **We believe that this claim is evidenced by [XZ24]**. We did not mean to suggest that our current algorithms are ready for training LLMs in practice yet. We apologize for any confusion. \n\n\n>*algorithms seem quite complicated. Is that complexity necessary?*\n\nGreat question. We believe that some mechanism for private outlier detection and removal is needed to obtain optimal rates for user-level DP SCO. This necessarily introduces additional complexity compared to the item-level setting, where no outlier removal is needed. That being said, we agree that finding simpler algorithms that achieve the optimal rates is an important problem for future work. We will highlight this in the conclusion of the revision.\n\n>*The paper is missing a description + summarization of simpler approaches and their limitations. E.g., what about plain-old DP-SGD? What happens when you try applying optimal item-level DP mechanisms to the user-level setting (with appropriate modifications). What are those modifications (I can think of a few natural ways to extend them)?*\n\nThank you for the nice suggestion! We will happily add such a description in the camera-ready version if our paper is accepted. \n\n**Simpler modifications of optimal item-level DP algorithms do not result in optimal user-level DP algorithms.** For example, naively applying group privacy to item-level DP-SGD yields suboptimal excess risk. Simple DP-SGD with outlier removal was essentially the algorithm of [AL24], which our algorithm improves over. Moreover, our results cannot be obtained by applying black-box item-level to user-level conversions (e.g. [Bun et al., STOC 2023]). Please let us know if you have any other simple approaches in mind. \n\n>*In what ways does your algorithm exploit the user-structure of the problem (the fact that each user holds m items)?*\n\nWe use the fact that each user holds $m$  items to add less noise than would be possible if each user only held 1 item. This is accomplished through our outlier removal procedures and by arguing that with high probability, users’ gradients (or iterates) concentrate around a ball that shrinks with $m$. \n\n>*The noise multiplier seems humongous, am I missing something? It's hard to believe this algorithm doesn't diverge…I have not checked your proofs at all.*\n\nFirst, our proofs show that **our algorithms are guaranteed to converge**. Moreover, the convergence rates and runtimes are optimal/state-of-the-art (up to constant and log factors), as we discuss in the paper. Second, **we do not optimize for constants** since this is a theoretical work concerned with asymptotic complexity bounds. Thus, it is very likely that a smaller noise multiplier can be used. We leave it for future work to implement practical versions of our algorithms with carefully optimized constants. \n\n>*Do you have any empirical evidence (even on synthetic data satisfying all your required assumptions) to confirm / augment your theorem statements?*\n\nTo reiterate, the focus of our paper is on understanding the theoretical complexity bounds for a fundamental problem, not empirical performance. We leave it for future work to implement practical versions of our algorithms and evaluate these algorithms empirically.", "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": "nfhMcF7deV", "reviewer": "Reviewer_Xb14", "summary": "This paper revisits the user-level private stochastic convex optimization (SCO) problem, where each user can possess multiple data points. The contributions of this paper are in two aspects:\n\n1. They propose a linear-time algorithm that attains the same excess risk as the prior linear-time algorithm, but with a milder assumption on the smooth parameter $\\beta$ and does not require the number of users $n$ to depend on dimension $d$, making the algorithm more applicable in practice.\n2. They propose an algorithm that achieves optimal excess risk with improved gradient complexity compared to previous work in both smooth and non-smooth settings.\n\nThe key insight behind the linear-time algorithm is to remove outlier SGD iterates instead of gradients. To achieve this, they prove a stability argument (Lemma 2.3), the utility then follows by the localization arguments in [FKT20].\n\nThe optimal algorithm is inspired by the item-level accelerated phased ERM algorithm of [KLL21], which is then applied to a user-level gradient outlier-removal procedure. The non-smooth case is done by a standard randomized smoothing technique.", "questions": "In the conclusion, it is stated that whether a linear-time algorithm with optimal risk exists for smooth losses is an open question. What about non-smooth losses? If one has a linear-time algorithm for smooth losses, does the randomized smoothing give a linear-time algorithm for non-smooth losses?", "limitations": "Successfully discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. DP SCO is a fundamental problem in private machine learning. In many applications, each user can hold more than one data point. Studying user-level DP SCO is of great importance.\n2. The proposed algorithms improve the previous algorithms in various settings, relaxing the assumptions and providing a better run time.\n3. The writing of this paper is clear.", "weaknesses": "The linear-time algorithm only has a suboptimal excess risk, while the optimal algorithm has a gradient complexity higher than linear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful feedback and positive assessment of our work. We respond to your comments below. \n\n>*In the conclusion, it is stated that whether a linear-time algorithm with optimal risk exists for smooth losses is an open question. What about non-smooth losses?*\n\nGood question. The non-smooth case is much harder, so we propose that future work should first focus on fully solving the smooth case. Even in the easier item-level setting, there are no known optimal and linear-time algorithms for the non-smooth case (in general arbitrary parameter regimes).\n\n\n>*If one has a linear-time algorithm for smooth losses, does the randomized smoothing give a linear-time algorithm for non-smooth losses?*\n\nUnfortunately, no: Randomized smoothing increases the runtime of the algorithm.", "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: The paper considers the problem of stochastic convex optimization under user-level privacy and provides efficient algorithms that achieve optimal risk without any assumptions. For non-smooth functions, prior works required (mn)^3 gradient computations and the proposed algorithms require n^{11/8} m^{5/4} computations, where n is the number of users and m is the number of samples per user. For beta-smooth functions, prior works required (mn)^{3/2} gradient computations  and proposed work reduces complexity to (mn)^{9/8} + n^{1/4} m^{5/4}. While these results advance the state of the art, reviewers raise concerns about the complexity of the algorithm and limited intuitive explanations on why this complexity is necessary.  Given the wide-audience of NeurIPS, I strongly encourage authors to add a high-level discussion in the paper to explain the need for each of the steps in the algorithm and how they came up with them.
Decision: Accept (poster)