Pith. sign in

REVIEW 3 major objections 5 minor 35 references

Linear-Time User-Level DP-SCO via Robust Statistics

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves a linear-time, near-optimal user-level DP-SCO algorithm using robust statistics, plus a nearly matching lower bound.

desk verdict First linear-time user-level DP-SCO algorithm in ℓ1/ℓ∞ geometry with a nice robust-statistics core, but the privacy proof has a sensitivity-scaling bug and an unmet parameter condition; both look fixable. read the letter →

arxiv 2502.08889 v1 pith:UPHVV4L5 submitted 2025-02-13 cs.LG cs.CRcs.DSstat.ML

Badih Ghazi , Ravi Kumar , Daogao Liu , Pasin Manurangsi This is my paper · ORCID
classification cs.LGcs.CRcs.DSstat.ML
keywords user-leveldifferentialprivacystochasticconvexoptimizationrobuststatisticsmedianandtrimmedmeanlinear-timealgorithmell-infinitygeometryiterationsensitivityfingerprintinglowerbound
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that user-level differentially private convex optimization admits a linear-time algorithm---the same total gradient cost as ordinary SGD---when the gradient oracle is replaced by robust statistics. Under convexity, $G$-Lipschitz continuity in the $\ell_1$-norm, smoothness with diagonally dominant Hessians, and an $\ell_\infty$-ball domain, it proves an excess-risk bound of $\tilde{O}(GD(d/\sqrt{nm} + d^{3/2}/(n \varepsilon^2 \sqrt{m})))$ using $mn$ gradient computations. A companion lower bound of $\tilde{\Omega}(GD\cdot\min\{d,\, d/\sqrt{nm} + d^{3/2}/(n\varepsilon\sqrt{m})\})$ shows the rate is optimal up to logarithmic factors and the dependence on $\varepsilon$. A sympathetic reader should care because prior linear-time user-level algorithms paid extra noise by privatizing every iteration, while this work shows that a coordinate-wise median or trimmed-mean estimator can keep the whole SGD trajectory stable under one-user replacement, so only the final localized iterate needs noise.

What carries the argument

The carrying object is the coordinate-wise robust-statistics gradient estimator (Algorithm 2), built from any statistic satisfying Assumption 3.3: a majority-concentration property, a 1-Lipschitz property under $\ell_\infty$ perturbations, and affine equivariance. For each coordinate, the estimator outputs the plain mean when the mean and the robust statistic are close, and otherwise projects the mean into the $\ell_\infty$-ball of radius $\varsigma$ around the robust statistic; Lemma 3.5 shows this projection preserves the 1-Lipschitz sensitivity bound in one dimension, which is enough when applied coordinate-wise. The other load-bearing pieces are Lemma 3.2, which uses diagonal dominance of the Hessian to prove that a gradient-descent step with $\eta\le 2/\beta$ is nonexpansive in $\ell_\infty$, yielding the iteration sensitivity bound $\|x_t-y_t\|_\infty \le \|x_1-y_1\|_\infty$ (Lemma 3.7), and Algorithm 3, the smoothed concentration test whose score $B^{-1}\sum_{Z,Z'} \exp(-\tau\|q_t(Z)-q_t(Z')\|_\infty)$ is fed to AboveThreshold so that the algorithm detects too many 'bad' users and falls back to the initial point. These pieces are wrapped in a localization framework that repeats the process over $O(\log n)$ phases with shrinking datasets and adds Gaussian noise only to the average iterate of each phase.

What would settle it

