A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
From MaRDI portal
Publication:508681
DOI10.1016/J.INS.2014.03.059zbMATH Open1355.68234arXiv1304.1014OpenAlexW2964052549WikidataQ62047577 ScholiaQ62047577MaRDI QIDQ508681FDOQ508681
Authors: Ricardo Ñanculef, Emanuele Frandi, Claudio Sartori, Héctor Allende 
Publication date: 7 February 2017
Published in: Information Sciences (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1304.1014
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
quadratic programmingconcave optimizationFrank-Wolfe methodslarge-scale support vector machineslearning from massive datasets
Cites Work
- Pegasos: primal estimated sub-gradient solver for SVM
- Statistical comparisons of classifiers over multiple data sets
- 10.1162/15324430260185619
- Title not available (Why is that?)
- Kernel methods in machine learning
- Convergence of a generalized SMO algorithm for SVM classifier design
- Working set selection using second order information for training support vector machines
- Title not available (Why is that?)
- Exploiting separability in large-scale linear support vector machine training
- Online learning and online convex optimization
- Core vector machines: fast SVM training on very large data sets
- Two Algorithms for the Minimum Enclosing Ball Problem
- Generalized equations and their solutions, part II: Applications to nonlinear programming
- Finding the Point of a Polyhedron Closest to the Origin
- Sequential greedy approximation for certain convex optimization problems
- Stochastic dual coordinate ascent methods for regularized loss minimization
- An Iterative Procedure for Computing the Minimum of a Quadratic Form on a Convex Set
- Large margin methods for structured and interdependent output variables
- Sublinear optimization for machine learning
- An efficient implementation of an active set method for SVMs
- 10.1162/1532443041827925
- A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training
- Title not available (Why is that?)
- Optimal core-sets for balls
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
- Title not available (Why is that?)
- Advanced Lectures on Machine Learning
- Online submodular minimization
- 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
- Some comments on Wolfe's ‘away step’
- Title not available (Why is that?)
- A Parametric Optimization Method for Machine Learning
- Coresets for polytope distance
- A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
- An online core vector machine with adaptive MEB adjustment
Cited In (16)
- Implementation of reduced gradient with bisection algorithms for non-convex optimization problem via stochastic perturbation
- Title not available (Why is that?)
- Avoiding bad steps in Frank-Wolfe variants
- 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
- Frank-Wolfe-type methods for a class of nonconvex inequality-constrained problems
- Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee
- 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
- Insensitive stochastic gradient twin support vector machines for large scale problems
Uses Software
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)
