Square-Root Clustered Lasso for High-Dimensional Linear Regression with Finite-Sample Theory and Efficient Algorithm Implementation

This paper proposes a square-root clustered Lasso penalized method for high-dimensional linear regression. By integrating square-root loss with the clustered Lasso penalty, the resulting method enables flexible regression modeling and allows tuning parameter selection independent of the unknown noise level. We establish weak decomposability of the clustered Lasso penalty and a noise-level-free tuning strategy under Gaussian noise. Furthermore, we establish the finite-sample prediction accuracy guarantees for the proposed method. The inherent nonsmoothness of the square-root loss and clustered Lasso penalty poses considerable computational difficulties. To resolve this issue, we develop an efficient semismooth Newton-based proximal augmented Lagrangian algorithm (N-ALM) to solve the corresponding dual optimization problem. The subproblems arising in the iteration are efficiently tackled by the semismooth Newton method, which fully utilizes the sparsity structure of the generalized Jacobian. We further establish global convergence and a local linear rate for the distance to the KKT solution set under suitable conditions; the local rate becomes superlinear when the penalty parameter tends to infinity. We conduct numerical experiments on real-world datasets to evaluate the computational performance of N-ALM. The results demonstrate that N-ALM solves the tested high-dimensional SRCL problems accurately and substantially reduces running times compared with d-ADMM.