Introduction
In high-dimensional statistics, the Lasso is a cornerstone for sparse regression. However, its performance is sensitive to the regularization parameter $\lambda$, which typically depends on the unknown noise level $\sigma$. The Square-Root-Lasso (SQRT-Lasso) addresses this by using the $\ell_2$ norm of residuals, making the optimal $\lambda$ "pivotal" (independent of $\sigma$). Despite its theoretical appeal, SQRT-Lasso is often avoided due to its nonsmooth loss function at the origin, which traditionally necessitated slower optimization methods like Second-Order Cone Programming (SOCP).
The SQRT-Lasso Challenge
The primary obstacle to using SQRT-Lasso is the nonsmoothness of the loss function $f(\theta) = \|y - X\theta\|_2$. This function is differentiable everywhere except where the residual vector $y - X\theta$ is zero.
As shown in Figure 1, the "kink" at the bottom of the loss surface suggests that standard gradient-based methods might struggle. However, in high-dimensional settings with noise, the model rarely achieves a perfect fit, meaning the optimization path typically stays within the smooth region.
Methodology: Proximal Algorithms and Pathwise Optimization
The authors propose that standard proximal algorithms—Proximal Gradient Descent (Prox-GD) and Proximal Newton—can achieve fast convergence for SQRT-Lasso when paired with a pathwise optimization strategy.
The pathwise scheme (Figure 2) starts with a large $\lambda$ and gradually decreases it. By using the solution from the previous $\lambda$ as a "warm start," the algorithm remains in a neighborhood where the loss function satisfies Restricted Strong Convexity (RSC) and Hessian Smoothness. This allows Prox-GD to achieve linear convergence and Prox-Newton to reach quadratic convergence rates, effectively treating the problem as if it were smooth.
Empirical Evaluation
The proposed methods were tested on several high-dimensional datasets, including synthetic sparse models and real-world data like the Greenhouse Gas Observing Network and DrivFace.
Key results include:
- Computational Speedup: On the Greenhouse dataset ($n=2,921, d=5,232$), Prox-Newton achieved convergence in 1.7 seconds, compared to 1,027 seconds for ADMM—a 600x improvement.
- Convergence Rates: Experiments confirmed that Prox-GD exhibits linear convergence, while Prox-Newton demonstrates quadratic convergence, as predicted by the local theory.
- Robustness: The "pivotal" property of SQRT-Lasso was maintained, with the algorithm performing consistently across varying noise levels without requiring $\lambda$ retuning.
Limitations and Future Work
While empirical results show global success, the current mathematical proofs are local, guaranteeing fast convergence once the algorithm is sufficiently close to the solution. Additionally, the exact number of steps required in the $\lambda$-path for guaranteed global convergence remains an open theoretical question.
Conclusion
This research demonstrates that the nonsmoothness of the SQRT-Lasso loss function is not a barrier to efficient optimization. By leveraging proximal algorithms and pathwise warm starts, practitioners can enjoy the "pivotal" benefits of SQRT-Lasso with the same computational efficiency as the standard Lasso. This "don't worry" philosophy suggests that many robust estimators previously thought to be computationally expensive may be solvable using efficient first- and second-order proximal methods.
Summary updated