Efficient Algorithms for Outlier-Robust Regression

Abstract

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.

27 pages. Appeared in COLT 2018. This update removes Lemma 6.2 that erroneously claimed an information-theoretic lower bound on error rate as a function of fraction of outliers

References in corpus (1)

• Better Agnostic Clustering Via Relaxed Tensor Norms

Cited by in corpus (11)

• Spectral Signatures in Backdoor Attacks
• Byzantine Stochastic Gradient Descent
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• High Dimensional Robust Sparse Regression
• Generalized Resilience and Robust Statistics
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing
• Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
• Robust estimation via generalized quasi-gradients
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Estimating Principal Components under Adversarial Perturbations