Source-linked AI summary
Robust Regression via Hard Thresholding
Kush Bhatia, Prateek Jain, Purushottam Kar
TL;DR
Robust least squares regression must recover coefficients when response corruptions are chosen adversarially, a setting where prior exact-recovery results impose independence and restrictive design assumptions. The paper proposes TORRENT, a hard-thresholding family with universal recovery guarantees under mild data conditions, plus scalable gradient-based variants. Empirically, TORRENT variants recover more effectively and faster than L1 solvers, including a 20× speed advantage for TORRENT-HYB in a 50K-dimensional, 40%-corrupted problem.
Problem
RLSR seeks reliable coefficients under arbitrary response corruptions, while prior exact-recovery results require corruption independence from X and w* and restrictive data assumptions.
Method
The paper develops TORRENT, which alternates hard-thresholded active-set selection with model updates, and extends it with gradient-based methods for large-scale and sparse recovery.
Results
20× faster: TORRENT-HYB outperformed L1 solvers on a 50K-dimensional problem with 40% corrupted responses, while the algorithms also showed better recovery properties.
Takeaways & Limitations
TORRENT provides exact-recovery guarantees for adversarial corruptions under deterministic conditions satisfied by sub-Gaussian designs, with guarantees applying universally to w*.
Takeaways & Limitations
The formulation remains non-convex and may be NP-hard to optimize directly; the model also assumes sparse gross corruptions.
Abstract
from arXiv · showhide
We study the problem of Robust Least Squares Regression (RLSR) where several response variables can be adversarially corrupted. More specifically, for a data matrix X \in R^{p x n} and an underlying model w*, the response vector is generated as y = X'w* + b where b \in R^n is the corruption vector supported over at most C.n coordinates. Existing exact recovery results for RLSR focus solely on L1-penalty based convex formulations and impose relatively strict model assumptions such as requiring the corruptions b to be selected independently of X. In this work, we study a simple hard-thresholding algorithm called TORRENT which, under mild conditions on X, can recover w* exactly even if b corrupts the response variables in an adversarial manner, i.e. both the support and entries of b are selected adversarially after observing X and w*. Our results hold under deterministic assumptions which are satisfied if X is sampled from any sub-Gaussian distribution. Finally unlike existing results that apply only to a fixed w*, generated independently of X, our results are universal and hold for any w* \in R^p. Next, we propose gradient descent-based extensions of TORRENT that can scale efficiently to large scale problems, such as high dimensional sparse recovery and prove similar recovery guarantees for these extensions. Empirically we find TORRENT, and more so its extensions, offering significantly faster recovery than the state-of-the-art L1 solvers. For instance, even on moderate-sized datasets (with p = 50K) with around 40% corrupted responses, a variant of our proposed method called TORRENT-HYB is more than 20x faster than the best L1 solver.
1 Introduction
Robust least squares regression seeks reliable coefficients when response variables contain arbitrary corruptions, but existing formulations face computational and modeling limitations. The paper introduces Torrent, a thresholding approach with exact-recovery guarantees under milder, adversarially robust assumptions.
- Motivation: RLSR aims to learn reliable regression coefficients despite arbitrary corruptions in the response vector.The problem is relevant to applications including signal processing, economics, computer vision, and astronomy.
- Challenges: The joint optimization over clean points and model parameters is generally non-convex and can be NP-hard to optimize.
- Prior work: Existing L1-based exact-recovery results require corruptions selected independently of X and w* and impose restrictive data-distribution assumptions.Prior guarantees include isotropic Gaussian or incoherent orthogonal-matrix settings.
- Method: Torrent-FC alternates between estimating a clean active set and minimizing least-squares error on that set.The approach formalizes a long-standing thresholding heuristic for robust regression.
- Guarantees: Torrent-FC exactly recovers w* under adversarial corruptions when X satisfies subset strong convexity and smoothness, with these properties holding for sub-Gaussian data when n ≥ p log p.
- Guarantees: The guarantees allow adversarial corruption support and values, use less restrictive data assumptions, and hold universally for any w*.
- Empirical results: 20× faster: Torrent-HYB outperformed L1 solvers on a 50K-dimensional problem with 40% corrupted responses and achieved lower error rates.
2 Problem Formulation
The problem formulation models responses as a true linear signal plus dense noise and sparse, potentially unbounded corruptions. Adaptive adversaries may inspect the data and clean responses before choosing corruption locations and magnitudes.
- Model: The model permits the regressor w* to be chosen adaptively after the data features have been generated.
- Perturbations: Responses may contain dense bounded noise and sparse, potentially unbounded corruptions, with gross corruptions required to be sparse.
- Adversary: Adaptive adversaries can inspect data points, clean responses, and dense-noise values before selecting corruption locations and amounts.
- Notation: The clean-point set is represented by S* = supp(b), while the corruption vector satisfies ||b||_0 ≤ α · n.
- Data assumptions: SSC and SSS impose uniform subset-level curvature and smoothness conditions on the data matrix.
- Algorithmic setup: Torrent algorithms initialize a model and active set, threshold residuals to update the active set, and then apply fully corrective or gradient-based model updates.
3 Torrent: Thresholding Operator-based Robust Regression Method
Torrent uses hard thresholding to alternate between selecting low-residual active points and updating the regression model. Its FC, GD, and HYB variants trade off per-step progress and computational cost.
- Core strategy: The hard thresholding operator retains a specified number of vector entries with the smallest magnitudes.
- Core strategy: Torrent alternates between selecting points with the smallest residuals and fitting a better regressor on the resulting active set.
- Variants: Torrent-FC performs a fully corrective least-squares update, making substantial progress but requiring more expensive iterations.
- Variants: Torrent-GD replaces the corrective solve with a cheaper single gradient-descent step, reducing per-iteration cost but slowing progress.
- Variants: Torrent-HYB chooses FC or GD updates according to whether the active set is stable across iterations.
- Guarantees: All three variants are shown to have a linear convergence rate, with applicability extending to high-dimensional sparse recovery.
4 Convergence Guarantees
The convergence analysis establishes geometric recovery under deterministic subset curvature and smoothness conditions, including for sub-Gaussian designs. The guarantees extend across fully corrective, gradient, and hybrid updates and accommodate dense noise.
- Torrent-FC: Torrent-FC’s proof combines the fully corrective update with hard thresholding under SSC and SSS conditions.
- Deterministic conditions: The deterministic guarantees require a contraction condition involving the subset smoothness and strong-convexity parameters.
- Random designs: Gaussian and sub-Gaussian designs satisfy the required conditions with high probability under suitable sample-size assumptions.
- Noise and scope: The analyses accommodate dense noise in addition to sparse unbounded corruptions, although the hybrid condition can reduce noise tolerance.
- Torrent-GD: Torrent-GD converges linearly using a gradient update with a step length determined by the subset smoothness parameter.
- Torrent-HYB: Torrent-HYB retains convergence for arbitrary interleavings of FC and GD steps when their contraction factors satisfy 2 · ηFC · ηGD < 1.
5 High-dimensional Robust Regression
The paper extends TORRENT to sparse high-dimensional robust regression, targeting recovery with n proportional to s* log p rather than p. Torrent-HD uses iterative hard thresholding and achieves recovery guarantees under subset restricted conditions, including the same corruption tolerance as Torrent-FC.
- Sparse robust regression assumes y = X^T w* + b, with w* s*-sparse and at most α·n corrupted responses.
- The sparse setting seeks recovery with n ∼ s* log p samples instead of the n ≳ p sample complexity of low-dimensional regression.
- Torrent-HD modifies Torrent-FC using an iterative hard-thresholding update for target sparsity s ≪ p.The update is designed for efficient sparse recovery under restricted convexity and smoothness conditions.
- Under SRSC and SRSS assumptions, Torrent-HD obtains an ϵ-accurate solution after a finite number of iterations for admissible corruption and thresholding parameters.The theorem applies when β ≥ α and imposes a lower bound on the target sparsity parameter s.
- Torrent-HD has the same corruption tolerance as Torrent-FC, while requiring sample complexity identical to standard high-dimensional sparse-recovery analyses up to constants.
6 Experiments
Experiments compare Torrent variants with a tuned DALM-based L1 solver in low-dimensional and sparse high-dimensional regression. Across recovery and runtime evaluations, Torrent generally achieves lower error and substantially faster computation, including robust recovery at high corruption rates.
- Experiments use Gaussian regression data, randomized corruptions, white noise, and repeated trials for phase-transition and mean-performance plots.Low-dimensional phase-transition diagrams repeat experiments 100 times, while other plots average 20 random instances.
- Low Dimensional Results: As corruption magnitude increases from U(−∥y*∥∞, ∥y*∥∞) to U(−20∥y*∥∞, 20∥y*∥∞), Torrent-FC and Torrent-HYB reduce recovery error while L1 error increases.
- Runtime: Torrent-HYB recovered w* about 50× faster than L1-DALM on ill-conditioned data, while L1-DALM failed to reach residual error 10^-4 within 500 iterations.The hybrid method combines fully corrective and gradient-descent updates to improve convergence speed.
- High-dimensional Results: In sparse high-dimensional experiments, Torrent-HD achieved perfect recovery up to α = 0.7, whereas L1-DALM failed for α > 0.5.The experiments used n = 5s* log(p).
- High-dimensional Results: L1-DALM was an order of magnitude slower than Torrent-HD and required about 250 iterations to identify clean points versus 5 for Torrent-HD.
A Convergence Guarantees with Dense Noise and Sparse Corruptions
Torrent-FC and its extensions provide geometric convergence for robust regression with sparse adversarial corruptions and dense bounded noise under SSC/SSS design conditions. With random designs, the method yields approximate recovery whose error includes the dense-noise level.
- Algorithmic guarantee: Torrent-FC alternates clean-point selection by hard thresholding with least-squares model updates.The analysis tracks residuals, missed clean points, and mistakenly retained corrupted points.
- Random-noise specialization: For Gaussian dense noise, the resulting bound becomes ∥w_t−w*∥_2 ≤ ϵ + 2σC after sufficiently many iterations.The Gaussian specialization uses concentration bounds for the noise.
- Contraction analysis: The convergence analysis reduces to a contraction factor η<1 determined by the SSC/SSS constants and the corruption threshold.The proof establishes this condition by bounding contributions from corrupted recoveries and missed detections.
C Proof of Theorem 4
For Gaussian designs, the proof verifies the deterministic SSC/SSS conditions with high probability and obtains geometric convergence for corruption levels below the stated threshold.
- Random-design verification: Gaussian designs satisfy the required SSC and SSS properties with high probability after whitening.The proof uses the fact that whitening a Gaussian vector produces a standard normal vector.
- Recovery guarantee: For α<1/65, Algorithm 1 achieves the claimed recovery guarantee after a logarithmic number of iterations.A tighter proof improves the basic tolerance from α≤1/190 to α<1/65.
D Proof of Theorem 5
Theorem 5 replaces the least-squares update with gradient descent, preserving geometric convergence under comparable design assumptions while reducing per-iteration computational cost. A hybrid method combines both update types under a uniform interleaving condition.
- Torrent-GD: Torrent-GD uses a gradient descent update with step length η=1/Λ_{1−β} and retains the thresholding-based corruption handling.The proof separately bounds the model-error and retained-corruption contributions.
- Torrent-GD: After sufficiently many iterations, Torrent-GD reaches an ϵ-accurate solution satisfying ∥w_t−w*∥_2≤ϵ.The result follows from a geometric potential-function contraction.
- Torrent-HYB: Torrent-HYB converges for arbitrary interleavings of FC and GD steps when 2·η_FC·η_GD<1.The hybrid analysis shows that successive FC and GD updates preserve nontrivial progress.
F Proof of Theorem 9
Torrent-HD extends thresholding-based robust regression to sparse high-dimensional models by using iterative hard thresholding. Under sparse restricted design conditions, it achieves recovery with sample complexity scaling logarithmically in p and supports Gaussian and sub-Gaussian designs.
- Sparse extension: Torrent-HD replaces the full least-squares update with an IHT update for models with sparsity s*≪p.This targets recovery with n∼s*log p samples rather than n≳p.
- Sparse recovery guarantee: Under SRSC and SRSS conditions, Algorithm 2 obtains an ϵ-accurate sparse solution satisfying ∥w_t−w*∥_2≤ϵ.The proof adapts the restricted design analysis to vectors arising after the covariance transformation.
- Random-design guarantee: For Gaussian designs, recovery is guaranteed for α≤β<1/65 once n is sufficiently large relative to sparse dimension and log p.The same corruption tolerance as the low-dimensional result is obtained in the sparse setting.
- Scope and comparison: The sparse analysis extends to sub-Gaussian designs and uses the same corruption tolerance as Torrent-FC.The required sample complexity matches standard high-dimensional sparse-recovery analyses up to constants.
G Robust Statistical Estimation
The paper establishes recovery guarantees for robust estimation under Gaussian and sub-Gaussian designs, extending them to sparse high-dimensional settings. The resulting corruption tolerance is nonzero but depends on distributional and covariance properties.
- Gaussian designs satisfy the SSC and SSS properties with high probability, providing the conditions used for recovery guarantees.
- The analysis extends to isotropic and general sub-Gaussian designs, with constants depending on the sub-Gaussian norm and covariance matrix.
- The bounds permit a non-zero fraction of adversarially corrupted data points.
- The tolerable corruption fraction depends intricately on the sub-Gaussian norm, covariance condition number, and smallest covariance eigenvalue.
- For general sub-Gaussian distributions, the bounds are less explicit in universal constants than for standard Gaussian designs.
- In sparse high-dimensional recovery, Torrent-FC has noise-tolerance properties characterized by the same largest corruption index as its low-dimensional counterpart.
H Supplementary Results
The supplementary results develop concentration arguments for Gaussian designs and report recovery-error comparisons across problem dimensions, noise levels, sample sizes, and solver runtimes.
- The ordering argument relates norms over subsets selected by coordinate magnitude, supporting bounds used in the supplementary analysis.
- The analysis bounds chi-squared concentration using sub-exponential norms and exponential Markov inequalities.
- Torrent outperformed DALM-L1 as recovery error was evaluated while varying p, σ, and n.
- Figure 3(d) compares recovery error against runtime for several state-of-the-art L1 solvers.