Near Optimal Private and Robust Linear Regression

Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh, Arun Sai Suggala

Abstract

We study the canonical statistical estimation problem of linear regression from $n$ i.i.d. examples under $(\varepsilon,\delta)$-differential privacy when some response variables are adversarially corrupted. We propose a variant of the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two innovations: a full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. When there is no adversarial corruption, this algorithm improves upon the existing state-of-the-art approach and achieves a near optimal sample complexity. Under label-corruption, this is the first efficient linear regression algorithm to guarantee both ($\varepsilon,\delta$)-DP and robustness. Synthetic experiments confirm the superiority of our approach.

Introduction

In modern data science, practitioners often face a dual challenge: protecting the sensitive information of individuals within a dataset while ensuring the model remains robust against adversarial data corruption. While linear regression is a foundational statistical tool, achieving both $(\varepsilon, \delta)$-Differential Privacy (DP) and robustness simultaneously is computationally difficult.

Previous efficient (polynomial-time) private algorithms frequently struggled with ill-conditioned data—datasets where features are highly correlated, represented by a large condition number $\kappa$. These methods often required a sample size scaling with $\kappa$ or $\kappa^2$ to reach target accuracy. Furthermore, most existing private algorithms are fragile; even a small fraction of corrupted labels ($y$-values) can significantly bias the resulting model. This paper introduces DP-RobGD (Differentially Private Robust Gradient Descent), an algorithm designed to address these limitations by providing near-optimal sample complexity and inherent resilience to label corruption.

Methodology: DP-RobGD

The DP-RobGD algorithm departs from standard Differentially Private Stochastic Gradient Descent (DP-SGD) through two primary innovations:

1. Separate Adaptive Clipping

Standard DP-SGD typically clips the norm of the entire gradient. However, this approach allows an adversary to "hide" significant label corruption within a sample that has a very small covariate ($x$), staying under the global clipping threshold while still biasing the model. DP-RobGD addresses this by clipping the covariate $x_i$ and the residual $(w^\top x_i - y_i)$ separately. These thresholds are not fixed but are estimated adaptively from the data using private pre-processing steps, ensuring the clipping is tuned to the specific scale of the dataset.

2. Full-Batch Gradient Descent with Resilience Analysis

Many previous state-of-the-art private methods relied on "streaming" SGD, where each data point is used only once to simplify the mathematical analysis of privacy. DP-RobGD utilizes full-batch updates, which the authors prove to be more sample-efficient. To handle the complex dependencies introduced by reusing data across iterations, the authors employ the concept of resilience—a property from robust statistics ensuring that the mean of any large subset of data remains close to the true population mean. This allows the algorithm to bridge the gap between robust statistics and differential privacy.

Experimental Setup

The authors evaluated DP-RobGD using synthetic datasets to precisely control the environment and test theoretical limits:

  • Generative Model: Covariates $x_i$ were drawn from a zero-mean Gaussian distribution $\mathcal{N}(0, \Sigma)$, where $\Sigma$ is a diagonal matrix used to control the condition number $\kappa$.
  • Corruption Simulation: To test robustness, an adversary replaced a fraction $\alpha$ of the labels with arbitrary values (e.g., setting them to 1000).
  • Noise Distributions: Beyond standard Gaussian noise, the algorithm was tested against "heavy-tailed" noise (sub-Weibull and hypercontractive distributions) to evaluate its performance on "spiky" data.

Key Insights and Results

The $\kappa^{1/2}$ Breakthrough

By moving to full-batch updates and refined resilience analysis, the authors reduced the sample complexity's dependence on the condition number from $\kappa^2$ or $\kappa$ down to $\kappa^{1/2}$. This makes the algorithm significantly more viable for real-world datasets where features are often highly correlated. The resulting sample complexity is $n = \tilde{O}\left(\frac{d}{\alpha^2} + \frac{\kappa^{1/2}d}{\epsilon\alpha}\right)$, matching the best-known exponential-time algorithms in most parameters except for the $\kappa^{1/2}$ factor.

Robustness as a Byproduct of Privacy

A significant finding of this research is that the separate clipping mechanism required for differential privacy also provides robustness against label corruption. If the clipping thresholds are estimated privately and adaptively, the model gains protection against outliers almost "for free."

Empirical Superiority

In head-to-head comparisons with DP-AMBSSGD (the previous state-of-the-art), DP-RobGD achieved lower error rates across varying sample sizes and condition numbers. Notably, while baseline private algorithms (like DP-SSP and standard DP-SGD) saw their error explode when just 1% of labels were corrupted, DP-RobGD remained stable and maintained high accuracy.

Limitations and Future Directions

While DP-RobGD represents a major advancement, several open questions remain:

  1. The $\kappa$ Gap: Theoretically optimal (but computationally inefficient) algorithms have no dependence on $\kappa$. It remains to be seen if a polynomial-time algorithm can achieve $\kappa$-independent sample complexity.
  2. Covariate Corruption: This work focuses on label corruption ($y$). Handling adversarial changes to the covariates ($x$) is significantly more challenging and remains an open problem for efficient private algorithms.
  3. Real-World Application: Future research should focus on applying these adaptive clipping strategies to high-dimensional, non-synthetic datasets, such as those found in genomics or finance.

Summary updated

Abstract

We study the canonical statistical estimation problem of linear regression from $n$ i.i.d.~examples under $(\varepsilon,\delta)$-differential privacy when some response variables are adversarially corrupted. We propose a variant of the popular differentially private stochastic gradient descent (DP-SGD) algorithm with two innovations: a full-batch gradient descent to improve sample complexity and a novel adaptive clipping to guarantee robustness. When there is no adversarial corruption, this algorithm improves upon the existing state-of-the-art approach and achieves a near optimal sample complexity. Under label-corruption, this is the first efficient linear regression algorithm to guarantee both $(\varepsilon,\delta)$-DP and robustness. Synthetic experiments confirm the superiority of our approach.
BibTeX
@inproceedings{liu2023near,
  author = {Xiyang Liu and Prateek Jain and Weihao Kong and Sewoong Oh and Arun Sai Suggala},
  title = {{Near Optimal Private and Robust Linear Regression}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=wPVw218szF},
}

Loading related content...

Figure