PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Empirical Risk Minimization

Kamalika Chaudhuri, Claire Monteleoni, Anand D. Sarwate

arXiv:0912.0071v5cs.LGcs.AIcs.CRcs.DB

TL;DR

Sensitive personal data requires classifiers that preserve privacy while retaining learning utility. The paper develops private regularized-ERM methods, including objective perturbation, and reports that objective perturbation generally outperforms output perturbation in this tradeoff.

  • Problem

    The paper addresses how to learn classifiers from sensitive personal data while protecting individual privacy.

  • Method

    The paper develops output and objective perturbation for regularized ERM, extends privacy-preserving learning to kernels, and adds private parameter tuning for end-to-end guarantees.

  • Results

    Objective perturbation generally outperforms output perturbation in managing the privacy–learning-performance tradeoff, while both methods can approach non-private classification with abundant training data.

  • Takeaways & Limitations

    The study demonstrates a privacy–utility tradeoff for ERM and provides privacy-preserving methods applicable to classifiers and parameter tuning.

  • Takeaways & Limitations

    The methods do not address regularized ERM with non-strongly-convex regularizers such as L1, and objective perturbation currently requires strongly convex regularization and differentiable losses.

Abstract

from arXiv · show

Privacy-preserving machine learning algorithms are crucial for the increasingly common setting in which personal data, such as medical or financial records, are analyzed. We provide general techniques to produce privacy-preserving approximations of classifiers learned via (regularized) empirical risk minimization (ERM). These algorithms are private under the $ε$-differential privacy definition due to Dwork et al. (2006). First we apply the output perturbation ideas of Dwork et al. (2006), to ERM classification. Then we propose a new method, objective perturbation, for privacy-preserving machine learning algorithm design. This method entails perturbing the objective function before optimizing over classifiers. If the loss and regularizer satisfy certain convexity and differentiability criteria, we prove theoretical results showing that our algorithms preserve privacy, and provide generalization bounds for linear and nonlinear kernels. We further present a privacy-preserving technique for tuning the parameters in general machine learning algorithms, thereby providing end-to-end privacy guarantees for the training process. We apply these results to produce privacy-preserving analogues of regularized logistic regression and support vector machines. We obtain encouraging results from evaluating their performance on real demographic and benchmark data sets. Our results show that both theoretically and empirically, objective perturbation is superior to the previous state-of-the-art, output perturbation, in managing the inherent tradeoff between privacy and learning performance.

1 Introduction

The paper addresses learning classifiers from sensitive personal data under differential privacy, developing private approximations to regularized ERM and evaluating their privacy–utility tradeoffs.

  • Motivation: Sensitive personal data can remain identifying after anonymization, motivating machine-learning algorithms that preserve individuals’ privacy.The paper cites re-identification through unique signatures, side information, structural properties, and released statistics.
  • Problem and privacy model: The work studies regularized ERM classification under ε-differential privacy, a randomized privacy model designed to resist known attacks involving side information.Regularized ERM adds a penalty term to the average prediction loss, while differential privacy bounds the information revealed by randomized outputs.
  • Contributions: The paper develops output perturbation and objective perturbation methods for private approximations to regularized ERM, with objective perturbation theoretically superior for most problems.Objective perturbation adds noise to the regularized ERM objective before minimization; output perturbation adds noise to the standard ERM output.
  • Contributions: The methods extend to nonlinear kernel classifiers through random projections and provide theoretical generalization results.For nonlinear kernels, random projections avoid directly releasing a classifier represented as a combination of training-point-centered kernels.
  • Contributions: A randomized parameter-tuning procedure protects holdout data and provides end-to-end privacy across training and model selection.The paper notes that using validation data to select parameters can otherwise violate the privacy guarantee for a fixed parameter.
  • Evaluation: Experiments on UCI and KDDCup datasets generally find objective perturbation superior to output perturbation and demonstrate the effect of end-to-end privacy on generalization error.The evaluation covers real demographic and benchmark datasets.

2 Model

