Faster Algorithms for User-Level Private Stochastic Convex Optimization

Authors: andrew  lowy
daogao  liu
hilal  asi
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 02:58:19

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.

Main paper: 
 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, LLL + 24b]. For instance, large language models (LLMs) are vulnerable to black-box attacks that extract individual training examples [CTW + 21]. Differential privacy (DP) [DMNS06] prevents ML models from leaking their training data.The classical definition of differential privacy-item-level differential privacy [DMNS06] -is illsuited for many modern applications. Item-level DP ensures that the inclusion or exclusion of any one training example has a 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 a strong guarantee that each user's data cannot be leaked. However, 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] .Given the practical importance of user-level DP SCO, it is unsurprising that many prior works have studied this problem. The work of [LSA + 21] initiated this line of work, and provided an excess risk lower bound of Ω(1/ √ nm + √ d/(εn √ m)), 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 β-smooth losses with β < (n/√ md ∧ n 3/2 /(d √ m)), provided that n ≥ √ d/ε and m ≤ max( √ d, nε 2 / √ d).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 is large. For example, in deep learning, we often have d ≫ n and an enormous smoothness parameter β ≫ 1. Moreover, their algorithm requires mn 3/2 gradient evaluations, making it slow when the number of users n is large. 2 The work of [GKK + 23] gave another user-level DP algorithm that only requires n ≥ log(d)/ε, 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 ≥ log(md)/ε 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 β-smooth losses, their algorithm requires β • (nm) 3/2 gradient evaluations; for non-smooth losses, their algorithm requires (nm) 3 evaluations.Evidently, the runtime requirements and parameter restrictions of existing algorithms for user-level DP SCO are prohibitive in many important ML applications. Thus, an important question is:Question 1. Can we develop faster user-level DP algorithms that achieve optimal excess risk without restrictive assumptions? Contribution 1. We give a positive answer to Question 1, providing a novel algorithm that achieves optimal excess risk using max{β 1/4 (nm) 9/8 , β 1/2 n 1/4 m 5/4 } gradient computations for β-smooth loss functions, with any β < ∞ (Theorem 3.2). For non-smooth loss functions, our algorithm achieves optimal excess risk using n 11/8 m 5/4 gradient evaluations for non-smooth loss functions (Theorem 4.1). 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 n 1-o(1) ≥ log(d)/ε users. See Table 1 for a comparison of our results vs. prior works. For example, for non-smooth loss functions, our optimal algorithm is faster than the previous state-of-the-art [AL24] by a multiplicative factor of n 13/8 m 7/4 . For smooth loss functions, our optimal algorithm is faster than [AL24] by a factor of (nm) 3/8 β 3/4 (in the typical parameter regime when n 7 ≥ m).-Smooth [BS23] & [AL24] NoneOur Algorithm 3 None Non-Smooth [AL24] NoneOur Algorithm 3 (smoothed) None β β ⋅ (mn)3/2 mn 3/2 β 1/4 ⋅ (mn) 9/8 + β 1/2 n 1/4 m 5/4(mn) 3 The "holy grail" of DP SCO is a 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 are known to 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 our second contribution, we 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]. 3 Their algorithm can achieve excess risk ≈ 1/ √ nmε + √ d/( √ nmε). Unfortunately, however, their algorithm requires a very stringent assumption on the smoothness parameter β < n 3 /(md 3 ), which is unlikely to 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 < d < n. These assumptions severely limit the applicability of [BS23, Algorithm 5] in practical ML scenarios. This leads us to:Question 2. Can we develop a linear-time userlevel DP algorithm with state-of-the-art excess risk, without restrictive assumptions? Contribution 2. We answer Question 2 affirmatively in Theorem 2.1: under a very mild requirement on the smoothness parameter β < √ nmd, our novel linear-time algorithm achieves excess risk of≈ 1/ √ nmε + √ d/( √ nmε). 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 n. Thus, our algorithm has excess risk matching that of [BS23] , but is much more widely applicable.We develop novel techniques and algorithms to achieve new state-of-the-art 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 [BFTT19] , which is optimal in the item-level setting. To do so, they observed that each user i's gradient 1 m m j=1 ∇f (x, Z i,j ) lies in a ball of radius ≈ 1/ √ m around the population gradient ∇F (x) with high probability, if the data is i.i.d (Z i ∼ P m ). Consequently, if the data is i.i.d., then replacing one user Z i ∈ D by another user Z ′ i ∈ D ′ will not change the empirical gradient ∇F D (x) by too much:∥∇F D (x) -∇F D ′ (x)∥ ≲ 1/(n √ m)with high probability. Thus, one would hope for a method to privatize ∇F D (x) by adding noise that scales with 1/(n √ m)-rather than 1/nwhich would allow for optimal excess risk. [AL24] devised such a method, which was inspired by FriendlyCore [TCK + 22]. Their method privately detects and removes "outlier" user gradients, and then adds noise to the average of the "inlier" user gradients. This outlier-removal procedure ensures privacy with noise scaling with 1/(n √ m), provided n ≳ 1/ε. Moreover, when the data is i.i.d., no 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 [AL24] in novel ways.Our linear-time Algorithm 1 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. 4 The high-level idea of our algorithm is to partition the n users into C ≈ 1/ε groups, with each group containing ≈ nε users. For each group of users, we run T ≈ mnε steps of online SGD using the samples in this group and obtain the average iterate of each group: {x j } C j=1 . We then privately identify and remove the outlier iterates from {x j } C j=1 . In order to successfully do so, we need to argue that if we run online SGD independently on user Z and user Z ′ to obtain x and x′ respectively, then ∥x -x′ ∥ ≲ ηT with high probability, where η is 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 [FKT20] , we obtain our state-of-the-art linear-time result.Our second algorithm, Algorithm 3, builds on [AL24] in a different way. In Algorithm 3, 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 [BBG18] . We then develop an accelerated [GL12] user-level DP algorithm that solves a carefully chosen sequence of regularized ERM problems, and applies localization in the spirit of [KLL21, AFKT21] . An obstacle that arises when we try to extend the ERM-based localization framework to the user-level DP setting is getting a 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.We consider loss functions f : X × Z → R, where X is a convex parameter domain and Z is a data universe. Let P be an unknown data distribution and F (x) := E z∼P [f (x, z)] be the population loss function. Denote F * := min x∈X F (x). The SCO problem is min x∈X F (x). Let ∥ • ∥ denote the ℓ 2 norm. Π X (u) := argmin x∈X ∥u -x∥ 2 denotes projection onto X .. Function g : X → R is L-Lipschitz if |g(x) -g(x ′ )| ≤ L∥x -x ′ ∥ 2 for all x, x ′ ∈ X . Function g : X → R is β-smooth if g is differentiable and has β-Lipschitz gradient: ∥∇g(x) -∇g(x ′ )∥ 2 ≤ β∥x -x ′ ∥ 2 . Function g : X → R is µ-strongly convex if g(αx + (1 -α)x ′ ) ≤ αg(x) + (1 -α)g(x ′ ) -α(1-α)µ 2 ∥x -x ′ ∥ 2 for all α ∈ [0, 1] and all x, x ′ ∈ X . If µ = 0, we say g is convex. Assumption 1.1. 1. The convex set X is compact with ∥x -x ′ ∥ ≤ R for all x, x ′ ∈ X . 2. The loss function f (•, z) is L-Lipschitz and convex for all z ∈ Z.In all of the paper except for Section 4, we will also assume:Assumption 1.2. The loss function f (•, z) is β-smooth for all z ∈ Z.Denote a ∧ b := min(a, b). For functions f and g of input parameters θ, we write f ≲ g if there is an absolute constant C > 0 such that f (θ) ≤ Cg(θ) for all permissible values of θ. We use O to hide logarithmic factors. Write a ≤ poly(b) if there exists some large J > 1 for which a ≤ b J .Differential Privacy. Definition 1.3 (User-Level Differential Privacy). Let ε ≥ 0, δ ∈ [0, 1). Randomized algorithm A : Z nm → X is (ε, δ)-user-level differentially private (DP) if for any two datasets D = (Z 1 , . . . , Z n ) and D ′ = (Z ′ 1 , . . . , Z ′ n ) that differ in one user's data (say Z i ̸ = Z ′ i but Z j = Z ′ j for j ̸ = i), we have P(A(D) ∈ S) ≤ e ε P(A(D ′ ) ∈ S) + δ,for all measurable subsets S ⊂ X .Definition 1.3 prevents any adversary from learning much more about an individual's data set than if that data had not been used for training. Appendix A contains the necessary background on DP.We begin with our state-of-the-art linear-time algorithm in Section 2. In Section 3, we present our error-optimal algorithm with state-of-the-art runtime for smooth loss functions. Section 4 extends our fast optimal algorithm to non-smooth loss functions. We conclude in Section 5 with a discussion and guidance on future research directions stemming from our work.2 A state-of-the-art linear-time algorithm for user-level DP SCOIn 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 a logarithmic number of phases.In each phase i, we first re-set algorithmic parameters and draw a disjoint set of n i users D i ⊂ D (lines 4-5). We further partitionD i into C disjoint subsets {D i,j } C j=1 . For each j ∈ [C],we pool together all of the n i m samples in D i,j and run one-pass online SGD on D i,j with initial point x i-1 given to us from the previous phase. Next, in lines 10-20, we privately detect and remove "outliers" from {x i,j } C j=1 . That is, our goal is to privately select a subset S i ⊂ {x i,j } C j=1 , such that for any two points xi,j , xi,j′ ∈ S i , ∥x i,j -xi,j ′ ∥ ≤ τ i = O(η i L √ T i). This will enable us to add noise scaling with τ i in line 22, rather than with the much larger worst-case sensitivity (that scales linearly with T i ). In order to privately select such a subset S i , we first compute (and privatize) the concentration score for {x i,j } C j=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 {x i,j } C j=1 is nearly τ i -concentrated and we may proceed with outlier removal in lines 12-15. Theorem 2.1 (Privacy and utility of Algorithm 1 -Informal). Let ε ≤ 10, n 1-o(1) ≳ log(n/δ) ε , β ≤ (L/R) √ dmnε, and m ≲ poly(n). Then, Algorithm 1 is (ε, δ)-user-level DP. Further,EF (x l ) -F * ≤ LR • O 1 √ nmε + d log(1/δ) √ nε √ m .The gradient complexity of Algorithm 1 is ≤ nm. Remark 2.2 (State-of-the-art excess risk in linear time, without the restrictive assumptions). Under the assumptions that β < (Lε 3 /R) n 3 /md 3 and m ≤ d/ε 2 ≤ n, [BS23] gave a linear-time algorithm with similar excess risk to Algorithm 1. However, their assumptions are very restrictive in practice: For example, in the canonical regime n ≈ d, their assumption on β rules out essentially every (non-linear) loss function. By contrast, our result holds even if the smoothness parameter is huge (β ≈ √ 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 1 is private, we essentially argue that for any phase i, the ℓ 2 -sensitivity of xi is upper bounded by O(τ i /C) with probability at least 1 -δ/2. The argument goes roughly as follows: First, the Laplace noise added to s i (τ i ) ensures that s i (τ i ) is ε/4-user-level DP. Now, it suffices to assume s i (τ i ) ≥ 4C/5, 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 O(1/ε), we know that s i (τ i ) ≥ 4C/5 =⇒ s i (τ i ) ≥ 2C/3 with high probability by our choice of C. In this case, an argument along the lines of [AL24, Lemma 3.5] shows that xi has sensitivity bounded by O(τ i /C) with probability at least 1 -δ/2. See Appendix B for the detailed proof.To prove the excess risk bound in Algorithm 1, the key step is to show that if the data is i.i.d., then with high probability, no points are removed from {x i,j } C j=1 during the outlier-removal phase Algorithm 1: User-Level DP Phased SGD with Outlier Iterate Removal and Output Perturbation Input: Dataset D = (Z 1 , . . . , Z n ), privacy parameters (ε, δ), parameters p, q > 0, stepsize η; Set l = ⌊log 2 (n)⌋, C := 100 log(20nme ε /δ)/ε;for i = 1, • • • , l do Set n i = (1 -(1/2) q )n/2 iq , η i = η/2 pi , N i = n i /C, T i = N i m, τ i = 1000η i L √ T i log(ndm);Draw disjoint users D i of size n i from D;Divide D i into C disjoint subsets {D i,j } C j=1 , each containing |D i,j | = N i users; for j = 1, • • • , C doxi,j ← SGD(D i,j , η i , T i , x i-1 ) = average iterate of T i steps of one-pass projected SGD with data D i,j , stepsize η i , and initial point x i-1 ;end Compute the concentration score for D i :s i (τ i ) := 1 C j,j ′ ∈[C] 1(∥x i,j -xi,j ′ ∥ ≤ τ i ) Let s i (τ i ) = s i (τ i ) + Lap(20/ε); if s i (τ i ) ≥ 4C 5 then S i = ∅ ; for j = 1, • • • , C do 14Compute the score function of xi,j :h i,j = C j ′ =1 1(∥x i,j -xi,j ′ ∥ ≤ 2τ i );Add xi,j to S i with probability p i,j for p i,j =      0 h i,j < C/2 1 h i,j ≥ 2C/3 hi,j -C/2 C/6 o.w.x i ← xi + ζ i , where ζ i ∼ N (0, σ 2 i I d ) with σ i = 100τi log 2 (n/δ) εC ; end Output: x l . (i.e. |S i | = C). If |S i | = Cholds, then we can use the convergence guarantees of SGD and the localization arguments in [FKT20] to establish the excess risk guarantee. In order to prove that |S i | = C with high probability, we need the following novel stability lemma: Lemma 2.3. Assume f (•, z) is convex, L-Lipschitz, and β-smooth on X with η ≤ 1/β. Let x ← SGD(D, η, T, x 0 ) and ỹ ← SGD(D ′ , η, T, x 0 ) be two independent runs of projected SGD, where D, D ′ ∼ P N are i.i.d. Then, with probability at least 1 -ζ, we have ∥x -ỹ∥ ≲ ηL T log(dT /ζ).We prove Lemma 2.3 via induction on t, using non-expansiveness of gradient descent on smooth losses [HRS16] , subgaussian concentration bounds, and a union bound. Lemma 2.3 implies that if the data is i.i.d., then the following events hold with high probability: ∥x i,j -xi,j ′ ∥ ≤ τ i for all j, j ′ ∈ [C i ] and hence s i (τ i ) = C. Further, conditional on s i (τ i ) = C, we know that s i (τ i ) ≥ 4C/5 with high probability, so that the algorithm does not halt. Also, ∥x i,j -xi,j ′ ∥ ≤ τ i for all j, j ′ implies p i,j = 1 for all j and hence |S i | = C for all j. The detailed excess risk proof is provided in Appendix B.Challenges of getting optimal excess risk in linear time: In the item-level DP setting, there are several (nearly) linear time algorithms that achieve optimal excess risk for smooth DP SCO under mild smoothness conditions, such as snowball SGD [FKT20] , 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 outlier-detection procedure in [AL24] . Specifically, since amplification by iteration intermediate only provides DP for the last iterate x T but not the intermediate iterates x t (t < T ), the sensitivity of the concentration score function is not O(1), which impairs DP outlier-detection. A 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 1, which extends phased SGD in an alternative way: by applying outlier-detection/removal 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.3 scales polynomially with T (and we believe this dependence on T is necessary), Algorithm 1 adds excessive noise and has suboptimal excess risk. We believe that obtaining optimal risk in linear time will require a fundamentally different user-level DP mean estimation procedure that does not suffer from the instability issue.3 An optimal algorithm with ≈ (mn) 9/8 gradient complexity for smooth lossesIn this section, we provide an algorithm that achieves optimal excess risk using ≈ (mn) 9/8 stochastic gradient evaluations. Our Algorithm 3 is inspired by the item-level accelerated phased ERM algorithm of [KLL21] . It applies iterative localization [FKT20] to the user-level DP accelerated minibatch SGD Algorithm 2. Algorithm 2 is a user-level DP variation of the accelerated minibatch SGD of [GL12, GL13] .Our Algorithm 2 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) i and determine whether or not most of the gradients of users in minibatch D t i are 2τ -close to each other. If s t i ≥ ∆ i , indicating that the gradients of users in D t i are nearly 2τ -concentrated, then we proceed with outlier removal in lines 8-12. We then invoke privacy amplification by subsampling [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 ε ≤ 10, q > 0 such that n 1-q > 100 log(20nmde ε /δ) ε(1-(1/2) q ). Then, Algorithm 3 is (ε, δ)-DP.Theorem 3.2 (Utility & runtime of Algorithm 3 -Informal). Let ε ≤ 10 and δ < 1/(mn). Then, Algorithm 3 yields optimal excess risk:EF (x l ) -F * ≤ LR • O 1 √ mn + d log(1/δ) εn √ m .The gradient complexity of this algorithm is upper bounded bymn 1 + ε βR L 1/4 (mn) 1/8 ∧ ε 2 n 2 m d 1/8 + βR L n 1/4 m 5/4 ε + n 1/2 m 5/4 d 1/4 ε 1/2 .If n = d, ε = 1, and βR = L then the gradient complexity bound in Theorem 3.2 simplifies to (mn) 9/8 + n 1/4 m 5/4 . Typically, n 7 ≥ m, so that the dominant term in this bound is (mn) 9/8 . Remark 3.3 (State-of-the-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 d [BS23, GKK + 23, AL24]. Note that while the mn 3/2 gradient complexity bound of [BS23] may appear to be better than β 1/4 (nm) 9/8 in certain parameter regimes (e.g. m > n 3 or β ≫ nm), this is not the case: the result of [BS23] requires m < n and β < n/m. Remark 3.4 (Mild assumptions). Note that Theorems 3.1 and 3.2 do not require any bound on the smoothness parameter β, and only require the number of users to grow logarithmically: n 1-o(1) ≥ Ω(1/ε). Contrast this with the results of previous works (e.g. [BS23] ).Algorithm 2: User-Level DP Accelerated Minibatch SGD( F i , T i , K i , x i-1 , τ, ε, δ) Initialize x 1 i-1 ← x i-1 ; for t = 1, • • • , T i do Draw K i random users D t i = {Z t i,j } Ki j=1 from D i uniformly with replacement; Set noisy threshold ∆ i := 4Ki 5 + ξ i , where ξ i ∼ Lap 8 ε ; Let q t (Z) := 1 m z∈Z ∇f (x t i-1 , z) for user Z;Compute the concentration score of D t i :s t i (τ ) := 1 K i Z,Z ′ ∈D t i 1(∥q t (Z) -q t (Z ′ )∥ ≤ 2τ ) Let s t i (τ ) = s t i (τ i ) + v t i , where v t i ∼ Lap 16 ε ; if s t i (τ ) ≥ ∆ i then S t i = ∅; for Each User Z ∈ D t i do Set h t i (Z) = Z ′ ∈D t i 1(∥q t (Z) -q t (Z ′ )∥ ≤ 2τ ); 11 Add Z to S t i with probability p t i (Z) :=      0 h t i (Z) < K i /2 1 h t i (Z) ≥ 2K i /3 h t i (Z)-Ki/2 Ki/6 o.w. end g t i = 1 |S t i | Z∈S t i ∇ F (x t i-1 , Z); g t i = g t i + ζ t i , where ζ t i ∼ N (0, σ 2 i ) with σ i = 1000τ √ Ti log(nde ε /δ) εni ; Do 1 iteration of Accelerated Minibatch SGD (AC-SA) [GL12] on F i , using gradient estimator g t i + λ i (x t i-1 -x i-1 ) to obtain x t+1 i-1 . end else Halt; Return 0 end end Output x Ti i-1 .Algorithm 3: User-Level DP Accelerated Phased ERM with Outlier Gradient RemovalInput: Dataset D = (Z 1 , . . . , Z n ), privacy parameters (ε, δ), parameters p, q, λ > 0; Set l = ⌊log 2 (n)⌋ and τ = O(L log(ndm)/ √ m), choose any initial point x 0 ∈ X ; for i = 1, • • • , l do Set n i = (1 -(1/2) q )n/2 iq , λ i = λ • 2 pi , T i = Θ(1 + β/λ i ), K i = 500 log(n 2 i m 2 e ε /δ) 1 ε + niε √ Ti log(1/δ) ; Draw disjoint users D i of size n i from D; Let F i (x) := 1 ni Zi,j ∈Di F (x, Z i,j ) + λi 2 ∥x -x i-1 ∥ 2 , where F (x, Z i,j) is user Z i,j 's empirical loss;x i ← User-Level DP Accelerated Minibatch SGD( F i , T i , K i , x i-1 , τ, ε, δ). ; end Output x l .A challenge in proving Theorem 3.2 is getting a tight bound on the variance of the the noisy minibatch stochastic gradients g t i that are used in Algorithm 2 (lines 12-14). Conditional on S t i = D t i , it is easy to obtain a variance bound of the form E∥ gt i -∇ F i (x t i )∥ 2 ≲ dσ 2 i + L 2Ki , since we are sampling K i 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:Lemma 3.5 (Variance Bound for Algorithm 2). Let δ ≤ 1/(nm), ε ≲ 1. Denote F i (x) := 1 ni Zi,j ∈Di F (x, Z i,j ). Then, conditional on S t i = D t i for all i ∈ [l], t ∈ [T i ],we haveE∥g t i -∇ F i (x t i-1 )∥ 2 ≲ L 2 log(ndm) Km for all i ∈ [l], t ∈ [T i ],where the expectation is over both the random i.i.d. draw of D = (Z 1 , . . . , Z n ) ∼ P nm and the randomness in Algorithm 3.The difficulty in proving Lemma 3.5 comes from the fact that the iterates x t i and the data D are not independent. To overcome this difficulty, we use the stability of user-level DP [BS23] to argue that for allZ ∈ D i , ∇ F (x t i-1 , Z) is ≈ L/ √ m-close to ∇F (x t i-1) with high probability, since x t i-1 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). If f (•, z) is µ-strongly convex, then Algorithm 3 can be combined with the meta-algorithm of [FKT20, Section 5.1] to obtain optimal excess riskL 2 µ • O 1 nm + d ln(1/δ) ε 2 n 2 mwith the same gradient complexity stated in Theorem 3.2. This improves over the previous state-ofthe-art gradient complexity ≈ β(mn) 3/2 of [AL24] .4 An optimal algorithm with subquadratic gradient complexity for non-smooth lossesIn 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 [YNS12, DBW12] to approximate non-smooth f by a β-smooth f . We can then apply Algorithm 3 to f . Since convolution smoothing is by now a standard optimization technique, we defer the details and proof to Appendix D. Theorem 4.1 (Privacy and utility of smoothed Algorithm 3 for non-smooth loss -informal). Let ε ≤ 10, δ < 1/(mn), and q > 0 such that n 1-q > 100 log(20nmde ε /δ)ε(1-(1/2) q ). Then, applying Algorithm 3 to the smooth approximation of f yields optimal excess risk:EF (x l ) -F * ≤ LR • O 1 √ mn + d log(1/δ) εn √ m .The gradient complexity of this algorithm is upper bounded bymn 1 + n 3/8 m 1/4 ε 1/4 .Remark 4.2 (State-of-the-art gradient complexity). The only previous polynomial-time algorithm that can achieve optimal excess risk for non-smooth loss functions is due to [AL24] . The algorithm of [AL24] required (nm) 3 + (mn) 2 √ d gradient evaluations. Thus, the gradient complexity of the smoothed version of Algorithm 3 offers a significant improvement over the previous state-of-the-art. For example, if ε = 1, then our algorithm is faster than the previous state-of-the-art by a multiplicative factor of at least n 13/8 m 7/4 .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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: See Appendix E.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section 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 on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 F. 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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-smooth loss functions, with significantly smaller computational cost than the previous state-of-the-art. Our linear-time Algorithm 1 achieves state-of-the-art 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 (≈ (nm) 9/8 ), we are now optimistic that the answer to this question is "yes." We believe that our novel techniques will be key to the development of an 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 to approximate (ε, δ)-DP. What rates are achievable under the stronger notion of pure ε-user-level DP? Third, it would be useful to develop fast and optimal algorithms that are tailored to federated learning environments [MRTZ18, GLZW24] , where only a 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.Algorithm 4: AboveThreshold Input: Dataset D = (Z 1 , . . . , Z n ), threshold ∆ ∈ R, privacy parameter ε, sequence of T queries q 1 , • • • , q T : Z n → R, each with ℓ 1 -sensitivity 1; Let ∆ := ∆ + Lap( 2 ε ); for t = 1 to T do Receive a new query q t : Z n → R ; Sample ν i ∼ Lap( 4 ε ); if q t (D) + ν i ≥ ∆if E[e ⟨v,X-EX⟩ ] ≤ e ∥v∥ 2 ζ 2 /2 for any v ∈ R d . Random vector X ∈ R d is Norm-SubGaussian with parameter ζ (nSG(ζ)) if P[∥X -EX∥ ≥ t] ≤ 2e -t 22ζ 2 for all t > 0. Theorem A.11 (Hoeffding-type inequality for norm-subGaussian,[JNG + 19]). Let X 1 , • • • , X k ∈ R d be random vectors, and let F i = σ(x 1 , •, x i ) for i ∈ [k] be the corresponding filtration. Suppose for each i ∈ [k], X i | F i-1 is zero-mean nSG(ζ i ).Then, there exists an absolute constant c > 0, for any γ > 0,P   i∈[k] X i ≥ c log(d/γ) i∈[k] ζ 2 i   ≤ γ.Lemma A.12 ([JNG + 19]). There exists an absolute constant c, such that if X is nSG(ζ), then for any fixed unit vector v ∈ R d , ⟨v, X⟩ is cζ norm-SubGaussian. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This is a theoretical paper without experiments. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? 
 
 Appendix: Theorem B.1 (Formal statement of Theorem 2.1). Suppose n 1-q ≥ (100/(1-1/2 q )) log(n/δ)/ε for some small q > 0, and m ≤ n J for some large J > 0. Choose p = J + 3/2 and η = R/(L √ dmnε). in Algorithm 1. Then, Algorithm 1 is (ε, δ)-user-level DP and achieves excess riskEF (x l ) -F * ≤ LR • O 1 √ nmε + d log(1/δ) √ nε √ m , using nm gradient evaluations, provided β ≤ (L/R) √ dmnε.The gradient complexity is clear by inspection of the algorithm: The number of stochastic gradients computed during the algorithm isl i=1 T i C = l i=1 N i mC = l i=1 n i m ≤ nm.Next, we will prove the privacy statement in Theorem B.1. The following lemma ensures that if the Laplace noise added in Algorithm 1 is sufficiently small and outlier detection succeeds, then the sensitivity of xi is O(τ i /C) with high probability.Lemma B.2. [AL24, Slight modification of Lemma 3.5] Let i ∈ [l] and ζ > 0. Suppose D i and D ′ i differ in the data of one user and we are in phase i of Algorithm 1. Let E i be the event that the Laplace noise added to the concentration score s i (τ i ) for D i has absolute value less than 2C/15 and define E ′ i similarly for data D ′ i . Denote a i := 1( s i (τ i ) ≥ 4C/5) and a ′ i := 1( s ′ i (τ i ) ≥ 4C/5), where s i (τ i ) and s ′ i (τ i ) are the noisy concentration scores that we get when running phase i of Algorithm 1 on neighboring D i and D ′ i , respectively. Then, conditional on a i = a ′ i and E i E ′ i , there is a coupling Γ i over xi and x′ i such that for (y i , y ′ i ) drawn from Γ i , we have∥y i -y ′ i ∥ ≲ τ i log(1/ζ) C with probability at least 1 -ζ.With Lemma B.2 in hand, we proceed to prove that Algorithm 1 is (ε, δ)-user-level DP:Proof of Theorem B.1 -Privacy. Privacy: Since the {D i } l i=1 are disjoint, parallel composition of DP [McS09] implies that it suffices to prove that phase i is (ε, δ)-user-level-DP for any fixed i and fixed x i-1 . To that end, let D and D ′ be adjacent datasets differing in the data of one user, say Z i,1 ̸ = Z ′ i,1 without loss of generality. We will show that the outputs of phase i when run on D and D ′ , x i := x i (D) and x ′ i := x i (D ′ ) respectively, are (ε, δ)-indistinguishable. Let E i be the event that the Laplace noise added in phase i (for data set D) has absolute value less than 2C/15 and define E ′ i analogously for data set D ′ . Note that E i and E ′ i are independent andP(E i , E ′ i ) ≥ 1 -δ/10e ε . Denote ζ := δ/10e ε . Let a i := 1( s i (τ i ) ≥ 4C/5) and a ′ i := 1( s ′ i (τ i ) ≥ 4C/5), where s i (τ i ) and s ′ i (τ i ) are the noisy concentration scores that we get when running phase i of Algorithm 1 on neighboring D i and D ′ i , respectively. By Lemma B.2 and our choice of C, we know that, conditional on E i E ′ i and on a i = a ′ i , there exists a coupling Γ over (x i , x′ i ) such that for (y i , y ′ i ) drawn from Γ, we haveEQUATIONwith probability at least 1 -ζ.Note that the sensitivity of s i is less than or equal to 2. Thus, by the privacy guarantees of the Laplace mechanism (Lemma A.4), we haveEQUATIONfor any b ∈ {0, 1}. Further, this impliesEQUATIONBy the bound (1), the privacy guarantee of the Gaussian mechanism (Lemma A.6), our choice of σ i , and independence of the Laplace and Gaussian noises that we add in Algorithm 1, we haveEQUATIONfor any event O ⊂ X .Moreover, since the algorithm halts and returns x i = 0 if a i = 0, we know thatEQUATIONfor any event O ⊂ X . Therefore,P(x i ∈ O) = P(x i ∈ O | E i )P(E i ) + P(x i ∈ O | E c i )P(E c i ) ≤ P(x i ∈ O | E i , a i = 1)P(E i , a i = 1) + P(x i ∈ O | E i , a i = 0)P(E i , a i = 0) + ζ (i) ≤ e ε/4 P(x ′ i ∈ O | E ′ i , a ′ i = 1)e ε/4 [P(E ′ i , a ′ i = 1) + ζ] + P(x ′ i ∈ O | E ′ i , a ′ i = 0)e ε/4 [P(E ′ i , a ′ i = 0) + ζ] + ζ ≤ e ε/2 P(x ′ i ∈ O, E ′ i ) + ζ 2e ε/2 + 1 ≤ e ε P(x ′ i ∈ O) + δ, where (i) follows from inequalities (3), (4), and (5). Thus, x i is (ε, δ)-user-level-DP. This completes the privacy proof.Next, we turn to the excess risk proof. The following lemma is immediate from [FKT20, Lemma 4.5]: Lemma B.3. Let η i ≤ 1/β. Then, for any y ∈ X and all i, j, we haveE[F (x i,j ) -F (y)] ≤ E∥y -x i-1 ∥ 2 η i T i + η i L 2 .The next novel lemma is crucial in our analysis: Note that this implies the lemma. We proceed by induction. The base case, when t = 0, is trivially true since x 0 = y 0 . For the inductive hypothesis, suppose there is an absolute constant c > 0 such that with probability at least 1 -tζ/T , we haveLemma B.4 (Re-statement of Lemma 2.3). Assume f (•, z) is convex, L-Lipschitz,∥x i -y i ∥ ≤ cηL i • log(dT /ζ) + 2ηL, ∀i ≤ t.Then, for the inductive step, we have by non-expansiveness of projection onto convex sets, thatEQUATIONwhere (i) follows from the non-expansive property of gradient descent on smooth convex function for η ≤ 1/β [HRS16] .Define a t := -2η⟨x t -η∇F (x t )-(y t -η∇F (y t )), g t -∇F (x t )-g ′ t +∇F (y t )⟩. By Inequality (6) and the inductive hypothesis, we obtain∥x t+1 -y t+1 ∥ 2 ≤ 4η 2 L 2 t + t i=1 a t .t i=1 a i . Note that E[a i | a 1 , • • • , a i-1 ] = 0,and by Lemma A.12 we know there is a constant c > 0 such that a i is nSG(cηL∥x i -y i ∥) for all i. Hence by Theorem A.11, we knowP   t i=1 a i ≥ cηL log(dT /γ) i≤t ∥x i -y i ∥ 2   ≤ 1 -ζ/T.Conditional on the event that ∥x i -y i ∥ ≤ c log(dT /ζ)ηL √ i for all i ≤ t (which happens with probability 1 -tζ/T by the inductive hypothesis), we knowP t i=1 a i ≥ c 2 (t + 1)L 2 η 2 log(dT /ζ) ∥x i -y i ∥ ≤ c log(dT /ζ)ηL √ i, ∀i ≤ t ≤ 1 -ζ/T.Hence we knowP ∥x t+1 -y t+1 ∥ 2 ≥ c 2 log(dT /ζ)η 2 L 2 (t + 1) ∥x i -y i ∥ ≤ c log(dT /ζ)ηL √ i, ∀i ≤ t ≤ 1 -ζ/T.Combining ∥x i,j -xi,j ′ ∥ ≤ τ i for all i ∈ [l], j, j ′ ∈ [C]with probability at least 1 -1/nm. Thus, s i (τ i ) = C with probability at least 1 -1/nm. Now, conditional on s i (τ i ) = C, we have s i (τ i ) ≥ 4C/5 for all i with probability at least 1 -1/nm by Laplace concentration and a union bound. Moroever, if ∥x i,j -xi,j ′ ∥ ≤ τ i for all j, j ′ , then p i,j = 1 for all j and hence there are no outliers:S i = {x i,j } j∈[C]. By a union bound, we conclude that S i = {x i,j } j∈[C] and hence xi = 1 Si Di,j ∈Si xi,j for all i with probability at least ≥ 1 -3/nm. By the law of total expectation and Lipschitz continuity, it suffices to condition on this high probability good event that xi = 1 C C j=1 xi,j for all i: the total expected excess risk can only be larger than the conditional excess risk by an additive factor of at most 3LR/nm.Si Di,j ∈Si xi,j , Lemma B.3 and Jensen's inequality impliesEQUATIONNext, let x * 0 := x * = argmin x∈X F (x), and writeE[F (x l ) -F * ] = l i=1 E[F (x * i ) -F (x * i-1 )] + E[F (x l ) -F (x * l )] ≲ R 2 ηT 1 + ηL 2 + l i=2 η i-1 L 2 d + η i L 2 + L 2 √ dη l T l ≲ R 2 ηT 1 + dηL 2 + L 2 √ dη l T l .Plugging in the prescribed algorithmic parameters completes the excess risk proof.Theorem C.1 (Re-statement of Theorem 3.1). Let ε ≤ 10, q > 0 such that n 1-q > 100 log(20nmdeε /δ) ε(1-(1/2) q ). Then, Algorithm 3 is (ε, δ)-DP.We require the following lemma, which is a direct consequence of [AL24, Lemma 3.5]:Lemma C.2. Consider Algorithm 2. Let D ′ i and D ′ i be two data sets that differ in the data of one user. LetE i = {|v t i | ≤ K i /20 ∀t ∈ [T i ] ∩ |ξ i | ≤ K i /20}. Define E ′ i similarly for independent draws of random Laplace noise:E ′ i = {|(v t i ) ′ | ≤ K i /20 ∀t ∈ [T i ] ∩ |ξ ′ i | ≤ K i /20}. Let a t i = 1( s t i (D i ) ≥ 4K i /5) and b t i = 1( s t i (D ′ i ) ≥ 4K i /5) denote the concentration scores in iteration t. Then, conditional on E i E ′ i and conditional on a t i = b t i , there exists a coupling Γ t i over g t i (D i ) and g t i (D ′ i ) such that for (h, h ′ ) drawn from Γ i , we have∥h -h ′ ∥ ≲ τ log(1/ζ) K i with probability at least 1 -ζ.Proof of Theorem C.1. Note that our assumption on n 1-q being sufficiently large implies thatn i ≳ log(nmd/δ) ε for all i ∈ [l]. By parallel composition [McS09] and post-processing, it suffices to show that { g t i } Ti t=1 satisfies (ε, δ)-user-level DP for any i ∈ [l]. To that end, fix any i ∈ [l] and let D and D ′ be adjacent datasets that differ in the data of one user such that D i ̸ = D ′ i . We will show that { g t i (D)} Ti t=1 and { g t i (D ′ )} Ti t=1 are (ε, δ)-indistinguishable, which will imply that Algorithm 3 is (ε, δ)-user-level DP.Let E i = {|v t i | ≤ K i /20 ∀t ∈ [T i ] ∩ |ξ i | ≤ K i /20}. Define E ′ i similarly for independent draws of random Laplace noise:E ′ i = {|(v t i ) ′ | ≤ K i /20 ∀t ∈ [T i ] ∩ |ξ ′ i | ≤ K i /20}. Our choice of K i ≥ 500 log(nmde ε /δ) εensures thatP E i E ′ i ≥ 1 -δ/(10e ε), by Laplace concentration and a union bound. Let ζ := δ/(10T i e ε ).Let a t i = 1( s t i (D) ≥ 4K i /5) and b t i = 1( s t i (D ′ ) ≥ 4K i /5). Note that if a t i = b t i = 0, then g t i (D) = 0 = g t i (D ′ ).Conditional on the good event that a t i = b t i for all t and conditional on E i E ′ i , we can bound the ℓ 2 -sensitivity of g t i with high probability, via Lemma C.2 and a union bound:∥g t i (D) -g t i (D ′ )∥ ≲ τ log(1/ζ) K i ≲ τ log(nme ε /δ) K i (8)for all t ∈ [T i ] with probability at least 1 -T i ζ = 1 -δ/(10e ε ).Note that { s t i (D)} Ti t=1 and { s t i (D ′ )} are ε/2-indistinguishable by the DP guarantees of AboveThreshold in Lemma A.9, since the sensitivity of s t i is upper bounded by 2. Therefore,P({a t i } Ti t=1 = v, E i ) ≤ e ε/2 P({b t i } Ti t=1 = v, E ′ i ) + ζ (9)for any v ∈ {0, 1} Ti . Now, by the sensitivity bound (8), the privacy guarantee of the Gaussian mechanism (Lemma A.6) and our choice of σ i , the advanced composition theorem (Lemma A.7), and privacy amplification by subsampling (Lemma A.8), we haveEQUATION) for any event O ⊂ X . Here we also used the fact thatK i ≥ niε √ Ti .For short-hand, write {a t i } Ti t=1 = 1 if a t i = 1 for all t ∈ [T i ] and {a t i } Ti t=1 = 0 if a t i = 0 for some t ∈ [T i ]; similarly for b t i . Then since the algorithm halts and returns { g t i (D)} Ti t=1 = 0 if {a t i } Ti t=1 = 0, we know thatEQUATIONfor any event O ⊂ X .Combining the above pieces, we haveP({ g t i (D)} Ti t=1 ∈ O) = P({ g t i (D)} Ti t=1 ∈ O | E i )P(E i ) + P({ g t i (D)} Ti t=1 ∈ O | E c i )P(E c i ) ≤ P({ g t i (D)} Ti t=1 ∈ O | E i , {a t i } Ti t=1 = 1)P(E i , {a t i } Ti t=1 = 1) + P({ g t i (D)} Ti t=1 ∈ O | E i , {a t i } Ti t=1 = 0)P(E i , {a t i } Ti t=1 = 0) + 2T ζ (i) ≤ e ε/2 P({ g t i (D ′ )} Ti t=1 ∈ O | E ′ i , {b t i } Ti t=1 = 1)e ε/4 P(E ′ i , {b t i } Ti t=1 = 1) + T ζ + P({ g t i (D ′ )} Ti t=1 ∈ O | E ′ i , {b t i } Ti t=1 = 0)e ε/2 P(E ′ i , {b t i } Ti t=1 = 0) + T ζ + T ζ ≤ e ε/2 P({ g t i (D ′ )} Ti t=1 ∈ O, E ′ i ) + 4T ζ 2e ε/2 + 1 ≤ e ε P({ g t i (D ′ )} Ti t=1 ∈ O) + δ,where (i) follows from inequalities (9), (10), and (11). Thus, { g t i (D)} Ti t=1 is (ε, δ)-user-level-DP, which implies the result.Theorem C.3 (Formal statement of Theorem 3.2). Let ε ≤ 10 and δ < 1/(mn). Then, choosingλ = L R 1 √ nm + √ d εn √m and p ≥ 3q + 2.5 + log n ( √ m) in Algorithm 3 yields optimal excess risk:EF (x l ) -F * ≤ LR • O 1 √ mn + d log(1/δ) εn √ m .The gradient complexity of this algorithm is upper bounded bymn 1 + ε βR L 1/4 (mn) 1/8 ∧ ε 2 n 2 m d 1/8 + βR L n 1/4 m 5/4 ε + n 1/2 m 5/4 d 1/4 ε 1/2 .We will need the following bound on the excess empirical risk of accelerated (noisy) SGD for the proof of Theorem C.3: Lemma C.4. [GL13, Proposition 7] Let x T be computed by T steps of (multi-stage) Accelerated Minibatch SGD on λ-strongly convex, β-smooth F with unbiased stochastic gradient estimator g t such that E∥g t -∇ F (x t )∥ 2 ≤ V 2 for all t ∈ [T ]. Then,E[ F (x T ) -min x∈X F (x)] ≲ [ F (x 0 ) -min x∈X F (x)] exp -T λ β + V 2 λT .Remark C.5. As noted in Lemma C.4, we technically need to call a multi-stage implementation of Algorithm 2 in line 7 of Algorithm 3 (as in [GL13] ) to 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, we obtain a bound on the variance of the noisy stochastic minibatch gradient estimator g t i in Algorithm 2, which can then be plugged in for V 2 in Lemma C.4.Lemma C.6 (Re-statement of Lemma 3.5). Let δ ≤ 1/(nm), ε ≲ 1. Denote F i (x) := 1 ni Zi,j ∈Di F (x, Z i,j ). Then, conditional on S t i = D t i for all i ∈ [l], t ∈ [T i ],we haveE∥g t i -∇ F i (x t i-1 )∥ 2 ≲ L 2 log(ndm) Km for all i ∈ [l], t ∈ [T i ],where the expectation is over both the random i.i.d. draw of D = (Z 1 , . . . , Z n ) ∼ P nm and the randomness in Algorithm 3.Proof. By [LJCJ17, Lemma A.1], we know that, conditional on the draw of the data D i and for fixed x t i-1 , the variance of the minibatch estimator of the gradient of the empirical loss isEQUATION)Recall F i (x) := 1 nim z∈Di f (x, z) is the empirical loss of D i . Now, for any fixed x and any Z ∈ D i , Hoeffding's inequality implies that∥∇ F (x, Z) -∇F (x)∥ ≤ τ = O L log(nd/γ) √ mwith probability at least 1 -γ, where F (x, Z) := 1 m z∈Z f (x, z) is user Z's empirical loss. Thus, by the stability of user-level DP (see [BS23, Theorem 3.4]), for any i ∈ [l], t ∈ [t], we have that∥∇ F (x t i-1 , Z) -∇F (x t i-1 )∥ ≤ τ (13)for all Z ∈ D with probability at least 1 -γ ′ = n(e 2ε γ + δ), since x t i-1 is (ε, δ)-user-level DP. To make γ ′ ≲ 1/m, we choose γ = 1/mn and use the assumptions that ε ≲ 1 and δ ≤ 1/mn. Thus, for any fixed i, t we have∥∇ F (x t i-1 , Z) -∇F (x t i-1 )∥ ≲ L log(n 2 md) √ mfor all Z ∈ D with probability at least 1 -1/m, which impliesE∥∇ F (x t i-1 , Z) -∇F (x t i-1 )∥ 2 ≲ L 2 log(nmd) m .This also impliesE∥∇ F D (x t i-1 ) -∇F (x t i-1 )∥ 2 ≲ L 2 log(nmd) m ,by Jensen's inequality, where F D (x) is the empirical loss over the entire data set D.Plugging the above bounds into (12) then yieldsE∥g t i -∇ F i (x t i-1 )∥ 2 ≲ L 2 log(ndm) Km = E D∼P nm ,{i l } K l=1 ∼Unif([n])    1 Km K l=1 m j=1 ∇f (x t i-1 , z t i l ,j ) -∇ F D (x t i-1 ) 2    ≲ 1(K = n) K • L 2 log 2 (nmd) m ,completing the proof.We are now ready to prove Theorem C.3:Proof of Theorem C.3. Excess risk: Note that the assumption in the theorem ensures that K i ≤ n i for all i. By similar arguments to those used in [AL24, Proposition 3.7], we will show that with high probability ≥ 1 -2/(nm), for all i ∈ [l], t ∈ [T i ], S t i = D t i and hence g t i is an unbiased estimator of ∇ F D t i (x t i ). To show this, first note that for any γ > 0 and any fixed x,∥∇ F (x, Z j ) -∇F (x)∥ ≤ L log(nd/γ) √ mwith probability at least 1 -γ/K i by Hoeffding's inequality (see [AL24, Lemma 4.3]). Next, we invoke the stability of differential privacy to show that for all t ∈ [T i ], (q t (Z t i,1 ), . . . , q t (Z t i,Ki )) is τ -concentrated (i.e. there exists q * ∈ R d such that ∥q t (Z t i,j -q * ∥ ≤ τ ) with probability at least 1 -T i (e 2ε γ + δ) (see [BS23, Theorem 4.3] ). By a union bound and the choice of γ = 1/[(nm) 5/4 log(ndm)e 2ε ], we have that (q t (Z t i,1 ), . . . , q t (Z t i,Ki )) is τ -concentrated for all i ∈ [l], t ∈ [T i ] with probability at least 1 -1/nm. Now, τ -concentration of (q t (Z t i,1 ), . . . , q t (Z t i,Ki )) implies s t i (τ ) = K i . Further, s t i (τ ) = K i implies s t i (τ ) ≥ 4K i /5 with probability at least 1 -ζ if K i ≥ 500 log(nm/ζ), by Laplace concentration and a union bound. Next, note that τ -concentration of (q t (Z t i,1 ), . . . , q t (Z t i,Ki )) implies p t i (Z t i,j ) = 1 for all j ∈ [K i ] and S t i = D t i . Thus, S t i = D t i for all i, t with probability at least 1 -1/nm. Setting ζ = 1/nm and using a union bound shows that with probability at least 1 -2/nm, we have S t i = D t i and g t i = ∇ F D t i (x t i ) for all i, t. Now, Lemma C.4 implies that, if the outlier-removal procedure in Algorithm 2 leads to an unbiased gradient estimator g t i (line 12) for all tEQUATIONwhereV 2 i = max t∈[ti] E∥ g t i -∇ F i (x t i )∥ 2 ≲ dσ 2 i + log(ndm)L 2(unconditionally, after taking expectation over the random draw of D ∼ P nm , by Lemma 3.5). We have shown that the event GOOD :={g t i = ∇ F D t i (x t i ) for all i ∈ [l], t ∈ [T i ]}occurs with probability at least 1 -2/nm. We will condition on 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/ √ nm.By stability of regularized ERM (see [SSSSS09] ), we haveEQUATIONfor all i, where x * i := argmin x F i (x). By strong convexity and ( 14), we haveEQUATIONThus,EQUATIONNow, letting x * 0 := x * = argmin x∈X F (x) and hiding logarithmic factors, we have:E[F (x l ) -F * ] = l i=1 E[F (x * i ) -F (x * i-1 )] + E[F (x l ) -F (x * l )] ≲ L 2 λ 1 n 1 m + λ 1 R 2 + l i=2 E L 2 λ i n i m + λ i ∥x i-1 -x * i-1 ∥ 2 + LE∥x l -x * l ∥ ≲ L 2 λnm + λR 2 + l i=2 L 2 λ i n i m + λ i dτ 2 log(1/δ) λ 2 i-1 ε 2 n 2 i-1 + L 2 λ 2 i-1 T i-1 K i-1 m + L √ dτ T l log(1/δ) λ l εn l ,where the first inequality used (15) and Lipschitz continuity, the second inequality used (17).Note that K i T i ≥ n i . Further, our choice of sufficiently large p makes λ l large enough thatL √ dτ √ T l log(1/δ) λ l εn l ≤ LR √ d εn √m . Therefore, upper bounding the sum by it's corresponding geometric series gives usEQUATION)Plugging in λ completes the excess risk proof.The gradient complexity isl i=1 T i K i m.Plugging in the prescribed choices of T i and K i completes the proof.For any loss function f (•, z), we define the convolution function f r (•, z) := f (•, z) * n r where n r is the uniform density in the ℓ 2 ball of radius r centered at the origin in R d . Specifically, n r (y) = Γ( d 2 +1) π d 2 r d for ∥y∥ ≤ r, and n r (y) = 0 otherwise. For simplicity, we omit the dependence on z in the following Lemma: Lemma D.1 (Randomized Smoothing, [YNS12, DBW12] ). For any r > 0, let X r := X + {x ∈ R d : ∥x∥ ≤ r}. If f is convex and L-Lipschitz over X r , then the convolution function f r has the following properties:• f r (x) ≤ f (x) ≤ f r (x) + Lr, for all x ∈ X . • f r is L-Lipschitz and convex. • f r is L √ d r -smooth. • For random variables y ∼ n r , we have E y [∇f (x + y)] = ∇f r (x).The following lemma can be easily seen from the proofs of Theorems 3.1 and 3.2: Lemma D.2 (Privacy and utility of Algorithm 3 for generalK i , T i ). Let ε ≤ 10, q > 0 such that n 1-q > 100 log(20nmde ε /δ) ε(1-(1/2) q ) . • If K i ≳ niε √ Ti + log(nmde ε /δ) ε , then Algorithm 3 is (ε, δ)-user-level DP. • If T i K i ≥ n i and T i ≳ (1 + β/λ i ) log(ndm)for all i, then Algorithm 3 achieves optimal excess risk. Theorem D.3 (Formal statement of Theorem 4.1). Let ε ≤ 10, δ < 1/(mn), and q > 0 such thatn 1-q > 100 log(20nmde ε /δ) ε(1-(1/2) q ). Suppose that for any z, f (, z) is convex and L-Lipschitz over X r forX r := X + {x ∈ R d : ∥x∥ ≤ r} where r = √ d εn √ m R.Then, running Algorithm 3 with functions {f r (x; z)} z∈D yields optimal excess risk:EF (x l ) -F * ≤ LR • O 1 √ mn + d log(1/δ) εn √ m .The gradient complexity of this algorithm is upper bounded by mn 1 + n 3/8 m 1/4 ε 1/4 .Proof. By Lemma D.1 and our choice of r, we have |f r (x, z)-f (x, z)| ≤ Lr = O(LR √ d εn √ m ). Set λ = 1 √ mn . Then we know that EF (x l ) -F * ≤E [F r (x l ) -F * r ] + O(LR √ d εn √ m ). Further, F r is β-smooth for β ≤ L R εn √ m. Set T i = (1 + β/λ i ) log(ndm) = 1 + n 3/4 i m 1/2 ε 1/2 log(ndm) and K i = niε √ Ti + log(nmde ε /δ) ε. Then Lemma D.2 implies that Algorithm 3 is (ε, δ) user-level DP, and yields the excess risk boundEF r (x l ) -F * r ≤ LR • Õ 1 √ mn + d log(1/δ) εn √ m ,as desired. The number of gradient evaluations isl i=1 T i K i m ≲ mn 1 + n 3/8 m 1/4 ε 1/4 .This completes the proof.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-convex 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 [LR22, ALT24] .Our algorithms are also faster than the previous state-of-the-art, including a linear-time Algorithm 1 with state-of-the-art excess risk. However, our error-optimal accelerated Algorithm 3 runs in superlinear time. Thus, in certain applications where a linear-time algorithm is needed due to strict computational constraints, Algorithm 1 should be used instead.Our work on differentially private optimization for machine learning advances the field of privacypreserving 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 it is essential to consider both potential positive and negative impacts.Positive Impacts:1. Enhanced Privacy Protections: By incorporating differential privacy into machine learning models, we can 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 as a valuable resource for future studies and fostering an environment of continuous improvement in privacy practices.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 as less accurate medical diagnoses or flawed economic forecasts. For example, an overly optimistic prediction of environmental impacts due to lower accuracy could be misused to weaken environmental protections.While recognizing the potential for misuse and the trade-offs involved, we firmly believe that the advancement and dissemination of differentially private machine learning algorithms offer a 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.In the introduction, whenever ε does not appear, we are assuming ε = 1 to ease readability. For runtime bounds, we also assume n = d to further simplify.It is trivial to achieve excess risk ≈ 1/ √ nm + √ d/(εn) with (ε, δ)-user-level, e.g. by applying group privacy to an optimal item-level DP algorithm such as[FKT20]. The error due to privacy in this bound does not decrease with m.The reason that this innovation is necessary is discussed in the last paragraph of Section 2. 


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

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

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

3.In item-level case, optimal rates with linear time has been achieved in

Feldman et al. Private stochastic convex optimization: optimal rates in linear time. STOC 2020.

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


Minor issue: The statements of three algorithms are not with the same font. The algorithm 2 is different with algorithm 1 and 3.

In 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.
questions: questions: 1. Can the authors provide more intuitive explanations of the design of algorithms, especially the second one? 

2. I wonder what will be the risk bound for strong convex loss functions. The case with strong convex loss function has been discussed in 

Kamath et al. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. ICML 2022.

This holds for item-level case. I wonder if one can derive the user-level counterparts.

3. Can the authors please provide more discussions on why it is hard to achieve linear time with optimal risk?
limitations: limitations: The authors have addressed limitations well in the conclusion.
paper_summary: paper_summary: This paper considers stochastic convex optimization under user-level differential privacy.

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

Algorithm 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.
strength_weakness: strength_weakness: 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?).
Contribution 2 of this paper lacks a comparison table to previous results.
questions: questions: The questions are asked in the 'Weaknesses' part.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.  

