- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies stochastic convex optimization (SCO) under user-level -differential privacy, where each of the users holds samples. Unlike previous work that assumes uniformly bounded gradients, this paper only imposes second- and -th moment bounds, denoted by and , on the per-sample Lipschitz parameter. This allows the gradients to be unbounded and potentially heavy-tailed.
The proposed algorithm combines user-level DP-SGD with a localization procedure. At each step, user gradients are clipped around a center obtained through FriendlyCore, followed by Gaussian noise addition. The authors establish nearly matching upper and lower bounds on the excess risk, up to logarithmic factors, of order , with a user requirement of . The paper also derives tight results for user-level mean estimation under norm-moment assumptions and removes the additional user requirement in Agarwal et al. (2025) under directional moment assumptions. The paper is entirely theoretical and does not include experiments.
Critical strengths
-
The paper relaxes the uniform-Lipschitz assumption while maintaining approximate DP and nearly optimal utility guarantees. Most existing results on user-level DP-SCO assume that every per-sample gradient is uniformly bounded by some constant . On the other hand, previous work on heavy-tailed DP-SCO has mainly focused on item-level privacy. This paper addresses the gap between these two settings. Under moment assumptions alone, it establishes an excess-risk bound consisting of three interpretable components: the non-private statistical error, the user-level privacy cost, and the additional error caused by heavy-tailed observations.
This is a meaningful extension because the resulting rate can be substantially smaller than bounds based on the worst-case Lipschitz constant when gradients are occasionally very large but typically much smaller. The matching lower bound also shows that the rate is essentially optimal, up to logarithmic factors.
I also find the mean-estimation results interesting in their own right. They do not require an a priori bound on the location of the population mean and improve the user requirement compared with Zhao et al., "A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy" (NeurIPS 2024).
-
The theoretical analysis is careful, and the main arguments appear correct. I examined the main proofs in detail and did not find any major mathematical errors. There are a few relatively minor issues that could be clarified. The privacy proofs for Algorithm 2 and the fused oracle refer to Asi and Liu, although the constants used here are different. The SCO theorem statements contain a factor, whereas the proof appears to establish . Also, the location-free initialization argument is only briefly sketched. I do not think these issues undermine the main results, but they should be addressed in a revision.
Critical weaknesses
-
The practical applicability is unclear, and the lack of experiments is a significant limitation. Although the theoretical results are interesting, I have several concerns about how the proposed algorithms would work in practice.
-
The moment parameters must be known in advance. The algorithm requires , , and as public inputs, and these quantities directly determine several important tuning parameters. For example, the FriendlyCore radius is set to , the clipping radius depends on and , and the Gaussian noise scale is proportional to .
In practice, these moment parameters are usually unknown. Estimating them from private data would itself require additional privacy budget, but the paper does not provide a private estimation procedure or analyze its cost. I am also concerned about sensitivity to misspecification. Underestimating may cause the concentration test to fail, leading the algorithm to abort and output zero, while overestimating it would increase the clipping radius and noise level. Some discussion or analysis of this issue would make the proposed approach more useful.
-
There are no experiments. I understand that the paper is primarily theoretical, but I believe even a small set of numerical experiments would considerably strengthen it. In particular, it would be useful to see whether the moment-based approach actually outperforms standard user-level DP-SGD with a carefully tuned clipping norm.
For example, the authors could consider user-level mean estimation and linear or logistic regression with heavy-tailed observations generated from Pareto or Student- distributions. They could report MSE, excess loss, or classification accuracy as functions of , , and , comparing against standard user-level DP-SGD and a non-private baseline. An experiment with misspecified and would also be particularly informative.
-
-
The novelty is partly based on combining existing techniques, and some of the claims could be more carefully qualified. The main contribution is the extension to the heavy-tailed user-level setting, but much of the upper-bound machinery builds on existing methods. In particular, the proposed approach uses ideas closely related to:
- Asi and Liu, "User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates" (AISTATS 2024), which develops user-level DP-SGD using AboveThreshold and FriendlyCore.
- Asi et al., "Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions" (NeurIPS 2024), which develops population localization for heavy-tailed private optimization.
- Tsfadia et al., "FriendlyCore: Practical Differentially Private Aggregation" (ICML 2022), which introduces the underlying FriendlyCore procedure.
The clipping-and-noise approach around a coarse center is also closely related to existing private mean-estimation techniques. I think the paper should be clearer about which components are genuinely new and which are adaptations of previous methods.
-
The lower-bound technique is not entirely new. The authors describe randomly generated outliers as a new idea, but similar random-outlier constructions have already appeared in the literature, including:
- Narayanan, "Better and Simpler Lower Bounds for Differentially Private Statistical Estimation" (arXiv 2023).
- Kamath et al., "New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma" (NeurIPS 2022).
Neither paper appears to be cited. The authors should discuss these connections and explain what is different about their lower-bound construction.
Questions for authors
-
How should practitioners choose , , and when these quantities are unknown? Is it possible to estimate them privately, and what additional privacy or statistical cost would this introduce? I would also like to know how sensitive the algorithm is to misspecification of these parameters.
-
Could the authors include some numerical experiments with heavy-tailed user data, such as mean estimation or linear/logistic regression? Comparisons with standard user-level DP-SGD using a tuned clipping threshold would help demonstrate the practical benefits of the proposed approach. It would be particularly useful to report performance as a function of , , and .
-
Is the proposed fused two-stage construction necessary for achieving the claimed rate? How would it compare with the original FriendlyCore approach or the algorithm of Asi and Liu when the filtering radius is chosen to be of order ?
6 comments
Response to Reviewer wjrr (2/2): Algorithmic and Lower-Bound Contributions
I think the paper should be clearer about which components are genuinely new and which are adaptations of previous methods.
Our contributions include new algorithmic constructions and privacy/utility analyses. FriendlyCore, AboveThreshold, and population localization are existing tools; the new ingredients are:
-
Norm-moment mean estimation: Our two-stage estimator addresses FriendlyCore’s filtering bias. Its analysis shows that even a coarse, noisy clipping center permits sharp bias bounds by exploiting the concentration of user averages via the Fuk–Nagaev inequality (lines 161–171).
-
SCO: Our adaptive fused estimator keeps clipping centers noiseless and internal, avoiding the additional center noise incurred by repeatedly applying our mean estimator. Proving privacy requires controlling how changing one user affects both the center and the full clipped average. A separate DP-stability analysis controls clipping bias at adaptive iterates despite reusing users (lines 186–194 and 399–425).
-
Directional-moment mean estimation: We develop a refinement analysis that relaxes Agarwal et al.’s per-round accuracy requirement. We choose the radius using a public bound on the current center error and prove convergence without their additional user threshold (lines 471–475; Lemmas G.3–G.4).
We will make these distinctions and the obstacles each new ingredient overcomes more explicit.
Is the proposed fused two-stage construction necessary for achieving the claimed rate? How would it compare with the original FriendlyCore approach or the algorithm of Asi and Liu when the filtering radius is chosen to be of order ?
Choosing radius in FriendlyCore or Asi-Liu fails to achieve optimal rates. This is because FriendlyCore can discard rare user averages whose contribution to the mean is significant. Our two-stage algorithm overcomes this obstacle by using FriendlyCore only to obtain a coarse center, then clipping all user averages in a fresh group around that center and adding Gaussian noise to their average, with the clipping radius chosen to balance bias and privacy noise (lines 161–171).
For SCO, repeatedly privatizing the centers increases their noise, which can worsen clipping bias; enlarging the clipping radius instead increases gradient noise. Our novel fused estimator overcomes these obstacles and achieves the optimal rate.
We do not claim that every optimal algorithm must use two stages.
similar random-outlier constructions have already appeared in the literature…The authors should discuss these connections and explain what is different about their lower-bound construction.
We agree that random-outlier constructions themselves are not new. We will revise our wording to make that clear and cite Narayanan (2023) and Kamath, Mouzakis & Singhal (2022).
Our technical contribution here is the sharp joint dependence on both moment scales in order to get tight lower bounds: we scale rare-outlier instances to satisfy both constraints and combine them with a Gaussian lower bound for whole user blocks. SCO additionally requires raw gradient-moment bounds. We will clarify these constructions and their relationship to prior methods.
Thank you for the detailed response. It addresses my concerns about novelty and the connection to existing lower-bound constructions. However, several other issues are left to the promised revisions, including the full privacy proofs and improved logarithmic factors. Since no revised manuscript has been uploaded, I cannot verify these changes. For now, I will keep my original score.
Response to Reviewer wjrr (1/2): Assumptions and Theoretical Scope
Thank you for your careful reading and assessment of our results. We address your comments below; our rebuttal is split into two comments due to character limits.
We will make the privacy calibration explicit and expand the initialization argument. Appendix D indeed yields Λ6; Λ8 is conservative. We will tighten the statements accordingly.
We will add details in the revision.
Our algorithms require public upper bounds on G2 and Gk, not exact moment values. Overestimating these parameters is safe and only weakens the utility bound quantitatively (G2↦G2, Gk↦Gk). Underestimating them may invalidate the accuracy guarantee. Privacy remains valid under these misspecifications.
Private moment estimation is possible under stronger assumptions (e.g., Kothari et al., 2022), but we do not know how to remove the known-moment assumption in our setting while preserving optimal rates. Adapting to unbounded gradient moments without prior scale information is nontrivial. Developing parameter-free heavy-tailed DP-SCO is an important direction for future work. We will mention this in the Conclusion.
Like many accepted ICLR papers, our work is about understanding the fundamental complexities of an important problem, and we hope our paper will be judged on those terms. Our contribution is purely theoretical: a minimax characterization of three fundamental problems under user-level DP with heavy tails. Matching upper and lower bounds establish our stated objective: characterizing minimax optimal rates. We make no claim of empirical superiority over tuned DP-SGD. The suggested experiments concern practical performance, which we leave to future work. We therefore ask that the absence of experiments be assessed against our theoretical objective. The ICLR reviewer guidelines likewise distinguish theoretical and empirical objectives and ask whether the evidence supports the claims made.