Efficient Algorithms and Lower Bounds for Robust Linear Regression

2018/05/31 by Ilias Diakonikolas, Diakonikolas, Ilias, Weihao Kong +3 · 4 citations
Computer Science · Engineering · Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1806.00040

openalex publication_date 2018/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 N(0, Σ) on ℝ^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 ℓ₂-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 Ω(d²/ε²) whose error guarantee scales with the ℓ₂-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 O(d²/ε²) unlabeled examples. On the other hand, an error of O(εσ) can be information-theoretically attained with O(d/ε²) 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 Ω(√ε σ).

Cited by

• Provably Outlier-resistant Semi-parametric Regression for Transferable Calibration of Low-cost Air-quality Sensors
• PTF Testing Lower Bounds for Non-Gaussian Component Analysis
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
• Linear Regression under Missing or Corrupted Coordinates

Related

• Optimal Robust Linear Regression in Nearly Linear Time
• Robust and Tuning-Free Sparse Linear Regression via Square-Root Slope
• Robust Regression Revisited: Acceleration and Improved Estimation Rates
• Robust Linear Regression: Optimal Rates in Polynomial Time
• Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures