Successive Ray Refinement and Its Application to Coordinate Descent for
  LASSO
  Coordinate descent is one of the most popular approaches for solving Lasso
and its extensions due to its simplicity and efficiency. When applying
coordinate descent to solving Lasso, we update one coordinate at a time while
fixing the remaining coordinates. Such an update, which is usually easy to
compute, greedily decreases the objective function value. In this paper, we aim
to improve its computational efficiency by reducing the number of coordinate
descent iterations. To this end, we propose a novel technique called Successive
Ray Refinement (SRR). SRR makes use of the following ray continuation property
on the successive iterations: for a particular coordinate, the value obtained
in the next iteration almost always lies on a ray that starts at its previous
iteration and passes through the current iteration. Motivated by this
ray-continuation property, we propose that coordinate descent be performed not
directly on the previous iteration but on a refined search point that has the
following properties: on one hand, it lies on a ray that starts at a history
solution and passes through the previous iteration, and on the other hand, it
achieves the minimum objective function value among all the points on the ray.
We propose two schemes for defining the search point and show that the refined
search point can be efficiently obtained. Empirical results for real and
synthetic data sets show that the proposed SRR can significantly reduce the
number of coordinate descent iterations, especially for small Lasso
regularization parameters.
