Near Optimal Private and Robust Linear Regression

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

TL;DR

This paper introduces a new algorithm for linear regression that achieves both differential privacy and robustness against adversarial label corruption, a combination that was previously elusive for efficient algorithms. The proposed method, DP-ROBGD, improves upon existing state-of-the-art in terms of sample complexity and is the first to offer provable guarantees for this challenging scenario.

What Problem Does This Paper Address?

In many real-world applications, data used for machine learning models needs to be kept private (e.g., medical records, financial data) and also needs to be robust against potential errors or malicious alterations in the data. Linear regression is a fundamental statistical task, but achieving both differential privacy (DP) and robustness against adversarial corruption simultaneously has been a significant challenge.

Differential privacy ensures that the output of an algorithm does not reveal information about any single individual's data. Robustness, on the other hand, means the algorithm's performance doesn't degrade significantly even if a portion of the data is corrupted, especially if an adversary intentionally modifies labels. While there are algorithms that achieve DP or robustness individually, or even optimal results for one of them, combining both efficiently has been an open problem. Specifically, existing DP algorithms often struggle with adversarial label corruption, and robust algorithms may not offer DP guarantees. This paper tackles this gap by proposing an efficient algorithm that provides both strong DP guarantees and robustness against adversarial label corruption in linear regression.

Methods

The authors propose a novel variant of the Differentially Private Stochastic Gradient Descent (DP-SGD) algorithm, named DP-ROBGD. Their approach incorporates two key innovations:

  1. Full-Batch Gradient Descent: Instead of using mini-batches, they employ full-batch gradient descent. While this makes theoretical analysis more complex due to the dependence of gradients on previous iterates, it allows for improved sample complexity.
  2. Novel Adaptive Clipping: This is the core innovation for achieving robustness. The algorithm adaptively clips both the covariate norms and the residuals (the difference between the true and predicted response) separately. This dual clipping strategy is crucial for handling adversarial label corruption, as it prevents corrupted data points with small norms but large residuals from disproportionately influencing the gradient estimate.

The algorithm also leverages techniques like private norm estimation and private distance estimation to determine the clipping thresholds in a privacy-preserving manner.

Datasets

The authors use synthetic datasets for their experiments. They generate data based on a linear model with covariates drawn from (K, a)-sub-Weibull distributions and noise from a uniform distribution. They specifically mention generating data for experiments with varying parameters like sample size ($n$), dimensionality ($d$), condition number ($\kappa$), noise level ($\sigma$), and privacy parameter ($\varepsilon$).

Key Insights and Ideas

  • The Power of Dual Clipping: The most significant insight is that adaptively clipping both the covariate norm and the residual is essential for achieving robustness against label corruption in a differentially private setting. Standard DP algorithms often clip only the gradient norm, which can be insufficient when an adversary can manipulate labels on points with small covariate norms.
  • Bridging the Gap Between DP and Robustness: This work demonstrates that it's possible to achieve near-optimal sample complexity for linear regression while satisfying both differential privacy and robustness to label corruption, a feat that was previously unachievable with efficient algorithms.
  • Resilience is Key: The analysis heavily relies on the concept of "resilience," a property of datasets that ensures statistics computed on large subsets are close to each other. This property is crucial for controlling the bias introduced by clipping and adversarial corruptions.

Key Results

  • Near-Optimal Sample Complexity: For private linear regression without corruption, DP-ROBGD achieves a sample complexity of $\tilde{O}(d/\alpha^2 + \kappa^{1/2}d/(\varepsilon\alpha))$, which is a significant improvement over prior efficient algorithms, especially in terms of dependence on the condition number $\kappa$.
  • Provable Robustness and Privacy: The algorithm provides provable $(\varepsilon, \delta)$-differential privacy and robustness against a fraction of adversarial label corruptions.
  • Outperforms Baselines: Experimental results show that DP-ROBGD outperforms existing DP algorithms like DP-AMBSSGD and DP-SSP in various settings, particularly in terms of parameter estimation error.
  • Handles Adversarial Corruption: In experiments with adversarial label corruption, DP-ROBGD shows significantly better performance than non-robust baselines, demonstrating its ability to handle corrupted data.

Limitations and Future Work

  • Label Corruption Only: The current algorithm is designed to be robust against adversarial label corruption. The authors acknowledge that a stronger adversary who can corrupt both labels and covariates poses a greater challenge, and efficient algorithms for this scenario remain an open question.
  • Computational Complexity: While the algorithm is considered "efficient" and improves upon prior work, its computational complexity is still $\tilde{O}(nd)$ for high-dimensional problems. The paper notes that some non-private or non-DP algorithms can achieve better complexity, and it remains an open question whether computationally efficient DP algorithms can match those rates.
  • Sub-optimal Dependence on $\kappa$: While DP-ROBGD improves the dependence on $\kappa$ compared to previous efficient DP algorithms, it still has a $\kappa^{1/2}$ factor in its sample complexity. The paper mentions that exponential-time algorithms can achieve $\kappa$-independent rates, and achieving this for efficient algorithms is an open problem.
  • Future Work: The authors suggest exploring more powerful adversaries (corrupting covariates) and investigating ways to achieve $\kappa$-independent sample complexity for efficient DP linear regression algorithms.

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 a fraction of 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 near optimal sample complexity. Under label-corruption, this is the first efficient linear regression algorithm to provably guarantee both $(\epsilon,\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 Suggala},
  title = {{Near Optimal Private and Robust Linear Regression}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=wPVw218szF},
}
Figure