The model formalizes regularized ERM classification and defines differential privacy through randomized outputs whose distributions remain close on datasets differing in one entry.

  • ERM setup: The training data consists of n labeled pairs, with binary classification using X = R^d and labels {−1, +1}; inputs lie in the unit ball.The unit-ball assumption is ∥x_i∥_2 ≤ 1.
  • ERM setup: Regularized ERM minimizes empirical prediction loss over a hypothesis class, while the regularizer penalizes complexity to prevent over-fitting.The initial analysis focuses on linear predictors.
  • Assumptions: Privacy and generalization results require analytic conditions including convexity and differentiability of the loss and regularizer.Strong convexity supports the privacy and generalization requirements.
  • Privacy model: The differential privacy model compares randomized output distributions for neighboring datasets differing in one individual entry, limiting the information gained by an adversary.The comparison applies to measurable output sets and is expressed through a bounded likelihood ratio.
  • Privacy model: The unperturbed ERM minimizer is not differentially private because changing a training point near the decision boundary can substantially change the classifier.Regularization limits changes in norm but does not fully control the direction of the change.
  • Sensitivity method: The sensitivity method adds Laplace noise calibrated to the maximum change in a function when one input changes, yielding ε_p-differential privacy.The same principle applies to scalar functions through ordinary sensitivity.

3 Privacy-preserving ERM

The paper introduces two approaches for constructing privacy-preserving algorithms from the regularized ERM objective.

  • Approaches: The two approaches are output perturbation and objective perturbation, which modify the ERM solution through different stages of the optimization pipeline.The supplied passage introduces the approaches but does not provide their detailed procedures.

3.1 Output perturbation : the sensitivity method

Output perturbation applies the sensitivity method to the ERM minimizer by adding calibrated random noise, masking individual data points but potentially requiring high-variance noise.

  • Algorithm: Algorithm 1 perturbs the ERM minimizer A(D) = argmin J(f, D) by adding a random vector b.The noise density is calibrated using β, which depends on privacy and the minimizer’s L2-sensitivity.
  • Sensitivity: L2-sensitivity measures the maximum change in a vector-valued function’s L2 norm when one input changes.This quantity controls the scale of output noise.
  • Tradeoff: Output noise masks the effect of any individual data point, but high minimizer sensitivity can require noise with high variance.This creates a direct accuracy cost for the sensitivity method.
  • Algorithm: Algorithm 1 is titled ERM with output perturbation and uses inputs D, ε_p, and Λ to produce an approximate minimizer f_priv.The procedure draws b and computes f_priv from the perturbed objective expression.

3.2 Objective perturbation

Objective perturbation adds noise to the objective function and outputs the perturbed minimizer, providing an alternative privacy mechanism for ERM. The method uses a density-controlled noise parameter and requires additional privacy slack in Algorithm 2.

  • Objective perturbation adds noise to the objective function before computing its minimizer.
  • The privacy parameter in objective perturbation does not depend on the classification algorithm’s sensitivity.
  • Algorithm 2 takes data, privacy and regularization parameters, and a curvature bound, then outputs an approximate minimizer.
  • Algorithm 2 requires additional privacy slack because the proof bounds extra factors in the ratio of output-noise densities.

3.3 Privacy guarantees

The paper establishes differential-privacy guarantees for output and objective perturbation under convexity, differentiability, and bounded-derivative conditions. The proofs use ERM sensitivity for output perturbation and Jacobian and density-ratio bounds for objective perturbation.

  • Output perturbation: Algorithm 1 is εp-differentially private when the regularizer is differentiable and 1-strongly convex and the loss is convex, differentiable, and has |ℓ′(z)| ≤1.
  • Output perturbation: This sensitivity result supports the privacy proof for output perturbation on neighboring datasets differing in one individual.
  • Output perturbation: The L2-sensitivity of regularized ERM is at most 2/(nΛ) under the same regularizer and loss conditions.
  • Objective perturbation: Algorithm 2 is εp-differentially private when the regularizer is 1-strongly convex and twice differentiable and the loss is convex, twice differentiable, and satisfies bounded first and second derivatives.
  • Objective perturbation: The objective-perturbation proof maps perturbed outputs to noise vectors and bounds density ratios using Jacobian determinants for neighboring datasets.
  • Objective perturbation: The Jacobian analysis compares matrices differing by a rank-at-most-two perturbation and controls their eigenvalues using strong convexity and bounded loss curvature.
  • Objective perturbation: The proof completes privacy by bounding density and determinant ratios, with separate cases for zero and positive curvature bounds.

3.4 Application to classification

