acceptodds
Under review as a conference paper at ICLR 2027

Optimal User-Level Private Stochastic Convex Optimization and Mean Estimation with Heavy Tails

Abstract

We study stochastic convex optimization with heavy-tailed stochastic gradients under -user-level differential privacy, which protects each user's entire collection of samples. Instead of assuming a uniformly bounded Lipschitz constant, we only assume bounds on the second- and -th moments of the random sample Lipschitz parameters. This allows for unbounded, heavy-tailed stochastic gradient distributions and can lead to sharper excess risk bounds. We characterize the minimax optimal excess population risk up to logarithmic factors. Our algorithm achieves the optimal rate with only users. As a byproduct of our algorithmic developments, we obtain tight bounds for user-level private mean estimation under norm-moment assumptions, improving over the guarantees of Esfandiari et al. (2022) and Zhao et al. (2024). Finally, for mean estimation under the directional-moment assumption of Agarwal et al. (2025), we close their remaining approximate-DP gap by removing the additional user requirement and attaining the optimal sample complexity up to logarithmic factors.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, stochastic convex optimization, mean estimation, heavy tailed data, user-level privacy

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_wjrrOpenReview ↗
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 (ϵ,δ)(\epsilon,\delta)-differential privacy, where each of the nn users holds mm samples. Unlike previous work that assumes uniformly bounded gradients, this paper only imposes second- and kk-th moment bounds, denoted by G2G_2 and GkG_k, 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 Dmin⁡{G2,En,m(G2,Gk)}D\min\{G_2,E_{n,m}(G_2,G_k)\}, with a user requirement of O~(1/ϵ)\widetilde{O}(1/\epsilon). The paper also derives tight results for user-level mean estimation under norm-moment assumptions and removes the additional d/ϵd/\epsilon user requirement in Agarwal et al. (2025) under directional moment assumptions. The paper is entirely theoretical and does not include experiments.

Critical strengths
  1. 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 LL. 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).

  2. 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 Λ8\Lambda^8 factor, whereas the proof appears to establish Λ6\Lambda^6. 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
  1. 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 G2G_2, GkG_k, and kk as public inputs, and these quantities directly determine several important tuning parameters. For example, the FriendlyCore radius is set to τ=2G240/m\tau=2G_2\sqrt{40/m}, the clipping radius RR depends on G2G_2 and GkG_k, and the Gaussian noise scale is proportional to RR.

      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 G2G_2 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-tt distributions. They could report MSE, excess loss, or classification accuracy as functions of nn, mm, and ϵ\epsilon, comparing against standard user-level DP-SGD and a non-private baseline. An experiment with misspecified G2G_2 and GkG_k would also be particularly informative.

  2. 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
  1. How should practitioners choose G2G_2, GkG_k, and kk 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.

  2. 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 ϵ\epsilon, nn, and mm.

  3. 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 RR?

6 comments
AuthorsOpenReview ↗

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.

the constants used here are different…The SCO theorem statements contain a Λ8\Lambda^8 factor, whereas the proof appears to establish Λ6\Lambda^6…

We will make the privacy calibration explicit and expand the initialization argument. Appendix D indeed yields Λ6\Lambda^6; Λ8\Lambda^8 is conservative. We will tighten the statements accordingly.

the location-free initialization argument is only briefly sketched.

We will add details in the revision.

The moment parameters must be known in advance.…I am also concerned about sensitivity to misspecification.

Our algorithms require public upper bounds on G2G_2 and GkG_k, not exact moment values. Overestimating these parameters is safe and only weakens the utility bound quantitatively (G2↦G~2G_2\mapsto\widetilde G_2, Gk↦G~kG_k\mapsto\widetilde G_k). Underestimating them may invalidate the accuracy guarantee. Privacy remains valid under these misspecifications.

Is it possible to estimate [moment parameters] privately, and what additional privacy or statistical cost would this introduce?

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.

