Model-Agnostic Private Learning via Stability

Raef Bassily, Om Thakkar, Abhradeep ThakurtaarXiv 2018 · OpenReview

Abstract

We design differentially private learning algorithms that are agnostic to the learning model. Our algorithms are interactive in nature, i.e., instead of outputting a model based on the training data, they provide predictions for a set of $m$ feature vectors that arrive online. We show that, for the feature vectors on which an ensemble of models (trained on random disjoint subsets of a dataset) makes consistent predictions, there is almost no-cost of privacy in generating accurate predictions for those feature vectors. To that end, we provide a novel coupling of the distance to instability framework with the sparse vector technique. We provide algorithms with formal privacy and utility guarantees for both binary/multi-class classification, and soft-label classification. For binary classification in the standard (agnostic) PAC model, we show how to bootstrap from our privately generated predictions to construct a computationally efficient private learner that outputs a final accurate hypothesis. Our construction - to the best of our knowledge - is the first computationally efficient construction for a label-private learner. We prove sample complexity upper bounds for this setting. As in non-private sample complexity bounds, the only relevant property of the given concept class is its VC dimension. For soft-label classification, our techniques are based on exploiting the stability properties of traditional learning algorithms, like stochastic gradient descent (SGD). We provide a new technique to boost the average-case stability properties of learning algorithms to strong (worst-case) stability properties, and then exploit them to obtain private classification algorithms. In the process, we also show that a large class of SGD methods satisfy average-case stability properties, in contrast to a smaller class of SGD methods that are uniformly stable as shown in prior work.

Introduction

Standard approaches to differential privacy (DP) in machine learning often face a "curse of dimensionality." To guarantee privacy, traditional methods typically add noise that scales with the number of features or the complexity of the model. While effective for simple linear models, this approach often fails for modern, over-parameterized deep learning models. Furthermore, many existing DP algorithms require the underlying optimization problem to be convex—an assumption that rarely holds for neural networks.

This paper introduces a new framework for differentially private machine learning that is model-agnostic, meaning it works with almost any model, including non-convex deep neural networks. By combining ensemble "stability" with the Sparse Vector Technique (SVT), the authors create a framework that provides accurate predictions where the privacy cost primarily scales with the number of times the models disagree, rather than the total number of queries.

The Stability-Based Framework

The core of the proposed approach is the concept of Stability. In the context of DP, a learning algorithm is considered stable if its output does not change significantly when a single individual's data is added to or removed from the training set.

Sub-sample and Aggregate ($\mathcal{A}_{\text{subSamp}}$)

The primary algorithm, $\mathcal{A}_{\text{subSamp}}$, operates through a multi-step process:

  1. Ensemble Creation: The private dataset is partitioned into $k$ disjoint subsets. A non-private "teacher" model is trained independently on each subset.
  2. Stability Check: When a new query (a feature vector) arrives, the algorithm evaluates the predictions of all $k$ teachers. If the teachers reach a strong consensus, the prediction is deemed "stable."
  3. SVT Integration: The researchers utilize the Sparse Vector Technique to manage the privacy budget. Instead of paying a privacy cost for every query, the budget is only significantly impacted when the ensemble is unstable (i.e., when the teachers disagree). This allows for "privacy for free" on queries where the model is naturally consistent.

Label-Private Learning and Knowledge Transfer

A significant contribution of this work is the construction of the first computationally efficient "label-private" learner. In label privacy, only the labels of the training data are considered sensitive, while the feature vectors are assumed to be public or non-sensitive.

To create a standalone, non-interactive model, the authors employ a Knowledge Transfer mechanism:

  • The private ensemble is used to generate labels for a set of public, unlabeled data.
  • A "student" model is then trained on this newly labeled public dataset.
  • Due to the "post-processing" property of differential privacy, the resulting student model inherits the privacy guarantees of the labeling process, making it a fully private learner.

Soft-Label Classification and SGD Stability

For soft-label classification, where outputs are continuous values (like probabilities) rather than discrete classes, the paper explores the stability of Stochastic Gradient Descent (SGD). The authors demonstrate that a wide class of SGD methods are stable "on-average."

To bridge the gap between average-case stability and the rigorous worst-case stability required for DP, they introduce a novel "shifted discretization" technique. This method boosts the inherent stability of SGD, allowing it to be used within their private prediction framework without requiring the strict uniform stability assumptions found in prior literature.

Theoretical Results and Sample Complexity

As a theoretical study, the paper provides formal proofs and sample complexity bounds rather than empirical benchmarks. The findings show that the sample complexity of their private learner depends primarily on the VC dimension (Vapnik–Chervonenkis dimension) of the model class. This mirrors the behavior of non-private learners, suggesting that the overhead for privacy is manageable.

In the "realizable" case (where a perfect classifier exists), the number of samples required for privacy is only a factor of $\tilde{O}(\sqrt{V/\alpha})$ worse than the non-private version, where $V$ is the VC dimension and $\alpha$ is the target accuracy. This demonstrates that for stable models, high-utility private learning is achievable with reasonable data requirements.

Limitations and Future Directions

While the framework is powerful, its utility is bounded by the stability of the underlying models. If the data is highly noisy or the model class is inherently unstable, the SVT threshold ($T$) may be reached quickly, causing the algorithm to stop answering queries to protect privacy.

Additionally, in the "agnostic" case (where no perfect classifier exists), the accuracy of the final model currently has a suboptimal dependency on the best possible error. Future work may focus on improving these constant factor overheads and reducing the reliance on public unlabeled data for the knowledge transfer stage.

Summary updated

Abstract

We design differentially private learning algorithms that are agnostic to the learning model. Our algorithms are interactive in nature, i.e., instead of outputting a model based on the training data, they provide predictions for a set of $m$ feature vectors that arrive online. We show that, for the feature vectors on which an ensemble of models (trained on random disjoint subsets of a dataset) makes consistent predictions, there is almost no-cost of privacy in generating accurate predictions for those feature vectors. To that end, we provide a novel coupling of the distance to instability framework with the sparse vector technique. We provide algorithms with formal privacy and utility guarantees for both binary/multi-class classification, and soft-label classification. For binary classification in the standard (agnostic) PAC model, we show how to bootstrap from our privately generated predictions to construct a computationally efficient private learner that outputs a final accurate hypothesis. Our construction - to the best of our knowledge - is the first computationally efficient construction for a label-private learner. We prove sample complexity upper bounds for this setting. As in non-private sample complexity bounds, the only relevant property of the given concept class is its VC dimension. For soft-label classification, our techniques are based on exploiting the stability properties of traditional learning algorithms, like stochastic gradient descent (SGD). We provide a new technique to boost the average-case stability properties of learning algorithms to strong (worst-case) stability properties, and then exploit them to obtain private classification algorithms. In the process, we also show that a large class of SGD methods satisfy average-case stability properties, in contrast to a smaller class of SGD methods that are uniformly stable as shown in prior work.
BibTeX
@misc{bassily2018model,
  author = {Raef Bassily and Om Thakkar and Abhradeep Thakurta},
  title = {{Model-Agnostic Private Learning via Stability}},
  year = {2018},
  eprint = {1803.05101},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.05101},
}
Figure