Check the edge of the theorem's domain by computing a single gradient-descent step for the convex $\beta$-smooth function $f(x)=\tfrac12 x^\top H x$ with $H = \begin{bmatrix} 1 & 1.2 \\ 1.2 & 2 \end{bmatrix}$ on $[-1,1]^2$, $\beta=3.2$, $\eta=0.625$: the points $(0,0)$ and $(1,-1)$ start at $\ell_\infty$ distance $1$ but their images are at distance $1.125$, so Lemma 3.2 fails as soon as diagonal dominance is dropped. Replaying this expansion inside a full neighboring-pair trajectory would break the query-sensitivity bound of $2$ on which the privacy proof rests.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1: under Assumptions 2.4 and 2.5 and the stated parameter constraints, Algorithm 5 is $(\varepsilon,\delta)$-user-level differentially private, runs in exactly $mn$ gradient computations, and for i.i.d. data satisfies $\mathbb{E}[F(x_S)-F(x^*)] \le \tilde{O}(GD(d/\sqrt{nm} + d^{3/2}/(n\varepsilon^2\sqrt{m})))$. Theorem 4.1 constructs a hard instance based on the linear loss $f(x;z)=-\langle x,z\rangle$ with $z$ supported in $[-\sqrt{m},\sqrt{m}]^d$ and shows every user-level-DP algorithm must pay $\tilde{\Omega}(GD\cdot\min\{d,\, d/\sqrt{nm} + d^{3/2}/(n\varepsilon\sqrt{m})\})$ in excess risk. Read together, the theorems say user-level privacy is achievable at the computational cost of non-private SGD in this geometry, and the only remaining gap in the rate is the dependence on $\varepsilon$. The mechanism that makes this possible is the central design choice: intermediate SGD iterates are never privatized; robust statistics render the entire trajectory stable under one-user replacement, and Gaussian noise is added only once per localization phase.

Load-bearing premise

The load-bearing premise is that every loss function has a diagonally dominant Hessian, meaning each coordinate's own curvature is at least as large as the total cross-curvature affecting it; if that fails, a gradient-descent step can push two neighboring runs further apart in $\ell_\infty$, and the claim that intermediate iterates need no per-step noise loses its proof.

Editorial extensions

If this is right

  • User-level DP-SCO under these assumptions becomes linear-time: the same $mn$ gradient evaluations as ordinary SGD buy excess risk $\tilde{O}(GD(d/\sqrt{nm} + d^{3/2}/(n\varepsilon^2\sqrt{m})))$.
  • The lower bound of Theorem 4.1 implies no user-level-DP algorithm for this problem class can improve that rate except in logarithmic factors and the power of $\varepsilon$.
  • Intermediate iterates carry no privacy noise, so memory and per-step computation match non-private SGD; privacy is paid only in $O(\log n)$ Gaussian perturbations across localization phases.
  • Setting $m=1$ recovers the item-level rate for $\ell_1$ geometry up to the $\varepsilon$ gap, showing the user-level extension is tight in the number of samples per user.
  • When the concentration test fails, the algorithm returns the initial point, so the user is explicitly told that the current batch did not satisfy the concentration condition rather than receiving an unverified private model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The recipe is more general than the theorem: any optimization problem with a natural norm and a 1-Lipschitz robust statistic could use this no-per-step-noise pattern; the paper's restriction to $\ell_\infty$ is exactly where such statistics are known to exist, so finding high-dimensional 1-Lipschitz estimators in $\ell_2$ would likely remove the diagonal-dominance assumption.
  • The $\varepsilon^2$-versus-$\varepsilon$ gap appears to trace to the robust statistic's sensitivity staying near $1/\sqrt{m}$ regardless of batch size $B$; a debiased estimator with sensitivity $O(1/(B\sqrt{m}))$ would close the gap under the same localization argument.
  • A practical extension would test the mechanism on models with block-diagonally-dominant Hessians: record the $\ell_\infty$ divergence between two SGD runs whose datasets differ by one user, and check whether the divergence stays bounded by the first-iterate difference as Lemma 3.7 predicts.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies user-level differentially private stochastic convex optimization (DP-SCO) under ℓ∞-geometry assumptions: convex, G-Lipschitz w.r.t. ℓ1, β-smooth functions with diagonally dominant Hessians, over an ℓ∞-ball. The main algorithmic contribution is a linear-time SGD-type method (Algorithm 5) whose gradient estimates are produced by coordinate-wise robust statistics (median/trimmed mean) with a debiasing projection, together with a smoothed concentration test built on AboveThreshold. The authors claim that no per-iteration Gaussian noise is needed, because the robust-statistic construction provably bounds the ℓ∞ sensitivity of all iterates; only one Gaussian mechanism per localization phase is used. The stated utility bound is Õ(GD(d/√(nm) + d^{3/2}/(n ε²√m))), with a matching lower bound up to logarithmic factors and the dependence on ε. The paper also gives a lower bound via the fingerprinting lemma. The central claim of the paper is that this is the first linear-time user-level DP-SCO algorithm with near-optimal rates in the ℓ∞ setting.