* 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.
questions: questions: * In what ways does your algorithm exploit the user-structure of the problem (the fact that each user holds m items)?

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

epsilon = 10
delta = 1e-6
step size = 1
n = 10 million
m = 100
d = 1 billion
L = 1
--> C = 475
--> T = ? >= 100
--> tau = 400,000
--> sigma = 250,000
limitations: limitations: Limitations are discussed in the appendix.
paper_summary: paper_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:

1. 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.
2. They propose an algorithm that achieves optimal excess risk with improved gradient complexity compared to previous work in both smooth and non-smooth settings.

The 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].

The 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.
strength_weakness: strength_weakness: The linear-time algorithm only has a suboptimal excess risk, while the optimal algorithm has a gradient complexity higher than linear.
questions: 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: limitations: Successfully discussed.

Comments: title: Reply
Further response
Note to all Reviewers
comment: Thank you for your response! You have answered my questions thoroughly.
First, we would like to thank the reviewer for replying to our responses in a timely fashion and engaging in this important discussion to clarify the limitations of prior works compared to our work. We respond to your comments below. 

>*The requirement should be $n \gtrsim \sqrt{d}/\epsilon$ instead of $d/\epsilon$*

Apologies for the confusion. We meant to write that $n \gtrsim d/\epsilon$ users are needed if one uses the two concurrent papers that the reviewer mentioned [1] and [2]: This can be seen by inspecting Theorem 1.2 in [1] and the discussion that follows the statement of the theorem, and by inspecting Eq. (3) and Theorems 2&3 in [2]. 

