# Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle

arXiv: https://arxiv.org/abs/1502.06309 · HTML: https://mlsanity.com/paper/1502.06309/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2015.

## Built on by (most cited first, 16 of 16)

- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [Selective Ensembles for Consistent Predictions](https://mlsanity.com/paper/2111.08230/) (2021)
- [On the Privacy Properties of GAN-generated Samples](https://mlsanity.com/paper/2206.01349/) (2022)
- [What You See is What You Get: Principled Deep Learning via Distributional Generalization](https://mlsanity.com/paper/2204.03230/) (2022)
- [Unveiling Privacy, Memorization, and Input Curvature Links](https://mlsanity.com/paper/2402.18726/) (2024)
- [Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learning](https://mlsanity.com/paper/2405.08920/) (2024)
- [A unifying framework for differentially private quantum algorithms](https://mlsanity.com/paper/2307.04733/) (2023)
- [Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms](https://mlsanity.com/paper/2203.03604/) (2022)
- [Samplable Anonymous Aggregation for Private Federated Data Analysis](https://mlsanity.com/paper/2307.15017/) (2023)
- [Curvature Clues: Decoding Deep Learning Privacy with Input Loss Curvature](https://mlsanity.com/paper/2407.02747/) (2024)
- [Generalization Bounds for Stochastic Gradient Langevin Dynamics: A Unified View via Information Leakage Analysis](https://mlsanity.com/paper/2112.08439/) (2021)
- [Stability and L2-penalty in Model Averaging](https://mlsanity.com/paper/2311.13827/) (2023)
- [On the ERM Principle in Meta-Learning](https://mlsanity.com/paper/2411.17898/) (2024)
- [Learning to Collaborate via Structures: Cluster-Guided Item Alignment for Federated Recommendation](https://mlsanity.com/paper/2602.21957/) (2026)
- [Dangerous Liaisons of Convex Learning and Non-Affine Aggregation](https://mlsanity.com/paper/2606.28123/) (2026)
- [Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustness](https://mlsanity.com/paper/2607.01492/) (2026)

## Abstract (arXiv)

While machine learning has proven to be a powerful data-driven solution to many real-life problems, its use in sensitive domains has been limited due to privacy concerns. A popular approach known as **differential privacy** offers provable privacy guarantees, but it is often observed in practice that it could substantially hamper learning accuracy. In this paper we study the learnability (whether a problem can be learned by any algorithm) under Vapnik's general learning setting with differential privacy constraint, and reveal some intricate relationships between privacy, stability and learnability. In particular, we show that a problem is privately learnable **if an only if** there is a private algorithm that asymptotically minimizes the empirical risk (AERM). In contrast, for non-private learning AERM alone is not sufficient for learnability. This result suggests that when searching for private learning algorithms, we can restrict the search to algorithms that are AERM. In light of this, we propose a conceptual procedure that always finds a universally consistent algorithm whenever the problem is learnable under privacy constraint. We also propose a generic and practical algorithm and show that under very general conditions it privately learns a wide class of learning problems. Lastly, we extend some of the results to the more practical (ε,δ)-differential privacy and establish the existence of a phase-transition on the class of problems that are approximately privately learnable with respect to how small δ needs to be.