Private Everlasting Prediction

• URL: http://arxiv.org/abs/2305.09579v1
• Date: Tue, 16 May 2023 16:26:49 GMT
• Title: Private Everlasting Prediction
• Authors: Moni Naor, Kobbi Nissim, Uri Stemmer, Chao Yan
• Abstract summary: A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points. Research uncovered that private learners may need to exhibit significantly higher sample complexity than non-private learners. We present a generic construction of private everlasting predictors in the PAC model.
• Score: 25.11710918054182
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points while protecting the privacy of the training set [Kasiviswannathan et al., FOCS 2008]. Research uncovered that private learners may need to exhibit significantly higher sample complexity than non-private learners as is the case with, e.g., learning of one-dimensional threshold functions [Bun et al., FOCS 2015, Alon et al., STOC 2019]. We explore prediction as an alternative to learning. Instead of putting forward a hypothesis, a predictor answers a stream of classification queries. Earlier work has considered a private prediction model with just a single classification query [Dwork and Feldman, COLT 2018]. We observe that when answering a stream of queries, a predictor must modify the hypothesis it uses over time, and, furthermore, that it must use the queries for this modification, hence introducing potential privacy risks with respect to the queries themselves. We introduce private everlasting prediction taking into account the privacy of both the training set and the (adaptively chosen) queries made to the predictor. We then present a generic construction of private everlasting predictors in the PAC model. The sample complexity of the initial training sample in our construction is quadratic (up to polylog factors) in the VC dimension of the concept class. Our construction allows prediction for all concept classes with finite VC dimension, and in particular threshold functions with constant size initial training sample, even when considered over infinite domains, whereas it is known that the sample complexity of privately learning threshold functions must grow as a function of the domain size and hence is impossible for infinite domains.

Related papers

• Private Truly-Everlasting Robust-Prediction [22.662255469977598]
  Private Everlasting Prediction (PEP) is a model for differentially private learning in which the learner never publicly releases a hypothesis. PEP provides privacy both for the initial training set and for the endless stream of classification queries. We present two conceptual modifications to the definition of PEP, as well as new constructions exhibiting significant improvements over prior work.
  arXiv  Detail & Related papers  (2024-01-09T02:00:55Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  We prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training.
  arXiv  Detail & Related papers  (2023-10-31T16:13:22Z)
• Training Private Models That Know What They Don't Know [40.19666295972155]
  We find that several popular selective prediction approaches are ineffective in a differentially private setting. We propose a novel evaluation mechanism which isolate selective prediction performance across model utility levels.
  arXiv  Detail & Related papers  (2023-05-28T12:20:07Z)
• Tight Auditing of Differentially Private Machine Learning [77.38590306275877]
  For private machine learning, existing auditing mechanisms are tight. They only give tight estimates under implausible worst-case assumptions. We design an improved auditing scheme that yields tight privacy estimates for natural (not adversarially crafted) datasets.
  arXiv  Detail & Related papers  (2023-02-15T21:40:33Z)
• Differentially Private Online Bayesian Estimation With Adaptive Truncation [1.14219428942199]
  We propose a novel online and adaptive truncation method for differentially private Bayesian online estimation of a static parameter regarding a population. We aim to design predictive queries with small sensitivity, hence small privacy-preserving noise, enabling more accurate estimation while maintaining the same level of privacy.
  arXiv  Detail & Related papers  (2023-01-19T17:53:53Z)
• What Should I Know? Using Meta-gradient Descent for Predictive Feature Discovery in a Single Stream of Experience [63.75363908696257]
  computational reinforcement learning seeks to construct an agent's perception of the world through predictions of future sensations. An open challenge in this line of work is determining from the infinitely many predictions that the agent could possibly make which predictions might best support decision-making. We introduce a meta-gradient descent process by which an agent learns what predictions to make, 2) the estimates for its chosen predictions, and 3) how to use those estimates to generate policies that maximize future reward.
  arXiv  Detail & Related papers  (2022-06-13T21:31:06Z)
• SF-PATE: Scalable, Fair, and Private Aggregation of Teacher Ensembles [50.90773979394264]
  This paper studies a model that protects the privacy of individuals' sensitive information while also allowing it to learn non-discriminatory predictors. A key characteristic of the proposed model is to enable the adoption of off-the-selves and non-private fair models to create a privacy-preserving and fair model.
  arXiv  Detail & Related papers  (2022-04-11T14:42:54Z)
• Conformal prediction for the design problem [72.14982816083297]
  In many real-world deployments of machine learning, we use a prediction algorithm to choose what data to test next. In such settings, there is a distinct type of distribution shift between the training and test data. We introduce a method to quantify predictive uncertainty in such settings.
  arXiv  Detail & Related papers  (2022-02-08T02:59:12Z)
• Private Prediction Sets [72.75711776601973]
  Machine learning systems need reliable uncertainty quantification and protection of individuals' privacy. We present a framework that treats these two desiderata jointly. We evaluate the method on large-scale computer vision datasets.
  arXiv  Detail & Related papers  (2021-02-11T18:59:11Z)
• Set Prediction without Imposing Structure as Conditional Density Estimation [40.86881969839325]
  We propose an alternative to training via set losses by viewing learning as conditional density estimation. Our framework fits deep energy-based models and approximates the intractable likelihood with gradient-guided sampling. Our approach is competitive with previous set prediction models on standard benchmarks.
  arXiv  Detail & Related papers  (2020-10-08T16:49:16Z)

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.