On Fast Convergence of Proximal Algorithms for SQRT-Lasso Optimization: Don't Worry About its Nonsmooth Loss Function

Xingguo Li, Haoming Jiang, Jarvis D. Haupt, Raman Arora, Han Liu, Mingyi Hong, Tuo ZhaoUAI 2019 · OpenReview

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.

The SQRT-Lasso loss function is generally smooth but exhibits nonsmoothness at the extreme where residuals are 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 optimization scheme uses warm starts to keep the solution trajectory within the fast convergence regions, avoiding the nonsmooth "kink".

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

BibTeX
@inproceedings{li2019fast,
  author = {Xingguo Li and Haoming Jiang and Jarvis D. Haupt and Raman Arora and Han Liu and Mingyi Hong and Tuo Zhao},
  title = {{On Fast Convergence of Proximal Algorithms for SQRT-Lasso Optimization: Don't Worry About its Nonsmooth Loss Function}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=l7re-zFJYU},
}
Figure