Fast and Scalable Lasso via Stochastic Frank-Wolfe Methods with a
  Convergence Guarantee
  Frank-Wolfe (FW) algorithms have been often proposed over the last few years
as efficient solvers for a variety of optimization problems arising in the
field of Machine Learning. The ability to work with cheap projection-free
iterations and the incremental nature of the method make FW a very effective
choice for many large-scale problems where computing a sparse model is
desirable.
  In this paper, we present a high-performance implementation of the FW method
tailored to solve large-scale Lasso regression problems, based on a randomized
iteration, and prove that the convergence guarantees of the standard FW method
are preserved in the stochastic setting. We show experimentally that our
algorithm outperforms several existing state of the art methods, including the
Coordinate Descent algorithm by Friedman et al. (one of the fastest known Lasso
solvers), on several benchmark datasets with a very large number of features,
without sacrificing the accuracy of the model. Our results illustrate that the
algorithm is able to generate the complete regularization path on problems of
size up to four million variables in less than one minute.
