# Robust Sparse Regression with Non-Isotropic Designs

arXiv: https://arxiv.org/abs/2410.23937 · HTML: https://mlsanity.com/paper/2410.23937/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 38 references that are in the map.
- First posted on arXiv 31 Oct 2024.

## Builds on (most cited first, 23 of 23)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Outlier-robust moment-estimation via sum-of-squares](https://mlsanity.com/paper/1711.11581/) (2017)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression](https://mlsanity.com/paper/1903.08192/) (2019)
- [Better Agnostic Clustering Via Relaxed Tensor Norms](https://mlsanity.com/paper/1711.07465/) (2017)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [How Hard Is Robust Mean Estimation?](https://mlsanity.com/paper/1903.07870/) (2019)
- [Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally](https://mlsanity.com/paper/2110.11853/) (2021)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [Consistent regression when oblivious outliers overwhelm](https://mlsanity.com/paper/2009.14774/) (2020)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers](https://mlsanity.com/paper/2111.02966/) (2021)
- [Outlier-robust sparse/low-rank least-squares regression and robust matrix completion](https://mlsanity.com/paper/2012.06750/) (2020)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)

## Built on by (most cited first, 1 of 1)

- [Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians](https://mlsanity.com/paper/2502.06564/) (2025)

## Abstract (arXiv)

We develop a technique to design efficiently computable estimators for sparse linear regression in the simultaneous presence of two adversaries: oblivious and adaptive. We design several robust algorithms that outperform the state of the art even in the special case when oblivious adversary simply adds Gaussian noise. In particular, we provide a polynomial-time algorithm that with high probability recovers the signal up to error O(√varepsilon) as long as the number of samples n ≥ tildeO(k2/varepsilon), only assuming some bounds on the third and the fourth moments of the distribution D of the design. In addition, prior to this work, even in the special case of Gaussian design and noise, no polynomial time algorithm was known to achieve error o(√varepsilon) in the sparse setting n < d2. We show that under some assumptions on the fourth and the eighth moments of D, there is a polynomial-time algorithm that achieves error o(√varepsilon) as long as n ≥ tildeO(k4 / varepsilon3). For Gaussian distribution, this algorithm achieves error O(varepsilon3/4). Moreover, our algorithm achieves error o(√varepsilon) for all log-concave distributions if varepsilon ≤ 1/polylog(d). Our algorithms are based on the filtering of the covariates that uses sum-of-squares relaxations, and weighted Huber loss minimization with ℓ1 regularizer. We provide a novel analysis of weighted penalized Huber loss that is suitable for heavy-tailed designs in the presence of two adversaries. Furthermore, we complement our algorithmic results with Statistical Query lower bounds, providing evidence that our estimators are likely to have nearly optimal sample complexity.