You are right that BS23 "only" needs $n \gtrsim \sqrt{d}/\epsilon$, which we mentioned in the second paragraph of our above response and in line 49 of our paper. Note that this **polynomial dependence on $d$ still leads to a strict requirement on the number of users in comparison to our work, which only requires the number of users to depend logarithmically on $d$**.

>*your discussion with reviewer jGa8 about outlier removal is not fully convincing to me*

Please let us know if there are any specific points in this discussion that you have doubts or questions about. We would be happy to clarify further why we believe that simpler approaches are unable to obtain our SOTA results (without further innovations), and why/how our outlier-removal technique is a powerful way to overcome the technical barriers faced in prior works (e.g. BS23).

>*I agree that your method have a much weaker assumption on the smoothness parameter...and that this new method is novel and interesting* 

Thank you for acknowledging these important aspects of our work. We re-iterate that our significant improvements in **runtime** and in the **number of users** needed (logarithmic instead of polynomial dependence on $d$) are also crucial components of our SOTA results.
Thanks for your further response.

**(i) the requirement on the number of users size is strict: $n\gtrsim d/\epsilon$**

This is inaccurate. The requirement should be $n\gtrsim \sqrt{d}/\epsilon$ instead of $d/\epsilon$. 

I agree that your method have a much weaker assumption on the smoothness $\beta$. The risk bound does not depend explicitly on $\beta$. In this aspect, you have solved part of my concerns. However, I still agree with the reviewer jGa8. While I agree that this new method is novel and interesting, this paper needs to be further polished before acceptance. In particular, your discussion with reviewer jGa8 about outlier removal is not fully convincing to me. Therefore, I would still like to keep my score.
>*A natural solution is to use these mean estimation algorithms to estimate the gradients, and then perform updates for $T$ steps….Could you please discuss what will the bound be if we just use these user-level mean estimation algorithms to estimate gradients?* 


