A Practical Scheme and Fast Algorithm to Tune the Lasso With Optimality Guarantees

Michael Chichignoud, Johannes Lederer, Martin J. WainwrightJMLR 2016 · OpenReview

TL;DR

This paper introduces a new, theoretically guaranteed method called Adaptive Validation for $l_\infty$ (AV$_\infty$) to select the regularization parameter for Lasso regression. It offers optimal finite-sample performance and a computationally efficient algorithm, outperforming standard methods like Cross-Validation in simulations.

What Problem Does This Paper Address?

In high-dimensional linear regression, the Lasso is a popular technique for simultaneously performing variable selection and coefficient shrinkage. However, its performance heavily relies on choosing an appropriate regularization parameter (often denoted by $\lambda$). Traditional methods for tuning this parameter, such as Cross-Validation (CV) or BIC-type criteria, either suffer from high computational costs or lack strong theoretical guarantees, especially in non-asymptotic settings. This paper addresses the critical need for a Lasso tuning method that is both theoretically sound (providing optimality guarantees) and practically efficient, particularly for controlling the $l_\infty$ norm of the estimation error.

Methods

The core contribution is the Adaptive Validation for $l_\infty$ (AV$_\infty$) scheme. This method is inspired by Lepski's method for bandwidth selection in non-parametric regression. The key idea is to perform a series of statistical tests on Lasso estimates obtained with different regularization parameters. Specifically, AV$_\infty$ selects a tuning parameter $\hat{\lambda}$ by finding the smallest $\lambda$ in a predefined grid such that the difference between Lasso estimates at $\lambda$ and a slightly larger $\lambda'$ is "small" relative to the difference between $\lambda$ and $\lambda'$. This "smallness" is quantified using a test based on the sup-norm difference of Lasso estimates.

The paper also provides a fast algorithm (Algorithm 1) to implement AV$_\infty$. This algorithm involves iterating backward through a sorted grid of potential $\lambda$ values, stopping when a specific condition related to the Lasso estimate differences is met. A crucial theoretical result (Theorem 3) guarantees that AV$_\infty$ achieves near-optimal $l_\infty$ error bounds, matching an "oracle" choice of $\lambda$ up to a small constant factor, with high probability. The paper also discusses conditions on the design matrix (e.g., diagonal dominance) that ensure these theoretical guarantees hold.

Datasets

The paper uses simulated data for evaluation. The simulations involve generating data from linear regression models with varying numbers of observations ($n$) and predictors ($p$), as well as different levels of correlation ($\kappa$) in the design matrix. Real data from a study on riboflavin production in B. subtilis is also used to demonstrate variable selection performance.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper successfully bridges the gap between theoretical optimality guarantees for Lasso tuning and practical, computationally efficient algorithms.
  • Lepski's Method Adaptation: The novel adaptation of Lepski's method for bandwidth selection to the Lasso tuning problem is a key innovation. This approach leverages statistical tests to make data-driven decisions about the regularization parameter.
  • Optimality in $l_\infty$ Norm: The method provides strong theoretical guarantees for controlling the $l_\infty$ estimation error, which is crucial for understanding the worst-case performance of the Lasso.
  • Computational Efficiency: AV$_\infty$ is significantly faster than k-fold Cross-Validation, requiring the computation of only one Lasso path, making it more practical for large datasets.
  • Variable Selection Guarantees: Beyond estimation, the method also offers theoretical insights into variable selection performance, enabling a "safe threshold" for identifying relevant features.

Key Results

  • Theoretical Guarantees: Theorem 3 shows that AV$_\infty$ achieves $l_\infty$ error bounds that are optimal up to a constant factor (specifically, within a factor of 3 of the oracle) with high probability.
  • Performance Comparison: In simulations, AV$_\infty$ consistently outperforms 10-fold Cross-Validation in terms of $l_\infty$ error across various settings of $p$ and $\kappa$.
  • Computational Speed: AV$_\infty$ is approximately $k$ times faster than $k$-fold Cross-Validation, where $k$ is the number of folds.
  • Variable Selection: For variable selection, AV$_\infty$ with a specific thresholding strategy (size $3C\hat{\lambda}$) leads to a considerably smaller number of false positives compared to Cross-Validation, while maintaining a low number of false negatives.
  • Real Data Application: The method shows competitive variable selection results on the B. subtilis dataset, aligning with other established methods.

Limitations and Future Work

  • Design Matrix Conditions: The theoretical guarantees for $l_\infty$ estimation and variable selection rely on certain conditions on the design matrix (e.g., diagonal dominance, compatibility). While the paper discusses verifiable conditions, these are still assumptions that might not hold in all real-world scenarios.
  • Generalizability to Other Penalties: The paper focuses exclusively on the Lasso. The authors suggest that the developed methods could be extended to problems with non-convex penalties (like SCAD, MCP) or other decomposable penalty functions (like the nuclear norm for matrix estimation).
  • Other Objectives: The current work targets $l_\infty$-estimation and variable selection. Future work could explore adaptations for other objectives like prediction or $l_2$-estimation, which might require different theoretical frameworks and could involve unknown quantities like sparsity.
  • Model Misspecification: The robustness of the AV$_\infty$ scheme to model misspecification (e.g., non-linearities) is an open question for future research.

Summary updated

Abstract

We introduce a novel scheme for choosing the regularization parameter in high-dimensional linear regression with Lasso. This scheme, inspired by Lepski’s method for bandwidth selection in non-parametric regression, is equipped with both optimal finite-sample guarantees and a fast algorithm. In particular, for any design matrix such that the Lasso has low sup-norm error under an “oracle choice” of the regularization parameter, we show that our method matches the oracle performance up to a small constant factor, and show that it can be implemented by performing simple tests along a single Lasso path. By applying the Lasso to simulated and real data, we find that our novel scheme can be faster and more accurate than standard schemes such as Cross-Validation.
BibTeX
@article{chichignoud2016practical,
  author = {Michael Chichignoud and Johannes Lederer and Martin J. Wainwright},
  title = {{A Practical Scheme and Fast Algorithm to Tune the Lasso With Optimality Guarantees}},
  journal = {J. Mach. Learn. Res.},
  year = {2016},
  url = {https://openreview.net/forum?id=TKnPDFDBcb},
}
Figure