Faster Algorithms for User-Level Private Stochastic Convex Optimization

Thank you very much for your thoughtful feedback and positive assessment of our work. We respond to your comments below.

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?

Good question. The non-smooth case is much harder, so we propose that future work should first focus on fully solving the smooth case. Even in the easier item-level setting, there are no known optimal and linear-time algorithms for the non-smooth case (in general arbitrary parameter regimes).

If one has a linear-time algorithm for smooth losses, does the randomized smoothing give a linear-time algorithm for non-smooth losses?

Unfortunately, no: Randomized smoothing increases the runtime of the algorithm.

Thank you very much for your thoughtful feedback and assessment of our work.

First, we would like to kindly remind you that our work focuses on understanding theoretical complexity bounds for a fundamental problem. This is both an important goal in its own right and also lays the foundation for future works focusing on practical aspects of user-level DP SCO. We did not intend to give the impression that our algorithms are ready for large-scale practical deployments yet. For example, we did not optimize for constants in our algorithms (e.g. in $\sigma$ and $C$), since our results are stated in big-O.

We respond to your specific comments below.

Evidence for the claim "our algorithm and result is applicable to many practical ML problems."

Thank you for raising this important point.

We stand by this claim, which refers to the applicability of our theoretical result. Theoretically, our Algorithm 1 is applicable whenever $\beta < \sqrt{nmd\varepsilon}$ and $n \gtrsim \log(n/\delta)/\varepsilon$. Typically, $\varepsilon$ is a small constant in practice and $n$ is quite large so that the second condition is easily satisfied. Moreover, $d$ is often large in practice and the smoothness condition holds (e.g. for linear/logistic regression). For such problems, our algorithm and result is (theoretically) applicable. We will revise the wording in the final version of our paper to clarify that we are referring to theoretical applicability of our result/algorithm to practical ML problems, in contrast to the result/algorithm of [BS23] which does not apply theoretically to these problems.

That being said, you raise a valid point about GPU memory and applicability in practice. An important direction for future research is to develop practical implementations of our algorithms that are well suited for large-scale tasks like training LLMs, e.g. by parallelizing computations and optimizing for constants to allow for smaller $C$.

The work is motivated by "modern ML applications, such as training LLMs..."

We only mentioned LLMs in order to motivate the importance of user-level DP. The full quote reads: “in many modern ML applications, such as training LLMs on users’ data in federated learning, each user contributes a large number of training examples [XZ24]. In such scenarios, the privacy protection that item-level DP provides for each user is insufficiently weak.” We believe that this claim is evidenced by [XZ24]. We did not mean to suggest that our current algorithms are ready for training LLMs in practice yet. We apologize for any confusion.

algorithms seem quite complicated. Is that complexity necessary?

Great question. We believe that some mechanism for private outlier detection and removal is needed to obtain optimal rates for user-level DP SCO. This necessarily introduces additional complexity compared to the item-level setting, where no outlier removal is needed. That being said, we agree that finding simpler algorithms that achieve the optimal rates is an important problem for future work. We will highlight this in the conclusion of the revision.

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)?

Thank you for the nice suggestion! We will happily add such a description in the camera-ready version if our paper is accepted.

Simpler modifications of optimal item-level DP algorithms do not result in optimal user-level DP algorithms. For example, naively applying group privacy to item-level DP-SGD yields suboptimal excess risk. Simple DP-SGD with outlier removal was essentially the algorithm of [AL24], which our algorithm improves over. Moreover, our results cannot be obtained by applying black-box item-level to user-level conversions (e.g. [Bun et al., STOC 2023]). Please let us know if you have any other simple approaches in mind.

In what ways does your algorithm exploit the user-structure of the problem (the fact that each user holds m items)?

We use the fact that each user holds $m$ items to add less noise than would be possible if each user only held 1 item. This is accomplished through our outlier removal procedures and by arguing that with high probability, users’ gradients (or iterates) concentrate around a ball that shrinks with $m$.

The noise multiplier seems humongous, am I missing something? It's hard to believe this algorithm doesn't diverge…I have not checked your proofs at all.

First, our proofs show that our algorithms are guaranteed to converge. Moreover, the convergence rates and runtimes are optimal/state-of-the-art (up to constant and log factors), as we discuss in the paper. Second, we do not optimize for constants since this is a theoretical work concerned with asymptotic complexity bounds. Thus, it is very likely that a smaller noise multiplier can be used. We leave it for future work to implement practical versions of our algorithms with carefully optimized constants.

Do you have any empirical evidence (even on synthetic data satisfying all your required assumptions) to confirm / augment your theorem statements?

To reiterate, the focus of our paper is on understanding the theoretical complexity bounds for a fundamental problem, not empirical performance. We leave it for future work to implement practical versions of our algorithms and evaluate these algorithms empirically.

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.

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

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.

Thank you very much for your thoughtful feedback and your positive assessment of our work. We respond to your comments below.

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?)

Great suggestion. We will elaborate on the intuition behind our techniques in the final version.

Since the item-level DP phased SGD algorithm [FKT20] adds noise to the iterates, removing outlier iterates is a natural approach for extending this algorithm to be user-level DP. If we instead attempt to remove outlier gradients, one issue is that large batch sizes lead to a severe restriction on the smoothness parameter.

