Source-linked AI summary
Online Optimization : Competing with Dynamic Comparators
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, Karthik Sridharan
TL;DR
The paper addresses online optimization against dynamic benchmarks while exploiting regularity in both cost-function and comparator sequences. It develops Adaptive Optimistic Mirror Descent with no prior environmental knowledge, and shows regret adapts to the smaller relevant complexity. In drifting zero-sum games, the resulting strategies support convergence to average minimax values and no regret against slowly varying action sequences.
Problem
Online learning needs methods that retain adaptive benefits from regular observation sequences while competing with complex, time-varying benchmarks.
Method
Adaptive Optimistic Mirror Descent combines adaptive step sizes with a doubling trick to incorporate DT, CT, and VT without prior knowledge.
Results
The regret bound captures regularity in function and comparator sequences and adapts to the smaller quantity; in drifting zero-sum games, payoffs converge to the average minimax value when games drift slowly.
Takeaways & Limitations
The framework provides a unified adaptive treatment of dynamic regret and extends no-regret guarantees to slowly drifting zero-sum games.
Abstract
from arXiv · showhide
Recent literature on online learning has focused on developing adaptive algorithms that take advantage of a regularity of the sequence of observations, yet retain worst-case performance guarantees. A complementary direction is to develop prediction methods that perform well against complex benchmarks. In this paper, we address these two directions together. We present a fully adaptive method that competes with dynamic benchmarks in which regret guarantee scales with regularity of the sequence of cost functions and comparators. Notably, the regret bound adapts to the smaller complexity measure in the problem environment. Finally, we apply our results to drifting zero-sum, two-player games where both players achieve no regret guarantees against best sequences of actions in hindsight.
I. INTRODUCTION
The paper studies online optimization against time-varying comparators while exploiting regularity in cost-function sequences. It develops an adaptive approach whose dynamic-regret guarantee captures these complexities together and applies the result to drifting zero-sum games.
- Contributions: The regret bound captures the interplay between function-sequence regularity and comparator-sequence regularity, adapting to the smaller quantity when the other is small.This avoids bounds based only on one complexity measure.
- Motivation: Dynamic regret compares performance with a time-varying comparator sequence rather than a single best action in hindsight.This makes the benchmark more stringent than static regret.
- Motivation: Worst-case dynamic-regret guarantees are impossible without assumptions, but comparator regularity can yield bounds interpolating between static and dynamic regret.The relevant comparator complexity is captured by CT.
- Contributions: The paper develops a fully adaptive method requiring no prior knowledge of CT, DT, or VT, with dynamic regret expressed through all three complexity measures.The method is designed for full-information online convex optimization and uses a variant of Optimistic Mirror Descent.
- Contributions: The analysis applies a doubling trick to a non-monotone quantity, producing a non-monotone step-size sequence.The paper identifies this technical treatment as novel to the authors’ knowledge.
- Application: For drifting zero-sum games, uncoupled strategies make payoffs converge to the average minimax value when games drift slowly, while both players obtain no-regret guarantees against slowly varying action sequences.This generalizes results for fixed games played repeatedly.
A. Notation
The notation tracks regularity of comparator sequences and distinguishes general comparator regularity from the loss-function minimizers used in the main bounds.
- The paper assumes a condition holding for every action x ∈ X at every time t.
- CT denotes the regularity of a comparator sequence, and without arguments refers to the minimizer sequence of the loss functions.
- The main results involving √CT require a computable quantity to tune the step size, so they are stated for CT(x*_1, . . . , x*_T).
- DT is defined with respect to an arbitrary predictable sequence {M_t}^T.
B. Comparing with existing regret bounds in the dynamic setting
The dynamic-setting literature includes regret analyses for comparator sequences, while existing bounds focus on only one of CT, DT, or VT.
- The dynamic setting considers an arbitrary comparator sequence {u_t}^T.
A. Optimistic Mirror Descent and Relation to Regularity
Optimistic Mirror Descent uses predictable gradient-side information and adaptive step sizes to obtain dynamic-regret bounds that depend on comparator regularity and deviations.
- Optimistic Mirror Descent receives a predictable process M_t computed from information available at the beginning of round t.
- The algorithm uses ∇_t = ∇f_t(x_t) and an adaptively chosen step size η_t to attain low regret.
- For M_t = 0, Optimistic Mirror Descent becomes Mirror Descent; for M_t = ∇_{t−1}, it recovers the scheme proposed in.
- Lemma 1 extends the regret result to arbitrary comparator sequences and yields tighter bounds when the learner's sequence is well-aligned with gradients.
- The bound combines deviation DT, comparator regularity CT, and the Bregman-divergence diameter R_max.
- The analysis assumes DR(x,z) − DR(y,z) ≤ γ∥x − y∥; for KL divergence, mixing a uniform distribution gives γ = O(log T).
- With prior knowledge of CT or an upper bound on it, the regret bound can be expressed in O-form using that regularity.
B. The Adaptive Optimistic Mirror Descent Algorithm
AOMD combines optimistic mirror descent with a doubling procedure to adapt simultaneously to variation, deviation, and comparator regularity without prior complexity budgets.
- AOMD is designed to adapt automatically to VT, DT, and CT while competing with both abrupt and gradual changes.
- The method builds on OMD with adaptive step sizes and applies a doubling trick to accumulated deviation, variation, and regularity.
- The scheme requires no prior knowledge of DT, CT, or VT, despite not knowing how variation is distributed over time.
- When its doubling condition is met, AOMD doubles L, discards accumulated quantities, and starts a new OMD epoch.
- The doubling condition produces a non-monotone sequence of step sizes during learning.
- Theorem 3 gives AOMD a dynamic-regret bound, with ˜O hiding a log T factor, and Table summaries specialize the bound across regimes.
- If VT = o(T), the regret is sub-linear; with bounded gradients, DT = O(T) holds and guarantees the worst-case bound.
- For B batches of smooth convex losses with VT = O(1), each batch achieves ˜O(1) regret and Theorem 3 gives O(log T).
A. Competing with Strategies
The paper extends regret analysis from fixed actions to structured comparator sequences, while adapting automatically to regularity in both costs and comparators. Its bound interpolates between static and dynamic regret without prior environmental knowledge.
- Comparator classes: The comparator class consists of sequences of mappings from past observations to actions, generalizing fixed and independently chosen comparators.Constant mappings recover static regret, while unrestricted mappings recover dynamic regret.
- Adaptive method: A modified AOMD algorithm replaces known complexity quantities with data-dependent estimates over doubling epochs.The modification uses mappings evaluated on each epoch’s observed function sequence.
- Interpolation: The corollary interpolates between static and dynamic regret: zero comparator complexity recovers the static result, while maximal comparator complexity recovers the dynamic bound.The static recovery holds up to logarithmic factors.
- Interpolation: The additional logarithmic factor is identified as the cost of adaptivity when the environment is unknown in advance.This factor arises because the algorithm does not receive prior knowledge of the relevant complexity measures.
B. Switching Zero-sum Games with Uncoupled Dynamics
The paper applies adaptive dynamic-regret strategies to time-varying zero-sum games, supporting robustness to unilateral deviations and convergence when both players follow the prescribed strategies.
- Game setting: The setting is a sequence of T zero-sum games with payoff matrices A_t ∈ [−1,1]^{m×n}, where each player acts each round.The players’ strategies are designed for changing game matrices.
- Unilateral deviation: The modified AOMD strategy gives Player I regret against any action sequence whose changes are controlled by its comparator complexity, even when Player II deviates.The construction uses KL divergence and mixes in a small uniform component.
- Equilibrium convergence: When both players follow the prescribed strategies, their payoffs converge to the average minimax value of the sequence of games.The convergence bound depends on the regularity of the game sequence and the players’ strategies.
- Switching games: If the game matrix switches at most K times, the strategy yields regret against comparator sequences switching at most K times and convergence at a logarithmic rate under the stated condition on L.The time-invariant case K = 0 recovers the static setting’s rate.
- Switching games: The result simultaneously supports low regret against changing comparator actions and fast convergence to average equilibrium when both players are honest.For a constant number of matrix switches, the paper highlights both guarantees together.
V. CONCLUSION
The paper develops a fully adaptive approach for dynamic environments and extends it to structured comparators and drifting zero-sum games. Its regret adapts to the smaller regularity measure, while game convergence depends on payoff-matrix variability.
- Conclusion: The proposed algorithm addresses online learning with time-varying cost functions and comparators without prior knowledge of the environment.The method is described as fully adaptive.
- Conclusion: Its dynamic-regret upper bound captures the interplay between regularity of the function sequence and regularity of the comparator sequence.The bound is intended to cover both environmental and benchmark variation.
- Conclusion: The regret bound adapts to the smaller of the two regularity quantities, combining the advantages associated with both regimes.The conclusion characterizes this as selecting the best of both worlds.
- Conclusion: For drifting zero-sum games, the analysis characterizes convergence to average minimax equilibrium through variability in the sequence of payoff matrices.This application instantiates the dynamic-regret framework in a changing-game setting.
APPENDIX : PROOFS
The appendix develops the regret and game-theoretic guarantees through comparator batching, adaptive mirror-descent identities, and separate analyses for compliant and deviating opponents.
- Adaptive analysis: The proof uses strong convexity, Jensen’s inequality, and triangle inequalities to control the terms in the mirror-descent decomposition.These steps convert the per-epoch inequalities into the stated cumulative bound.
- Comparator batching: The analysis embeds optimal comparator sequences into the admissible comparator set and uses their optimality to derive the dynamic-regret bound.The proof invokes fixed-comparator membership and optimality across batches.
- Comparator batching: The proof decomposes comparator sequences into batches with fixed comparators, controlling their number through comparator variation.The construction chooses the batch count from the variation and regularizer parameters.
- Adaptive analysis: The adaptive AOMD proof tunes step sizes through doubling epochs and bounds violations using the regularizer and variation quantities.The number of epochs is controlled using the growth schedule for L_i.
- Game analysis: For the game application, the appendix specializes the regularizer to KL divergence and adds uniform mixing to control deviations and coordinate-wise terms.The resulting bounds apply both when the second player follows the strategy and when that player is dishonest.
- Game analysis: Combining both players’ bounds yields convergence of payoffs to average minimax values, while the unilateral-deviation case preserves regret against changing comparator sequences.The proof separately derives the compliant-opponent and deviating-opponent guarantees.