Title: Approximate and Stochastic Greedy Optimization,
Abstract: 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.