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.

通过利用公共数据来提高私人学习算法的性能，本研究提出了第一种具有计算有效性的算法，以确保在满足与私人样本相关的差分隐私的同时，当私人数据分布足够接近公共数据时也能保证学习效果，并且在函数类可非私密学习时可进行私人学习的证明。

基于公共数据的差分隐私学习的Oracle高效实现