There are no experiments.…it would be useful to see whether the moment-based approach actually outperforms standard user-level DP-SGD with a carefully tuned clipping norm.

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.

AuthorsOpenReview ↗

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 d/εd/\varepsilon 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 G2/mG_2/\sqrt m?

Choosing radius O(G2/m)O(G_2/\sqrt m) 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.

Reviewer_qaJhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This work investigates mean estimation and stochastic convex optimization (SCO) under user-level central differential privacy when the data is drawn from a heavy-tailed distribution. In mean estimation, this distribution is assumed to have bounded 2nd2^{\text{nd}} and kthk^{\text{th}} centered norm moments. In SCO, the gradients are assumed to have bounded 2nd2^{\text{nd}} and kthk^{\text{th}} norm moments. Then, given nn users with mm datapoints each, the goal is to design optimal algorithms for mean estimation and SCO.

Their mean estimation algorithm uses FriendlyCore (Asi & Liu, 2024; Tsfadia et al, 2022) to come up with a coarse estimate of the mean given half the samples. It then projects the remaining samples to be within a ball centered at this estimate, and computes a noisy estimate of their mean. Their algorithm and analysis work for all n≥1/ϵn \geq 1 / \epsilon. Their upper bound for mean estimation matches the lower bound up to log factors.

The SCO algorithm relies on solving ERM on blocks of s<ns < n users, and aggregating the results using a geometric mechanism. To solve each ERM, they run a gradient-descent style algorithm, wherein they use FriendlyCore to select a subset of users' gradients at each step. Their algorithm then uses these subselected gradients to come up with a coarse estimate of the mean, and then projects the true gradients onto the ball centered at this estimate. They proved that the error achieved by this algorithm is optimal (up to log factors) with matching upper and lower bounds.

The authors also study a third setting of mean estimation under bounded directional moment assumptions. In this setting, they combine an estimator of Agarwal et al. (2025) with their mean estimator and a novel analysis, and prove almost matching upper and lower bounds.

Critical strengths
  • The authors provide optimal algorithms for private mean estimation and DP-SCO under heavy-tailed assumptions. This result was previously known for n>d/ϵn > d/\epsilon, but the authors extend it to n>1/ϵn > 1/\epsilon. This signals the significance of the paper.
  • The paper removes the somewhat unrealistic assumption of bounded gradients. Instead, it assumes that moments of the gradient norm are bounded. This also contributes to the paper's significance.
