Source-linked AI summary
Efficient Algorithms for Outlier-Robust Regression
Adam Klivans, Pravesh K. Kothari, Raghu Meka
TL;DR
The paper addresses whether regression can remain accurate when adversaries corrupt both inputs and labels. It uses sum-of-squares relaxations under certifiable hypercontractivity, obtaining polynomial-time robust regression near the best distributional fit while showing that distributional assumptions are necessary.
Problem
Robust regression with adversarial corruption of both examples and labels lacks meaningful guarantees without assumptions on the input distribution.
Method
The algorithm uses sum-of-squares reasoning and pseudo-distributions as an efficient relaxation of searching over large low-loss subsets of corrupted samples.
Results
Under certifiable hypercontractivity, polynomial-time algorithms achieve linear and analogous polynomial regression guarantees close to the best-fitting error, with err_D(ℓ) ≤ ε in the realizable case.
Takeaways & Limitations
Robust regression is computationally achievable for broad distribution families including Gaussian, strongly log-concave, and bounded product distributions.
Takeaways & Limitations
The guarantees require certifiable hypercontractivity, and the dependence of error on η is identified as likely suboptimal.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces efficient outlier-robust linear regression under certifiable hypercontractivity, allowing adversarial corruption of both examples and labels. Its sum-of-squares approach yields guarantees near optimal regression error, while showing distributional assumptions are necessary.
- Problem and contribution: The paper gives the first efficient algorithms for least-squares regression when an η fraction of examples and labels may be adversarially corrupted.The setting imposes no structure on the corruption beyond its fraction.
- Limits: Without distributional assumptions, robust regression can have no meaningful error bound, and the method’s dependence on η remains an open problem for improvement.The paper also notes that statistical consistency is impossible in general under adversarial corruptions.
- Assumptions: Certifiable hypercontractivity of the input marginal supports the guarantees and includes Gaussian, strongly log-concave, and bounded product distributions.The condition is invariant under affine transformations and therefore does not depend on covariance condition number.
- Guarantees: For polynomial-size corrupted samples, the algorithm runs in polynomial time and outputs a linear function whose error is close to the best achievable error under D.The informal theorem applies when η < c/C^2 and the optimal regressor has polynomial bit-complexity.
- Guarantees: In the realizable case, the theorem gives err_D(ℓ) ≤ ε, so the error approaches zero at a polynomial rate.The result also has an analogous extension to outlier-robust polynomial regression.
- Approach: The approach relaxes the non-convex search over a large low-loss subset into an efficiently computable sum-of-squares formulation using pseudo-distributions.Pseudo-distributions preserve conclusions justified by sufficiently low-degree sum-of-squares proofs.
2 Preliminaries and Notation
The paper defines its regression error notation and the certifiable hypercontractivity assumption used for the input marginal. This assumption includes several natural distribution families.
- For a distribution D and function f, err_D(f) is the expected squared prediction error; for a vector ℓ, err_D(ℓ) uses ⟨ℓ,x⟩.
- The paper studies input distributions including Gaussian, log-concave, and product distributions.
- Certifiable hypercontractivity requires degree-k sum-of-squares proofs of moment inequalities for linear functions up to degree k/2.
- Gaussian, Boolean-hypercube, and strongly log-concave distributions satisfy certifiable hypercontractivity under the stated conditions.
3 Robust Certifiability
Robust certifiability connects low regression error on a sufficiently large corrupted sample to low error on the uncorrupted distribution. Hypercontractivity enables consistency, whereas arbitrary distributions do not generally permit it.
- For nice input distributions, a hypothesis inferred from a large enough corrupted sample has low error on the uncorrupted distribution.
- Without distributional assumptions, non-trivial robust-regression guarantees are information-theoretically impossible.
- The incurred error depends on the best-fitting hypothesis’s L2 squared loss, so consistency is not obtained without additional distributional assumptions.
- The L2 certifiability result assumes total variation distance at most ε and certifiable C-hypercontractivity of the input marginal.
- The result applies when η satisfies 2C(k/2)η^(1−2/k) < 0.9.
- The robust-certifiability argument extends from L2 linear regression to polynomial regression.
4 Sum of Squares proofs and Sum of Squares Optimization
The paper introduces pseudo-distributions and sum-of-squares proofs as a convex framework for reasoning about polynomial constraints. Low-degree SoS optimization is computationally efficient for explicitly bounded systems.
- Pseudo-distributions relax probability distributions by requiring only low-degree non-negativity tests.
- A degree-ℓ pseudo-distribution is represented through moments of monomials up to degree ℓ, forming a convex optimization domain.
- Weak separation for moment tensors provides the algorithmic basis for efficient approximate optimization over pseudo-distributions.
- The level-ℓ sum-of-squares algorithm optimizes over level-ℓ pseudo-distributions satisfying polynomial constraints.
- An explicitly bounded satisfiable system with n variables and m constraints can be optimized approximately in (n+m)^O(ℓ) time.
- Sum-of-squares proofs allow properties of constrained pseudo-distributions to be deduced using polynomial certificates.
5 Algorithm
The section develops polynomial-time robust regression algorithms using sum-of-squares optimization, proving guarantees for corrupted samples under certifiable hypercontractivity and related assumptions. It also extends the approach to robust L1 regression and establishes analogous polynomial-regression results.
- Extensions: Analogous guarantees extend to outlier-robust polynomial regression, while the dependence of the error on η is identified as potentially suboptimal.The polynomial-regression extension is stated separately, and improving its η dependence remains open.
- Algorithm: The algorithm receives an η-corrupted labeled sample from a certifiably hypercontractive distribution and searches for a feasible level-k pseudo-distribution via sum-of-squares optimization.The formulation relaxes selecting a large uncorrupted subset and jointly fitting a regression function.
- Analysis: The proof separates optimization error from generalization error, then controls both through robust certifiability and truncation of large residual values.Truncation produces a nearby distribution where the relevant k-th residual moment is bounded, enabling concentration arguments.
- Analysis: The optimization analysis bounds empirical squared error by (1 + O(C)η^(1−2/k)) · c_optSOS + O(C)η^(1−2/k)c_optk.This bound appears in the pseudo-distribution analysis and is combined with generalization bounds to prove the main theorem.
- Extensions: Robust L1 regression is also presented, with analogous proofs and a robust-certifiability lemma as its main technical ingredient.This result is framed separately from the hypercontractive L2 analysis.
6 Statistical Limits of Outlier-Robust Regression
The section shows that robust regression cannot achieve distribution-independent guarantees under sample contamination. Simple indistinguishable-distribution constructions establish a constant lower bound on achievable error.
- Necessity of assumptions: Without assumptions on the input distribution, no estimator can guarantee error h(η) tending to zero as η tends to zero under sample contamination.This contrasts with classical least-squares regression, where bounded labels support consistency without marginal-distribution assumptions.
- Lower bound: There is a universal constant c > 0 such that, for every η > 0, no algorithm always finds a hypothesis with error below c from η-corrupted samples.The lower bound applies to distributions with labels in [−1, 1].
- Lower-bound construction: Two distributions can each be realized by η-corruptions of a common distribution while having different zero-error linear predictors.One construction uses predictors (0, 1) and (1, 0), making the observed corrupted samples statistically ambiguous.
- Scope: The lower-bound argument also applies in the weaker Huber contamination model, although that model is not studied in the paper.This extends the stated statistical obstruction beyond the contamination model used for the main algorithms.
- Lower-bound construction: For sufficiently large κ and κ ≥ 1/√η, every linear predictor has constant error on at least one of the paired distributions.The construction yields err_D(w) + err_D′(w) ≥ 1 + ηκ^2 and consequently a constant lower bound for one distribution.
A Outlier-Robust Polynomial Regression
The paper extends its outlier-robust regression framework from linear functions to bounded-degree polynomials. The extension uses polynomial certifiable hypercontractivity and yields analogous guarantees under the corresponding marginal-distribution assumption.
- Extension: The framework extends straightforwardly to outlier-robust polynomial regression.The paper elaborates the extension through a polynomial version of its robust-certifiability analysis.
- Assumption: Certifiable polynomial hypercontractivity requires sum-of-squares proofs controlling polynomial moments up to the specified degree.The definition applies to degree-t polynomial features and a degree-k sum-of-squares proof system.
- Assumption: Many natural distributions, including Gaussian and bounded-marginal product distributions on the hypercube, satisfy the polynomial hypercontractivity condition.The stated class supplies examples to which the polynomial-regression results apply.
- Guarantee: For distributions with polynomially certifiable hypercontractive marginals, the theorem compares a learned degree-t polynomial's squared error with the best degree-t polynomial of bounded bit complexity.The labels are bounded in [−M, M], and the optimizer is defined over degree-t polynomials.