Logarithmic Regret for Alternating Mirror Descent

Source: arxiv.org/abs/2611.05243

Tianlong Nan, Christian Kroer

arXivarxiv/2611.05243Nov 3, 2026cs.LGscore 0

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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.05243
curl -X POST /api/v1/records/arxiv/2611.05243/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05243/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'