Privacy-preserving Prediction

Abstract

Ensuring differential privacy of models learned from sensitive user data is an important goal that has been studied extensively in recent years. It is now known that for some basic learning problems, especially those involving high-dimensional data, producing an accurate private model requires much more data than learning without privacy. At the same time, in many applications it is not necessary to expose the model itself. Instead users may be allowed to query the prediction model on their inputs only through an appropriate interface. Here we formulate the problem of ensuring privacy of individual predictions and investigate the overheads required to achieve it in several standard models of classification and regression. We first describe a simple baseline approach based on training several models on disjoint subsets of data and using standard private aggregation techniques to predict. We show that this approach has nearly optimal sample complexity for (realizable) PAC learning of any class of Boolean functions. At the same time, without strong assumptions on the data distribution, the aggregation step introduces a substantial overhead. We demonstrate that this overhead can be avoided for the well-studied class of thresholds on a line and for a number of standard settings of convex regression. The analysis of our algorithm for learning thresholds relies crucially on strong generalization guarantees that we establish for all differentially private prediction algorithms.

arXiv commentAccepted for presentation at Conference on Learning Theory (COLT) 2018

References in corpus (2)

• Model-Agnostic Private Learning via Stability
• Generalization for Adaptively-chosen Estimators via Stable Median

Cited by in corpus (13)

• When Machine Learning Meets Privacy: A Survey and Outlook
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• A survey of algorithmic recourse: definitions, formulations, solutions, and prospects
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Adversarial Neural Network Inversion via Auxiliary Knowledge Alignment
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• PAC learning with stable and private predictions
• The Trade-Offs of Private Prediction
• PrivGen: Preserving Privacy of Sequences Through Data Generation
• An Extension of Fano's Inequality for Characterizing Model Susceptibility to Membership Inference Attacks
• Developing Non-Stochastic Privacy-Preserving Policies Using Agglomerative Clustering
• A Tight Lower Bound for Uniformly Stable Algorithms