Significance. If the result held as stated, it would be a meaningful advance for user-level DP-SCO: it transfers the FKT-style stability-based linear-time approach to the user-level setting and, in the ℓ∞ geometry, avoids the noise accumulation of iteratively privatized SGD. The use of 1-Lipschitz robust statistics to control trajectory sensitivity is an elegant and potentially reusable idea, and the lower bound is derived independently by standard fingerprinting arguments. The paper is also transparent about the restrictiveness of the diagonal-dominance assumption and about the remaining ε-gap between upper and lower bounds. However, the current manuscript does not establish the stated privacy guarantee because of a load-bearing error in the AboveThreshold accounting, and a second parameter condition needed by the proof is not guaranteed by the stated choices.

major comments (3)
  1. [§3 (Algorithm 3), Eq. (4), Lemma 3.10, Appendix A.3] The privacy accounting for the concentration test is not correct as written. Equation (4) and Lemma 3.9 establish sensitivity at most 2 for the queries sconc_t, but Algorithm 3 calls AboveThreshold with privacy parameter ε/2. The AboveThreshold implementation in Algorithm 4 and the quoted Lemma A.3 are stated for queries of sensitivity 1. For a query of sensitivity s, the required Laplace scales are 2s/ε and 4s/ε; with s=2 and parameter ε/2 the actually instantiated noise is only half of what is required, i.e. the implemented test is (ε,0)-DP rather than (ε/2,0)-DP. Lemma 3.10 then composes the test with the Gaussian mechanism using ε/2, so the proof gives at best a (cε,δ) guarantee with c>1, not the stated (ε,δ) guarantee. This is load-bearing for Theorem 3.1. The likely fix is local—call AboveThreshold with parameter ε/4 (or normalize the queries to sensitivity 1 and keep ε/2)—but as written the claimed privacy guarantee is not established.
  2. [Lemma 3.9 and Lemma 3.12 parameter settings] Lemma 3.9 requires the condition 6βηB ≤ 1 to conclude that the query sensitivity is at most 2, and this condition is invoked in the privacy proof of Lemma 3.10. However, no displayed parameter choice in Theorem 3.1 or Lemma 3.12 implies 6βηB ≤ 1. With B = 100 log(mnd/δ)/ε and the displayed η bound, the second term of the β bound can be used to get βη ≤ 1, which only gives 6βηB ≤ 6B, and the first η argument can make βη much larger. Thus the sensitivity bound used in the privacy proof is not currently supported by the stated assumptions. Either an additional parameter restriction or a sharper argument is needed; as written, this is another load-bearing gap.
  3. [Lemma 3.10, case (i)] The case analysis in the privacy proof has an unstated implication. Lemma 3.10 case (i) says that when (D1,D1′) is not (1/τ)-aligned, Lemma 3.8 gives Pr[a1=⊥]≥1−δ/2 or Pr[a1′=⊥]≥1−δ/2eε. But Lemma 3.8 requires the stronger condition that |Xgood| < B/3 for every point Y, whereas non-alignment only means that no pair of centers X′,Y′ has |Xgood|≥2B/3 and |Ygood|≥2B/3 with the good sets coming from the neighboring datasets. It is not immediate that non-alignment implies the <B/3 condition. The argument can likely be repaired, since a concentration score below 0.8B may hold already when fewer than 2B/3 users are good, but this repair is not present in the manuscript.
minor comments (5)
  1. [Lemma 3.9 statement] The lemma statement compares sconc_t(D,τ) with sconc_1(D′,τ); the second term should be sconc_t(D′,τ).
  2. [Lemma 3.10, proof of case (ii)] The proof says Lemma 3.9 'suggests that the query sensitivity is always bounded by 1,' but Lemma 3.9 and Eq. (4) both give sensitivity at most 2. This inconsistency is directly tied to the privacy accounting error above.
  3. [Theorem 3.1 and Lemma 3.12] The displayed β condition has unbalanced parentheses and is difficult to parse; the text '√nε√m log(nmd/δ)' does not make clear whether the logarithmic factor is in the numerator or denominator. This should be corrected.
  4. [Algorithm 5, line 3] The setting 'S = ⌈log n/B⌉' appears to be a typo; the localization proof in Lemma 3.12 sums over Θ(log n) phases, and with B>1 the displayed formula would give only one phase.
  5. [Lemma 3.8] The phrase 'with probability at least 1−δ/T exp(ε)' is ambiguous; it should be '1−δ/(T exp(ε))' or the intended bound should be written unambiguously.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the derivation is assumption-based and externally benchmarked, though it contains a non-circular privacy-accounting gap.

