Accelerate the warm-up stage in the Lasso computation via a homotopic approach

Yujie Zhao and Xiaoming Huo

Computational Statistics & Data Analysis, 2023, vol. 184, issue C

Abstract: In optimization of the least absolute shrinkage and selection operator (Lasso) problem, the fastest algorithm has a convergence rate of O(1/ϵ). This polynomial order of 1/ϵ is caused by the undesirable behavior of the absolute function at the origin. To expedite the convergence, an algorithm called homotopy shrinkage yielding (HOSKY) is proposed. It helps expedite the warm-up stage of the existing algorithms. With the acceleration by HOSKY in the warm-up stage, one can get a provable convergence rate lower than O(1/ϵ). The main idea of the proposed HOSKY algorithm is to use a sequence of surrogate functions to approximate the ℓ1 penalty that is used in Lasso. This sequence of surrogate functions, on the one hand, gets closer and closer to the ℓ1 penalty; on the other hand, they are strictly convex and well-conditioned, which enables a provable exponential rate of convergence by gradient-based approaches. As the proof shows, the convergence rate of the HOSKY algorithm is O([log⁡(1/ϵw)]2), where ϵw is the precision used in the warm-up stage (ϵw↛0). Additionally, the numerical simulations also show that HOSKY empirically performs better in the warm-up stage and accelerates the overall convergence rate.

Keywords: Lasso; Homotopic method; Convergence rate; ℓ1 regularization (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167947323000580
Full text for ScienceDirect subscribers only.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:csdana:v:184:y:2023:i:c:s0167947323000580

DOI: 10.1016/j.csda.2023.107747

Access Statistics for this article

Computational Statistics & Data Analysis is currently edited by S.P. Azen

More articles in Computational Statistics & Data Analysis from Elsevier
Bibliographic data for series maintained by Catherine Liu ().