Oracle-Efficient Differentially Private Learning with Public Data
Adam Block Mark Bun Rathin Desai Abhishek Shetty Steven Wu
Due to statistical lower bounds on the learnability of many function classes
under privacy constraints, there has been recent interest in leveraging public
data to improve the performance of private learning algorithms. In this model,
algorithms must always guarantee differential privacy with respect to the
private samples while also ensuring learning guarantees when the private data
distribution is sufficiently close to that of the public data. Previous work
has demonstrated that when sufficient public, unlabelled data is available,
private learning can be made statistically tractable, but the resulting
algorithms have all been computationally inefficient. In this work, we present
the first computationally efficient, algorithms to provably leverage public
data to learn privately whenever a function class is learnable non-privately,
where our notion of computational efficiency is with respect to the number of
calls to an optimization oracle for the function class. In addition to this
general result, we provide specialized algorithms with improved sample
complexities in the special cases when the function class is convex or when the
task is binary classification.