Title: 

Projection-free Optimization and Online Learning

Abstract:

Modern large data sets prohibit any super-linear time operations. This motivates the study of iterative optimization algorithms with low complexity per iteration. The computational bottleneck in applying state-of-the-art iterative methods is many times the so-called "projection step".
We consider projection-free optimization/learning that replaces projections by more efficient linear optimization steps. We describe the first linearly-converging algorithm of this type for polyhedral sets and how it gives rise to optimal-rate stochastic optimization and online learning algorithms.