PaperlayerView exact revision on arXiv

Source-linked AI summary

Differential Privacy and Machine Learning: a Survey and Review

Zhanglong Ji, Zachary C. Lipton, Charles Elkan

arXiv:1412.7584v1cs.LGcs.CRcs.DB

TL;DR

The paper examines how to reconcile machine learning’s utility goals with privacy when analyzing sensitive data. It surveys privacy-preserving learning and data-release mechanisms, reviews theoretical results, and highlights conditions, trade-offs, and open questions surrounding utility under differential privacy.

  • Problem

    Machine learning seeks useful information from data while privacy requires concealing individual information, creating a tension that matters for sensitive applications such as medical research.

  • Method

    The survey organizes differentially private machine-learning algorithms by task, reviews private data-release mechanisms, explains their operation, and compares theoretical guarantees.

  • Results

    The survey reports that differential privacy can be free for certain learning models, including regularized logistic regression and linear SVM, where privacy noise is O(1/n) versus sample randomness O(1/√n).

  • Takeaways & Limitations

    Reducing noise generally favors one-time addition over repeated addition, while iterative training-time noise can lead to significantly worse performance.

  • Takeaways & Limitations

    Asymptotic accuracy matching non-private estimators is not guaranteed for models that do not converge to a fixed point or have varying numbers of features.

Abstract

from arXiv · show

The objective of machine learning is to extract useful information from data, while privacy is preserved by concealing information. Thus it seems hard to reconcile these competing interests. However, they frequently must be balanced when mining sensitive data. For example, medical research represents an important application where it is necessary both to extract useful information and protect patient privacy. One way to resolve the conflict is to extract general characteristics of whole populations without disclosing the private information of individuals. In this paper, we consider differential privacy, one of the most popular and powerful definitions of privacy. We explore the interplay between machine learning and differential privacy, namely privacy-preserving machine learning algorithms and learning-based data release mechanisms. We also describe some theoretical results that address what can be learned differentially privately and upper bounds of loss functions for differentially private algorithms. Finally, we present some open questions, including how to incorporate public data, how to deal with missing data in private datasets, and whether, as the number of observed samples grows arbitrarily large, differentially private machine learning algorithms can be achieved at no cost to utility as compared to corresponding non-differentially private algorithms.

0.1 Prior Work

Prior surveys cover differential privacy and data science, but this survey focuses specifically on their interaction with machine learning and organizes methods by task.

  • Earlier surveys emphasize statistical estimators or discuss high-level interactions between differential privacy and machine learning.
  • This survey studies methods for making machine learning algorithms differentially private across classification, regression, clustering, and dimensionality reduction.
  • It also reviews differentially private data-release mechanisms because their mechanisms and outputs support differentially private machine learning.
  • The survey explains mechanisms, compares their theoretical guarantees, and follows with general theoretical results and discussion.

1 Differential Privacy

Differential privacy formalizes protection by requiring outputs to remain similar when one sample changes. The section introduces mechanisms for private queries, adaptive sensitivity, model selection, and mechanism composition, while noting utility and leakage trade-offs.

  • Differential privacy requires a mechanism’s output to be robust to any change of one sample, thereby protecting individual privacy.
  • Smaller ε and δ make neighboring output distributions closer and provide stronger privacy protection, while δ > 0 permits a small chance of information leakage.
  • A common heuristic sets δ ∈ o(1/n), because larger δ can allow expected leakage of nδ samples.
  • The Laplacian mechanism adds noise calibrated to query sensitivity, while Gaussian noise reduces very large deviations but generally provides only (ε, δ)-differential privacy.
  • The exponential mechanism privately selects a high-scoring element from a candidate set, and composition can worsen utility because privacy budgets or sample sizes are divided.
  • Smooth sensitivity adapts noise to the database rather than worst-case sensitivity, reducing noise while using the weaker (ε, δ)-privacy guarantee.

2 Machine Learning

Machine learning selects models that capture useful information from data, while differential privacy aims to limit the influence of any individual sample. The section organizes private learning approaches and explains why their utility comparisons depend on differing evaluation choices and application needs.

  • 2 Machine Learning: Machine learning training selects the model that best fits a dataset for prediction, interpretation, or discovering structure.Models support regression, classification, clustering, and dimensionality reduction tasks.
  • 2.1 Performance Measurement: Utility analyses differ in their definitions of the true model, model distance, and closeness, limiting direct comparisons between mechanisms.True models may be noiseless outputs on training data or optimal models under the true distribution; distances may use target functions or parameters.
  • 2.1 Performance Measurement: Closeness may mean convergence without a rate, bounded convergence rates, worst-case guarantees, or expected difference.The (α, β)-usefulness criterion guarantees error below α with probability at least 1 −β.
  • 2.1 Performance Measurement: Mechanism choice depends on application-specific tolerance for privacy leakage and utility trade-offs.A mechanism allowing a small leakage probability may be preferred in one application, while pure ε-differential privacy may be preferred in another.
  • 2.2 Differentially Private Machine Learning: Private learning mechanisms include perturbing a trained model, perturbing objective functions, sample-and-aggregate procedures, and other specialized constructions.Some methods apply Laplacian or exponential mechanisms to models or iterative parameters, while objective perturbation adds noise to target functions.
  • 2.2 Differentially Private Machine Learning: Output and objective perturbation usually require bounded sample spaces, whereas sample-and-aggregate avoids this limitation but usually provides (ε, δ)-differential privacy.For unbounded spaces, preprocessing by independent truncation can support ε-differential privacy.

