Approximate and Stochastic Greedy Optimization
This work provides theoretical insights into optimization algorithms, but it is incremental as it builds on existing methods like Frank-Wolfe and Jones algorithms.
The paper analyzes approximate and stochastic variants of greedy optimization algorithms for convex minimization, establishing convergence conditions and rates, and showing that using a single stochastic gradient can fail on smooth convex functions.
We consider two greedy algorithms for minimizing a convex function in a bounded convex set: an algorithm by Jones [1992] and the Frank-Wolfe (FW) algorithm. We first consider approximate versions of these algorithms. For smooth convex functions, we give sufficient conditions for convergence, a unified analysis for the well-known convergence rate of O(1/k) together with a result showing that this rate is the best obtainable from the proof technique, and an equivalence result for the two algorithms. We also consider approximate stochastic greedy algorithms for minimizing expectations. We show that replacing the full gradient by a single stochastic gradient can fail even on smooth convex functions. We give a convergent approximate stochastic Jones algorithm and a convergent approximate stochastic FW algorithm for smooth convex functions. In addition, we give a convergent approximate stochastic FW algorithm for nonsmooth convex functions. Convergence rates for these algorithms are given and proved.