Source-linked AI summary
Optimization, Learning, and Games with Predictable Sequences
Alexander Rakhlin, Karthik Sridharan
TL;DR
The paper asks how predictable structure in sequences can improve online-learning guarantees across optimization, games, and convex programming. It develops Optimistic Mirror Descent and applies it to Mirror Prox, strongly uncoupled zero-sum games, partial information, and approximate Max Flow. The applications recover accelerated or simplified guarantees, including O((log T)/T) game convergence and ˜O(d3/2/ϵ) Max Flow time.
Problem
Worst-case no-regret guarantees can be loose for structured sequences, motivating methods that exploit predictable gradients; the paper also addresses simple strongly uncoupled game algorithms and partial-information convergence.
Method
The paper develops applications of Optimistic Mirror Descent, using predictable sequences computed from past observations, side information, or problem structure.
Results
The applications recover Mirror Prox, extend rates to Hölder-smooth functions, obtain O((log T)/T) minimax convergence for strongly uncoupled players, and give a simple ˜O(d3/2/ϵ) approximate Max Flow algorithm.
Takeaways & Limitations
Predictable-sequence information provides a common route to improved optimization and game-learning rates and to simpler convex-programming algorithms.
Takeaways & Limitations
The applications rely on smoothness to construct predictable processes; in partial information, the fast rate requires knowing the opposing player’s number of actions, and one-play-per-round attainment remains open.
Abstract
from arXiv · showhide
We provide several applications of Optimistic Mirror Descent, an online learning algorithm based on the idea of predictable sequences. First, we recover the Mirror Prox algorithm for offline optimization, prove an extension to Holder-smooth functions, and apply the results to saddle-point type problems. Next, we prove that a version of Optimistic Mirror Descent (which has a close relation to the Exponential Weights algorithm) can be used by two strongly-uncoupled players in a finite zero-sum matrix game to converge to the minimax equilibrium at the rate of O((log T)/T). This addresses a question of Daskalakis et al 2011. Further, we consider a partial information version of the problem. We then apply the results to convex programming and exhibit a simple algorithm for the approximate Max Flow problem.
1 Introduction
The paper applies predictable-sequence ideas to optimization, games, partial information, and convex programming. It recovers Mirror Prox, obtains faster convergence for structured games, and gives a simple approximate Max Flow algorithm.
- Motivation: Predictable sequences exploit non-worst-case structure in data that makes standard no-regret guarantees loose.The relevant structure can arise from computations performed by the learner.
- Optimization: Mirror Prox is presented as an instance of the predictable-sequence approach, with predictability arising from smoothness and saddle-point structure.The analysis extends to Hölder-smooth functions, interpolating between predictable and unpredictable gradients.
- Games: Optimistic Mirror Descent gives strongly uncoupled players in finite zero-sum matrix games convergence to the minimax equilibrium at O((log T)/T).The algorithm is fully adaptive, retains O(T^-1/2) convergence against arbitrary sequences, and also treats partial information.
- Convex programming: An application to convex programming yields a simple ϵ-approximate Max Flow algorithm with time complexity ˜O(d3/2/ϵ).The result matches a prior performance obtained through a relatively involved procedure.
2 Online Learning with Predictable Gradient Sequences
Optimistic Mirror Descent uses an available prediction of the next gradient to improve regret bounds. In smooth offline optimization, this becomes Mirror Prox, while Hölder smoothness yields an interpolation between standard and accelerated rates.
- Online learning: Online convex optimization asks a learner to choose ft∈F each round, observe a convex function Gt, and control cumulative regret.The learner may use a vector Mt computed from past observations or side information before observing the current gradient.
- Online learning: Optimistic Mirror Descent interleaves primary ft and secondary gt sequences using Bregman divergence and adaptively chosen step sizes.The method is compatible with the online protocol because Mt is available before the round and ∇Gt(ft) afterward.
- Regret analysis: The regret analysis bounds performance through the prediction error between the observed gradient and Mt.A fixed-step bound contains a regularizer term η^-1R2 and a prediction-error term proportional to η.
- Offline optimization: Mirror Prox results when Mt is set to the previous gradient for a smooth offline objective.Lipschitz gradient smoothness controls the difference between the current gradient and this prediction.
- Offline optimization: HR2/T bounds the averaged optimization error for Lipschitz-smooth functions, recovering the known Mirror Prox rate.The paper extends this result to arbitrary α-Hölder smooth functions.
- Offline optimization: The Hölder-smooth result interpolates between T^-1/2 at α=0 and T^-1 when smoothness enables strong gradient predictability.The interpolation quantifies how predictability improves the rate over the unpredictable-gradient case.
3 Structured Optimization
Structured saddle-point optimization can be solved by running two online convex optimization algorithms against each other. Coupled regret bounds exploit smoothness to establish near-optimal averaged strategies.
- Problem structure: The structured problem has G(f)=supx∈X φ(f,x), where φ is convex in f and concave in x over convex sets.Although G itself need not be smooth, the structure of φ can support improved optimization rates.
- Two-player reduction: Players I and II generate primal and dual sequences with regret-minimization algorithms.Standard inequalities combine their regrets to control the averaged strategies.
- Optimistic dynamics: Optimistic Mirror Descent can be applied to both players with predictable sequences, strongly convex regularizers, and fixed learning rates.The construction uses primary sequences ft, xt and secondary sequences gt, yt.
- Coupled analysis: Hölder smoothness of φ is used to define predictable gradients for the two players.The analysis summarizes the relevant smoothness exponents through γ=min{α,α′,β,β′} and constants through H=max{H1,H2,H3,H4}.
- Coupled analysis: Coupling the players’ regret bounds creates cancellations between negative terms from one player and positive terms from the other.These cancellations can produce faster rates under appropriate smoothness assumptions.
4 Zero-sum Game and Uncoupled Dynamics
The paper answers whether simple, strongly uncoupled learning dynamics can achieve fast convergence in finite zero-sum games while retaining robustness against arbitrary play. It develops Optimistic Mirror Descent variants for first-order and partial-information settings, obtaining fast equilibrium rates under cooperation and standard regret guarantees more generally.
- Zero-Sum Games: The game objective is to find mixed strategies whose payoff is close to the minimax value, with neither player knowing the matrix or the opponent’s action count.This strongly uncoupled setting also restricts communication, arithmetic, and memory, motivating simple decentralized dynamics.
- First-Order Information: O((log T)/T) convergence is achieved by strongly uncoupled players using a modified Optimistic Mirror Descent algorithm in finite zero-sum matrix games.The algorithm does not require prior knowledge of whether the opponent is collaborating, and adaptive step sizes preserve robustness against arbitrary sequences.
- First-Order Information: The algorithm is essentially entropy-regularized Optimistic Mirror Descent with uniform-distribution mixing when a coordinate becomes smaller than 1/(nT^2) or its analogue.The mixing step supports adaptive robustness, while the underlying updates remain closely related to Exponential Weights.
- First-Order Information: O(log(nT)/T) worst-case regret is obtained in general online linear optimization, while stable opponent moves yield intermediate rates including O(ηlogT/T).If the opponent uses a method with η ∝ T^-1/2, the first player still obtains O(logT/T) regret.
- Partial Information: Partial-information play can also attain the previous fast rate, but the construction requires four δ-close plays per round and knowledge of the opponent’s action count or an upper bound.The paper leaves achieving a 1/T-type rate with only one play per round as an open problem.
- Partial Information: When both players observe only realized scalar payoffs, the paper leaves attaining a 1/T-type rate open and hypothesizes that better than T^-1/2 may be impossible.The partial-information question is whether enough scalar observations can support an ε-optimal minimax strategy while preserving the usual no-regret rate.
5 Approximate Smooth Convex Programming
The paper reformulates smooth convex programming as a saddle-point problem and applies predictable-sequence methods to obtain approximate solutions. For Max Flow, this yields a simple algorithm with the stated time complexity.
- Convex programming: Smooth convex programming is reformulated as a saddle-point problem between a flow-like player and a constraint-mixture player.The first player minimizes over feasible objective-level points, while the second maximizes over mixtures of constraints.
- Convex programming: The resulting averaged solution satisfies all d constraints and is an ǫ-approximate maximizer.A convex combination with the strictly feasible point produces a feasible solution while preserving the approximation guarantee.
- Max Flow: For Max Flow, the flow projection and Exponential Weights updates each take O(d) time per iteration.The flow projection uses the Euclidean norm squared and conjugate gradients, while the constraint update processes order d constraints.
6 Discussion
The discussion presents predictable sequences as a broadly useful tool across optimization, convex programming, and game theory. It identifies smoothness as the basis of the paper’s applications and proposes broader predictability conditions as future work.
- Discussion: Predictable sequences support applications in optimization, convex programming, and game theory.The paper frames extra information about the encountered sequence as a powerful source of improved bounds.
- Discussion: All applications in the paper use some notion of smoothness to construct the predictable process M_t.The discussion explicitly identifies this shared assumption as a boundary of the presented applications.
- Discussion: Future work could identify predictability conditions for functions that are not smooth and use them to build adaptive optimization procedures.The paper suggests bundle methods as one possible way to restrict possible gradients.
Proofs
The proofs derive regret and suboptimality bounds for optimistic mirror descent and combine the players’ bounds in structured optimization and games. They also extend the analysis to changing step sizes, deviations, partial information, and Max Flow.
- Core bounds: Optimistic mirror descent updates satisfy a comparator-dependent inequality involving the linear loss and Bregman divergence.The analysis repeatedly uses strong convexity to control divergence terms.
- Extensions: The analysis also covers changing step sizes, arbitrary opponent behavior, and unbiased partial-information estimates.The partial-information proof begins by establishing unbiasedness for the estimated payoff vectors.
- Core bounds: Hölder’s inequality, conjugate powers, AM-GM, and norm inequalities convert smoothness assumptions into upper bounds.These inequalities are used throughout the proofs of the optimistic regret lemmas and corollaries.
- Game analysis: The proofs bound simplex regret using entropy regularization, coordinate smoothing, strong convexity, and KL-divergence control.The smoothing step handles coordinates below 1/(nT^2), while the comparator is a simplex vertex.
- Game analysis: The game analysis combines both players’ regret bounds to obtain an overall suboptimality bound.Negative terms from one player’s regret can cancel positive terms from the other player’s regret under the appropriate assumptions.
- Convex programming and Max Flow: For convex programming and Max Flow, the proofs use smooth constraints, a strictly feasible point, and linear-constraint structure to derive iteration and runtime bounds.For Max Flow, linear constraints give H = 0 and each iteration has O(d) time complexity.