Differentially Private Linear Regression via Medians

Alexander Knop, Thomas SteinkeNeurIPS 2022 · OpenReview

TL;DR

This paper introduces a new differentially private linear regression algorithm that avoids the need for strict data clipping by leveraging a robust, median-based approach inspired by the Theil-Sen estimator. This method offers a more favorable privacy-utility trade-off, especially in high-dimensional settings, and demonstrates superior performance compared to existing differentially private regression techniques.

What Problem Does This Paper Address?

Linear regression is a fundamental machine learning task, but making it differentially private (DP) has been challenging. Standard DP methods often rely on adding noise to model parameters or gradients, which requires bounding the "sensitivity" of these quantities. This typically involves clipping input data or intermediate statistics, leading to a harsh privacy-utility trade-off: overly aggressive clipping distorts the data and harms accuracy, while insufficient clipping might compromise privacy. The authors aim to develop a DP linear regression algorithm that is less sensitive to these bounds, offering better utility without sacrificing privacy guarantees.

Methods

The core of the proposed method is a multivariate extension of the Theil-Sen estimator. Instead of directly minimizing the squared error (like Ordinary Least Squares), the Theil-Sen estimator uses medians of pairwise slopes to find a robust linear fit. The authors adapt this by:

  • Subproblem Decomposition: Breaking down the problem into multiple smaller subproblems. For each subproblem, they select a subset of data points (specifically, $d$ points for a $d$-dimensional problem) that uniquely define a linear model.
  • Median-Based Aggregation: Computing a solution for each subproblem and then aggregating these solutions using a differentially private median. This median computation is the key to achieving robustness and reducing sensitivity.
  • DP Median Subroutine: The paper utilizes the exponential mechanism to compute differentially private medians for each coordinate of the regression coefficients. This is a standard technique for DP, but its application here as a subroutine for a robust estimator is novel.
  • Sensitivity Agnosticism: The median-based approach inherently has lower sensitivity than mean-based methods, reducing the need for aggressive data clipping. The theoretical analysis shows that the algorithm's privacy guarantee is achieved through composition of the DP median computations.

Datasets

The paper uses synthetic data for its experiments. The features ($X$) are sampled either from a standard Gaussian distribution ($N(0, I)$) or uniformly from $[-1, 1]^d$. The target variable ($y$) is generated as $y \sim N(\langle \theta^*, x \rangle, \sigma^2)$, where $\theta^*$ is the true regression coefficient and $\sigma$ is a noise parameter. This synthetic setup allows for precise control over assumptions and a clear comparison of algorithms. No new datasets were introduced.

Key Insights and Ideas

  • Median as a DP Workhorse: The paper highlights that medians, due to their robustness, are a powerful tool for achieving differential privacy, especially when compared to means. This insight is extended from univariate mean estimation to multivariate linear regression.
  • Decoupling Privacy and Utility: By avoiding direct noise addition to sensitive quantities and instead relying on DP medians, the algorithm achieves a better balance between privacy and predictive accuracy. This is particularly beneficial when dealing with data that might have outliers or when strict bounds are difficult to set.
  • Theil-Sen's DP Potential: The Theil-Sen estimator, known for its robustness in non-private settings, provides a natural framework for DP regression. The authors demonstrate a practical and theoretically sound way to make it differentially private.
  • High-Dimensional Advantage: The proposed method shows particular promise in high-dimensional settings, where traditional DP methods often struggle with the curse of dimensionality and the need for large amounts of noise.

Key Results

  • Theoretical Guarantees: The paper provides theoretical guarantees for both privacy (ε-DP and concentrated DP) and accuracy. The accuracy bound shows a dependency on the dimension ($d$), sample size ($n$), privacy parameters ($\epsilon, \delta$), and a parameter $r$ related to the range of coefficients.
  • Experimental Superiority: Figure 1 and Figure 2 show that the proposed "Private Theil-Sen estimator" consistently outperforms other state-of-the-art DP linear regression algorithms (DP-GD, Gaussian Mechanism Regressor, DP-Functional Mechanism Regressor) in terms of mean square error across various dimensions and sample sizes.
  • Robustness to Parameters: The experiments suggest that the algorithm is relatively robust to the choice of the number of subproblems ($l$), with $l=1$ often being sufficient.

Limitations and Future Work

  • Range Restriction: While the algorithm is less sensitive to data clipping, it still requires restricting the range of the regression coefficients to a bounded set $R$. The paper acknowledges this as a necessary restriction for DP in the private case.
  • Computational Complexity: The paper mentions that the standard Theil-Sen estimator considers all $\binom{n}{d}$ subproblems, which is computationally prohibitive. Their approach randomly selects $l \cdot m$ subproblems, which is more efficient but still involves solving multiple subproblems.
  • Synthetic Data: The experimental evaluation is based on synthetic data. While this allows for controlled comparisons, testing on real-world datasets would be valuable.
  • Future Work: The authors suggest exploring more advanced DP median heuristics and further investigating the trade-offs associated with the parameter $r$. They also note that their theoretical analysis could be improved with more advanced composition techniques.

Summary updated

Abstract

Linear regression is one of the simplest machine learning tasks. Despite much work, differentially private linear regression still lacks effective algorithms. We propose a new approach based on a multivariate extension of the Theil-Sen estimator. The theoretical advantage of our approach is that we do not directly rely on noise addition, which requires bounding the sensitivity. Instead we compute differentially private medians as a subroutine, which are more robust. We also show experimentally that our approach compares favourably to prior work.
BibTeX
@inproceedings{knop2022differentially,
  author = {Alexander Knop and Thomas Steinke},
  title = {{Differentially Private Linear Regression via Medians}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=JSBgIaxAXk9},
}
Figure