**The suggested approach of using a user-level DP mean estimator to estimate the gradient in each iteration was taken by [BS23]**. The result of [BS23] is discussed in our paper: see e.g. row 1 of Fig. 1, lines 47-53, and remarks 3.3 & 3.4. Recall that although the [BS23] approach can obtain optimal excess risk for certain sufficiently smooth functions, it has the following limitations: (i) **the requirement on the number of users size is strict: $n \gtrsim d/\epsilon$**; (ii) **strict restriction on the smoothness parameter (see row 1 of Fig. 1) and does not work for non-smooth functions**. By contrast, *our results only require $n \gtrsim \log(d)/\epsilon$, our smoothness requirement is much milder than [BS23], and we get optimal excess risk even for non-smooth* functions. 


*Technical reasons for limitations (i) and (ii)*: Existing near-optimal $(\epsilon, \delta)$- user-level-DP mean estimators require $n \gtrsim d/\epsilon$ (in the two recent papers the reviewer suggests) or $n\gtrsim \sqrt{d}/\epsilon$ [BS23]. However, if we use full-batch and run DP-GD for $T$ steps, then advanced composition implies that we need $n \gtrsim\sqrt{T d}/\epsilon$. Here, $T$ needs to depend on $n$ to get optimal excess risk, which leads to severe restrictions on the smoothness parameter. In particular, their approach cannot handle non-smooth functions (assuming $\epsilon < \sqrt{d}$) since $T \sim n^2$ would be needed in their algorithm to get optimal risk for such functions. 


