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

Yujie Zhao, Xiaoming Huo

TL;DR

This paper introduces HOSKY, a novel algorithm that accelerates the "warm-up" phase of Lasso optimization. By using a sequence of smooth, strictly convex surrogate functions to approximate the non-smooth L1 penalty, HOSKY achieves a provably faster convergence rate, leading to improved overall performance in Lasso computations.

What Problem Does This Paper Address?

The Lasso (Least Absolute Shrinkage and Selection Operator) is a powerful technique for variable selection and model estimation in linear regression. However, a key challenge in efficiently solving Lasso problems lies in the non-smooth nature of the L1 penalty term (||β||₁). This non-smoothness at the origin causes many standard optimization algorithms to have a slow convergence rate, particularly in the initial "warm-up" stage where initial parameter estimates are established. Existing methods often struggle to efficiently navigate this region, leading to slower overall computation times. This paper aims to address this bottleneck by developing a method that specifically targets and accelerates this warm-up phase.

Methods

The core innovation of HOSKY is its "homotopic approach." Instead of directly minimizing the non-smooth Lasso objective function, HOSKY iteratively minimizes a sequence of surrogate functions. These surrogate functions are designed to:

  1. Approximate the L1 penalty: As the algorithm progresses, these surrogates become increasingly closer to the true L1 penalty.
  2. Be strictly convex and well-conditioned: This is achieved by replacing the absolute value function with a smooth, quadratic-like function near zero and linear-like elsewhere. This property is crucial for enabling fast convergence using gradient-based methods.

HOSKY employs a two-loop structure:

  • Outer-loops: These loops manage the sequence of surrogate functions, gradually refining the approximation of the L1 penalty. The hyper-parameters controlling the surrogates are updated in a decreasing sequence.
  • Inner-loops: Within each outer-loop, an Accelerated Gradient Descent (AGD) algorithm is used to minimize the current surrogate function. AGD is chosen for its proven efficiency on smooth, strongly convex functions.

The paper also proposes specific designs for the surrogate functions and the hyper-parameter update rules, along with theoretical analysis to establish the convergence rate of HOSKY.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical simulations using synthetic data generated for sparse linear regression and image de-noising tasks.

Key Insights and Ideas

  • Smoothness is key for speed: The non-smoothness of the L1 norm is the primary culprit for slow convergence in Lasso. By replacing it with smooth, well-behaved surrogates, we can leverage faster optimization techniques.
  • Homotopy as a path to efficiency: The idea of gradually deforming the objective function (via surrogate functions) to approach the true problem allows for a more efficient traversal of the optimization landscape, especially in the challenging initial stages.
  • Warm-up matters: Accelerating the warm-up stage doesn't just speed up that phase; it can also lead to better initial points that expedite the subsequent "after-warm-up" stage, improving overall performance.
  • Provable gains: The paper provides theoretical guarantees for HOSKY's convergence rate, showing it can outperform existing methods in terms of computational complexity for the warm-up phase.

Key Results

  • Theoretical Convergence Rate: HOSKY achieves a provable warm-up convergence rate of $O([\log(1/\epsilon_w)]^2)$, which is significantly better than the polynomial $O(1/\epsilon_w)$ rate of standard methods like ISTA, FISTA, and CD.
  • Empirical Performance: Numerical simulations demonstrate that HOSKY performs better in the warm-up stage compared to benchmarks like ridge regression, ISTA, and FISTA.
  • Image De-noising: In an image de-noising example, HOSKY produced a de-noised image of better quality than its benchmarks.
  • Overall Speedup: Simulations also showed that using HOSKY for the warm-up stage can lead to a faster overall computation time for achieving a desired final precision. For instance, in one scenario, HOSKY required fewer numerical operations and less running time for both the warm-up and after-warm-up stages combined.

Limitations and Future Work

  • Hyper-parameter t: The theoretical analysis relies on a condition that the hyper-parameter t (controlling the surrogate function's closeness to the L1 norm) does not converge to zero. The authors suggest it would be interesting to explore ways to relax this condition.
  • Support Recovery: While HOSKY aims to find a good initial point, the paper discusses that its surrogate functions might not guarantee sparse solutions directly, unlike the standard Lasso. Proposition 5.2 shows that under certain conditions, the algorithm can still achieve small prediction and estimation errors, but it requires strong assumptions on the model matrix X for guaranteed support recovery.
  • Practical Implementation of Inner-loop Precision: The theoretical stopping rule for the inner-loops requires knowing the minimum of the surrogate function, which is often unknown in practice. The authors mention using fixed numbers of inner-loops as a practical alternative, though this might slightly increase computational complexity beyond the theoretical bound.
  • Generalization of Path Following: The paper contrasts its approach with "path following" methods that tune the regularization parameter $\lambda$. It highlights that these methods have different problem formulations and may not guarantee optimal solutions or low complexity in all cases. Future work could explore connections or further distinctions.

Summary updated

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.
BibTeX
@article{zhao2023accelerate,
  author = {Yujie Zhao and Xiaoming Huo},
  title = {{Accelerate the warm-up stage in the Lasso computation via a homotopic approach}},
  journal = {Comput. Stat. Data Anal.},
  year = {2023},
  doi = {10.1016/j.csda.2023.107747},
}
Figure