Accelerate the Warm-up Stage in the Lasso Computation via a Homotopic Approach
This work addresses computational inefficiency in Lasso-type estimators for optimization practitioners, offering a faster algorithm with theoretical guarantees, though it is incremental as it builds on existing homotopic approaches.
The paper tackles the slow warm-up stage in Lasso computation by proposing a homotopic method using surrogate functions to approximate the L1 penalty, achieving a proven convergence rate of O([log(1/ε)]^2), which is faster than existing methods with O(1/ε) or O(1/√ε) rates.
In optimization, it is known that when the objective functions are strictly convex and well-conditioned, gradient-based approaches can be extremely effective, e.g., achieving the exponential rate of convergence. On the other hand, the existing Lasso-type estimator in general cannot achieve the optimal rate due to the undesirable behavior of the absolute function at the origin. A homotopic method is to use a sequence of surrogate functions to approximate the $\ell_1$ penalty that is used in the Lasso-type of estimators. The surrogate functions will converge to the $\ell_1$ penalty in the Lasso estimator. At the same time, each surrogate function is strictly convex, which enables a provable faster numerical rate of convergence. In this paper, we demonstrate that by meticulously defining the surrogate functions, one can prove a faster numerical convergence rate than any existing methods in computing for the Lasso-type of estimators. Namely, the state-of-the-art algorithms can only guarantee $O(1/ε)$ or $O(1/\sqrtε)$ convergence rates, while we can prove an $O([\log(1/ε)]^2)$ for the newly proposed algorithm. Our numerical simulations show that the new algorithm also performs better empirically.