To address the above two limitations, [AL24] designed a new mean estimation sub-procedure based on incorporating outlier removal with the AboveThreshold procedure. Our algorithms build on the techniques of [AL24], as we discussed in Section 1.1. 


We will include this more detailed discussion/comparison of the [BS23]-type approach and the technical reasons for its limitations in the final version. 


>*I do not understand "one can not assume the data is i.i.d when bounding sensitivity". As far as I know, existing research on user-level DP usually assume that all samples are i.i.d.*


We meant that **one cannot *use* the i.i.d. assumption in the privacy analysis**, because (user-level) DP is a strong *worst-case, distribution-free* requirement that must hold for all pairs of adjacent databases, not just i.i.d. databases.   

We thank the reviewer again for giving us an opportunity to further clarify these points.
Acknowledging response.  I think the paper could be significantly stronger by thinking more carefully about these things and incorporating this discussion into the paper.  I am keeping my original rating as is since I think it would be a net positive for the scientific community for this work to be polished a bit more.  I am reducing the soundness rating since I think there are some improvements you can make to the scientific methodology that came up in the discussion.  However, there are some technical merits to the paper, and if other reviewers are happy to accept it as-is, I would not object to acceptance.
Thank you for your response.
I have seen your discussion with reviewer jGa8. Your reply is

