Private PAC Learning May be Harder than Online Learning
- URL: http://arxiv.org/abs/2402.11119v1
- Date: Fri, 16 Feb 2024 22:44:52 GMT
- Title: Private PAC Learning May be Harder than Online Learning
- Authors: Mark Bun, Aloni Cohen, Rathin Desai
- Abstract summary: We show that any concept class of Littlestone dimension $d$ can be privately PAC learned using $mathrmpoly(d)$ samples.
This raises the natural question of whether there might be a generic conversion from online learners to private PAC learners.
- Score: 14.180842831990999
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We continue the study of the computational complexity of differentially
private PAC learning and how it is situated within the foundations of machine
learning. A recent line of work uncovered a qualitative equivalence between the
private PAC model and Littlestone's mistake-bounded model of online learning,
in particular, showing that any concept class of Littlestone dimension $d$ can
be privately PAC learned using $\mathrm{poly}(d)$ samples. This raises the
natural question of whether there might be a generic conversion from online
learners to private PAC learners that also preserves computational efficiency.
We give a negative answer to this question under reasonable cryptographic
assumptions (roughly, those from which it is possible to build
indistinguishability obfuscation for all circuits). We exhibit a concept class
that admits an online learner running in polynomial time with a polynomial
mistake bound, but for which there is no computationally-efficient
differentially private PAC learner. Our construction and analysis strengthens
and generalizes that of Bun and Zhandry (TCC 2016-A), who established such a
separation between private and non-private PAC learner.
Related papers
- When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
A new complexity measure, called the emphspanning capacity, depends solely on the set $Pi$ and is independent of the MDP dynamics.
We show there exists a policy class $Pi$ with a bounded spanning capacity that requires a superpolynomial number of samples to learn.
This reveals a surprising separation for learnability between generative access and online access models.
arXiv Detail & Related papers (2023-10-09T19:40:54Z) - Provable Advantage in Quantum PAC Learning [3.291862617649511]
We show that PAC learners can achieve a generic advantage in quantum learning.
Up to polylogarithmic factors, this is a square root improvement over the classical learning sample complexity.
arXiv Detail & Related papers (2023-09-19T19:26:20Z) - Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
This paper contributes to the study of CPAC learnability by solving three open questions from recent papers.
Firstly, we prove that every CPAC learnable class is contained in a class which is properly CPAC learnable with a sample complexity.
Secondly, we show that there exists a decidable class of hypothesis which is properly learnable, but only with uncomputably fast growing sample complexity.
arXiv Detail & Related papers (2023-02-06T02:52:36Z) - Differentially-Private Bayes Consistency [70.92545332158217]
We construct a Bayes consistent learning rule that satisfies differential privacy (DP)
We prove that any VC class can be privately learned in a semi-supervised setting with a near-optimal sample complexity.
arXiv Detail & Related papers (2022-12-08T11:57:30Z) - Multiclass versus Binary Differentially Private PAC Learning [32.22526322514124]
We show a generic reduction from multiclass differentially private PAC learning to binary private PAC learning.
Our proof extends the notion of $Psi$-dimension defined in work of Ben-David et al. [JCSS '95] to the online setting and explores its general properties.
arXiv Detail & Related papers (2021-07-22T18:06:39Z) - 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) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
We prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $tilde O(d6)$, ignoring privacy and accuracy parameters.
This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2O(d)$ on the sample complexity.
arXiv Detail & Related papers (2020-12-07T18:17:46Z) - Reducing Adversarially Robust Learning to Non-Robust PAC Learning [39.51923275855131]
We give a reduction that can robustly learn any hypothesis class using any non-robust learner.
The number of calls to $mathcalA$ depends logarithmically on the number of allowed adversarial perturbations per example.
arXiv Detail & Related papers (2020-10-22T20:28:35Z) - A Computational Separation between Private Learning and Online Learning [19.001036556917818]
A concept class is privately learnable if and only if it is online learnable.
This equivalence incurs significant losses in both sample and computational efficiency.
We show that, assuming the existence of one-way functions, such an efficient conversion is impossible for pureprivate learners with sample complexity.
arXiv Detail & Related papers (2020-07-11T02:41:54Z) - A Theory of Usable Information Under Computational Constraints [103.5901638681034]
We propose a new framework for reasoning about information in complex systems.
Our foundation is based on a variational extension of Shannon's information theory.
We show that by incorporating computational constraints, $mathcalV$-information can be reliably estimated from data.
arXiv Detail & Related papers (2020-02-25T06:09:30Z)
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.