Second Order Methods for Solving Lasso Problems and Their Extensions

In statistics and machine learning, lasso (least absolute shrinkage and selection operator; also Lasso, LASSO or L1 regularization), a term coined by Professor Robert Tibshirani in 1996, is a regression analysis method that performs both variable selection and regularization in order to enhance the prediction accuracy and interpretability of the resulting statistical model. Most of the popular existing packages for solving lasso problems are based on first-order methods such as the block coordinate descent methods and proximal gradient methods. In order to get fast convergent algorithms with accurate solutions, from 2018 we started to develop second-order based semismooth Newton methods for solving lasso problems and their extensions. See Xudong Li, Defeng Sun, and Kim Chuan Toh, “A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems’’, SIAM Journal on Optimization 28 (2018) 433–458. [This paper brought Xudong Li the Best Paper Prize for Young Researchers in Continuous Optimization announced in the ICCOPT 2019 held in Berlin, August 3-8, 2019. This is the only prize given in the flagship international conference on continuous optimization held every three years]; Xudong Li, Defeng Sun, and Kim Chuan Toh, “On efficiently solving the subproblems of a level-set method for fused lasso problems”, SIAM Journal on Optimization 28 (2018) 1842–1862; Yancheng Yuan, Defeng Sun, and Kim Chuan Toh, “An efficient semismooth Newton based algorithm for convex clustering”, Proceedings of the 35-th International Conference on Machine Learning (ICML), Stockholm, Sweden, PMLR 80, 2018; Meixia Lin, Yong-Jin Liu, Defeng Sun, and Kim Chuan Toh, “Efficient sparse semismooth Newton methods for the clustered lasso problem”, SIAM Journal on Optimization 29 (2019) 2026–2052; Ziyan Luo, Defeng Sun, Kim Chuan Toh, and Naihua Xiu, “Solving the OSCAR and SLOPE models using a semismooth Newton-based augmented Lagrangian method”, Journal of Machine Learning Research 20(106):1–25, 2019; Yangjing Zhang, Ning Zhang, Defeng Sun, and Kim Chuan Toh, “An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems”, Mathematical Programming 179 (2020) 223–263; Yangjing Zhang, Ning Zhang, Defeng Sun, and Kim Chuan Toh, “A proximal point dual Newton algorithm for solving group graphical Lasso problems”, SIAM Journal on Optimization 30 (2020) 2197–2220; Peipei Tang, Chengjing Wang, Defeng Sun, and Kim Chuan Toh, “A sparse semismooth Newton based proximal majorization-minimization algorithm for nonconvex square-root-loss regression problems”, Journal of Machine Learning Research 21(226):1–38, 2020; Ning Zhang, Yangjing Zhang, Defeng Sun, and Kim Chuan Toh, “An efficient linearly convergent regularized proximal point algorithm for fused multiple graphical Lasso problems”, SIAM Journal on Mathematics of Data Science 3:2 (2021) 524–543; Defeng Sun, Kim Chuan Toh, and Yancheng Yuan, “Convex clustering: Model, theoretical guarantee and efficient algorithm”, Journal of Machine Learning Research 22(9):1−32, 2021; Yancheng Yuan, T.-H. Chang, Defeng Sun, and Kim-Chuan Toh, “A dimension reduction technique for structured sparse optimization problems with application to convex clustering”, SIAM Journal on Optimization 32 (2022) 2294–2318; Qian Li, Binyan Jiang, and Defeng Sun, “MARS: a second-order reduction algorithm for high-dimensional sparse precision matrices estimation”, Journal of Machine Learning Research 24 (134):1−44, 2023; Meixia Lin, Yancheng Yuan, Defeng Sun, and Kim-Chuan Toh, “A highly efficient algorithm for solving exclusive Lasso problems”, Optimization Methods and Software 39: 3 (2024) 489–518; Qian Li, Defeng Sun, and Yancheng Yuan, “An efficient sieving based secant method for sparse optimization problems with least-squares constraints”, SIAM Journal on Optimization 34:2 (2024) 2038–-2066; and Yancheng Yuan, Meixia Lin, Defeng Sun, and Kim-Chuan Toh, “Adaptive sieving: A dimension reduction technique for sparse optimization problems”, Mathematical Programming Computation (2025), in print. arXiv:2306.17369 (2023; Revised September 2024).