"Notice that your proposed approach would fail to satisfy user-level DP without incorporating some outlier removal step or adding excessive noise (leading to suboptimal risk). This is because one cannot assume the data is i.i.d. when bounding sensitivity/proving privacy. That is why we need to use outlier removal in our algorithms."

This is also not convincing to me. The following two papers discuss the solution of mean estimation under user-level DP:

[1] Agarwal, Sushant, et al. "Private Mean Estimation with Person-Level Differential Privacy." arXiv:2405.20405.

[2] Zhao, Puning, et al. "A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy." arXiv:2405.13453.

Both two papers calculate the user-wise mean first, which reduces the sensitivity to $1/\sqrt{m}$.  User-level DP requirements are satisfied in both papers. Therefore, I can not agree with your statement that the solution proposed by reviewer jGa8 fails to satisfy user-level DP. Moreover, you have mentioned multiple times that simple extensions of item-level methods do not benefit from large $m$. Actually, both methods in [1] and [2] benefit significantly from large $m$. The mean estimation problem is somewhat different from optimization problem. However, a natural solution is to use these mean estimation algorithms to estimate the gradients, and then perform updates for $T$ steps. To bound the risk of optimization, some tricks may be necessary  (such as bounding the generalization gap). Could you please discuss what will the bound be if we just use these user-level mean estimation algorithms to estimate gradients?

