{"id":"arxiv/2611.05243","url":"https://arxiv.org/abs/2611.05243","tags":["cs.LG","cs.GT","math.OC","stat.ML"],"score":0,"title":"Logarithmic Regret for Alternating Mirror Descent","domain":"cs.LG","source":"arxiv","authors":["Tianlong Nan","Christian Kroer"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}