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.

研究了凸优化问题，提出了基于无遗憾游戏动力学的算法框架，并讨论了多种无遗憾学习算法的选择策略及其拥有的收敛性质，证明了很多经典的凸一阶方法都可以被理解为该框架的特殊情况，并且提出了一些之前未被发现的用于特殊凸优化问题的一阶方法。