Also, I do not understand "one can not assume the data is i.i.d when bounding sensitivity". As far as I know, existing research on user-level DP usually assume that all samples are i.i.d. 

It is reasonable not to cite these two papers for now because they are both posted after the NeurIPS submission deadline. However, due to these concerns that are also raised by reviewer jGa8, currently I can not increase my overall rating.
First, **there are known trivial approaches that obtain excess risk $1/\sqrt{nm}+\sqrt{d}/n\epsilon$**: e.g. reducing to item-level DP SCO via group privacy or by averaging each user’s gradients. This bound $1/\sqrt{nm}+\sqrt{d}/n\epsilon$ is the same as the excess risk bound that the reviewer claimed their simple approach obtains. Note that while these results are simple to obtain, **they do not benefit significantly from large $m$** because *the privacy term $\sqrt{d}/n\epsilon$ does not shrink as $m$ increases*. Thus, an important challenge in user-level DP SCO is getting risk bounds that decay with large $m$. Getting such bounds is non-trivial and has been the topic of a long line of work (involving complicated algorithms) that we discuss in the Introduction. By contrast, if $m$ is small, then one can simply apply a trivial approach without suffering too much. **For these reasons, the large $m$ regime is more interesting** theoretically. 

That being said, we clearly acknowledge that the trivial baseline rate $1/\sqrt{nm}+\sqrt{d}/n\epsilon$ can be better than our linear-time bound in Theorem 2.1 when $n > m$. However, it is not clear to us whether one can obtain the trivial bound both in linear time and with a mild smoothness assumption like the one in our Theorem 2.1. Moreover, we reiterate that **this trivial bound is suboptimal, since it is bigger than the optimal bound given in our Theorem 3.2**. We will add this comparison/discussion in the final revision. Thank you again for this valuable suggestion.

Finally, we want to emphasize again that **we do not see any way for simpler approaches to obtain any of our main results** (Theorems 2.1, 3.2, or 4.1). We believe that developing simpler optimal algorithms for user-level DP SCO is an interesting open question and invite the reviewer to make progress on this problem. We do note that several of the reviewer’s ideas were already explored in early suboptimal works on user-level DP SCO (e.g. LSA+21 and BS23) and therefore will probably not result in optimal rates.

We thank the reviewer once again for their feedback.
* Reducing user-level DP to item-level DP, similar to your proposal, is trivial, but does not benefit significantly from larger m.
>* This may be true, although you have not convinced me yet, but either way this discussion is missing in this paper.  You need to make a convincing case of this in the paper, and such changes would be large enough to warrant a fresh review in my opinion.  

*  Indeed, the regime is more interesting theoretically for user-level DP SCO.
>* One of the things I look for based on the reviewer guidelines is "are the claims made supported by evidence."  What evidence do you have to support this statement?  What does it even mean to be "more interesting theoretically"?

* runtime of your proposed **suboptimal** algorithm
>* I don't believe you adequetely showed this was suboptimal, other than saying (without evidence) that "m > n" is the more interesting regime.  At minimum, you should qualify your claims of optimality with the caveat "under some conditions".  

