A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
arXiv:1301.4666
Abstract
Linear optimization is many times algorithmically simpler than non-linear convex optimization. Linear optimization over matroid polytopes, matching polytopes and path polytopes are example of problems for which we have simple and efficient combinatorial algorithms, but whose non-linear convex counterpart is harder and admits significantly less efficient algorithms. This motivates the computational model of convex optimization, including the offline, online and stochastic settings, using a linear optimization oracle. In this computational model we give several new results that improve over the previous state-of-the-art. Our main result is a novel conditional gradient algorithm for smooth and strongly convex optimization over polyhedral sets that performs only a single linear optimization step over the domain on each iteration and enjoys a linear convergence rate. This gives an exponential improvement in convergence rate over previous results. Based on this new conditional gradient algorithm we give the first algorithms for online convex optimization over polyhedral sets that perform only a single linear optimization step over the domain while having optimal regret guarantees, answering an open question of Kalai and Vempala, and Hazan and Kale. Our online algorithms also imply conditional gradient algorithms for non-smooth and stochastic convex optimization with the same convergence rates as projected (sub)gradient methods.
References in corpus (4)
Cited by in corpus (32)
- On the Global Linear Convergence of Frank-Wolfe Optimization Variants
- Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
- The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
- Variance-Reduced and Projection-Free Stochastic Optimization
- Efficient Second Order Online Learning by Sketching
- Online Continuous Submodular Maximization
- An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms
- Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
- Blended Conditional Gradients: the unconditioning of conditional gradients
- Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
- Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls
- Projection-Free Optimization on Uniformly Convex Sets
- Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions
- Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
- Linearly Convergent Frank-Wolfe with Backtracking Line-Search
- Lazifying Conditional Gradient Algorithms
- A Newton Frank-Wolfe Method for Constrained Self-Concordant Minimization
- On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization
- No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
- Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
- An algorithm to compute the Hoffman constant of a system of linear constraints
- Faster Projection-free Online Learning
- Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization
- On the von Neumann and Frank-Wolfe Algorithms with Away Steps
- Non-convex Conditional Gradient Sliding
- A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming
- Discovering a set of policies for the worst case reward
- A Policy Efficient Reduction Approach to Convex Constrained Deep Reinforcement Learning
- Semi-Stochastic Frank-Wolfe Algorithms with Away-Steps for Block-Coordinate Structure Problems
- Trace-Norm Adversarial Examples
- Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
- Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum