The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty

Tal Amir, Ronen Basri, Boaz Nadler

Introduction

Sparse recovery—the task of identifying a small number of relevant features from a high-dimensional dataset—is a cornerstone of modern signal processing, statistics, and machine learning. The gold standard for this task is "best subset selection," which seeks to minimize the residual sum of squares subject to an $L_0$-norm constraint. However, this problem is NP-hard. While the $L_1$-regularized Lasso is a popular convex relaxation, it introduces significant bias and often fails to recover the true support when features are highly correlated or the signal-to-noise ratio is low.

This paper explores the Trimmed Lasso, a non-convex penalty that bridges the gap between the $L_1$ and $L_0$ norms by penalizing only the smallest $d-k$ coefficients. While theoretically powerful, the Trimmed Lasso is non-smooth and notoriously difficult to optimize. The authors propose the Generalized Soft-Min (GSM) penalty, a smooth surrogate that enables efficient, high-quality sparse recovery through a novel recursive algorithm and a homotopy optimization framework.

The Generalized Soft-Min (GSM) Penalty

The core challenge of the Trimmed Lasso is its combinatorial nature. To address this, the authors introduce the GSM penalty, which uses a "softness" parameter $\gamma$ to interpolate between the standard Lasso and the Trimmed Lasso.

  1. Smooth Interpolation: When $\gamma = 0$, the GSM penalty reduces to the $L_1$ norm (Lasso). As $\gamma$ increases toward infinity, the penalty converges to the Trimmed Lasso. This allows for a continuation approach where the optimizer starts with a simple convex problem and gradually moves toward the non-convex target.
  2. Bias Reduction: Unlike the Lasso, which applies a uniform shrinkage to all coefficients (including the large, significant ones), the GSM penalty focuses its regularization pressure on the smallest coefficients. This preserves the magnitude of the true signal, leading to lower estimation bias and better support recovery.

Efficient Computation and Optimization

A naive implementation of the GSM penalty would require summing over $\binom{d}{k}$ possible sparse patterns, which is computationally impossible for large dimensions. The authors overcome this via two primary innovations:

The Recursive Algorithm

The authors derive a recursive dynamic programming-style algorithm that computes the GSM penalty and its gradient in $O(kd)$ time. This reduction from exponential to linear complexity (relative to dimension $d$ and sparsity $k$) makes the GSM penalty as computationally feasible as many standard regularizers.

Homotopy and Majorization-Minimization (MM)

To navigate the non-convex landscape of the Trimmed Lasso, the authors employ a Majorization-Minimization (MM) framework within a homotopy scheme. The process begins by solving the easy convex Lasso problem. The solution is then used to initialize the next step as $\gamma$ is incrementally increased. This "warping" of the objective function guides the optimizer toward a high-quality local minimum of the Trimmed Lasso objective, effectively avoiding the poor local minima that plague direct non-convex optimization methods like ADMM or DC programming.

Experimental Evaluation

The performance of the GSM-based Trimmed Lasso was evaluated using extensive synthetic benchmarks against state-of-the-art methods, including Iterative Support Detection (ISD), Iterative Reweighted Least Squares (IRLS), Orthogonal Matching Pursuit (OMP), and the Mixed Integer Programming (MIP) based L0Learn solver. The testing suite included uncorrelated random matrices and highly correlated matrices (Toeplitz-like correlation $\rho=0.8$).

Key Findings

  • Resilience to Correlation: In settings where most methods fail due to feature correlation, GSM maintained a high recovery rate. For example, in a $100 \times 800$ matrix setting, GSM successfully recovered signals with significantly higher sparsity levels ($k$) than ISD or OMP.
  • Sample Efficiency: GSM requires fewer measurements ($n$) to achieve perfect recovery compared to its closest competitors.
  • Comparison to MIP: While MIP solvers like L0Learn are highly optimized for speed, GSM demonstrated superior support precision in challenging, low-SNR scenarios where MIP-based heuristics often struggled.
  • Theoretical Stability: The authors provide theoretical guarantees, proving that for a sufficiently large penalty parameter $\lambda$, any local minimum of the objective is $k$-sparse. They also establish stable recovery bounds under a variant of the Restricted Isometry Property (RIP).

Conclusion

The Generalized Soft-Min penalty provides a robust and computationally efficient path to solving the Trimmed Lasso problem. By combining the theoretical advantages of non-convex regularization with the practical benefits of smooth optimization and homotopy, the authors offer a powerful tool for sparse recovery in high-dimensional, highly correlated settings. While the current implementation carries some computational overhead compared to simple greedy heuristics, its superior recovery performance makes it a compelling choice for applications where accuracy is paramount. Future work will focus on automated parameter selection and testing the GSM penalty on real-world genomic and imaging datasets.

Summary updated

BibTeX
@article{amir2021trimmed,
  author = {Tal Amir and Ronen Basri and Boaz Nadler},
  title = {{The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty}},
  journal = {SIAM J. Math. Data Sci.},
  year = {2021},
  doi = {10.1137/20m1330634},
}
Figure