* would need to be at least **quadratic in n**
>* Again, you are making these claims without evidence, and as far as I can tell is simply not true either.  BFTT sets the batch sizes to n sqrt(epsilon / 4T) and runs for T <= n/8 iterations.  This means that it requires sqrt(epsilon * n) / m passes over the dataset.  If m > n as you purport, this is actually sub-linear, not quadratic.
>* Second, BFTT14 is 10 years old -- of course there are more recent papers that achieve the same rates with much less runtime.   I did not suggest running BFTT with a small T, but just used that as one of the simplest example algorithm that achieves the optimal rates.  I believe the modifications I proposed are compatible with any optimal item-level DP mechanisms in principle, including the linear-time ones.

* Finally, if you try to modify FKT20 with your proposed simple approach, you obtain a suboptimal linear-time algorithm that suffers from a very severe smoothness restriction.
>* This very well may be true, I am not familiar enough with the prior results to confirm or deny.  But given the flaws in reasoning I've identified above, I will not trust the statement **without evidence**.  

* **your proposed approach would fail to satisfy user-level DP**
>* I didn't actually propose a specific mechanism here, and maybe it is the case that the only way to get 1/sqrt(m) rates is with outlier removal, but again, you are making this claim without providing evidence.  Can you prove there is no other way to do this?  In principle you should be able to run any linear-time algorithm for item-level DP, and replace the step that does item-level DP mean estimation of the minibatch gradient with a step that does user-level DP mean estimation of the minibatch gradient.  This would lead to a valid algorithm, that leverages and connects to prior work already done on this problem of user-level DP mean estimation.
Thank you very much again for your feedback and for engaging in this productive discussion with us. We hope that our responses clarified your concerns, so that you can re-evaluate your score. If you have any remaining questions, comments, or suggestions for us, please do let us know.
Thanks for your response.
Thank you very much for your timely reply. 

As a general comment, we emphasize that there is a long line of work on the user-level DP-SCO problem, which tries to get optimal rates via complicated algorithms. Reducing user-level DP to item-level DP, similar to your proposal, is trivial, but does not benefit significantly from larger $m$. The challenge of user-level DP SCO is designing algorithms that benefit (in all of the error terms) from large $m$, as our algorithms do. Indeed, the regime $m > n$ is more interesting theoretically for user-level DP SCO. We will discuss this and the other naive baselines (e.g. group privacy) in the final version. 

We respond to your specific comments below. 

>*it is better than your utility guarantee for Alg 1 as far as I can tell, assuming n > m...*

First, note that the **runtime of your proposed *suboptimal* algorithm** (using BFTT19) **would need to be at least *quadratic* in $n$** in order to achieve the suboptimal risk bound stated in your above comment, even for smooth losses (after optimizing for $T$). This runtime is worse than any of the algorithms we provide in our paper. In particular, **our Algorithm 3 achieves *optimal* excess risk with runtime that is *subquadratic* in $n$**, scaling with $n^{9/8}$. Moreover, **our Algorithm 1 is linear-time**. Furthermore, a linear-time implementation of your proposed BFTT19-based algorithm (by simply choosing $T$ to be small) would result in a fairly strict restriction on the smoothness parameter ($\beta \lesssim \sqrt{m}$) in order to achieve inferior excess risk of $\approx 1/\sqrt{m} + \sqrt{d}/n\varepsilon$. 

Finally, if you try to modify FKT20 with your proposed simple approach, you obtain a suboptimal linear-time algorithm that suffers from a very severe smoothness restriction. 


All that being said, we agree that simplicity is a virtue and will gladly add discussion of your proposed simple approach to the final version. Thank you very much for your interesting suggestion.


>*Under your I.i.d. assumption, the variance of the average of m samples would be 1/m smaller. I believe you should be able to leverage this to add sqrt(m) less noise and recover the rates you get for Alg 3, with a much simpler approach.*


Notice that **your proposed approach would fail to satisfy user-level DP** without incorporating some outlier removal step or adding excessive noise (leading to suboptimal risk). This is because *one cannot assume the data is i.i.d. when bounding sensitivity/proving privacy*. That is why we need to use outlier removal in our algorithms. 

We really appreciate you engaging with us in this productive discussion and believe that implementing your suggestions will strengthen the final version. Please let us know if you have any further questions or comments.
Thank you very much for your response and for giving us an opportunity to further clarify this important point. 


First, to be clear, we do require $\varepsilon$ to be bounded by some constant (e.g. $\varepsilon \leq 100$) in the current algorithm/analysis. Thank you for catching this. We will add this assumption to our statement of Theorem 2.1 in the revision. We believe that this assumption is very reasonable, since the privacy guarantees degrade rapidly as $\varepsilon$ grows. 

Next, we respond to your specific question: 

>*in the paper, data are divided into $1/ϵ$  groups. So if ϵ>1, how to divide it?*


In fact, we don’t divide the data into $1/\varepsilon$ groups exactly, but rather we divide the data into $C$ groups, where $C$ is defined in line 2 of Algorithm 1. Note that $C \geq 2$ for any $\varepsilon > 0$. 


The reason that we choose $C$ the way we do is in order to ensure that the Laplace noise added in line 10 of Algorithm 1 is much smaller than $C$ with high probability. This ensures that the outlier-removal procedure succeeds with high probability.
* Agreed that what I proposed does not match your guarantee for Alg 3.  But it is better than your utility guarantee for Alg 1 as far as I can tell, assuming n > m, since sqrt(m n) < n.  I think it is reasonable to assume n >> m.  

* Another simple way I believe you could get a sqrt(m) dependence in term 1 would be to use an existing optimal item-level DP mechanism, and each time you sample a user, you compute the average gradient over all of their examples.  Under your I.i.d. assumption, the variance of the average of m samples would be 1/m smaller.  I believe you should be able to leverage this to add sqrt(m) less noise and recover the rates you get for Alg 3, with a much simpler approach.  

I will revisit my evaluation and consider updating my score after your next response.
Thanks for your reply. Regarding $\epsilon$, in the paper, data are divided into $1/\epsilon$ groups. So if $\epsilon>1$, how to divide it? Do you mean that data are actually divided into $\lceil 1/\epsilon\rceil$ groups? If so, my intuitive feeling is that there should be a phase transition at $\epsilon = 1$. Your bound does not have any phase transition, which looks a bit strange for me. Please correct me if I am wrong.
Thank you very much for acknowledging the theoretical nature of our paper and for giving us an opportunity to further clarify the drawbacks of other simple approaches.

**The user-level DP modification of DP-SGD that you propose does not achieve the SOTA bounds that our algorithms achieve:** In particular, your *proposed algorithm cannot achieve the optimal excess risk of our Algorithm 3*. Moreover, a one-pass (linear-time) implementation of your proposed algorithm *does not achieve the SOTA excess risk in linear time of our Algorithm 1*: Note that each of the error terms in our Theorems 2.1 and 3.2 decrease with $m$, whereas the private optimization error term in your proposed algorithm would not depend on $m$.

*Why the private optimization error term in your proposed algorithm does not decrease with $m$ (in contrast to our algorithms):* The variance of the additive noise in your proposed user-level DP algorithm does not decrease with $m$, since no outlier-detection/removal procedures are used and hence the worst-case user-level sensitivity of gradients in your algorithm is $\Theta(1)$ . By contrast, our algorithms add less noise scaling with $\tau \approx 1/\sqrt{m}$ by incorporating outlier-detection/removal. This is what enables our algorithms to offer superior performance compared to simple approaches that do not involve outlier-removal. By the same reasoning, **applying your simple modification to FKT20 would also not result in algorithms with the SOTA guarantees that our novel algorithms provide**.

We sincerely hope that our response clarifies your concerns so that you can increase your score. Please let us know if any other questions remain.
Acknowledging as a paper that is 100% theoretical, I think it is fair to judge the work on its theoretical rather than practical merits.

However, it still seems this approach is a bit more complicated than it ought to be.  For example, taking Alg 1 from [BFTT14](https://arxiv.org/pdf/1908.09970) as a starting point, we could modify it so that in step 5 each batch only contains a single example per user.  Accounting wise, this user-level privacy properties of this algorithm on a dataset with n users is identical to the example-level privacy properties of Alg 1 on a dataset with n examples.  As far as I can tell, Thm 3.2 still goes through, with the sqrt(d log(1/delta)) / (epsilon n) term remaining the same, as sigma depends on the number of users only.  The second term 1/sqrt(n) I believe would change to 1/sqrt(n m).  This bound seems comparable to Thm 2.1.

While [BFTT14] was not linear time, I believe a similar modification could be made to an optimal linear-time algorithm like [FKT20](https://arxiv.org/pdf/2005.04763), with some tweaking to hyper-parameters.
Thank you very much for your thoughtful assessments of our work and your constructive feedback! 

We are very happy that *all of the reviewers* appreciated the **strength of our results**, which improve over the state-of-the-art on an “**important problem**” (*Reviewers JSLp, jGa8 and Xb14*). We are also glad that you enjoyed our **writing/presentation**, noting that our “results are strong, and clearly stated, presented, and discussed,” our work is “well-motivated” and makes a “compelling story” (Reviewer jGa8), and that “the writing of this paper is clear” (*Reviewer Xb14*). Additionally, we are pleased that you appreciated our “**Novel techniques and analysis**...which may be of independent interest” (*Reviewer W7xk*). 

We respond to each of your comments below. We look forward to receiving your responses to our rebuttals and engaging in a productive discussion.