  We develop an algorithmic framework for solving convex optimization problems
using no-regret game dynamics. By converting the problem of minimizing a convex
function into an auxiliary problem of solving a min-max game in a sequential
fashion, we can consider a range of strategies for each of the two-players who
must select their actions one after the other. A common choice for these
strategies are so-called no-regret learning algorithms, and we describe a
number of such and prove bounds on their regret. We then show that many
classical first-order methods for convex optimization -- including
average-iterate gradient descent, the Frank-Wolfe algorithm, Nesterov's
acceleration methods, and the accelerated proximal method -- can be interpreted
as special cases of our framework as long as each player makes the correct
choice of no-regret strategy. Proving convergence rates in this framework
becomes very straightforward, as they follow from plugging in the appropriate
known regret bounds. Our framework also gives rise to a number of new
first-order methods for special cases of convex optimization that were not
previously known.