full rationale

No circular step reduces the claimed results to their inputs. Theorem 3.1 is built from stated assumptions (Lipschitz/smoothness, diagonal dominance), Assumption 3.3 on robust statistics, Lemma 3.5, Lemmas 3.6–3.9, and external tools Lemma A.3 and Lemma A.6; the parameters B, tau, upsilon, and eta are set as functions of epsilon, delta, n, m, d, G, D, and beta, and are not fitted to any dataset or to the target rate. The lower bound (Theorem 4.1) is independent, using the external fingerprinting lemma [KLSU19] and an external averaging reduction [LSA+21]. Self-citations such as [GKK+23, LLA24, AL24, ALT24] appear only in the introduction and related work and are not load-bearing; the paper itself flags the restrictive diagonal-dominance assumption in Section 5, which is a scope limitation rather than a circular step. The one notable defect is not circular: Algorithm 3 invokes AboveThreshold with privacy budget epsilon/2, while Eq. (4) and Lemma 3.9 bound the query sensitivity by 2, and Lemma A.3 is stated for sensitivity-1 queries; the proof of Lemma 3.10 then asserts 'the query sensitivity is always bounded by 1' (Appendix B.7). This is an internal accounting mismatch that would need repair, but it does not make the derivation circular.

Assumptions & free parameters 5 free parameters · 7 assumptions · 0 invented entities

The algorithm introduces no new physical or mathematical entities; its free parameters are hyperparameters set analytically by the proof. The main additional assumption beyond the standard problem setup is diagonal dominance, which is the price paid for the ℓ∞ stability analysis.

free parameters (5)
  • Batch size B = 100 log(mnd/δ)/ε
    Chosen to satisfy the concentration test (Lemma 3.8) and privacy composition; the exact constant is set by the proof.
  • Concentration threshold τ = O(G log(nmd)/√m)
    Sets the scale at which gradients are considered close; must balance bias (Lemma 3.11) and sensitivity.
  • Test threshold υ = 0.9B + 2 log(T/δ)/ε
    Chosen so that the AboveThreshold test passes for good datasets and fails when more than 2B/3 users are bad.
  • Step size η = ≤ (D/G)·min{ B√m/√n, √m ε/(√d log(1/δ) log(nmd)) }
    Chosen to balance the SGD bias-variance trade-off in Lemma 3.11 and the localization noise in Lemma 3.12.
  • Gaussian noise scale σ_s = O(η_s G √d log(exp(ε)/δ) log(nmd)/(√m ε))
    Added to privatize each localized solution; the unspecified O(1) constant is part of the construction.
assumptions (7)
  • domain assumption Each f(·;z) is convex, G-Lipschitz w.r.t. ℓ1, β-smooth w.r.t. the ℓ∞ operator norm, and X is an ℓ∞-ball of radius D (Assumption 2.4).
    Defines the problem setting; not standard for prior Euclidean-space DP-SCO work.
  • ad hoc to paper The Hessian of each f(·;z) is diagonally dominant (Assumption 2.5).
    Used only to prove ℓ∞ contractivity of gradient descent (Lemma 3.2); this is the paper's main extra restriction and is not needed in prior work.
  • domain assumption The robust statistic used in Algorithm 2 satisfies Assumption 3.3 (break-point closeness, 1-Lipschitz perturbation stability, affine equivariance).
    Holds for coordinate-wise median and trimmed mean, which the paper cites as the implemented choices.
  • domain assumption The nm functions in the dataset are i.i.d. from an unknown distribution P (for the utility guarantee only).
    Standard in SCO; privacy does not rely on this.
  • standard math AboveThreshold satisfies its stated privacy and accuracy guarantees (Lemma A.3).
    Imported from Dwork and Roth (2014).
  • standard math Fingerprinting lemma (Lemma C.4) from KLSU19.
    Used for the lower bound.
  • standard math Hoeffding-type concentration for norm-subGaussian vectors (Theorem A.5).
    Used to show user gradient averages are close to the population gradient.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Linear-Time User-Level DP-SCO via Robust Statistics." pith.science (2026). https://pith.science/paper/UPHVV4L5

