mlsanityData to 14 Oct 2026

On User-Level Private Convex Optimization

arXiv 2305.04912 ↗First posted 8 May 2023cs.LG cs.CRcited by 8

Not on the map. Why?

Abstract (arXiv)

We introduce a new mechanism for stochastic convex optimization (SCO) with user-level differential privacy guarantees. The convergence rates of this mechanism are similar to those in the prior work of Levy et al. (2021); Narayanan et al. (2022), but with two important improvements. Our mechanism does not require any smoothness assumptions on the loss. Furthermore, our bounds are also the first where the minimum number of users needed for user-level privacy has no dependence on the dimension and only a logarithmic dependence on the desired excess error. The main idea underlying the new mechanism is to show that the optimizers of strongly convex losses have low local deletion sensitivity, along with an output perturbation method for functions with low local deletion sensitivity, which could be of independent interest.

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

Builds on

11 of 39 references.

References · 11

  1. 2019Advances and Open Problems in Federated Learningcited by 3,046
  2. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  3. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  4. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  5. 2018Privately Learning High-Dimensional Distributionscited by 104
  6. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  7. 2021Learning with User-Level Privacycited by 72
  8. 2022Private Convex Optimization via Exponential Mechanismcited by 49
  9. 2020Learning discrete distributions: user vs item-level privacycited by 41
  10. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  11. 2013Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins [Full Version, Draft 0.1]cited by 13

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 5.

8 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. 2023User-Level Differential Privacy With Few Examples Per Usercited by 12
  4. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  5. 2024Faster Algorithms for User-Level Private Stochastic Convex Optimizationcited by 4
  6. 2023Learning across Data Owners with Joint Differential Privacycited by 1
  7. 2024Better Locally Private Sparse Estimation Given Multiple Samples Per Usercited by 1
  8. 2024Generalizability of experimental studiescited by 0