Contribution 2 of this paper lacks a comparison table to previous results.

This is a very good suggestion. The only previous linear-time algorithm for user-level DP SCO is due to [BS23]. We compare our result against [BS23] in lines 80-93 and Remark 2.2. We will put this comparison into a second table in the final version.

Thank you very much for your thoughtful feedback and your positive assessment of our work. We respond to your comments below.

Main ideas of the second algorithm (Section 3 in the paper)

Our second algorithm is inspired by the item-level accelerated phased ERM algorithm of [KLL21]. Their algorithm runs in $\log_2 (n)$ phases. In each phase $i$, a disjoint batch of $n_i$ samples is used to define a regularized empirical loss function, $\hat{F}_i(x)$. The main ideas of the algorithm are:

• A noisy DP variation of accelerated SGD is used to efficiently find an approximate DP minimizer $x_i$ of $\hat{F}_i(x)$. This approximate minimizer $x_i$ is then used as the initial point in phase $i+1$.

• By stability of regularized ERM, $x_i$ is also an approximate minimizer of the underlying population loss function $F$.

• Iterative localization: As $i$ increases and $x_i$ gets closer to $x^* = argmin_{x} F(x)$ , we increase the regularization parameter (geometrically) to prevent $x_i$ from moving too far away from $x_{i-1}$ and hence from $x^*$. We also shrink $n_i$ geometrically.

Our algorithm is a user-level DP variation of the algorithm described above: Our Algorithm 2 uses outlier-detection and outlier-removal procedures to get a low-variance noisy user-level DP estimate of the gradient (with sensitivity scaling with $\tau \approx 1/\sqrt{m}$) in each iteration. This noisy user-level DP gradient is then used to take a step of accelerated SGD. Algorithm 3 uses Algorithm 2 as a subroutine to get a stable, user-level DP approximate solution of a regularized ERM problem in each phase, and applies iterative localization.

Please see Section 1.1 and lines 219-225 for a more detailed description of our algorithmic techniques.

it seems that this paper requires $\varepsilon <1$, since it divides users into $1/\varepsilon$ groups…I feel that the bound with $\varepsilon >1$ may not be optimal. Please correct me if it is wrong.

Good question. In fact, we do not require $\varepsilon <1$.

For Algorithm 1, we do not necessarily need $\varepsilon < 1$: it suffices that $\varepsilon < 50 \log(20 n m e^{\varepsilon}/\delta)$, so that $C \geq 2$. This condition is not practically restrictive.

Algorithm 3 is also optimal for $\varepsilon > 1$: This algorithm does not divide users into groups that depend on $\varepsilon$.

More explanations on why achieving linear time with optimal risk is hard for user-level cases…why the methods in Feldman et al. can not be simply extended to user-level case?

Excellent question! Note that even obtaining user-level DP algorithms with polynomial runtime was challenging and only recently solved by the work of Asi & Liu (2023).

In the item-level DP setting, Feldman et al. give two optimal linear-time algorithms: snowball SGD and phased SGD.

It is not at all clear how to extend snowball SGD into an optimal linear-time user-level DP algorithm.

Therefore, we aimed to extend their phased SGD algorithm into a user-level DP algorithm with our Algorithm 1. The key challenge in obtaining optimal user-level DP excess risk with this algorithm is controlling the user-level sensitivity of the iterates of one-pass SGD. In the item-level case, the sensitivity of the iterates is $O(\eta L)$ [Feldman et al., Lemma 4.3], independent of the number of iterations $T$. However, in the user-level case, the sensitivity is $O(\eta L \sqrt{T})$ (our Lemma 2.3), and we believe this bound is tight. Hence the additive Gaussian noise that is needed to privatize the iterates is too large to obtain the optimal rate in the phased SGD framework. Thus, a fundamentally different algorithmic framework that leverages Lemma 2.3 in a more effective way may be needed to obtain the optimal rate in linear time.

A second challenge in designing user-level DP variations of phased SGD is instability of the outlier-detection scheme: If the initial point $x_{i-1}$ changes by a small amount and we do outlier-detection, then the output can change greatly. Moreover, outlier detection seems to be necessary for any optimal user-level DP algorithm. Thus, another direction for future work could be to develop a new, more stable outlier detection method.

We will add a discussion of these challenges and potential ways to overcome them in the final version of the paper.

My feeling is that using something like two-stage approach (such as Levy et al. NeurIPS 2021), the item-level methods can be converted to user-level ones with optimal rate.

First, recall that the approach of Levy et al. does not obtain optimal rates. Moreover, their two-stage approach is similar to our outlier removal procedure. Their approach suffers from similar instability as our outlier removal approach. Thus, we do not see any way for their approach to allow for improvements over our algorithms. Please let us know if you have any ideas for how to leverage Levy et al. that we might be missing.

What will be the risk bound for strong convex loss functions?

Great question! The risk bounds for $\mu$-strongly convex loss functions will essentially be the square of the convex risk bound (but with the scaling factor $LR$ replaced by $L^2/\mu$). This follows from a reduction in [FKT20]. In particular, Algorithm 3 can easily be converted into an optimal algorithm for strongly convex functions with state-of-the-art runtime. We will comment on this in the revision.

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.

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.