Logarithmic Regret for Alternating Mirror Descent
Abstract
Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained O(T1/3) and O(T1/5) regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether AltOMD achieves near-constant regret has remained an open question. In this paper we resolve the question of whether AltOMD achieves near-constant regret in the affirmative. In particular, we show an $O(log(T))$ regret bound on the sum of the players' external regrets for any two-player zero-sum bilinear game with compact convex strategy sets, under mild regularity assumptions on the regularizers. We verify that our assumptions hold for the negative entropy regularizer, thereby obtaining logarithmic regret for the alternating multiplicative weights updates algorithm. The regret bound also yields an $O(log(T)/T)$ duality gap bound for the averaged strategies.
Related
- Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
- Mirror descent algorithms with logarithmic barriers
- Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
- Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
- Does Policy Mirror Descent Converge in Policy with Non-Decomposable Mirror Maps? A Counterexample
BibTeX
@misc{nan2026logarithmic,
title = {{Logarithmic Regret for Alternating Mirror Descent}},
author = {Tianlong Nan and Christian Kroer},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05243},
eprint = {2611.05243},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05243},
}
RIS
TY - UNPB
TI - Logarithmic Regret for Alternating Mirror Descent
AU - Tianlong Nan
AU - Christian Kroer
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05243
UR - https://arxiv.org/abs/2611.05243
AB - Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained O(T^1/3) and O(T^1/5) regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether AltOMD achieves near-constant regret has remained an open question. In this paper we resolve the question of whether AltOMD achieves near-constant regret in the affirmative. In particular, we show an $O(log(T))$ regret bound on the sum of the players' external regrets for any two-player zero-sum bilinear game with compact convex strategy sets, under mild regularity assumptions on the regularizers. We verify that our assumptions hold for the negative entropy regularizer, thereby obtaining logarithmic regret for the alternating multiplicative weights updates algorithm. The regret bound also yields an $O(log(T)/T)$ duality gap bound for the averaged strategies.
ER -