Variance-Reduced and Projection-Free Stochastic Optimization
arXiv:1602.02101
Abstract
The Frank-Wolfe optimization algorithm has recently regained popularity for machine learning applications due to its projection-free property and its ability to handle structured constraints. However, in the stochastic learning setting, it is still relatively understudied compared to the gradient descent counterpart. In this work, leveraging a recent variance reduction technique, we propose two stochastic Frank-Wolfe variants which substantially improve previous results in terms of the number of stochastic gradient evaluations needed to achieve accuracy. For example, we improve from to if the objective function is smooth and strongly convex, and from to if the objective function is smooth and Lipschitz. The theoretical improvement is also observed in experiments on real-world datasets for a multiclass classification application.
References in corpus (3)
Cited by in corpus (39)
- A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
- HardCoRe-NAS: Hard Constrained diffeRentiable Neural Architecture Search
- Conservative Stochastic Optimization with Expectation Constraints
- VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
- Stochastic Conditional Gradient++
- One Sample Stochastic Frank-Wolfe
- Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
- Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
- Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
- Revisiting Projection-free Online Learning: the Strongly Convex Case
- Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
- Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization
- Boosting Frank-Wolfe by Chasing Gradients
- A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition
- Projection-Free Adaptive Gradients for Large-Scale Optimization
- Black Box Submodular Maximization: Discrete and Continuous Settings
- Deep Neural Network Training with Frank-Wolfe
- Global Convergence of Frank Wolfe on One Hidden Layer Networks
- Faster Projection-free Online Learning
- Safe Learning under Uncertain Objectives and Constraints
- Zeroth-Order Stochastic Block Coordinate Type Methods for Nonconvex Optimization
- Efficient Projection-Free Online Convex Optimization with Membership Oracle
- Convex optimization based on global lower second-order models
- Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization
- Efficient Projection-Free Online Methods with Stochastic Recursive Gradient
- Parameter-free Locally Accelerated Conditional Gradients
- Efficient Projection-Free Algorithms for Saddle Point Problems
- An -Cost Algorithm for Semidefinite Programs with Diagonal Constraints
- Experimental Design for Regret Minimization in Linear Bandits
- Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step
- Communication-Efficient Asynchronous Stochastic Frank-Wolfe over Nuclear-norm Balls
- Approximate and Stochastic Greedy Optimization
- Primal-Dual Block Frank-Wolfe
- Robust Structured Statistical Estimation via Conditional Gradient Type Methods
- An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization
- Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets
- Scalable Projection-Free Optimization
- Safe Convex Learning under Uncertain Constraints
- MEMOIR: Multi-class Extreme Classification with Inexact Margin