Projection-free Online Learning

Abstract

The computational bottleneck in applying online learning to massive data sets is usually the projection step. We present efficient online learning algorithms that eschew projections in favor of much more efficient linear optimization steps using the Frank-Wolfe technique. We obtain a range of regret bounds for online convex optimization, with better bounds for specific cases such as stochastic online smooth convex optimization. Besides the computational advantage, other desirable features of our algorithms are that they are parameter-free in the stochastic case and produce sparse decisions. We apply our algorithms to computationally intensive applications of collaborative filtering, and show the theoretical improvements to be clearly visible on standard datasets.

ICML2012

References in corpus (1)

• Convex Optimization without Projection Steps

Cited by in corpus (32)

• Optimization with First-Order Surrogate Functions
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• Variance-Reduced and Projection-Free Stochastic Optimization
• Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
• A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints
• Conservative Stochastic Optimization with Expectation Constraints
• Stochastic Conditional Gradient++
• One Sample Stochastic Frank-Wolfe
• A Conditional Gradient-Based Augmented Lagrangian Framework
• O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
• Revisiting Projection-free Online Learning: the Strongly Convex Case
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Improved Regret Bounds for Projection-free Bandit Convex Optimization
• Boosting Frank-Wolfe by Chasing Gradients
• Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Efficient Projection-Free Online Convex Optimization with Membership Oracle
• Faster Projection-free Online Learning
• Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization
• Safe Learning under Uncertain Objectives and Constraints
• Efficient Projection-Free Algorithms for Saddle Point Problems
• Efficient Projection-Free Online Methods with Stochastic Recursive Gradient
• From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds
• Projection Algorithms for Non-Convex Minimization with Application to Sparse Principal Component Analysis
• Online Boosting with Bandit Feedback
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step
• Improved Regret Bounds for Online Submodular Maximization
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Scalable Projection-Free Optimization
• Probable convexity and its application to Correlated Topic Models