The paper applies privacy-preserving ERM results to logistic regression and support vector machines, using smooth loss formulations where needed to satisfy privacy-proof conditions. These constructions provide ε-differentially private classifier approximations, including an alternative treatment for the non-differentiable hinge loss.

  • 3.4.1 Logistic Regression: Privacy-preserving logistic regression follows by applying the general ERM results to logistic loss and an L2 regularizer.The logistic loss is continuous and differentiable, with its second derivative bounded by 1/4.
  • 3.4.1 Logistic Regression: The output of Algorithm 2 with the specified L2 regularizer and logistic loss is an εp-differentially private approximation to logistic regression.
  • 3.4.2 Support Vector Machines: Support vector machines require smooth loss handling because the hinge loss is continuous but not differentiable and fails the theorem conditions.The paper proposes a doubly differentiable approximation whose loss approaches hinge loss as h → 0.
  • 3.4.2 Support Vector Machines: The smooth convex loss ℓs enables privacy-preserving approximations to regularized support vector machines under the general ERM theorems.Its second derivative is nonnegative, and the paper states that it can be used in Theorems 1 and 2.
  • 3.4.2 Support Vector Machines: Huber loss provides another route to an εp-differentially private SVM approximation despite not being globally doubly differentiable.The proof handles the finite set of non-differentiable values and establishes the required probability bound for neighboring datasets.

4 Generalization performance

The section develops sample-complexity and generalization guarantees for privacy-preserving ERM under i.i.d. sampling, comparing output and objective perturbation. Objective perturbation has better dependence on classifier margin in difficult learning problems, while both methods support logistic regression and Huber SVM results under stated analytic conditions.

  • Performance criteria: Sample complexity measures the number of i.i.d. training examples needed to achieve expected loss within ǫg of a reference classifier’s loss.The reference classifier f0 has loss L(f0)=L∗, and the bounds assume data are drawn from a fixed distribution P.
  • Performance criteria: Non-private L2-regularized SVM provides the reference order against which privacy-induced sample-complexity burdens are compared.The reference bound scales with ||f0||2 and logarithmic dependence on inverse error and confidence terms.
  • Output versus objective perturbation: Objective perturbation’s dominating sample-complexity term has better dependence on ||f0|| and 1/ǫg than output perturbation.Because harder learning problems tend to have larger ||f0||, the analysis predicts greater advantage for objective perturbation in those settings.
  • Output perturbation: The generalization analysis for output perturbation assumes bounded data and loss derivatives, differentiability, Lipschitz derivatives, and i.i.d. sampling.The resulting theorem bounds the loss of the private classifier relative to a reference classifier with high probability over privacy noise and data.
  • Objective perturbation: Objective perturbation receives an analogous high-probability generalization bound under convexity, double differentiability, and bounded first and second loss derivatives.The section also derives logistic-regression and Huber-SVM corollaries, with weaker analytic requirements available for some output-perturbation results.

5 Kernel methods

The kernel-method section addresses the privacy problem caused by releasing training-centered kernel representations. It uses random projections to transform translation-invariant nonlinear kernels into privacy-preserving linear ERM problems with privacy and generalization guarantees.

  • Privacy challenge: Kernel ERM predictors are linear combinations of kernel functions centered at training points, so releasing them can reveal private training data.The paper therefore avoids directly releasing the training-centered representation.
  • Random-projection approach: Algorithm 3 releases the random projection map and a privacy-preserving linear classifier, yielding a nonlinear-kernel predictor without releasing training points.The classifier evaluates the released linear model on the projected representation of a new input.
  • Random-projection approach: Random projections approximate suitable translation-invariant kernels and produce finite-dimensional features for private linear classification.The transformed data use sampled feature functions, after which output or objective perturbation is applied in the projected space.
  • Privacy guarantees: Theorem 5 guarantees ǫp-differential privacy for the projected kernel classifier when the sampled projection points are independent of the dataset.The privacy guarantee follows from the privacy of the underlying linear ERM algorithms and data-independent projection sampling.
  • Generalization performance: Theorem 6 and Theorem 7 provide generalization guarantees against classifiers bounded in ||f0||∞ or ||f0||H, respectively.For suitable Λ and projection dimension D, the objective-perturbation version achieves L(fpriv)−L(f0)≤ǫg with probability at least 1−4δ.

6 Parameter tuning

