mlsanityData to 14 Oct 2026

Faster Algorithms for User-Level Private Stochastic Convex Optimization

arXiv 2410.18391 ↗First posted 24 Oct 2024cs.LG cs.CR math.OCcited by 4

Not on the map. Why?

Abstract (arXiv)

We study private stochastic convex optimization (SCO) under user-level differential privacy (DP) constraints. In this setting, there are n users (e.g., cell phones), each possessing m data items (e.g., text messages), and we need to protect the privacy of each user's entire collection of data items. Existing algorithms for user-level DP SCO are impractical in many large-scale machine learning scenarios because: (i) they make restrictive assumptions on the smoothness parameter of the loss function and require the number of users to grow polynomially with the dimension of the parameter space; or (ii) they are prohibitively slow, requiring at least (mn)3/2 gradient computations for smooth losses and (mn)3 computations for non-smooth losses. To address these limitations, we provide novel user-level DP algorithms with state-of-the-art excess risk and runtime guarantees, without stringent assumptions. First, we develop a linear-time algorithm with state-of-the-art excess risk (for a non-trivial linear-time algorithm) under a mild smoothness assumption. Our second algorithm applies to arbitrary smooth losses and achieves optimal excess risk in ≈ (mn)9/8 gradient computations. Third, for non-smooth loss functions, we obtain optimal excess risk in n11/8 m5/4 gradient computations. Moreover, our algorithms do not require the number of users to grow polynomially with the dimension.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 20 of its 37 references that are in the map. First posted on arXiv 24 Oct 2024.

Builds on

20 of 37 references.

References · 20

  1. 2016Membership Inference Attacks against Machine Learning Modelscited by 2,281
  2. 2020Extracting Training Data from Large Language Modelscited by 2,189
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  4. 2013The Composition Theorem for Differential Privacycited by 297
  5. 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 242
  6. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  7. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  8. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  9. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  10. 2021Learning with User-Level Privacycited by 72
  11. 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
  12. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
8 more
  1. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  2. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  3. 2024Why Does Differential Privacy with Large Epsilon Defend Against Practical Membership Inference Attacks?cited by 12
  4. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  5. 2023On User-Level Private Convex Optimizationcited by 8
  6. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  7. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  8. 2024Analyzing Inference Privacy Risks Through Gradients in Machine Learningcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Ratescited by 1
  2. 2026On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCAcited by 1
  3. 2026Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacycited by 0
  4. 2026Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tailscited by 0