mlsanityData to 7 Oct 2026

Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds

arXiv 1405.7085 ↗First posted 27 May 2014cs.LG cs.CR stat.MLcited by 104

Not on the map. Why?

Abstract (arXiv)

In this paper, we initiate a systematic investigation of differentially private algorithms for convex empirical risk minimization. Various instantiations of this problem have been studied before. We provide new algorithms and matching lower bounds for private ERM assuming only that each data point's contribution to the loss function is Lipschitz bounded and that the domain of optimization is bounded. We provide a separate set of algorithms and matching lower bounds for the setting in which the loss functions are known to also be strongly convex. Our algorithms run in polynomial time, and in some cases even match the optimal non-private running time (as measured by oracle complexity). We give separate algorithms (and lower bounds) for (ε,0)- and (ε,δ)-differential privacy; perhaps surprisingly, the techniques used for designing optimal algorithms in the two cases are completely different. Our lower bounds apply even to very simple, smooth function families, such as linear and quadratic functions. This implies that algorithms from previous work can be used to obtain optimal error rates, under the additional assumption that the contributions of each data point to the loss function is smooth. We show that simple approaches to smoothing arbitrary loss functions (in order to apply previous techniques) do not yield optimal error rates. In particular, optimal algorithms were not previously known for problems such as training support vector machines and the high-dimensional median.

Key facts. Cited by 104 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 May 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 41; 2022: 37; 2023: 16; 2024: 1; 2025: 5; 2026: 4.

104 papers.

Sort:

By area:

  1. 2021Large Language Models Can Be Strong Differentially Private Learnerscited by 405
  2. 2021Opacus: User-Friendly Differential Privacy Library in PyTorchcited by 375
  3. 2021A Field Guide to Federated Optimizationcited by 312
  4. 2021Machine Unlearning via Algorithmic Stabilitycited by 128
  5. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 127
  6. 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
  7. 2021Trustworthy AI: A Computational Perspectivecited by 93
  8. 2021Large Scale Private Learning via Low-rank Reparametrizationcited by 87
  9. 2021Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learningcited by 86
  10. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  11. 2021The Skellam Mechanism for Differentially Private Federated Learningcited by 66
  12. 2022Mixed Differential Privacy in Computer Visioncited by 53
38 more
  1. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  2. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  3. 2022Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learningcited by 48
  4. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  5. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  6. 2022Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)cited by 45
  7. 2022Composition of Differential Privacy & Privacy Amplification by Subsamplingcited by 42
  8. 2022Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimizationcited by 35
  9. 2021Fast and Memory Efficient Differentially Private-SGD via JL Projectionscited by 29
  10. 2022Amplifying Membership Exposure via Data Poisoningcited by 29
  11. 2022Reconstructing Training Data from Model Gradient, Provablycited by 27
  12. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  13. 2021The Role of Adaptive Optimizers for Honest Private Hyperparameter Selectioncited by 25
  14. 2022CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learningcited by 24
  15. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  16. 2022Differentially Private SGDA for Minimax Problemscited by 23
  17. 2023Correlated Noise Provably Beats Independent Noise for Differentially Private Learningcited by 23
  18. 2023Selective Pre-training for Private Fine-tuningcited by 22
  19. 2021Not all noise is accounted equally: How differentially private learning benefits from large sampling ratescited by 21
  20. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  21. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 19
  22. 2022How Much Privacy Does Federated Learning with Secure Aggregation Guarantee?cited by 19
  23. 2023Practical Differentially Private and Byzantine-resilient Federated Learningcited by 18
  24. 2021Differential Privacy and Byzantine Resilience in SGD: Do They Add Up?cited by 17
  25. 2021Wide Network Learning with Differential Privacycited by 17
  26. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17
  27. 2021Shuffle Private Stochastic Convex Optimizationcited by 17
  28. 2021On the Renyi Differential Privacy of the Shuffle Modelcited by 16
  29. 2022Training Large-Vocabulary Neural Language Models by Private Federated Learning for Resource-Constrained Devicescited by 16
  30. 2023Unlocking Accuracy and Fairness in Differentially Private Image Classificationcited by 16
  31. 2025Synthesizing Privacy-Preserving Text Data via Finetuning without Finetuning Billion-Scale LLMscited by 15
  32. 2022Bounding Membership Inferencecited by 14
  33. 2022Private Convex Optimization in General Normscited by 13
  34. 2023Amplitude-Varying Perturbation for Balancing Privacy and Utility in Federated Learningcited by 13
  35. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  36. 2021Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Ratescited by 10
  37. 2021Towards Understanding the Impact of Model Size on Differential Private Classificationcited by 10
  38. 2022Differentially Private Regression with Unbounded Covariatescited by 10

50 most cited of 104 All 104 (JSON)