mlsanityData to 14 Oct 2026

User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates

arXiv 2311.03797 ↗First posted 7 Nov 2023cs.LG cs.CR cs.DScited by 12

Not on the map. Why?

Abstract (arXiv)

We study differentially private stochastic convex optimization (DP-SCO) under user-level privacy, where each user may hold multiple data items. Existing work for user-level DP-SCO either requires super-polynomial runtime [Ghazi et al. (2023)] or requires the number of users to grow polynomially with the dimensionality of the problem with additional strict assumptions [Bassily et al. (2023)]. We develop new algorithms for user-level DP-SCO that obtain optimal rates for both convex and strongly convex functions in polynomial time and require the number of users to grow only logarithmically in the dimension. Moreover, our algorithms are the first to obtain optimal rates for non-smooth functions in polynomial time. These algorithms are based on multiple-pass DP-SGD, combined with a novel private mean estimation procedure for concentrated data, which applies an outlier removal step before estimating the mean of the gradients.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 23 of its 39 references that are in the map. First posted on arXiv 7 Nov 2023.

Builds on

23 of 39 references.

References · 23

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  3. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  5. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  6. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  7. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  8. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  9. 2021Learning with User-Level Privacycited by 72
  10. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  11. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  12. 2020Learning discrete distributions: user vs item-level privacycited by 41
11 more
  1. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  2. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  3. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21
  4. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 20
  5. 2022Discrete Distribution Estimation under User-level Local Differential Privacycited by 17
  6. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  7. 2022Private Convex Optimization in General Normscited by 13
  8. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
  9. 2023User-Level Differential Privacy With Few Examples Per Usercited by 12
  10. 2021User-Level Private Learning via Correlated Samplingcited by 9
  11. 2023On User-Level Private Convex Optimizationcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 7; 2025: 4; 2026: 1.

12 papers.

  1. 2024Fine-Tuning Large Language Models with User-Level Differential Privacycited by 29
  2. 2024Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuningcited by 24
  3. 2025Towards User-level Private Reinforcement Learning with Human Feedbackcited by 14
  4. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  5. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  6. 2024Faster Algorithms for User-Level Private Stochastic Convex Optimizationcited by 4
  7. 2024Learning with User-Level Local Differential Privacycited by 3
  8. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  9. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  10. 2025Private Geometric Median in Nearly-Linear Timecited by 1
  11. 2024Preserving Expert-Level Privacy in Offline Reinforcement Learningcited by 0
  12. 2026Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacycited by 0