Bounds on the sample complexity for private learning and private data release

By Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, Kobbi Nissim. 2010

215 citations recorded by the source corpus.

Subfields: 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 Statistical Learning Theory

In Privacy & Security

Citations in the corpus

Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, background): “Another mechanism to amplify privacy is through randomized sampling [BKN10, KLN + 11, Ull17].”
A General Approach to Adding Differential Privacy to Iterative Training Procedures (2018, background): “25 /δ , the mechanism is ( qǫ, qδ ) -differentially private with respect to the full database [Beimel et al., 2014, Dwork and Roth, 2014]. p Importantly, the privacy cost of this mechanism is fully speciﬁed by q together with the privacy tuple ( S, σ ) , where S is an upper bound on the L 2 norm of…”
Privacy Amplification by Iteration (2018, background): “The only systematically studied instance of this phenomenon is privacy ampliﬁcation by sampling [KLN + 08, BBKN14, WFS15, BDRS18, WBK18, ACG + 16].”
Tight Lower Bounds for Differentially Private Selection (2017, methodology): “(ε, δ)differential privacy with δ = 0) lower bounds can be proved using the “packing” technique [38], [39], [40].”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “[3], Chaudhuri and Hsu [9], Beimel et al.”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, background): “A sequence of prior negative results have shown that any mechanism providing overly accurate responses cannot be private (Dinur and Nissim, 2003; Dwork et al., 2007; Dwork and Yekhanin, 2008).”
Learning Differentially Private Language Models Without Losing Accuracy (2017, background): “The main goal of this work is to provide a strong guarantee that the trained model protects the privacy of individuals’ data without undue sacriﬁce in model quality, building upon recent work in applying differential privacy to machine learning [11, 10, 16, 8, 6, 5, 18, 24, 22, 1, 20, 26].”
Minimax Optimal Procedures for Locally Private Estimation (2016, background): “…recent work within the context of classification problems and the “probably approximately correct” framework of statistical learning theory (e.g., Beimel, Kasiviswanathan, and Nissim 2010; Kasiviswanathan et al. 2011) that treats the data as random and aims to recover aspects of the underlying…”
Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences (2018, methodology): “Privacy ampliﬁcation with Poisson sampling was used in [Chaudhuri and Mishra, 2006, Beimel et al., 2010, Kasiviswanathan et al., 2011, Beimel et al., 2014], which considered loose bounds.”
Separating Local & Shuffled Differential Privacy via Histograms (2019, neutral): “Central Θ ( 1 εn min ( log d, log 1δ )) N/A [9, 7, 4, 14]”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “There have also been attempts to explicitly and precisely determine the sample complexity of even simpler query families than k-way conjunctions, such as point functions and interval functions [2, 3, 4].”
Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo (2015, methodology): “Lemma 4.4 in Beimel et al. (2014).)”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, background): “[3], where it is shown that every private proper learner for POINTd requires Ω(d/(αε)) labeled examples.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, neutral): “Central Θ ( 1 ε log ( min ( 1 δ , k ))) [14, 26, 12] Θ (√ k α(2) + √ k α √ ε + k 1/3 α4/3ε2/3 + 1 αε ) [2] Θ ( 1 ε ) [19] *”
Characterizing the sample complexity of private learners (2013, methodology): “Finally, it is conceptually simpler and in particular it avoids the sub-sampling technique used in [3].”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, background): “In particular, Beimel et al. (2013a) characterized the sample complexity of privately learnable problems using a combinatorial condition they call a “Probabilistic Representation”, which basically involves finding a finite, data-independent set of hypotheses to approximate any hypothesis in the clas”
Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget (2018, methodology): “At each iteration, their algorithm perturbs the gradient with Gaussian noise and applies the advanced composition [10] together with privacy amplification result [3] to get an upper bound on the total privacy loss.”