3 Differentially Private Supervised Learning

Differentially private supervised learning adapts common classifiers and regressors by protecting the statistics, objectives, parameters, or kernels used during training. The surveyed mechanisms rely on assumptions such as bounded data, and their analyses provide utility guarantees for some models.

  • Naive Bayes: Naive Bayes privately estimates label and feature statistics, requiring bounded feature values to calibrate noise.The mechanism assumes all feature values are bounded by a known number and adds noise to the information needed to compute the model.
  • Naive Bayes: Adding noise directly to counts is preferable to perturbing logarithms because logarithmic transformation does not reduce small-count noise and increases large-count noise.The cited analysis contrasts the sensitivity and resulting noise behavior of transformed and direct counts.
  • Linear Regression: For linear regression, one mechanism approximates the square-loss objective with a low-order Taylor expansion, perturbs its coefficients, and minimizes the approximation.The construction assumes a bounded sample space and uses the Laplacian mechanism after computing coefficient sensitivities.
  • SVM and Logistic Regression: Output and objective perturbation provide ε-differentially private mechanisms for strongly convex, differentiable losses whose derivatives have bounded sensitivity.The stated conditions apply to linear SVM and other models satisfying them, including regularized logistic regression under bounded sample spaces.
  • SVM and Logistic Regression: O(log(1/β)/(αε)) samples suffice for the objective-perturbation mechanism to achieve (α, β)-usefulness and ε-differential privacy.Usefulness means the private model’s true loss is within α of the true model’s loss with probability greater than 1 −β.
  • Kernel SVM: Kernel SVM requires different privacy techniques because its model contains all training data.One surveyed method handles translation-invariant kernels, while another applies to all RKHS kernels.

4 Differentially Private Unsupervised Learning

Private k-means uses sample and aggregate to estimate cluster centers while protecting the aggregation step. The approach assumes well-separated data, and its noise bound is not directly tied to the total dataset size.

  • 4.1 K-means clustering: The private k-means mechanism randomly splits data, runs non-private k-means on subsets, and adds noise while aggregating the resulting models.The sample-and-aggregate framework is used to construct an (ε, δ)-differentially private algorithm.
  • 4.1 K-means clustering: The mechanism assumes clusters are well separated so they can be estimated accurately from a small number of samples.This property is required by the sample step of the framework.
  • 4.1 K-means clustering: With bounded sample space and enough samples, the added noise has a bound that is not directly related to the dataset’s number of samples.The method can use k-means modifications such as k-means++ when they preserve small-sample estimability.

5 Differentially Private Dimensionality Reduction

Differentially private dimensionality reduction targets feature selection and principal components, where lower-dimensional representations can reduce sensitivity. The surveyed PCA mechanisms privately select eigenvectors iteratively or jointly and provide utility conditions for some outputs.

  • 5 Dimensionality Reduction: Lower-dimensional representations are desirable because they reduce model degrees of freedom, overfitting risk, and often sensitivity.Feature selection retains a subset of features, while PCA learns a projection explaining as much variance as possible.
  • 5.1 Feature Selection: PrivateKD greedily selects categorical features using a score that counts how many cross-class sample pairs the selected features distinguish.The method assumes finite possible values for all categorical features.
  • 5.1 Feature Selection: A stable feature-selection algorithm can privately recover the correct selection with probability 1 −β when changing ε samples does not change the selection result.A related bootstrap-based mechanism releases the most frequently selected feature set when the correct output is sufficiently more frequent.
  • 5.2 Principal Component Analysis: PCA mechanisms iteratively select the largest eigenvector and remove its component, using either the power method or the exponential mechanism.Another mechanism selects the k largest eigenvectors simultaneously with an exponential mechanism over matrix projections.
  • 5.2 Principal Component Analysis: The power-method guarantee controls the distance from an output vector to the leading eigenvector but provides no direct guarantee on the k eigenvectors.Noise prevents arbitrary-accuracy convergence, so the mechanism outputs each vector after a fixed number of iterations.
  • 5.2 Principal Component Analysis: For the exponential-mechanism PCA method, E[vT Av] ≥(1 −δ)λ1 when λ1 > O(ln(1/δ)/(nεδ)).A separate bound controls the largest eigenvalue of the residual after k-rank approximation under a stronger eigenvalue condition.

6 Statistical Estimators

