Logarithmic Regret for Alternating Mirror Descent
The authors prove that the sum of both players’ external regrets grows only logarithmically with the number of rounds.
The result resolves an open question about near-constant regret for alternating online mirror descent, improving earlier bounds of O(T⅓) and O(T⅕). It applies to two-player zero-sum bilinear games with compact convex strategy sets, under mild regularity assumptions on the regularizers. The authors verify those assumptions for negative entropy, extending the guarantee to alternating multiplicative weights updates. The bound also gives an O(log(T)/T) duality gap for averaged strategies.
ArXiv · AI/CL/LG's note
The result resolves an open question about near-constant regret for alternating online mirror descent, improving earlier bounds of O(T⅓) and O(T⅕). It applies to two-player zero-sum bilinear games with compact convex strategy sets, under mild regularity assumptions on the regularizers. The authors verify those assumptions for negative entropy, extending the guarantee to alternating multiplicative weights updates. The bound also gives an O(log(T)/T) duality gap for averaged strategies.
ArXiv · AI/CL/LG's note
score 5