A communication-efficient method for ℓ0 regularization linear regression models. Issue 4 (4th March 2023)

• Record Type: Journal Article
• Authors: Kang, Lican; Li, Xuerui; Liu, Yanyan; Luo, Yuan; Zou, Zhikang
• Is Part Of: Journal of statistical computation and simulation. Volume 93:Issue 4(2023)
• Page Start: 533
• Page End: 555
• Publication Date: 2023-03-04
• Subjects: ℓ0 regularization -- distributed sparse learning -- KKT system -- steepest gradient descent; Mathematical statistics -- Data processing -- Periodicals; Digital computer simulation -- Periodicals; 519.5028505
• DOI: 10.1080/00949655.2022.2111567
• Languages: English
• ISSNs: 0094-9655

Abstract

Abstract : We propose a communication-efficient distributed learning algorithm for high-dimensional sparse linear regression models in the scenario that the data are stored across multiple machines. Our approach is a distributed version of the SDAR [Huang J, Jiao Y, Liu Y, et al. A constructive approach to l0 penalized regression. J Mach Learn Res. 2018;19(1):403–439] method for solving the KKT system of the ℓ 0 regularized least squares. At each step of the proposed method, the reduced least squares are solved by the steepest descent method, which only needs to calculate the gradient vectors on each node machine and communicate them instead of the data. We refer to this as SD-SDAR for brevity. Under some regular conditions, we obtain the sharp ℓ 2 and ℓ ∞ error bounds for the solution sequences generated by SD-SDAR algorithm. We investigate the computational complexity and show that the number of rounds of communications are bounded by O ( log ⁡ ( N / log ⁡ p ) log ⁡ ( R J ) ) and O ( log ⁡ ( N / log ⁡ p ) log ⁡ ( R ) ), respectively, where J is the number of important predictors, R is the relative magnitude of the non-zero target coefficients, N is the total sample size and p is the dimension of covariates. Simulation studies illustrate that SD-SDAR outperforms some existing distributed methods in accuracy, efficiency and support recovery.