On Fast Convergence of Proximal Algorithms for SQRT-Lasso Optimization: Don't Worry About Its Nonsmooth Loss Function
arXiv:1605.07950
Abstract
Many machine learning techniques sacrifice convenient computational structures to gain estimation robustness and modeling flexibility. However, by exploring the modeling structures, we find these "sacrifices" do not always require more computational efforts. To shed light on such a "free-lunch" phenomenon, we study the square-root-Lasso (SQRT-Lasso) type regression problem. Specifically, we show that the nonsmooth loss functions of SQRT-Lasso type regression ease tuning effort and gain adaptivity to inhomogeneous noise, but is not necessarily more challenging than Lasso in computation. We can directly apply proximal algorithms (e.g. proximal gradient descent, proximal Newton, and proximal Quasi-Newton algorithms) without worrying the nonsmoothness of the loss function. Theoretically, we prove that the proximal algorithms combined with the pathwise optimization scheme enjoy fast convergence guarantees with high probability. Numerical results are provided to support our theory.
References in corpus (6)
- Simultaneous analysis of Lasso and Dantzig selector
- Pathwise coordinate optimization
- Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming
- Efficient Smoothed Concomitant Lasso Estimation for High Dimensional Regression
- Pathwise Coordinate Optimization for Sparse Learning: Algorithm and Theory
- A Likelihood Ratio Framework for High Dimensional Semiparametric Regression