We consider the Frank-Wolfe (FW) method for constrained convex optimization, and we show that this classical technique can be interpreted from a different perspective: FW emerges as the computation of an equilibrium (saddle point) of a special convex-concave zero sum game. This saddle-point trick relies on the existence of no-regret online learning to both generate a sequence of iterates but also to provide a proof of convergence through vanishing regret. We show that our stated equivalence has several nice properties, as it exhibits a modularity that gives rise to various old and new algorithms. We explore a few such resulting methods, and provide experimental results to demonstrate correctness and efficiency.

The paper draws a connection between the classical Frank-Wolfe algorithm for constrained smooth & convex optimization (aka conditional gradient method) and using online learning algorithms to solve zero-sum games. This connection is made by casting the constrained convex optimization problem as a convex-concave saddle point problem between a player that takes actions in the feasible set and another player that takes actions in the gradient space of the objective function. This saddle point problem is derived using the Flenchel conjugate of the objective. Once this is achieved, a known and well explored paradigm of using online learning algorithms can be applied to solving this saddle point problem (where each player applies its own online algorithm to either minimize or maximize), and the average regret bounds obtained by the algorithms translate back to the approximation error with respect to the objective on the original offline convex optimization problem. The authors show that by applying this paradigam with different kinds of online learning algorithms, they can recover the original Frank-Wolfe algorithm (though with a slightly different step size and rate worse by a factor of log(T)) and several other variants, including one that uses the averaged gradient, using stochastic smoothing for non-smooth objectives and even a new variant that converges for non-smooth objectives (without smoothing), when the feasible set is strongly convex.

We consider the Frank-Wolfe (FW) method for constrained convex optimization, and we show that this classical technique can be interpreted from a different perspective: FW emerges as the computation of an equilibrium (saddle point) of a special convex-concave zero sum game. This saddle-point trick relies on the existence of no-regret online learning to both generate a sequence of iterates but also to provide a proof of convergence through vanishing regret. We show that our stated equivalence has several nice properties, as it exhibits a modularity that gives rise to various old and new algorithms. We explore a few such resulting methods, and provide experimental results to demonstrate correctness and efficiency. Papers published at the Neural Information Processing Systems Conference.