Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee
From MaRDI portal
(Redirected from Publication:331671)
Abstract: 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.
Recommendations
- Frank-Wolfe style algorithms for large scale optimization
- scientific article; zbMATH DE number 6253925
- A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
- An iterative reduction FISTA algorithm for large-scale LASSO
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
Cites work
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 6253925 (Why is no real title available?)
- 10.1162/153244303322753751
- A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
- Biclustering via sparse singular value decomposition
- Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
- Gradient methods for minimizing composite functions
- Greed is Good: Algorithmic Results for Sparse Approximation
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Least angle regression. (With discussion)
- On the adaptive elastic net with a diverging number of parameters
- Pathwise coordinate optimization
- Regression Shrinkage and Selection via The Lasso: A Retrospective
- Regularization and Variable Selection Via the Elastic Net
- Ridge Regression: Biased Estimation for Nonorthogonal Problems
- Scikit-learn: machine learning in Python
- Sparse online learning via truncated gradient
- Sparsity and Smoothness Via the Fused Lasso
- The Adaptive Lasso and Its Oracle Properties
- The Elements of Statistical Learning
- Trading accuracy for sparsity in optimization problems with sparsity constraints
Cited in
(9)- Frank-Wolfe style algorithms for large scale optimization
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants
- Spatial Homogeneity Pursuit of Regression Coefficients for Large Datasets
- On the selection of predictors by using greedy algorithms and information theoretic criteria
- A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
- FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank–Wolfe Algorithms and Conditional Gradients
- Runtime guarantees for regression problems
- Accelerate the warm-up stage in the Lasso computation via a homotopic approach
This page was built for publication: Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q331671)
