Oracle-Efficient Differentially Private Learning with Public Data
- URL: http://arxiv.org/abs/2402.09483v1
- Date: Tue, 13 Feb 2024 23:40:50 GMT
- Title: Oracle-Efficient Differentially Private Learning with Public Data
- Authors: Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, and Steven Wu
- Abstract summary: We present the first computationally efficient, algorithms to provably leverage public data to learn privately whenever a function class is learnable non-privately.
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.
- Score: 21.771932463130252
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- Privacy-Computation trade-offs in Private Repetition and Metaselection [28.11248357424981]
A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability.
Existing algorithms for these tasks pay either a large overhead in privacy cost, or a large overhead in computational cost.
This is in stark contrast with the non-private setting, where the failure probability falls exponentially in the computational overhead.
arXiv Detail & Related papers (2024-10-22T18:33:02Z) - PILLAR: How to make semi-private learning more effective [12.292092677396347]
In Semi-Supervised Semi-Private (SP) learning, the learner has access to both public unlabelled and private labelled data.
We propose a computationally efficient algorithm that achieves significantly lower private labelled sample complexity and can be efficiently run on real-world datasets.
arXiv Detail & Related papers (2023-06-06T18:45:05Z) - Privacy-preserving Non-negative Matrix Factorization with Outliers [2.84279467589473]
We focus on developing a Non-negative matrix factorization algorithm in the privacy-preserving framework.
We propose a novel privacy-preserving algorithm for non-negative matrix factorisation capable of operating on private data.
We show our proposed framework's performance in six real data sets.
arXiv Detail & Related papers (2022-11-02T19:42:18Z) - Stochastic Differentially Private and Fair Learning [7.971065005161566]
We provide the first differentially private algorithm for fair learning that is guaranteed to converge.
Our framework is flexible enough to permit different fairness, including demographic parity and equalized odds.
Our algorithm can be applied to non-binary classification tasks with multiple (non-binary) sensitive attributes.
arXiv Detail & Related papers (2022-10-17T06:54:57Z) - Personalization Improves Privacy-Accuracy Tradeoffs in Federated
Optimization [57.98426940386627]
We show that coordinating local learning with private centralized learning yields a generically useful and improved tradeoff between accuracy and privacy.
We illustrate our theoretical results with experiments on synthetic and real-world datasets.
arXiv Detail & Related papers (2022-02-10T20:44:44Z) - A Graph Federated Architecture with Privacy Preserving Learning [48.24121036612076]
Federated learning involves a central processor that works with multiple agents to find a global model.
The current architecture of a server connected to multiple clients is highly sensitive to communication failures and computational overloads at the server.
We use cryptographic and differential privacy concepts to privatize the federated learning algorithm that we extend to the graph structure.
arXiv Detail & Related papers (2021-04-26T09:51:24Z) - Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
Local exchange of estimates allows inference of data based on private data.
perturbations chosen independently at every agent, resulting in a significant performance loss.
We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
arXiv Detail & Related papers (2020-10-23T10:35:35Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
We give efficient differentially private algorithms for basic clustering problems.
Our results imply an improved algorithm for the Sample and Aggregate privacy framework.
One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
arXiv Detail & Related papers (2020-08-18T16:22:06Z) - Tighter Generalization Bounds for Iterative Differentially Private
Learning Algorithms [95.73230376153872]
This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps.
We prove that $(varepsilon, delta)$-differential privacy implies an on-average generalization bound for multi-Database learning algorithms.
We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization.
arXiv Detail & Related papers (2020-07-18T09:12:03Z) - New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
We present three new algorithms for constructing differentially private synthetic data.
The algorithms satisfy differential privacy even in the worst case.
Compared to the state-of-the-art method High-Dimensional Matrix Mechanism citeMcKennaMHM18, our algorithms provide better accuracy in the large workload.
arXiv Detail & Related papers (2020-07-10T15:46:05Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.