@misc{pith2026250208889,
  author       = {Pith},
  title        = {Pith review of: Linear-Time User-Level DP-SCO via Robust Statistics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UPHVV4L5}},
  note         = {Machine review of arXiv:2502.08889}
}
abstract

User-level differentially private stochastic convex optimization (DP-SCO) has garnered significant attention due to the paramount importance of safeguarding user privacy in modern large-scale machine learning applications. Current methods, such as those based on differentially private stochastic gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility due to the need to privatize every intermediate iterate. In this work, we introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges. Our approach uniquely bounds the sensitivity of all intermediate iterates of SGD with gradient estimation based on robust statistics, thereby significantly reducing the gradient estimation noise for privacy purposes and enhancing the privacy-utility trade-off. By sidestepping the repeated privatization required by previous methods, our algorithm not only achieves an improved theoretical privacy-utility trade-off but also maintains computational efficiency. We complement our algorithm with an information-theoretic lower bound, showing that our upper bound is optimal up to logarithmic factors and the dependence on $\epsilon$. This work sets the stage for more robust and efficient privacy-preserving techniques in machine learning, with implications for future research and application in the field.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 31 canonical work pages

  1. [1]

    Private stochastic convex optimization: Optimal rates in l1 geometry

    Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in l1 geometry. In ICML , pages 393--403, 2021

    work page 2021

  2. [2]

    User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates

    Hilal Asi and Daogao Liu. User-level differentially private stochastic convex optimization: Efficient algorithms with optimal rates. In AISTATS , pages 4240--4248, 2024

    work page 2024

  3. [3]

    Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

    Hilal Asi, Daogao Liu, and Kevin Tian. Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions. arXiv , 2406.02789, 2024

    work page Pith review arXiv 2024

  4. [4]

    From robustness to privacy and back

    Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back. In ICML , pages 1121--1146, 2023

    work page 2023

  5. [5]

    Information-theoretic lower bounds on the oracle complexity of convex optimization

    Alekh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information-theoretic lower bounds on the oracle complexity of convex optimization. In NIPS , 2009

    work page 2009

  6. [6]

    Stability of stochastic gradient descent on nonsmooth convex losses

    Raef Bassily, Vitaly Feldman, Crist \'o bal Guzm \'a n, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. arXiv , 2006.06914, 2020

    arXiv 2006

  7. [7]

    Private stochastic convex optimization with optimal rates

    Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In NIPS , pages 11282--11291, 2019

    work page 2019

  8. [8]

    Non-euclidean differentially private stochastic convex optimization

    Raef Bassily, Crist \'o bal Guzm \'a n, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. In COLT , pages 474--499, 2021

    work page 2021

