Limits of Private Learning with Access to Public Data

By Noga Alon, Raef Bassily, Shay Moran. 2019

58 citations recorded by the source corpus.

We consider learning problems where the training set consists of two types of examples: private and public. The goal is to design a learning algorithm that satisfies differential privacy only with respect to the private examples. This setting interpolates between private learning (where all examples are private) and classical learning (where all examples are public). We study the limits of learning in this setting in terms of private and public sample complexities. We show that any hypothesis class of VC-dimension $d$ can be agnostically learned up to an excess error of $\alpha$ using only (roughly) $d/\alpha$ public examples and $d/\alpha^2$ private labeled examples. This result holds even when the public examples are unlabeled. This gives a quadratic improvement over the standard $d/\alpha^2$ upper bound on the public sample complexity (where private examples can be ignored altogether if the public examples are labeled). Furthermore, we give a nearly matching lower bound, which we prove via a generic reduction from this setting to the one of private learning without public data.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

The Power of the Hybrid Model for Mean Estimation (2018, background): “Recently, theoretical works [9, 10] have explored the limits of this model’s power via lower bounds on the sample complexity of fundamental statistical problems.”
Private Query Release Assisted by Public Data (2020, methodology): “The number of public examples that suffices to construct such approximation is about d/α (Alon et al., 2019a).”
Differentially Private Fine-tuning of Language Models (2021, background): “Finally, other works (both theoretical and experimental) investigate the role of public data in private query release, synthetic data generation, and prediction (Ji & Elkan, 2013; Beimel et al., 2016; Alon et al., 2019; Nandi & Bassily, 2020; Bassily et al., 2020a;b; Liu et al., 2021).”
Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification (2020, methodology): “To implement this subroutine, we follow a long line of work that studies private data analysis with access to an auxiliary public dataset Sh drawn from the same distribution P , for which we don’t need to provide formal privacy guarantee [2, 3, 5, 16, 28].”