A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
From MaRDI portal
(Redirected from Publication:508681)
Abstract: Recently, there has been a renewed interest in the machine learning community for variants of a sparse greedy approximation procedure for concave optimization known as {the Frank-Wolfe (FW) method}. In particular, this procedure has been successfully applied to train large-scale instances of non-linear Support Vector Machines (SVMs). Specializing FW to SVM training has allowed to obtain efficient algorithms but also important theoretical results, including convergence analysis of training algorithms and new characterizations of model sparsity. In this paper, we present and analyze a novel variant of the FW method based on a new way to perform away steps, a classic strategy used to accelerate the convergence of the basic FW procedure. Our formulation and analysis is focused on a general concave maximization problem on the simplex. However, the specialization of our algorithm to quadratic forms is strongly related to some classic methods in computational geometry, namely the Gilbert and MDM algorithms. On the theoretical side, we demonstrate that the method matches the guarantees in terms of convergence rate and number of iterations obtained by using classic away steps. In particular, the method enjoys a linear rate of convergence, a result that has been recently proved for MDM on quadratic forms. On the practical side, we provide experiments on several classification datasets, and evaluate the results using statistical tests. Experiments show that our method is faster than the FW method with classic away steps, and works well even in the cases in which classic away steps slow down the algorithm. Furthermore, these improvements are obtained without sacrificing the predictive accuracy of the obtained SVM model.
Recommendations
- Frank-Wolfe style algorithms for large scale optimization
- New analysis and results for the Frank-Wolfe method
- Generalized self-concordant analysis of Frank-Wolfe algorithms
- Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
Cites work
- scientific article; zbMATH DE number 5764862 (Why is no real title available?)
- scientific article; zbMATH DE number 3526459 (Why is no real title available?)
- scientific article; zbMATH DE number 1314294 (Why is no real title available?)
- scientific article; zbMATH DE number 2079414 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- 10.1162/15324430260185619
- 10.1162/1532443041827925
- A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
- A Parametric Optimization Method for Machine Learning
- A conditional gradient method with linear rate of convergence for solving convex linear systems
- A linearly convergent linear-time first-order algorithm for support vector classification with a core set result
- A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
- Advanced Lectures on Machine Learning
- An Iterative Procedure for Computing the Minimum of a Quadratic Form on a Convex Set
- An efficient implementation of an active set method for SVMs
- An online core vector machine with adaptive MEB adjustment
- Convergence of a generalized SMO algorithm for SVM classifier design
- Core vector machines: fast SVM training on very large data sets
- Coresets for polytope distance
- Exploiting separability in large-scale linear support vector machine training
- Finding the Point of a Polyhedron Closest to the Origin
- Generalized equations and their solutions, part II: Applications to nonlinear programming
- Kernel methods in machine learning
- Large margin methods for structured and interdependent output variables
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
- Online learning and online convex optimization
- Online submodular minimization
- Optimal core-sets for balls
- Pegasos: primal estimated sub-gradient solver for SVM
- Sequential greedy approximation for certain convex optimization problems
- Some comments on Wolfe's ‘away step’
- Statistical comparisons of classifiers over multiple data sets
- Stochastic dual coordinate ascent methods for regularized loss minimization
- Sublinear optimization for machine learning
- Two Algorithms for the Minimum Enclosing Ball Problem
- Working set selection using second order information for training support vector machines
Cited in
(16)- Insensitive stochastic gradient twin support vector machines for large scale problems
- Implementation of reduced gradient with bisection algorithms for non-convex optimization problem via stochastic perturbation
- Avoiding bad steps in Frank-Wolfe variants
- scientific article; zbMATH DE number 7705675 (Why is no real title available?)
- Using Taylor-approximated gradients to improve the Frank-Wolfe method for empirical risk minimization
- Polytope conditioning and linear convergence of the Frank-Wolfe algorithm
- Frank-Wolfe style algorithms for large scale optimization
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee
- Frank-Wolfe-type methods for a class of nonconvex inequality-constrained problems
- A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
- Scalable Gaussian kernel support vector machines with sublinear training time complexity
- Support vector machine classification applied to the parametric design of centrifugal pumps
- Rank-two update algorithm versus Frank-Wolfe algorithm with away steps for the weighted Euclidean one-center problem
- Selective bi-coordinate method for limit non-smooth resource allocation type problems
- On the von Neumann and Frank-Wolfe algorithms with away steps
This page was built for publication: A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q508681)
