Privacy-preserving logistic regression

Kamalika Chaudhuri, Claire MonteleoniNeurIPS 2008 · OpenReview

This paper, a foundational work in the field of private machine learning, explores how to train logistic regression models while strictly adhering to $\epsilon$-differential privacy. The authors move beyond the standard approach of adding noise to a model's output, proposing instead to perturb the optimization objective itself—a shift that yields significantly better accuracy without sacrificing privacy.

TL;DR

The authors introduce a novel "objective perturbation" method for privacy-preserving logistic regression that outperforms traditional "output perturbation" techniques. By adding noise directly to the optimization goal rather than the final weights, they achieve tighter theoretical learning guarantees and superior empirical performance, especially when regularization is low.

What Problem Does This Paper Address?

Training machine learning models on sensitive data (like medical records or financial transactions) poses a massive privacy risk: an adversary might be able to "reverse-engineer" the training set by observing the model's behavior.

To prevent this, researchers use $\epsilon$-differential privacy, a rigorous mathematical standard that ensures the presence or absence of a single individual in a dataset doesn't significantly change the algorithm's output. The standard way to achieve this is to calculate the "sensitivity" of a function—how much one person's data can change the result—and add noise proportional to that sensitivity.

However, for logistic regression, this sensitivity can be quite high. Adding enough noise to guarantee privacy often "breaks" the model, making it no more accurate than a coin flip. The authors set out to find a way to maintain privacy while keeping the model useful.

Methods

The paper compares two primary approaches:

  1. Algorithm 1 (Output Perturbation): This follows the classic sensitivity-based method. You train a standard regularized logistic regression model and then add random noise (drawn from a Laplace distribution) to the resulting weight vector. The noise scale is determined by the regularization parameter ($\lambda$) and the number of samples ($n$).
  2. Algorithm 2 (Objective Perturbation): This is the paper's core contribution. Instead of training a model and then adding noise, the authors add a random noise term ($b^T w$) directly into the optimization objective function. The model then minimizes this "noisy" objective.

The authors prove that this second method also satisfies $\epsilon$-differential privacy but provides much tighter bounds on the "excess risk" (the loss in accuracy due to privacy).

Datasets

The authors evaluated their methods using synthetic datasets to maintain a controlled environment for comparing privacy-utility tradeoffs:

  • Separable Data: 10-dimensional data points sampled from a unit hypersphere, separated by a linear plane with a small margin (0.03).
  • Non-separable Data: Similar to the above, but with "noisy" labels (20% of labels flipped within a 0.1 margin) to simulate real-world complexity.
  • Scale: Experiments were conducted using 17,500 data points.

Key Insights and Ideas

  • Regularization is a Privacy Tool: One of the most elegant insights is the formal connection between regularization and privacy. Regularization ($\lambda$) is designed to prevent overfitting by making the model less sensitive to individual data points. The authors show that higher regularization mathematically reduces the amount of noise needed to achieve privacy.
  • Perturbing the Goal vs. the Result: By perturbing the objective function, the optimization process effectively "smooths out" the noise. This leads to a model that is more stable and accurate than one where noise is simply slapped onto the final weights.
  • Generality: While focused on logistic regression, the authors provide a generalized theorem showing that objective perturbation works for any optimization problem involving a strongly convex, differentiable loss function.

Key Results

  • Superior Accuracy: In simulations, the "New Method" (objective perturbation) consistently outperformed the "Sensitivity Method" (output perturbation). For example, on separable data, the new method achieved a test error of ~0.14, while the sensitivity method lagged at ~0.29.
Average test error comparison
  • Sample Efficiency and Privacy Budget ($\epsilon$): The learning curves demonstrated that the new method reaches a lower error rate much faster (with fewer samples) than the sensitivity-based approach. Furthermore, the new method proved superior across a wide range of privacy levels. While the sensitivity method only performed well when privacy requirements were extremely loose, the objective perturbation method remained useful even under stricter privacy constraints.
Learning curves and error vs epsilon

Limitations and Future Work

  • Convexity Requirements: The theoretical proofs rely on the loss function being differentiable and strongly convex. This means the method doesn't immediately translate to non-convex models like deep neural networks.
  • Parameter Tuning: The performance still depends on choosing the right regularization parameter ($\lambda$). The authors suggest that while $\lambda$ helps privacy, choosing it solely for privacy might hurt the model's ability to learn the underlying data patterns.
  • Expanding the Toolbox: The authors suggest exploring whether other techniques used to prevent overfitting (like dropout or different types of kernels) might also offer "built-in" privacy benefits.

Summary updated

Abstract

This paper addresses the important tradeoff between privacy and learnability, when designing algorithms for learning from private databases. First we apply an idea of Dwork et al. to design a specific privacy-preserving machine learning algorithm, logistic regression. This involves bounding the sensitivity of logistic regression, and perturbing the learned classifier with noise proportional to the sensitivity. Noting that the approach of Dwork et al. has limitations when applied to other machine learning algorithms, we then present another privacy-preserving logistic regression algorithm. The algorithm is based on solving a perturbed objective, and does not depend on the sensitivity. We prove that our algorithm preserves privacy in the model due to Dwork et al., and we provide a learning performance guarantee. Our work also reveals an interesting connection between regularization and privacy.
BibTeX
@inproceedings{chaudhuri2008privacy,
  author = {Kamalika Chaudhuri and Claire Monteleoni},
  title = {{Privacy-preserving logistic regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=HyN13v-dZS},
}
Figure