The parameter-tuning section closes a privacy gap that arises when regularization is selected from private validation performance. It proposes public-data tuning when available and a differentially private partition-and-selection procedure otherwise.

  • Privacy challenge: Choosing the regularization parameter Λ from private validation performance can violate privacy even when training is private for each fixed Λ.The released classifier may reveal the data-dependent parameter choice and information about the private database.
  • Public-data tuning: Public holdout data from the same distribution can tune Λ independently of the private training data.The selected parameter can then be used to train on private data without depending on its values.
  • Private tuning procedure: Without public data, the procedure trains candidate predictors on disjoint data subsets and evaluates them on a separate validation subset.A randomized privacy-preserving comparison selects among the candidate parameters, protecting validation-set individuals.
  • Privacy guarantee: Theorem 8 states that the complete parameter-tuning procedure is ǫp-differentially private.The proof uses disjoint subsets, independent privacy mechanisms, and a randomized selection step.
  • Utility guarantee: The selected classifier’s validation error is close to that of the best candidate with high probability when the dataset is sufficiently large.This utility statement compares the randomized choice against the best classifier among the candidate set.

7 Experiments

Experiments on Adult and KDDCup99 evaluate privacy-accuracy tradeoffs and learning curves for private logistic regression and SVM classifiers. Objective perturbation generally outperforms the sensitivity method, with private error typically decreasing as training data increases.

  • Datasets: Adult contains approximately 47,000 demographic records, while KDDCup99 contains about 5,000,000 network-connection instances.Adult predicts whether annual income exceeds $50,000; KDDCup99 predicts denial-of-service attacks.
  • Privacy-Accuracy Tradeoff: Experiments compare objective perturbation and the sensitivity method for logistic regression and Huber SVM under varying privacy levels.The privacy parameter is εp, and classifiers are evaluated using test classification error.
  • Privacy-Accuracy Tradeoff: On Adult, objective perturbation outperforms sensitivity, while objective-perturbation SVM achieves lower error than objective-perturbation logistic regression.Non-private logistic regression and SVM each have classification error about 0.15, compared with about 0.25 for the constant negative classifier.
  • Privacy-Accuracy Tradeoff: On KDDCup99, objective perturbation outperforms sensitivity for both classifiers, with sensitivity nearly matching it for SVM at high εp.Under low privacy, objective-perturbation logistic regression is better; under high privacy, objective-perturbation SVM is better. Non-private error is about 0.001 for both classifiers.
  • Privacy-Accuracy Tradeoff: For SVMs, private error can increase slightly as εp rises from 0.25 because perturbation shifts false-positive and false-negative rates under label imbalance.The authors attribute the effect to the imbalanced labels and the resulting behavior of the optimal classifier.
  • Accuracy vs. Training Data Size Tradeoffs: As KDDCup99 training size increases, private error usually decreases, and objective perturbation outperforms sensitivity across the learning-curve experiments.Non-private logistic regression and SVM error remains constant with increasing data size; SVMs generally outperform logistic regression.

8 Discussions and Conclusions

The paper develops computationally efficient differentially private methods for regularized ERM classification and finds objective perturbation generally manages the privacy–learning tradeoff better than sensitivity methods. Its scope is bounded by assumptions such as strongly convex regularization and differentiable losses, with several extensions remaining open.

  • Contributions: The paper proposes two privacy-preserving ERM algorithms, including objective perturbation, with applications to logistic regression, SVMs, kernels, and validation.It also provides sample requirements and generalization bounds for achieving a target generalization error.
  • Results: Error rates increase as privacy requirements become more stringent, while more training data improves both private algorithms and can bring performance close to non-private classification.The generalization guarantees formalize this privacy–utility tradeoff.
  • Assumptions: Output perturbation and objective perturbation require different conditions, including strong convexity of the regularizer for output perturbation.Output perturbation also requires convexity and bounded derivative or Lipschitz conditions for the loss.
  • Results: Objective perturbation usually provides more accurate solutions than output perturbation in both theoretical and experimental results.The paper recommends objective perturbation when the loss satisfies Theorem 2's conditions.
  • Limitations: The methods do not address private regularized ERM when the regularizer is not strongly convex, including L1-regularized ERM.A one-point dataset change can significantly alter the solution in L1-regularized ERM.
  • Open Questions: Open problems include extending objective perturbation to broader convex optimization, improving kernel classification, and obtaining more statistically efficient linear-classification algorithms.Kernel privacy is difficult because high-dimensional linearization can require substantial training data while privacy mechanisms often degrade with dimensionality.
Loading 0912.0071v5…