Efficient Algorithms and Lower Bounds for Robust Linear Regression

By Ilias Diakonikolas, Weihao Kong, Alistair Stewart. 2018

174 citations recorded by the source corpus.

We study the problem of high-dimensional linear regression in a robust model where an $\epsilon$-fraction of the samples can be adversarially corrupted. We focus on the fundamental setting where the covariates of the uncorrupted samples are drawn from a Gaussian distribution $\mathcal{N}(0, \Sigma)$ on $\mathbb{R}^d$. We give nearly tight upper bounds and computational lower bounds for this problem. Specifically, our main contributions are as follows: For the case that the covariance matrix is known to be the identity, we give a sample near-optimal and computationally efficient algorithm that outputs a candidate hypothesis vector $\widehat{\beta}$ which approximates the unknown regression vector $\beta$ within $\ell_2$-norm $O(\epsilon \log(1/\epsilon) \sigma)$, where $\sigma$ is the standard deviation of the random observation noise. An error of $\Omega (\epsilon \sigma)$ is information-theoretically necessary, even with infinite sample size. Prior work gave an algorithm for this problem with sample complexity $\tilde{\Omega}(d^2/\epsilon^2)$ whose error guarantee scales with the $\ell_2$-norm of $\beta$. For the case of unknown covariance, we show that we can efficiently achieve the same error guarantee as in the known covariance case using an additional $\tilde{O}(d^2/\epsilon^2)$ unlabeled examples. On the other hand, an error of $O(\epsilon \sigma)$ can be information-theoretically attained with $O(d/\epsilon^2)$ samples. We prove a Statistical Query (SQ) lower bound providing evidence that this quadratic tradeoff in the sample size is inherent. More specifically, we show that any polynomial time SQ learning algorithm for robust linear regression (in Huber's contamination model) with estimation complexity $O(d^{2-c})$, where $c>0$ is an arbitrarily small constant, must incur an error of $\Omega(\sqrt{\epsilon} \sigma)$.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, methodology): “For the case of linear regression, [DKS18] provide eﬃcient robust algorithms with near-optimal error guarantees under various distributional assumptions and establish matching computational-robustness tradeoﬀs.”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “…work (e.g., see (Charikar, Steinhardt, and Valiant 2017; Diakonikolas, Kane, and Stewart 2017; 2018; Diakonikolas et al. 2018; Prasad et al. 2018; Diakonikolas, Kong, and Stewart 2018) and references therein) exploring the possibility of robust statistics over poisoned data with algorithmic…”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “[27], Hopkins and Li [34], Klivans et al.”
Learning under p-Tampering Attacks (2018, background): “These works led to an active line of work (e.g., see [CSV17, DKS17, DKS18a, DKK + 18, PSBR18, DKS18b] and references therein) exploring the possibility of robust statistics over poisoned data with algorithmic guarantees.”