What Can We Learn Privately?
By Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam D. Smith. 2008
1,627 citations recorded by the source corpus.
Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. We ask: what concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in the contexts where aggregate information is released about a database containing sensitive information about individuals. We present several basic results that demonstrate general feasibility of private learning and relate several models previously studied separately in the contexts of privacy and standard learning.
Subfields: Artificial Intelligence, Safety, Robustness & Interpretability, 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
- Peter Kairouz
- Philip S. Yu
- Jonathan Ullman
- Abhradeep Thakurta
- Percy Liang
- Vitaly Feldman
- Dawn Song
- Kunal Talwar
In Safety, Robustness & Interpretability
- Nicolas Papernot
- Nicholas Carlini
- Dawn Song
- Patrick Drew McDaniel
- Florian Tramèr
- Abhradeep Thakurta
- Prateek Mittal
- Vitaly Feldman
In Privacy & Security
- Jonathan Ullman
- Peter Kairouz
- Abhradeep Thakurta
- Kunal Talwar
- Vitaly Feldman
- Adam D. Smith
- Borja Balle
- Thomas Steinke
Citations in the corpus
- Towards the Science of Security and Privacy in Machine Learning (2016, methodology): “An instance of training data randomization is formalized by local privacy [96].”
- Advances and Open Problems in Federated Learning (2019, methodology): “2, achieving LDP while maintaining utility can be difficult [229, 388].”
- A ug 2 01 4 Local Privacy , Data Processing Inequalities , and Minimax Rates (2018, background): “[37], working within a local differential privacy setting, study Probably-Approximately-Correct (PAC) learning problems and show that the statistical query model [38] and local learning are equivalent up to polynomial changes in the sample size.”
- Pan-Private Uniformity Testing (2019, background): “One solution to this family of problems is local differential privacy [24, 32].”
- Privacy Amplification by Iteration (2018, methodology): “, [3], [8]) require that either data be stored centrally (thus eliminating local differential privacy guarantees) or all-to-all communications.”
- Memory, Communication, and Statistical Queries (2016, background): “…can be learned within this framework (e.g., Blum et al., 1994), including recent results showing inherent connections between statistical query learnability and differential privacy (Gupta et al., 2011; Kasiviswanathan et al., 2011; Balcan and Feldman, 2013) and evolvability (Feldman, 2009).”
- Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “[31]) to run the algorithm for many steps without a significant cost to privacy.”
- Local, Private, Efficient Protocols for Succinct Histograms (2015, background): “Most relevant here are the results of [15, 3] on learning and statistical estimation in the local model.”
- The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “The local model of di ff erential privacy [66, 43] has recently emerged as one of the promising approaches for achieving the goals of enabling data-driven innovation while preserving a rigorous notion of privacy for individuals that also addresses the above challenges.”
- Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity (2018, methodology): “It is instructive to compare our technique with privacy amplification by subsampling [KLN + 08].”
- P3SGD: Patient Privacy Preserving SGD for Regularizing Deep CNNs in Pathological Image Classification (2019, methodology): “The proof can be done using the privacy amplification [18] and the theorem in the prior literature [2].”
- Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible (2017, background): “In the interactive world, LDP is promised with connection to Statistical Query (SQ) model (Kearns, 1998), from its very beginning (Kasiviswanathan et al., 2011).”
- Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “tral server, then encryption and other standard security protocols are a primary line of defense for this type of attack. A stronger guarantee can be achieved by enforcing local differential privacy (Kasiviswanathan et al., 2008; Duchi et al., 2014), where rather than adding noise to the final model,”