PAC learning with stable and private predictions

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.

References in corpus (13)

• Poisoning Attacks against Support Vector Machines
• The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks
• Scalable Private Learning with PATE
• Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data
• Towards Demystifying Membership Inference Attacks
• Towards Measuring Membership Privacy
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Privacy-preserving Prediction
• Limits of Private Learning with Access to Public Data
• Private Query Release Assisted by Public Data
• Privately Answering Classification Queries in the Agnostic PAC Model
• Model-Agnostic Private Learning via Stability
• Subgaussian Tail Bounds via Stability Arguments

Cited by in corpus (3)

• Reasoning About Generalization via Conditional Mutual Information
• The Trade-Offs of Private Prediction
• Realizable Learning is All You Need