Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee

DOI10.1007/S10994-016-5578-4zbMATH Open1386.68130arXiv1510.07169OpenAlexW2108943779WikidataQ62047569 ScholiaQ62047569MaRDI QIDQ331671FDOQ331671

Emanuele Frandi, Ricardo Ñanculef, Johan A. K. Suykens, Stefano Lodi, Claudio Sartori

Publication date: 27 October 2016

Published in: Machine Learning (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1510.07169

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

zbMATH Keywords

LassoFrank-Wolfe algorithmlarge-scale regression

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Quadratic programming (90C20) Ridge regression; shrinkage estimators (Lasso) (62J07)

Cites Work

• Title not available (Why is that?)
• The Adaptive Lasso and Its Oracle Properties
• Least angle regression. (With discussion)
• Pathwise coordinate optimization
• Title not available (Why is that?)
• Regression Shrinkage and Selection via The Lasso: A Retrospective
• Sparsity and Smoothness Via the Fused Lasso
• Regularization and Variable Selection Via the Elastic Net
• Ridge Regression: Biased Estimation for Nonorthogonal Problems
• Gradient methods for minimizing composite functions
• On the adaptive elastic net with a diverging number of parameters
• Greed is Good: Algorithmic Results for Sparse Approximation
• Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Title not available (Why is that?)
• Sparse online learning via truncated gradient
• Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints
• 10.1162/153244303322753751
• Biclustering via sparse singular value decomposition
• A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
• The Elements of Statistical Learning

Cited In (5)

• 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
• FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank–Wolfe Algorithms and Conditional Gradients
• Accelerate the warm-up stage in the Lasso computation via a homotopic approach

Uses Software

• UCI-ml
• LIBSVM
• glmnet
• Scikit
• SLEP

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)