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

By Yu-Xiang Wang, Jing Lei, Stephen E. Fienberg. 2015

108 citations recorded by the source corpus.

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 $(\epsilon,\delta)$-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 $\delta$ needs to be.

Subfields: Artificial Intelligence, Sociology and Political Science, Statistical Learning Theory, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Subsampled Rényi Differential Privacy and Analytical Moments Accountant (2018, methodology): “A side note is that privacy ampliﬁcation is also the key underlying technical tool for characterizing the learnability in statistical learning (Wang et al., 2016) and achieving tight sample complexity bounds for simple function classes (Beimel et al., 2013; Bun et al., 2015).”
Learning Anonymized Representations with Adversarial Neural Networks (2018, background): “In the machine learning literature, [Wasserman and Zhou, 2010] and [Chaudhuri et al., 2011] develop differentially private empirical risk minimization algorithms, and [Bassily et al., 2014] and [Wang et al., 2016] study similar statistical and sample complexity of differentially private procedures.”
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences (2018, methodology): “This setting has been used in [Beimel et al., 2013, Bassily et al., 2014, Wang et al., 2016] with non-tight bounds.”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “[32] and [31] explored the problem from the perspective of learnability and stability.”
Generalization in Adaptive Data Analysis and Holdout Reuse (2015, background): “Connections between stability, empirical risk minimization and differential privacy in the context of learnability have been recently explored in [21].”
The Unintended Consequences of Overfitting: Training Data Inference Attacks (2017, background): “Following the connection between diﬀerential privacy and stability from statistical learning theory [12,13,14,15,16,17], one such factor that has started to emerge [4,7] as a likely culprit is overﬁtting .”
Differentially Private Data Publishing and Analysis: A Survey (2017, background): “Another line of differential privacy research investigates learning problems from the perspective of machine learning theory [67].”
Poission Subsampled Rényi Differential Privacy (2019, background): “…DP algorithms for empirical risk minimization (Bassily et al., 2014) and Bayesian learning (Wang et al., 2015), as well as for studying learning-theoretic questions with differential privacy constraints (Kasiviswanathan et al., 2011; Beimel et al., 2013; Bun et al., 2015; Wang et al., 2016).”
Privacy-Preserving Stochastic Gradual Learning (2018, background): “Unfortunately, large-scale sensitive data are ubiquitous in the real world, such as electronic health record [6], mobile app information [7,8], and genome-wide association database [9,10,11].”
Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting (2017, background): “Following the connection between differential privacy and stability from statistical learning theory [12], [13], [14], [15], [16], [17], one such factor that has started to emerge [4], [7] as a likely culprit is overfitting.”