Efficient Algorithms for Outlier-Robust Regression

By Adam R. Klivans, Pravesh Kothari, Raghu Meka. 2018

171 citations recorded by the source corpus.

We give the first polynomial-time algorithm for performing linear or polynomial regression resilient to adversarial corruptions in both examples and labels. Given a sufficiently large (polynomial-size) training set drawn i.i.d. from distribution D and subsequently corrupted on some fraction of points, our algorithm outputs a linear function whose squared error is close to the squared error of the best-fitting linear function with respect to D, assuming that the marginal distribution of D over the input space is \emph{certifiably hypercontractive}. This natural property is satisfied by many well-studied distributions such as Gaussian, strongly log-concave distributions and, uniform distribution on the hypercube among others. We also give a simple statistical lower bound showing that some distributional assumption is necessary to succeed in this setting. These results are the first of their kind and were not known to be even information-theoretically possible prior to our work. Our approach is based on the sum-of-squares (SoS) method and is inspired by the recent applications of the method for parameter recovery problems in unsupervised learning. Our algorithm can be seen as a natural convex relaxation of the following conceptually simple non-convex optimization problem: find a linear function and a large subset of the input corrupted sample such that the least squares loss of the function over the subset is minimized over all possible large subsets.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

Spectral Signatures in Backdoor Attacks (2018, background): “Another line of work focuses on applying the robust statistics tools developed in [8, 22, 5, 9] to robust stochastic optimization problems [2, 5, 10, 17, 27].”
Learning with Bad Training Data via Iterative Trimmed Loss Minimization (2018, background): “Another line of recent work on robust regression consider strong robustness where the adversary poisons both the inputs and outputs, in both low-dimensional [DKK + 18, PSBR18, KKM18] and high dimensional [CCM13, BDLS17, LSLC18] settings.”
Choosing the Sample with Lowest Loss makes SGD Robust (2020, background): “Recently, [5, 6, 32, 20, 18] have proposed robust learning algorithms for linear regression which require the computation of gradient over the entire dataset which may be computationally intractable for large datasets.”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “Various different models have been introduced, see Charikar, Steinhardt, and Valiant [17], Diakonikolas, Kamath, Kane, Li, Moitra, and Stewart [23, 24, 25], Diakonikolas, Kane, and Stewart [26], Diakonikolas, Kong, and Stewart [27], Hopkins and Li [34], Klivans, Kothari, and Meka [42], Kothari, Stei”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “A recent line of work develops eﬃcient robust estimation algorithms in high-dimensional settings [8, 22, 39, 13, 60, 45, 9, 36, 46].”
Efficient Algorithms and Lower Bounds for Robust Linear Regression (2018, methodology): “Three recent works [PSBR18, DKK + 18b, KKM18] provide robust eﬃcient algorithms for linear regression in various settings.”