RECORD
PAC learning with stable and private predictions
Machine Learning · Submitted 24 Nov 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Here we demonstrate several general approaches to stable and private prediction that either eliminate or significantly reduce the overhead.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We study binary classification algorithms for which the prediction on any point is not too sensitive to individual examples in the dataset. Specifically, we consider the notions of uniform stability (Bousquet and Elisseeff, 2001) and prediction privacy (Dwork and Feldman, 2018). Previous work on these notions shows how they can be achieved in the standard PAC model via simple aggregation of models trained on disjoint subsets of data. Unfortunately, this approach leads to a significant overhead in terms of sample complexity. Here we demonstrate several general approaches to stable and private prediction that either eliminate or significantly reduce the overhead. Specifically, we demonstrate that for any class $C$ of VC dimension $d$ there exists a $\gamma$-uniformly stable algorithm for learning $C$ with excess error $\alpha$ using $\tilde O(d/(\alpha\gamma) + d/\alpha^2)$ samples. We also show that this bound is nearly tight. For $\epsilon$-differentially private prediction we give two new algorithms: one using $\tilde O(d/(\alpha^2\epsilon))$ samples and another one using $\tilde O(d^2/(\alpha\epsilon) + d/\alpha^2)$ samples. The best previously known bounds for these problems are $O(d/(\alpha^2\gamma))$ and $O(d/(\alpha^3\epsilon))$, respectively.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study binary classification algorithms for which the prediction on any point is not too sensitive to individual examples in the dataset. | background 0.56 | 0.25 | 0.04 | asserted 0.92 |
| s1 | Specifically, we consider the notions of uniform stability (Bousquet and Elisseeff, 2001) and prediction privacy (Dwork and Feldman, 2018). | background 0.99 | 0.10 | 0.03 | asserted 0.92 |
| s2 | Previous work on these notions shows how they can be achieved in the standard PAC model via simple aggregation of models trained on disjoint subsets of data. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s3 | Unfortunately, this approach leads to a significant overhead in terms of sample complexity. | gap 0.60 | 0.14 | 0.02 | asserted 1.00 |
| s4 | Here we demonstrate several general approaches to stable and private prediction that either eliminate or significantly reduce the overhead. | contribution 1.00 | 0.93 | 0.69 | asserted 1.00 |
| s5 | Specifically, we demonstrate that for any class $C$ of VC dimension $d$ there exists a $\gamma$-uniformly stable algorithm for learning $C$ with excess error $\alpha$ using $\tilde O(d/(\alpha\gamma) + d/\alpha^2)$ samples. | result 0.94 | 0.95 | 0.46 | asserted 1.00 |
| s6 | We also show that this bound is nearly tight. | result 0.88 | 0.89 | 0.09 | asserted 0.99 |
| s7 | For $\epsilon$-differentially private prediction we give two new algorithms: one using $\tilde O(d/(\alpha^2\epsilon))$ samples and another one using $\tilde O(d^2/(\alpha\epsilon) + d/\alpha^2)$ samples. | result 0.64 | 0.96 | 0.20 | asserted 1.00 |
| s8 | The best previously known bounds for these problems are $O(d/(\alpha^2\gamma))$ and $O(d/(\alpha^3\epsilon))$, respectively. | background 0.59 | 0.06 | 0.12 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We study binary classification algorithms for which the prediction on any point is not too sensitive to individual examples in the dataset. Specifically, we consider the notions of uniform stability (Bousquet and Elisseeff, 2001) and prediction privacy (Dwork and Feldman, 2018). Previous work on these notions shows how they can be achieved in the standard PAC model via simple aggregation of models trained on disjoint subsets of data. Unfortunately, this approach leads to a significant overhead in terms of sample complexity. Here we demonstrate several general approaches to stable and private prediction that either eliminate or significantly reduce the overhead. Specifically, we demonstrate that for any class $C$ of VC dimension $d$ there exists a $\gamma$-uniformly stable algorithm for learning $C$ with excess error $\alpha$ using $\tilde O(d/(\alpha\gamma) + d/\alpha^2)$ samples. We also show that this bound is nearly tight. For $\epsilon$-differentially private prediction we give two new algorithms: one using $\tilde O(d/(\alpha^2\epsilon))$ samples and another one using $\tilde O(d^2/(\alpha\epsilon) + d/\alpha^2)$ samples. The best previously known bounds for these problems are $O(d/(\alpha^2\gamma))$ and $O(d/(\alpha^3\epsilon))$, respectively.
Human review
How the literature uses it
4 arXiv papers cite this in 9 sentences
Papers citing it · 3 sentences without a confident label
Compares with it 1 paper
-
In an independent work, [ref] further study the connections between uniform stability and differential privacy in the context of PAC learning, and give a new algorithm that yields a sample complexity bound of $≈()/α^2 + ()^2/ α$ in the single-query setting.
Privately Answering Classification Queries in the Agnostic PAC Model · Related work · 0.93
Cites it as background 3 papers
-
Private prediction methods [ref] perturb the predictions of non-private models to obfuscate any information that can be inferred about the data used to trained those models.
The Trade-Offs of Private Prediction · Introduction · 0.88
-
Starting with Kasiviswanathan et al.'s work [ref] , the line of research presenting the details of private learning process from privacy based on empirical risk minimization [ref] , to prediction [ref] , Bayesian inference [ref] and the multi-armed bandit [ref] .
More Than Privacy: Applying Differential Privacy in Key Areas of Artificial Intelligence · Private machine learning · 0.96
-
There is a long line of work [ref] on proving generalization from stability – specifically, stability with respect to the loss.
Reasoning About Generalization via Conditional Mutual Information · Uniform Stability · 0.98
What it cites · 7 sentences without a confident label
Uses the method or tool of 1 paper
-
The function output by this step is used to re-label $S$, and the result is used as a training set for the private prediction algorithm from [ref] that assumes a realizable setting.
Privacy-preserving Prediction · Our contribution · 0.98
Compares with 1 paper
-
The only known result in which learning with $$-private prediction requires fewer samples than $$-DP learning for all $α$ is the algorithm for learning thresholds on a line with sample complexity of $Õ(1/(α) + 1/α^2)$ [ref] .
Privacy-preserving Prediction · Our contribution · 0.92
Cites as support 2 papers
-
For example, for models trained using typical deep learning algorithms, such access allows to infer whether a point $x$ is present in the training dataset with high accuracy [ref] and to complete sentences used in the training data [ref] .
Towards Measuring Membership Privacy · Introduction · 0.98
-
For example, for models trained using typical deep learning algorithms, such access allows to infer whether a point $x$ is present in the training dataset with high accuracy [ref] and to complete sentences used in the training data [ref] .
Towards Demystifying Membership Inference Attacks · Introduction · 0.98
Cites as background 2 papers
-
Prediction privacy was defined by [ref] to study privacy-preserving learning in the setting where the description of the model trained on sensitive data is not accessible to the (potentially adversarial) users.
Privacy-preserving Prediction · Introduction · 0.98
-
Stability is a classical approach for understanding and analysis of generalization bounds [ref] .
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate · Introduction · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.