No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization

Abstract

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.

arXiv commentarXiv admin note: substantial text overlap with arXiv:2106.12923

References in corpus (15)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Online Learning: A Modern Introduction Using Convex Optimization
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• A geometric alternative to Nesterov's accelerated gradient descent
• From Averaging to Acceleration, There is Only a Step-size
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
• Acceleration through Optimistic No-Regret Dynamics
• Online to Offline Conversions, Universality and Adaptive Minibatch Sizes
• Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
• Curvature of Feasible Sets in Offline and Online Optimization
• Linear Bandits on Uniformly Convex Sets