Differentially private statistical estimators protect individual information while approximating population quantities and learning models. The surveyed mechanisms use robustness, sensitivity control, partitioning, and noisy estimation, with accuracy and privacy depending on explicit conditions.

  • Differentially private estimators are needed because estimates of population quantities can leak information about individuals, especially in small datasets or when features are rare.
  • Robust Statistics Estimator: Robust estimation supports privacy by limiting how much the output changes when a small number of samples change.The Propose-Test-Release framework adds Laplacian noise when the statistic is sufficiently stable.
  • Robust Statistics Estimator: A robust linear regression estimator outputs a model with probability 1 −O(n−c ln n) and converges to the true regression parameter as n tends to infinity.
  • Robust Statistics Estimator: If one sample’s effect is bounded by O(1/n) and the estimator’s range is bounded, smooth sensitivity provides bounded error.
  • Robust Statistics Estimator: When the estimator’s range is unbounded across possible distributions, no ǫ-differentially private mechanism can have uniformly bounded error.
  • Point Estimator: Private point-estimation mechanisms split data into subsets, estimate parameters, and privately aggregate the subset estimates; unbounded parameter spaces require truncation and yield (ǫ, δ)-differential privacy.
  • Point Estimator: These mechanisms can match non-private estimators asymptotically under sufficient conditions, but no such guarantee holds for some non-convergent models or models with varying feature counts.
  • M-estimator: An M-estimator minimizes a sample-based function, while its private mechanism partitions the sample space, adds Laplacian noise to cell counts, and releases a noisy minimizer.

7 Learning in Private Data Release

The surveyed data-release mechanisms generate privacy-preserving datasets or summaries that retain information useful for machine learning. They rely on partitioning, generative models, public data, private LDA models, and sparsity assumptions, each with corresponding accuracy or noise trade-offs.

  • The survey focuses on data-release mechanisms that are useful for machine learning or based on machine learning algorithms.
  • Partition-based mechanisms: Partition-based mechanisms assume smooth densities, tree-compatible data, or information-preserving partitions, then publish counts for the resulting regions.
  • Non-partition mechanisms: Non-partition mechanisms either privately select a model from a suitable family and generate data from it, or exploit properties such as sparsity.
  • Generative models: Graph-release mechanisms train a generative model, add Laplacian noise to its parameters, and generate a new graph from the noisy model.
  • Generative models: Hierarchical random graph models can require too much noise because their parameter count grows with the number of graph nodes, while direct exponential-mechanism use is difficult without a suitable score function.
  • Public data: Public-data methods assign weights to examples in a smaller similarly structured dataset; under the exact matching assumption, the resulting estimate is asymptotically unbiased.
  • Model-based release: A private LDA-based mechanism first computes a noisy LDA model and then draws a dataset minimizing distance to that model, preserving classification information.
  • Sparsity-based mechanisms: For sparse data matrices, compressive sensing can reduce the Laplacian-noise scale from O(√n/ǫ) to O(log n/ǫ) given n samples.

8 Theoretical Results

Theoretical work studies when learning can remain differentially private and how privacy mechanisms affect loss bounds. The surveyed results establish broad private learnability claims while noting that one mechanism’s bound need not be optimal.

  • If a classification problem is learnable, it can also be learned differentially privately using an exponential mechanism over hypotheses scored by correct classifications.
  • Differentially private learning can be analyzed through PAC-Bayesian bounds for parametrized models with bounded loss functions.
  • The PAC-Bayesian bound upper-bounds the loss function, but other mechanisms may achieve a better bound, so the exponential mechanism is not necessarily optimal.

9 Discussion

The survey identifies strategies for reducing noise in differentially private learning, while highlighting open challenges involving iterative training, public or incomplete data, and privacy’s utility cost.

  • Noise reduction: One-time noise addition is usually better because repeated additions split the privacy budget and can amplify aggregate noise.The survey contrasts adding noise to the training process with adding it to the target function or final model; iterative training noise led to significantly worse performance in its experience.
  • Noise reduction: Lowering global sensitivity can reduce noise, either by approximating queries with less-sensitive components or by modifying the model.Examples include perturbing counts instead of naive Bayes conditional probabilities and replacing kernel SVM or standard regression models with alternatives.
  • Noise reduction: Public data from a similar population can sometimes provide similar or better utility because differential privacy distorts private data.The survey reports that public datasets can enhance the performance of differentially private mechanisms.
  • Noise reduction: Iterative noise addition may be reasonable when each iteration has lower sensitivity than the final model parameters, depending on the training path.The survey notes that the summed sensitivity can be much smaller than parameter sensitivity except in extreme cases, and mentions MCMC-based methods as a possible approach.
  • Open questions: Missing or non-relational medical data remains a practical boundary because transformations can lose information, increase sensitivity, or fail to preserve privacy.The survey calls for mechanisms designed for temporal or structural medical data and incomplete datasets.
  • Open questions: Differential privacy can potentially be achieved at no utility cost when privacy noise is smaller than sample randomness.For cited mechanisms, privacy noise is O(1/n), whereas sample randomness is O(1/√n) under stated model conditions.
Loading 1412.7584v1…