# Feature Adaptation for Sparse Linear Regression

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 48 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Learning Some Popular Gaussian Graphical Models without Condition Number Bounds](https://mlsanity.com/paper/1905.01282/) (2019)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [On the Prediction Performance of the Lasso](https://mlsanity.com/paper/1402.1700/) (2014)
- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators](https://mlsanity.com/paper/1503.03188/) (2015)
- [Approximate Sparse Linear Regression](https://mlsanity.com/paper/1609.08739/) (2016)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Graph-based regularization for regression problems with alignment and highly-correlated designs](https://mlsanity.com/paper/1803.07658/) (2018)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [Approximate k-flat Nearest Neighbor Search](https://mlsanity.com/paper/1411.1519/) (2014)

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

- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Sparse Linear Regression and Lattice Problems](https://mlsanity.com/paper/2402.14645/) (2024)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Lasso and Partially-Rotated Designs](https://mlsanity.com/paper/2505.11093/) (2025)
- [Sparse Linear Regression is Easy on Random Supports](https://mlsanity.com/paper/2511.06211/) (2025)

## Abstract (arXiv)

Sparse linear regression is a central problem in high-dimensional statistics. We study the correlated random design setting, where the covariates are drawn from a multivariate Gaussian N(0,Sigma), and we seek an estimator with small excess risk. If the true signal is t-sparse, information-theoretically, it is possible to achieve strong recovery guarantees with only O(tlog n) samples. However, computationally efficient algorithms have sample complexity linear in (some variant of) the condition number of Sigma. Classical algorithms such as the Lasso can require significantly more samples than necessary even if there is only a single sparse approximate dependency among the covariates. We provide a polynomial-time algorithm that, given Sigma, automatically adapts the Lasso to tolerate a small number of approximate dependencies. In particular, we achieve near-optimal sample complexity for constant sparsity and if Sigma has few ``outlier'' eigenvalues. Our algorithm fits into a broader framework of feature adaptation for sparse linear regression with ill-conditioned covariates. With this framework, we additionally provide the first polynomial-factor improvement over brute-force search for constant sparsity t and arbitrary covariance Sigma.