---
title: "Logarithmic Regret for Alternating Mirror Descent"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.05243v1"
permalink: "https://feed.astralor.com/items/itm_5b1bcca217fe3118cbbdfb05"
published: "2026-11-03T17:26:41.000Z"
score: 56
channel: "ai"
tags: ["RAG","Logarithmic Regret","Alternating Mirror Descent","Alternating","AltOMD","OMD","Previous"]
---

# Logarithmic Regret for Alternating Mirror Descent

## 速览

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 bo…

## 关键点

- 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.

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_5b1bcca217fe3118cbbdfb05