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

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

TL;DR

This paper tackles a fundamental problem in sparse linear regression: Lasso's poor performance with highly correlated features, often caused by unobserved latent variables. The authors introduce a "smart scaling" technique that preprocesses the data, allowing Lasso to achieve strong theoretical guarantees. Crucially, they also provide evidence that this improvement, particularly the quadratic dependence on sparsity, is computationally necessary for efficient algorithms.

What Problem Does This Paper Address?

Sparse Linear Regression (SLR) is a cornerstone of high-dimensional statistics, aiming to identify a few important features (a sparse signal) that explain an outcome. The Lasso algorithm is a popular, computationally efficient tool for SLR. However, Lasso's performance degrades significantly when the input features (covariates) are highly correlated. This is particularly problematic in real-world scenarios where correlations often arise from unobserved "latent" factors, making them difficult to directly account for. While computationally expensive methods like Best Subset Selection can handle these correlations, they are impractical for large datasets. This paper addresses the gap between the statistical efficiency of impractical methods and the computational efficiency but statistical inefficiency of Lasso in the presence of strong, latent-induced correlations. They aim to find an efficient algorithm that performs well even in these challenging settings and to understand the fundamental limits of such algorithms.

Methods

The core of the paper's algorithmic contribution is a novel preprocessing step called SmartScaling. Instead of the standard practice of scaling covariates to unit variance, SmartScaling adaptively rescales each covariate based on its empirical variance and its ability to be explained by other covariates. This is achieved through an iterative procedure that refines a diagonal scaling matrix. After this scaling, the standard Lasso algorithm is applied.

The theoretical analysis relies on a new concept of (a,h)-rescalability for covariance matrices, which captures settings where correlations are structured (e.g., low-rank plus diagonal). This concept unifies the two main settings considered in the paper: latent variable models and eigenspectra with outliers.

To establish computational-statistical gaps, the authors introduce a novel reduction from a problem in sparse Principal Component Analysis (PCA), specifically a "near-critical negative spike" variant, to sparse linear regression. This reduction, combined with an analysis of low-degree polynomial algorithms, provides evidence that the quadratic dependence on sparsity in their RescaledLasso algorithm is likely information-theoretically necessary for efficient algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design for synthetic data distributions (Gaussian random design).

Key Insights and Ideas

  • Smart Scaling as a "Fix" for Lasso: The paper demonstrates that a simple, adaptive rescaling of covariates can dramatically improve Lasso's performance in the presence of strong, latent-induced correlations, bridging the gap with more statistically powerful but computationally expensive methods.
  • Unifying Rescalability: The concept of (a,h)-rescalability provides a unified framework for understanding when Lasso can be made efficient, encompassing both latent variable models and structured eigenspectra.
  • Negative Spike PCA as a Hardness Oracle: The reduction from a specific, challenging variant of sparse PCA (near-critical negative spike) to sparse linear regression is a key technical innovation. This allows the authors to leverage existing hardness conjectures in PCA to argue for the necessity of their algorithm's complexity.
  • Computational-Statistical Tradeoff is Inherent: The paper provides strong evidence, via low-degree polynomial analysis, that the quadratic dependence on sparsity in their algorithm is not an artifact of their specific method but a fundamental limitation for any efficient algorithm in these settings.

Key Results

  • Efficient Algorithm (RescaledLasso): The proposed RescaledLasso algorithm achieves near-optimal sample complexity (up to a factor of $k^2$) for sparse linear regression in settings with structured correlations, matching information-theoretic bounds for certain parameters.
  • Computational-Statistical Gap: The paper establishes the first computational-statistical gap for sparse linear regression under a plausible conjecture (Low-Degree Hypothesis), showing that efficient algorithms require $\Omega(k^2 \log n)$ samples, whereas information-theoretically $\Omega(k \log n)$ suffice.
  • Application to Gaussian Graphical Models: The hardness results for sparse PCA are extended to establish a computational-statistical gap for learning Gaussian Graphical Models.

Limitations and Future Work

  • Quadratic Dependence on Sparsity: While the paper argues this is computationally necessary, the $\Omega(k^2)$ dependence on sparsity is still a factor of $k$ worse than the information-theoretic optimum. The authors suggest this gap might be closed for specific settings or with different algorithmic approaches.
  • Unknown Structure: The algorithms and analyses assume the existence of rescalability but do not require explicit knowledge of the underlying latent variables or the exact structure of the covariance matrix. However, learning this structure itself can be computationally hard, and the paper's approach bypasses this need.
  • Generalization to Other Models: The paper focuses on Gaussian random design. Extending the results to other distributions (e.g., sub-Gaussian) or misspecified models would be a valuable next step.
  • Practical Performance: While theoretically sound, the practical performance of SmartScaling and RescaledLasso compared to other methods in real-world applications would benefit from further empirical study. The paper includes a small simulation demonstrating improved performance over standard Lasso.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kelner2024lasso,
  author = {Jonathan A. Kelner and Frederic Koehler and Raghu Meka and Dhruv Rohatgi},
  title = {{Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps}},
  booktitle = {Conference on Learning Theory},
  year = {2024},
  url = {https://openreview.net/forum?id=QSTSwTMQF8},
}
Figure