Critical weaknesses
  • The paper is written in such a way that is very difficult to understand. For example, it introduces new terms without enough context (ex: it's unclear why the ERM algorithm is call "fused"). Further, while the paper explains the different steps of the algorithm and the proofs, it does not do a great job of explaining the intuition behind them. The proofs themselves also often lack detail and clarity. Another suggestion here is to include the main facts (such as the Fuk-Nagaev Inequality and the geometric aggregation mechanism) in the appendix or elsewhere, so that the paper is more self-contained. Overall, the lack of clarity in the paper makes it very hard to parse.
  • The algorithms themselves are mostly small adaptations to or additional steps after existing algorithms like FriendlyCore. This reduces the novelty of the paper.
Questions for authors

The proposed algorithms take as input user averages, instead of the user's entire dataset. How is the resulting problem (and privacy setting) different from item-level DP, where each item is an average?

What is the runtime of the proposed algorithms?

4 comments
AuthorsOpenReview ↗

Response to Reviewer qaJh: Technical Contributions and Clarifications

Thank you for recognizing the significance of our optimal algorithms. We address your comments below.

The authors provide optimal algorithms for private mean estimation and DP-SCO under heavy-tailed assumptions. This result was previously known for n>d/εn>d/\varepsilon, but the authors extend it to n>1/εn>1/\varepsilon.

Not quite. Our optimal heavy-tailed user-level SCO bounds were not previously known in any nontrivial parameter regime: Table 2’s prior user-level SCO results require uniformly bounded gradients. The user threshold reduction from d/εd/\varepsilon to O~k(1/ε)\widetilde O_k(1/\varepsilon) concerns mean estimation, closing gaps left by Zhao et al. (2024) and Agarwal et al. (2025).

introduces new terms without enough context (ex: it's unclear why the ERM algorithm is call "fused")

“Fused” combines coarse-center construction and clipping into one private gradient release: the center remains noiseless and internal; only the noisy clipped average is released. Please let us know if there are any other terms needing clarification.

while the paper explains the different steps of the algorithm and the proofs, it does not do a great job of explaining the intuition behind them.

We will make the intuition explicit. For mean estimation, an accurate coarse center leaves user averages near the population mean unchanged by clipping, so the tails control the bias. For SCO, we avoid adding noise to the clipping center, since this can worsen clipping bias. We keep it noiseless and internal and add Gaussian noise only to the final clipped average. Privacy holds because changing one user has only a small effect on the center and clipped average. For utility, privacy limits the iterates’ dependence on any individual user, allowing us to control clipping bias despite data reuse.

The proofs themselves also often lack detail and clarity.…include the main facts (such as the Fuk-Nagaev Inequality and the geometric aggregation mechanism)

We will expand abbreviated proof steps and state these facts, including their assumptions, in the appendix.

The algorithms themselves are mostly small adaptations to or additional steps after existing algorithms like FriendlyCore.

We respectfully disagree: obtaining optimal rates requires nontrivial combinations of existing tools and new analyses. For example:

  • Norm-moment mean estimation: FriendlyCore’s filtering can introduce excessive bias. Our novel two-stage algorithm addresses this issue: user-average concentration via the Fuk–Nagaev inequality yields sharp clipping-bias bounds despite a coarse, noisy center (lines 161–171).

  • SCO: Iterating this mean estimator adds privacy noise to clipping centers, which can increase bias or require a larger clipping radius and hence more gradient noise. Our novel adaptive fused estimator avoids this obstacle by keeping centers noiseless and internal and noising only the final clipped average (lines 186–194). Privacy requires controlling how changing one user moves the center and affects every clipped gradient (lines 399–405). Utility requires a separate DP-stability analysis of adaptive clipping bias, comparing one- and two-user terms with independent replacement users to avoid a polynomial loss in the iteration count (lines 411–425).

  • Directional-moment mean estimation: Our refinement analysis relaxes Agarwal et al.’s per-round accuracy requirement. We choose the radius from a public bound on the current center error and prove convergence without their additional d/εd/\varepsilon user threshold (lines 471–475; Lemmas G.3–G.4).

We will foreground these obstacles and solutions in Section 1.2.

How is the resulting problem (and privacy setting) different from item-level DP, where each item is an average?

Item-level DP on user averages gives user-level DP. The challenge is optimal accuracy. For equal moment scales GG and a=d/(nε)<1a=\sqrt d/(n\varepsilon)<1, a generic item-level mean estimator applied to user averages gives privacy error

$ \frac{G}{\sqrt m}a^{1-1/k} \quad\text{versus our optimal}\quad \frac{G}{\sqrt m}a+G(a/m)^{1-1/k},$

up to logarithms and constants, omitting the common non-private sampling term. Our analysis exploits the concentration structure of i.i.d. averages to obtain optimal rates. For SCO, raw gradient moments of a user’s empirical loss need not shrink with mm, so a generic item-level reduction is also suboptimal.

What is the runtime of the proposed algorithms?

For fixed kk, the runtimes are:

  • Norm-moment mean estimation: O(nmd+n2d)O(nmd+n^2d) arithmetic operations.

  • SCO: O~k(n2m2)\widetilde O_k(n^2m^2) sample-gradient evaluations, O~k(nm)\widetilde O_k(nm) projections, and O~k(dn2m(n+m))\widetilde O_k(dn^2m(n+m)) additional arithmetic operations.

  • Directional-moment mean estimation: O~k(nmd+n2d)\widetilde O_k(nmd+n^2d) arithmetic operations.

These are polynomial when gradients and projections are efficient. We will add these bounds.

Thank you for your response and the clarification of the result's impact. You have addressed my concerns regarding the paper's novelty. However, I maintain concerns about the presentation and will keep my score.

AuthorsOpenReview ↗

Presentation Revisions

Thank you for confirming that our response addressed your novelty concerns.

We have now uploaded a revised manuscript addressing your presentation feedback:

  • Terminology and intuition: Section 1.2 explains “fused” and clarifies the intuition behind our constructions and their privacy and utility analyses.

  • Proof details and organization: We substantially expanded and clarified the proofs in Appendices B–D and reorganized them to follow the order of results in the main body. These expanded existing proofs remain black for readability.

  • Self-contained mathematical tools: Lemma B.5 (p. 18) states Fuk–Nagaev with its assumptions; Lemma C.2 (p. 29) states and proves geometric aggregation.

  • Item-level DP with user averages: Table 1 and Appendix A (p. 14) explain the naive item-level reduction and its accuracy limitations.

  • Runtime: Appendix E (p. 53) derives the runtime bounds.

We hope these revisions address your remaining presentation concerns sufficiently for you to raise your score.

AuthorsOpenReview ↗

Follow-up on Presentation Revisions

Dear Reviewer qaJh,

With the discussion period ending today, could you please review the presentation revisions described above? The revised manuscript adds proof intuition, expands the appendix proofs, and includes the mathematical tools you requested.

We believe these revisions address your remaining presentation concerns, and would be grateful if you could reconsider your score in light of them.

We would be happy to clarify any specific issues that remain. Thank you for your time.

Reviewer_dm7mOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies mean estimation and stochastic convex optimization under user-level (ε,δ)(\varepsilon,\delta)-differential privacy, where each of n users contributes m independent observations from a common distribution. The main statistical assumption replaces uniformly bounded sample gradients with bounded second and k-th moments of the random sample Lipschitz constant, for fixed k>2.

Critical strengths

The paper provides matching bounds for both norm-moment mean estimation and convex optimization while preserving separate dependence on G_2 and G_k. This distinction matters when the higher-moment scale is substantially larger than the second-moment scale: replacing both by G_k can unnecessarily inflate the sampling and Gaussian privacy terms. The minimum between the second-moment and higher-moment heavy-tail terms also gives a meaningful characterization across parameter regimes. The matching lower bounds support the claim that this dependence is intrinsic rather than an artifact of the estimator.

Critical weaknesses
  1. The paper’s presentation could be improved. The main text devotes considerable space to proof sketches and technical details, while the novel ideas and their significance are not explained clearly enough. I would encourage the authors to foreground the central contributions, explain how they advance beyond prior work, and clarify why these advances matter. Although rigorous proofs are essential, the main narrative would be more effective if it emphasized the key conceptual insights and proof intuition, with detailed technical arguments deferred to the appendix.

  2. My main concern is the paper’s limited novelty. I know in the works you mentioned in 2024 such as Lowy and Asi, they have already done the most of the work for central DP. It seems that you extend the SCO to minimax and user-level SCO problem, do I comprehend it correctly? As currently presented, the work appears to combine existing ideas, while its substantive contribution beyond prior work remains unclear. I would be willing to raise my score if the authors could clearly identify the novel technical contributions, explain how they go beyond established results, and demonstrate why these advances are significant.

Questions for authors

See weaknesses

3 comments
AuthorsOpenReview ↗

Response to Reviewer dm7m: Novelty and Significance

Thank you for your feedback. We are glad you appreciated the matching bounds and the importance of preserving separate second- and higher-moment scales.

The paper’s presentation could be improved… the novel ideas and their significance are not explained clearly enough. My main concern is the paper’s limited novelty… the work appears to combine existing ideas… I would be willing to raise my score if the authors could clearly identify the novel technical contributions, explain how they go beyond established results, and demonstrate why these advances are significant.

These concerns are closely related, so we address them together. The introduction discusses our contributions and their significance, and Section 1.2 describes the technical challenges and techniques. We will sharpen this discussion around the following points.

1. Advances beyond prior work. For SCO, prior work establishes optimal rates for user-level DP with uniformly bounded gradients (Asi & Liu, 2024; Lowy, Liu & Asi, 2024) and for item-level SCO with heavy tails (Lowy & Razaviyayn, 2023; Asi, Liu & Tian, 2024). For mean-estimation, prior work on user-level DP with heavy tails leaves gaps across parameter regimes; for example, Zhao et al. (2024) and Agarwal et al. (2025) require n>d/εn>d/\varepsilon users.

Our paper goes beyond these works: we characterize the minimax optimal rates for user-level SCO with heavy tails and close these mean-estimation gaps, attaining optimal rates throughout the stated user regime, up to logarithmic factors. Our matching upper and lower bounds also establish that the separate second- and higher-moment dependence is intrinsic.

2. Significance. User-level privacy protects a person’s entire collection of records, as needed when users contribute multiple messages or measurements (lines 36–42). Meanwhile, uniform Lipschitz bounds can be extremely large or infinite even in squared-loss regression, while moment bounds remain finite (lines 44–58). Understanding the statistical complexity of user-level learning under these weaker assumptions is therefore a practically motivated, fundamental theoretical problem.

3. Novel techniques. Obtaining our novel results requires new constructions and analyses that overcome technical obstacles to directly combining existing methods.

For norm-moment mean estimation, FriendlyCore’s filtering can introduce excessive bias. Our novel two-stage algorithm addresses this issue, with an analysis showing that even a coarse, noisy clipping center permits sharp bias bounds by exploiting the concentration of user averages via Fuk–Nagaev inequality (lines 161–171).

For SCO, directly iterating this mean estimator requires additional privacy noise in the clipping centers. This can increase clipping bias; enlarging the clipping radius instead increases the final gradient noise. Our novel adaptive fused estimator avoids this obstacle by keeping the centers noiseless and internal and adding Gaussian noise only to the final clipped average (lines 186–194). Proving privacy requires a delicate argument controlling how changing one user moves the center and affects every clipped gradient (lines 399–405). Proving utility requires a separate DP-stability analysis of adaptive clipping bias, comparing one- and two-user terms with independent replacement users to avoid a polynomial loss in the iteration count (lines 411–425).

For directional-moment estimation, we relax Agarwal et al.’s per-round accuracy requirement, choose the clipping radius using a public bound on the current center error, and prove convergence without their additional d/εd/\varepsilon user threshold (lines 471–475).

We will foreground these results, motivations, and technical innovations in the revision, while moving technical details to the appendix where possible.

We hope these clarifications address your concerns sufficiently for you to raise your score.

main narrative would be more effective if it emphasized the key conceptual insights and proof intuition

We will make the conceptual insights and proof intuition more explicit. For mean estimation, an accurate coarse center ensures that clipping leaves user averages near the population mean unchanged, so the distribution’s tails control the resulting bias. For SCO, the central idea is to avoid adding noise to the clipping center before clipping, since this noise can worsen clipping bias. We keep the center noiseless and internal and add Gaussian noise only to the final clipped average. This preserves privacy because changing one user has only a small effect on the center and hence on the clipped average. For the utility proof, we exploit the fact that privacy limits how strongly the iterates depend on any individual user, allowing us to control clipping bias despite reusing the data.

Thanks for your reply, and I will raise my score.

Thank you very much for engaging with our responses and raising your score.

Reviewer_CJYvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies stochastic convex optimization (SCO) and mean estimation under (ϵ,δ)(\epsilon, \delta)-user-level differential privacy with heavy-tailed stochastic gradients/data, replacing bounded Lipschitz/data assumptions with second- and kk-th moment bounds. It characterizes minimax optimal excess population risk and l2l_{2}-error rates up to logarithmic factors across the regime n≥Ω~k(1/ϵ)n \ge \tilde{\Omega}_k(1/\epsilon). It introduces a two-stage mean estimator (FriendlyCore coarse estimation followed by clipped-average-and-noise), a fused adaptive gradient estimator for regularized ERM, and closes the approximate-DP gap for directional-moment mean estimation.

Critical strengths

The theoretical contribution is rigorous and resolves open questions in private machine learning.

Critical weaknesses
  1. The paper is purely theoretical, featuring 27 pages of dense mathematical proofs but zero experiments. Note that this paper also proposes complex and multi-stage algorithmic pipelines, such as Algorithm 1 (FriendlyCore + clip-average-noise) and Algorithm 4 (fused adaptive DP SGD with Above Threshold tests, outlier filtering, and dynamic clipping), which benefit immensely from empirical validation. Why not conduct experiments to verify the feasibility and effectiveness of these algorithms? I wonder whether such intricate algorithms are only artifacts of worst-case bound proofs or if they function effectively in practice.

  2. The analysis relies heavily on the standard assumption that all nmnm observations (m samples across n users) are drawn i.i.d. from the underlying distribution PP. In real-world federated learning and user-level DP settings (e.g., typed text on a phone, patient vitals), data generated by the same user shows strong internal correlation, non-stationarity, or heterogeneity (non-I.I.D. data). Assuming complete independence in user blocks simplifies the tail bounds (via Fuk-Nagaev inequalities for sums of independent random variables) but limits the realism of the model.

  3. The proposed algorithms combine FriendlyCore distance calculations (O(n12)O(n_1^2) pairwise checks), Above Threshold sequential hypothesis testing, population localization meta-algorithms with IJIJ phases, and adaptive SGD with dynamic clipping. Furthermore, the error bounds and sample complexity requirements feature high-order polynomial dependencies on logarithmic factors (e.g., Λ4,Λ6,Λ8\Lambda^4, \Lambda^6, \Lambda^8). I wonder whether the constant factors are so large that the bounds become vacuous in realistic parameter regimes. Thus experiments on computational complexity should be conducted to check whether there are high algorithmic complexity and intractable theoretical constants description.

  4. This paper provides incremental conceptual novelty. The individual components are largely borrowed from recent literature (e.g., Asi & Liu, 2024; Lowy, 2026; Mollenhauer & Fiedler, 2025), making the paper a technical synthesis rather than a conceptual breakthrough.

Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer CJYv: Theoretical Scope and Technical Novelty

Thank you for your feedback. We are glad you found our contribution rigorous and noted that it “resolves open questions in private machine learning.”

Experiments and practical performance

Like many accepted ICLR papers, we characterize minimax optimal rates through matching upper and lower bounds. The ICLR reviewer guidelines ask reviewers to consider a paper’s objectives and whether its claims are supported. We therefore do not view the absence of experiments as a weakness relative to our theoretical objective. Practical implementations and empirical evaluation remain future work (Conclusion and Limitations).

The analysis relies heavily on the standard assumption that all observations (m samples across n users) are drawn i.i.d. from the underlying distribution…

Indeed, i.i.d. observations are standard in user-level SCO and estimation (Esfandiari et al., 2022; Asi & Liu, 2024; Lowy et al., 2024; Zhao et al., 2024; Agarwal et al., 2025). We retain this assumption, relaxing the uniformly Lipschitz assumption of Asi & Liu and Lowy et al. to allow heavy tails, and improving mean-estimation guarantees under prior works’ respective assumptions.

User-level privacy holds for arbitrary datasets, including correlated or heterogeneous user blocks.

Characterizing minimax optimal rates for heterogeneous users is an important future direction we will mention in the Conclusion.

The error bounds and sample complexity requirements feature high-order polynomial dependencies on logarithmic factors.

Matching rates up to logarithmic factors identifies the necessary and sufficient polynomial dependence on the number of users, samples per user, dimension, privacy, and moment bounds. Determining the tight logarithmic dependence remains open, and we will mention this as a possible future direction.

I wonder whether the constant factors are so large that the bounds become vacuous in realistic parameter regimes.

Our results characterize statistical complexity up to logarithmic factors. We do not claim favorable constants at practical sample sizes. Conservative worst-case constants do not diminish this characterization or establish poor empirical performance. Practical algorithms and empirical evaluation remain important future directions (Conclusion).

Computational complexity

Norm-moment mean estimation takes O(nmd+n2d)O(nmd+n^2d) arithmetic operations, including FriendlyCore’s pairwise distances. SCO uses O~k(n2m2)\widetilde O_k(n^2m^2) sample-gradient evaluations, O~k(nm)\widetilde O_k(nm) projections, and O~k(dn2m(n+m))\widetilde O_k(dn^2m(n+m)) additional arithmetic operations. These bounds are polynomial when gradient evaluation and projection are efficient. We will add these bounds.

This paper provides incremental conceptual novelty. The individual components are largely borrowed from recent literature….

We develop new algorithmic constructions and analyses to overcome obstacles that direct combinations of existing techniques do not resolve.

SCO: A natural approach applies population localization to a DP-SGD ERM solver that iterates our two-stage “FriendlyCore + clip-and-noise” mean estimator. However, this approach is suboptimal: Composing the private queries requires increased noise in each clipping center. This perturbation increases clipping bias at a fixed radius; enlarging the radius to accommodate it increases gradient noise. Our novel fused estimator avoids this obstacle: it uses FriendlyCore’s outlier removal to construct a noiseless, internal center, then clips all user gradients around that center and adds Gaussian noise only to their average (lines 186–194).

Proving privacy of our fused estimator is also non-trivial: changing one user can move the internal center and thus change every clipped gradient. Our sensitivity analysis controls both the center’s movement and its effect on the full clipped average (lines 399–405; Lemma E.3). Separately, reusing users makes the iterates data-dependent, preventing direct application of fixed-query clipping-bias bounds. We control the average squared empirical clipping bias by expanding it into one- and two-user terms and applying DP stability with independent replacement users, avoiding a polynomial loss in the iteration count (lines 411–425).

Directional-moment mean estimation: We develop a novel refinement analysis that avoids the stringent per-round accuracy requirement responsible for Agarwal et al.’s additional d/εd/\varepsilon user threshold. We choose the clipping radius using a public bound on the current center error and prove that successive error bounds contract toward the target accuracy without that earlier requirement (lines 471–475; Lemmas G.3–G.4).

We will foreground these obstacles and the new constructions and analyses that overcome them in the revision.

AuthorsOpenReview ↗

Follow-up on Our Rebuttal and Revised Manuscript

Dear Reviewer CJYv,

We would appreciate your thoughts on our rebuttal, particularly our explanations of the paper’s theoretical scope and technical novelty. We have also uploaded a revised manuscript that clarifies the technical contributions and intuition in Section 1.2 and provides runtime bounds in Appendix E.

Could you please let us know whether our response and these revisions address your concerns, or whether further clarification would be helpful?

Thank you for your time.

AuthorsOpenReview ↗

Final Follow-up on Our Rebuttal and Revised Manuscript

Dear Reviewer CJYv,

As the discussion period ends today, we would appreciate your assessment of our rebuttal and revised manuscript, particularly our explanations of the theoretical scope and technical novelty and the added runtime bounds.

We believe our responses and revisions address your concerns, and would be grateful if you could reconsider your score in light of them.

We would be happy to provide any further clarification before the discussion closes. Thank you for your time.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.