Show all 35 references
  1. [9]

    Practical gauss-newton optimisation for deep learning

    Aleksandar Botev, Hippolyt Ritter, and David Barber. Practical gauss-newton optimisation for deep learning. In International Conference on Machine Learning , pages 557--565. PMLR, 2017

    2017

  2. [10]

    User-level private stochastic convex optimization with optimal rates

    Raef Bassily and Ziteng Sun. User-level private stochastic convex optimization with optimal rates. In ICML , pages 1838--1851, 2023

    2023

  3. [11]

    Private empirical risk minimization: Efficient algorithms and tight error bounds

    Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In FOCS , pages 464--473, 2014

    2014

  4. [12]

    Convex optimization: Algorithms and complexity

    S \'e bastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8(3-4):231--357, 2015

    2015

  5. [13]

    Optimal rates for o (1)-smooth dp-sco with a single epoch and large batches

    Christopher A Choquette-Choo, Arun Ganesh, and Abhradeep Guha Thakurta. Optimal rates for o (1)-smooth dp-sco with a single epoch and large batches. In ALT , 2024

    2024

  6. [14]

    Extracting training data from large language models

    Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In USENIX Security , pages 2633--2650, 2021

    2021

  7. [15]

    Towards quantifying the preconditioning effect of adam

    Rudrajit Das, Naman Agarwal, Sujay Sanghavi, and Inderjit S Dhillon. Towards quantifying the preconditioning effect of adam. arXiv preprint arXiv:2402.07114 , 2024

    2024 arXiv

  8. [16]

    The projection median of a set of points

    Stephane Durocher and David Kirkpatrick. The projection median of a set of points. Computational Geometry , 42(5):364--375, 2009

    2009

  9. [17]

    Differential privacy and robust statistics

    Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In STOC , pages 371--380, 2009

    2009

  10. [18]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC , pages 265--284, 2006

    2006

  11. [19]

    The algorithmic foundations of differential privacy

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9(3--4):211--407, 2014

    2014

  12. [20]

    Private stochastic convex optimization: optimal rates in linear time

    Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In STOC , pages 439--449, 2020

    2020

  13. [21]

    On user-level private convex optimization

    Badih Ghazi, Pritish Kamath, Ravi Kumar, Raghu Meka, Pasin Manurangsi, and Chiyuan Zhang. On user-level private convex optimization. arXiv , 2305.04912, 2023

    2023 arXiv

  14. [22]

    Private convex optimization via exponential mechanism

    Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. In COLT , pages 1948--1989, 2022

    1948

  15. [23]

    A short note on concentration inequalities for random vectors with subgaussian norm

    Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv , 1902.03736, 2019

    1902 arXiv

  16. [24]

    Privately learning high-dimensional distributions

    Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high-dimensional distributions. In COLT , pages 1853--1902, 2019

    1902

  17. [25]

    Differential privacy and robust statistics in high dimensions

    Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. In COLT , pages 1167--1246, 2022

    2022

  18. [26]

    Faster algorithms for user-level private stochastic convex optimization

    Andrew Lowy, Daogao Liu, and Hilal Asi. Faster algorithms for user-level private stochastic convex optimization. In NeurIPS , 2024

    2024

  19. [27]

    Learning with user-level privacy

    Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. NeurIPS , pages 12466--12479, 2021

    2021

  20. [28]

    Analyzing leakage of personally identifiable information in language models

    Nils Lukas, Ahmed Salem, Robert Sim, Shruti Tople, Lukas Wutschitz, and Santiago Zanella-B \'e guelin. Analyzing leakage of personally identifiable information in language models. In S & P , pages 346--363, 2023

    2023

  21. [29]

    On the linearity of large non-linear models: when and why the tangent kernel is constant

    Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems , 33:15954--15964, 2020

    2020

  22. [30]

    Optimizing neural networks with kronecker-factored approximate curvature

    James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In International conference on machine learning , pages 2408--2417. PMLR, 2015

    2015

  23. [31]

    Faster rates of private stochastic convex optimization

    Jinyan Su, Lijie Hu, and Di Wang. Faster rates of private stochastic convex optimization. In ALT , pages 995--1002, 2022

    2022

  24. [32]

    Perturbed m-estimation: A further investigation of robust statistics for differential privacy

    Aleksandra Slavkovic and Roberto Molinari. Perturbed m-estimation: A further investigation of robust statistics for differential privacy. In Statistics in the Public Interest: In Memory of Stephen E. Fienberg , pages 337--361. Springer, 2012

    2012

  25. [33]

    Convergence rates of stochastic gradient descent under infinite noise variance

    Hongjian Wang, Mert Gurbuzbalaban, Lingjiong Zhu, Umut Simsekli, and Murat A Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance. Advances in Neural Information Processing Systems , 34:18866--18877, 2021

    2021

  26. [34]

    Advances in private training for production on-device language models

    Zheng Xu and Yanxiang Zhang. Advances in private training for production on-device language models. https://research.google/blog/advances-in-private-training-for-production-on-device-language-models/, 2024. Google Research Blog

    2024

  27. [35]

    Differentially private online-to-batch for smooth losses

    Qinzi Zhang, Hoang Tran, and Ashok Cutkosky. Differentially private online-to-batch for smooth losses. In NeurIPS , 2022

    2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.