Stephen Wright, University of Wisconsin, Madison

Abstract

Interest in the conditional gradient algorithm, proposed by Frank and Wolfe in 1956, has revived in recent years because of its relevance to many data science paradigms. The basic algorithm for optimizing a smooth convex function over a closed convex compact set is appealing for its simplicity and its elementary convergence theory. However, the convergence is too slow for many applications. This talk describes enhancements of conditional gradient that improve its performance in several ways. A common feature of these enhancements is the maintenance of a "basis" of extreme points of the feasible set, being the solutions of the linear oracle from a subset of previous calls. We describe a "lazy" variant in which the linearized objective is minimized only over the convex hull of this basis on most iterations, a variant in which the objective is periodically reoptimized over the convex hull of this basis, and a sparsified variant in which this basis is sometimes reduced in size. (These techniques can be applied in tandem.) We show how convergence rates are affected by these techniques, and present computational results on a variety of applications.

This talk describes joint work with Sebastian Pokutta, Gábor Braun, Dan Tu, Nikhil Rao, and Parikshit Shah.