Source-linked AI summary
Efficient Algorithms and Lower Bounds for Robust Linear Regression
Ilias Diakonikolas, Weihao Kong, Alistair Stewart
TL;DR
The paper studies high-dimensional linear regression with adversarially corrupted samples, seeking tradeoffs among sample complexity, computational complexity, and robustness. It develops efficient robust algorithms and SQ lower bounds, including an O(σε log(1/ε)) estimation guarantee and computational barriers for stronger accuracy.
Problem
The paper asks how to robustly estimate the regression vector when an ε-fraction of labeled samples may be arbitrarily corrupted, while balancing sample and computational complexity.
Method
The paper combines filtering-based robust mean estimation for known covariance with robust covariance learning for unknown covariance, and analyzes Statistical Query lower bounds under Huber contamination.
Results
O(σε log(1/ε)) estimation error is achieved efficiently with nearly optimal labeled-sample complexity, while the SQ lower bound rules out o(√ε σ) error for algorithms with estimation complexity O(d^{2-c}).
Takeaways & Limitations
Efficient robust regression can match the known-covariance error guarantee for unknown covariance using an additional ˜O(d^2/ε^2) samples, while stronger accuracy has a computational barrier.
Takeaways & Limitations
The algorithmic analysis includes a dependence on sufficiently large sample sizes, and uniformly controlling the relevant second moments for arbitrary candidate vectors requires at least Ω(d^2) samples.
Abstract
from arXiv · showhide
We study the problem of high-dimensional linear regression in a robust model where an $ε$-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, Σ)$ 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β$ which approximates the unknown regression vector $β$ within $\ell_2$-norm $O(ε\log(1/ε) σ)$, where $σ$ is the standard deviation of the random observation noise. An error of $Ω(εσ)$ is information-theoretically necessary, even with infinite sample size. Prior work gave an algorithm for this problem with sample complexity $\tildeΩ(d^2/ε^2)$ whose error guarantee scales with the $\ell_2$-norm of $β$. 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/ε^2)$ unlabeled examples. On the other hand, an error of $O(εσ)$ can be information-theoretically attained with $O(d/ε^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 $Ω(\sqrtε σ)$.
1 Introduction
The paper studies high-dimensional linear regression with adversarially corrupted samples and Gaussian covariates, targeting tradeoffs among robustness, sample complexity, and computation. It gives efficient algorithms with near-optimal error and SQ lower bounds showing computational-statistical tradeoffs for unknown covariance.
- Problem setting: The model allows an adversary to change an arbitrary ε-fraction of labeled samples, while the goal is accurate ℓ2 estimation of β.The studied covariates are Gaussian with covariance either known or unknown, and observation noise is Gaussian.
- Known covariance algorithms: O(d/ε^2) samples support a basic efficient robust regression algorithm, but its error depends on ∥β∥2 and does not vanish as σ approaches zero.The basic approach reduces robust regression to robust mean estimation using yX and filtering.
- Known covariance algorithms: O(d/ε^2) samples yield an efficient estimator with error O(σε log(1/ε)) when the covariance is known to be the identity.This matches the information-theoretic lower bound Ω(σε) up to a logarithmic factor.
- Unknown covariance: ˜O(d^2/ε^2) additional samples suffice to robustly learn unknown covariance and reduce the problem to the known-covariance algorithms.The same approach works when the covariance is only approximately known.
- SQ lower bounds: O(d/ε^2) samples information-theoretically suffice for O(εσ) error with unknown covariance, whereas efficient SQ methods face a computational tradeoff.The SQ lower bound rules out o(√ε) error unless algorithms use exponentially many queries or queries requiring Ω(d^2) samples to simulate.
2 Robust Algorithm for Linear Regression
This section develops iterative filtering algorithms for robust linear regression under adversarial corruption. For identity covariance, the method achieves near-optimal sample complexity and error guarantees, while an extended procedure removes dependence on ∥β∥.
- Algorithmic framework: The iterative algorithm repeatedly either estimates β or returns a cleaner dataset for another filtering iteration.The procedure terminates after repeatedly invoking the filtering subroutine on progressively cleaner data.
- Identity covariance: The filter estimates σ_y, computes the empirical mean and covariance of yX, and tests whether their relationship is consistent with uncorrupted data.If a direction violates the expected tail behavior, the algorithm identifies a threshold and removes offending samples.
- Identity covariance: O(d/ε^2 polylog(d/(ετ))) samples suffice for the identity-covariance algorithm to achieve error O(σ_y ε log(1/ε)) with probability at least 1−τ.The clean sample set satisfies the required regularity conditions with high probability at this sample size.
- Regularity conditions: The clean-set regularity conditions include bounded samples, empirical tail bounds, and concentration of empirical means and covariances.These conditions hold with high probability for near-linear sample size and support the correctness of the filtering procedure.
- Removing dependence on ∥β∥: O(d/ε^2 polylog(d/(ετ))) samples also yield error O(σε log(1/ε)) without dependence on ∥β∥.The improved method filters residuals, covariates, and residual-covariate products after computing an ordinary least-squares estimate.
3 Statistical Query Lower Bounds
This section establishes an SQ lower bound for robust linear regression with unknown covariance and noise. The construction makes the regression direction difficult to identify by matching low-order conditional moments after contamination.
- Lower-bound setting: The lower-bound setting uses Huber contamination with unknown bounded covariance Σ and unknown bounded noise variance σ^2.The observed distribution is Q′=(1−ε)Q+εN, where Q is the clean joint distribution of (X,y).
- SQ lower bound: SQ algorithms cannot achieve error o(√ε) on all instances without more than 2^{Ω(d^c)}d^{4c−2} oracle calls for any c>0.The theorem applies under 1/2 I ⪯ Σ ⪯ I and σ^2≤1.
- Scope of the bound: The lower bound remains meaningful because the covariance is bounded below; without that condition, directions in the null space of Σ would be unidentifiable.The paper explicitly contrasts this with the case where Σv=0 for a nonzero v.
- Proof intuition: The construction makes X conditioned on y standard Gaussian in directions orthogonal to the regression direction while matching the first three moments in that direction.This prevents SQ algorithms from reliably finding the direction of β.
- Proof intuition: When ∥β∥^2=O(√ε), matching the first three conditional moments requires only an O(μ^2) noise fraction before averaging over y.The resulting overall added noise remains below ε in the stated regime.
A Proof of Proposition 2.3: Deterministic Regularity Conditions for Algorithm 1
This proof establishes that clean Gaussian samples satisfy the deterministic regularity conditions required by the identity-covariance filtering algorithm. The argument combines Gaussian concentration, tail bounds, and empirical covariance control.
- Covariance control: The proof uses Hanson–Wright concentration to control quadratic forms and thereby establish empirical covariance regularity.The bounded-support portion is handled by standard covariance concentration, while the unbounded tail has small probability and limited covariance effect.
- Proposition 2.3: N=Ω((d/ε^2) polylog(d/(ετ))) clean samples are (ε,τ)-good with probability at least 1−τ.These conditions are the basis for Proposition 2.3 and the near-optimal sample complexity of the algorithm.
- Concentration and tails: Gaussian concentration bounds uniformly control sample magnitudes and the tails of one-dimensional projections.The proof first bounds coordinates and norms, then extends scalar tail bounds to all directions using a covering argument.
- Concentration and tails: The empirical tail bound is Pr[|v·X|>T]≤5 exp(−T^2/4)+ε^2 for every unit vector v and threshold T.This bound is obtained by combining one-dimensional Gaussian estimates with a net over unit directions.
- Mean concentration: The empirical mean estimate satisfies ∥β_S−β∥_2≤εσ_y with probability at least 1−τ/10 at the stated sample size.This is one of the deterministic conditions required by the filtering algorithm.
A.1 Handling Approximate Identity Covariance
The approximate-identity setting extends the identity-covariance analysis to covariance matrices close to I. The unknown-covariance algorithm first estimates Σ robustly, then applies the known-covariance regression procedure.
- Approximate identity covariance: If (1−ε)I⪯Σ⪯(1+ε)I, the same algorithm achieves the identity-case guarantee under modified regularity conditions.The clean samples satisfy these conditions with high probability using Ω((d/ε^2) polylog(d/(ετ))) samples.
- Reduction: The reduction sets Z=Σ^−1/2X, transforming the approximately known covariance problem into an identity-covariance Gaussian regression problem.The transformed pair (y,Z) is analyzed using the identity-covariance regularity proposition.
- Unknown covariance: ṼO(d^2/ε^2) additional samples suffice to robustly estimate the covariance before applying the known-covariance regression algorithm.This two-stage procedure yields the desired efficient result for unknown covariance.
B Proof of Proposition 2.1
The proof establishes that filtering reduces the discrepancy between the corrupted and uncorrupted sample sets, while controlling the regression and spectral errors. It concludes that the returned estimate has error O(σ_y ε log(1/ε)).
- Matrix control: The proof bounds the contribution of the removed set through the quadratic form |v^T M_L v| for every unit vector v.This reduces the operator-norm analysis to one-dimensional expectations over the removed samples.
- Regression-error control: O(σ_y ε log(1/ε)) bounds the deviation of β_S′ from β after accounting for retained corruptions.The decomposition separates the corruption contribution from the controlled error term.
- Small spectral norm: O(σ_y^2 ε log^2(1/ε)) controls the small-spectral-norm case used to justify the algorithm’s returned vector.The argument bounds the spectral contribution of the retained set and derives the corresponding regression estimate.
- Large spectral norm: The large-spectral-norm case guarantees that a threshold T satisfying the filtering condition in Step 10 exists.The contradiction argument uses λ* = O(σ_y^2 ε log^2(1/ε)) together with the bound ελ* ≤ λ.
- Progress of filtering: ∆(S, S′′) < ∆(S, S′) whenever the filter removes more corrupted than uncorrupted samples.The proof compares rejected points from S′\S with rejected points from S∩S′.
C Deterministic Regularity Conditions for Algorithm 2
This section defines deterministic regularity conditions for uncorrupted Gaussian samples and shows that sufficiently many samples satisfy them with high probability. These conditions control means, covariances, tails, and conditioned moments needed by the filtering algorithm.
- Representative samples: O(d polylog(d/ετ)/ε^2) uncorrupted samples suffice for S to be (ε, τ)-representative except with probability 1/τ.The representative conditions provide the deterministic regularity framework used by Algorithm 2.
- Covariate regularity: O(ε) bounds the empirical mean and covariance deviations of Gaussian covariates with probability at least 1 − τ/10.The bounds are obtained from standard Gaussian mean and covariance estimation results.
- Residual tails: 10 exp(−T^2/16σ_β′^2) bounds the empirical residual tail probability for every β′ and threshold T.Here σ_β′^2 = σ^2 + ∥β − β′∥_2^2.
- Product tails: 24 exp(−T/16σ_β′^2) bounds the conditioned tail of (y − β′ · X)(v · X) for every unit vector v.The bound applies to the residual-filtered sample set R_β′,T′.
- Conditioned moments: εσ^2 bounds the discrepancy between conditioned second moments under R_β′,T′ and D_β′,T′.A corresponding first-moment discrepancy is bounded by εσ_β′.
D.1 Analysis if we Remove Samples at Any Step
The analysis shows that each filtering step strictly improves the discrepancy between the current sample set and the uncorrupted set. The argument applies both to the subgaussian filters and to the residual-based filter.
- Subgaussian filtering: ∆(S, S′′) < ∆(S, S′) holds when either Step 7 or Step 13 returns a filtered subset.The representative conditions satisfy the requirements of the subgaussian filter.
- Residual filtering: ∆(S \ U, S′′ \ U) < ∆(S \ U, S′ \ U) holds for the residual-based filter applied after removing U.The conditions on S′\U match those required for the earlier filtering proof.
- Filter reduction: The residual-based filter is equivalent to the earlier filter after replacing y by y − β′ · X.This reduction lets the correctness argument from the earlier section apply directly.
D.2 Analysis of Correctness if we Return β′
The correctness analysis bounds the effect of removing a small set U and transfers the resulting moment control into an estimate of β. It concludes that the returned β′ is O(ε log(1/ε)σ)-accurate.
- Effect of removing U: |U| ≤ ε|S′| after Step 7, so removing U affects the relevant moments only by controlled amounts.The resulting quadratic and linear moment contributions are bounded by O(ε log(1/ε)) factors.
- Moment control: O(ε log(1/ε)σ_β′) bounds the residual moment ∥E_S′\U[(y − β′ · X)X]∥_2.This follows from controlling the contribution of U and applying Cauchy–Schwarz.
- Regression correction: O(ε log(1/ε)σ_β′) bounds the distance between the residual moment and β − β′.The bound transfers the small-spectral-norm analysis to the residual-filtered set.
- Final accuracy: O(ε log(1/ε)σ) bounds ∥β − β′∥_2 for sufficiently small ε.The self-referential σ_β′ bound is converted to a σ-scaled bound using σ_β′ ≤ σ + ∥β − β′∥_2.
E Proof of Theorem 3.1: Statistical Query Lower Bounds
The proof constructs corrupted regression distributions whose conditional covariates match low-order Gaussian moments, making the hidden regression direction difficult for statistical-query algorithms. Bounding pairwise correlations then yields the stated SQ lower bound.
- Theorem 3.1 rules out SQ algorithms achieving o(√ε) estimation error under unknown noise and covariance bounded by (1/2)I ⪯ Σ ⪯ I.
- The construction modifies X conditioned on y so it matches the first three moments of a standard Gaussian while retaining a hidden direction.This adapts the direction-hiding construction of [DKS17c] to the regression setting.
- Lemma E.2 supplies a distribution matching the first three Gaussian moments by mixing N(µ, 2/3) with an additional distribution.
- The resulting corrupted distribution is an ε-contamination of the original regression distribution.
- A large set of nearly orthogonal hidden directions has bounded pairwise statistical correlation, enabling the classical SQ lower-bound argument.The proof obtains a query lower bound of at least 2^Ω(d^c)d^(4c−2) in the cited construction.
F Proof of Lemma E.2
Lemma E.2 constructs moment-matching distributions that approximate a shifted Gaussian using a small contamination component. The proof uses case-based Gaussian mixtures and bounds their chi-square divergence from the standard Gaussian.
- Lemma E.2 constructs A_µ matching the first three moments of N(0, 1) while containing (1−ε_µ)N(µ, 2/3) plus ε_µB_µ.
- The construction uses several three-Gaussian mixtures whose parameters satisfy the first-, second-, and third-moment constraints.
- The mixture parameters can be chosen with component standard deviations between 0.9 and 1.1.
- The resulting distribution A_µ,ε is well-defined and has first three moments 0, 1, and 0.
- For the large-µ case, the Gaussian means remain O(1/√ε), yielding χ2(P4,µ,ε, N(0, 1)) = eO(1/ε).