# Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 79 references that are in the map.
- First posted on arXiv 23 Feb 2024.

## Builds on (most cited first, 30 of 33)

- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Sparse CCA: Adaptive Estimation and Computational Barriers](https://mlsanity.com/paper/1409.8565/) (2014)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [Learning Some Popular Gaussian Graphical Models without Condition Number Bounds](https://mlsanity.com/paper/1905.01282/) (2019)
- [Finding a sparse vector in a subspace: Linear sparsity using alternating directions](https://mlsanity.com/paper/1412.4659/) (2014)
- [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)
- [Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness](https://mlsanity.com/paper/1902.07380/) (2019)
- [Counterexamples to the Low-Degree Conjecture](https://mlsanity.com/paper/2004.08454/) (2020)
- [The Fine-Grained Hardness of Sparse Linear Regression](https://mlsanity.com/paper/2106.03131/) (2021)
- [Rounding Sum-of-Squares Relaxations](https://mlsanity.com/paper/1312.6652/) (2013)
- [Sum-of-Squares Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1507.06370/) (2015)
- [Certifiably Optimal Low Rank Factor Analysis](https://mlsanity.com/paper/1604.06837/) (2016)
- [Average-case Hardness of RIP Certification](https://mlsanity.com/paper/1605.09646/) (2016)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [Do semidefinite relaxations solve sparse PCA up to the information limit?](https://mlsanity.com/paper/1306.3690/) (2013)
- [Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators](https://mlsanity.com/paper/1503.03188/) (2015)
- [The Average-Case Time Complexity of Certifying the Restricted Isometry Property](https://mlsanity.com/paper/2005.11270/) (2020)
- [Scaling Law for Recovering the Sparsest Element in a Subspace](https://mlsanity.com/paper/1310.1654/) (2013)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Sparse PCA from Sparse Linear Regression](https://mlsanity.com/paper/1811.10106/) (2018)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm](https://mlsanity.com/paper/1711.04952/) (2017)
- [High Dimensional Linear Regression using Lattice Basis Reduction](https://mlsanity.com/paper/1803.06716/) (2018)

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

- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [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)

It is well-known that the statistical performance of Lasso can suffer significantly when the covariates of interest have strong correlations. In particular, the prediction error of Lasso becomes much worse than computationally inefficient alternatives like Best Subset Selection. Due to a large conjectured computational-statistical tradeoff in the problem of sparse linear regression, it may be impossible to close this gap in general. In this work, we propose a natural sparse linear regression setting where strong correlations between covariates arise from unobserved latent variables. In this setting, we analyze the problem caused by strong correlations and design a surprisingly simple fix. While Lasso with standard normalization of covariates fails, there exists a heterogeneous scaling of the covariates with which Lasso will suddenly obtain strong provable guarantees for estimation. Moreover, we design a simple, efficient procedure for computing such a "smart scaling." The sample complexity of the resulting "rescaled Lasso" algorithm incurs (in the worst case) quadratic dependence on the sparsity of the underlying signal. While this dependence is not information-theoretically necessary, we give evidence that it is optimal among the class of polynomial-time algorithms, via the method of low-degree polynomials. This argument reveals a new connection between sparse linear regression and a special version of sparse PCA with a near-critical negative spike. The latter problem can be thought of as a real-valued analogue of learning a sparse parity. Using it, we also establish the first computational-statistical gap for the closely related problem of learning a Gaussian Graphical Model.