On fast convergence of proximal algorithms for SQRT-lasso optimization: Don’t worry about its nonsmooth loss function

Xinguo Li, Haoming Jiang, Jarvis Haupt, Raman Arora, Han Liu, Mingyi Hong, Tuo Zhao

Research output: Contribution to conferencePaper

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 about the nonsmoothness of the loss function. Theoretically, we prove that the proximal algorithms enjoy fast local convergence with high probability. Our numerical experiments also show that when further combined with the pathwise optimization scheme, the proximal algorithms significantly outperform other competing algorithms.

Original languageEnglish (US)
StatePublished - 2019
Event35th Conference on Uncertainty in Artificial Intelligence, UAI 2019 - Tel Aviv, Israel
Duration: Jul 22 2019Jul 25 2019

Conference

Conference35th Conference on Uncertainty in Artificial Intelligence, UAI 2019
CountryIsrael
CityTel Aviv
Period7/22/197/25/19

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'On fast convergence of proximal algorithms for SQRT-lasso optimization: Don’t worry about its nonsmooth loss function'. Together they form a unique fingerprint.

  • Cite this

    Li, X., Jiang, H., Haupt, J., Arora, R., Liu, H., Hong, M., & Zhao, T. (2019). On fast convergence of proximal algorithms for SQRT-lasso optimization: Don’t worry about its nonsmooth loss function. Paper presented at 35th Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel.