Timezone: »

 
Clairvoyant Regret Minimization: Equivalence with Nemirovski’s Conceptual Prox Method and Extension to General Convex Games
Gabriele Farina · Christian Kroer · Chung-Wei Lee · Haipeng Luo

@
in OPT 2022: Optimization for Machine Learning »
Event URL: https://openreview.net/forum?id=5LMyDvjhq5 »

A recent paper by Piliouras et al. introduces an uncoupled learning algorithm for normal-form games---called Clairvoyant MWU (CMWU). In this paper we show that CMWU is equivalent to the conceptual prox method described by Nemirovski. This connection immediately shows that it is possible to extend the CMWU algorithm to any convex game, a question left open by Piliouras et al. We call the resulting algorithm---again equivalent to the conceptual prox method---Clairvoyant OMD. At the same time, we show that our analysis yields an improved regret bound compared to the original bound by Piliouras et al., in that the regret of CMWU scales only with the square root of the number of players, rather than the number of players themselves.

Author Information

Gabriele Farina (Meta AI; Carnegie Mellon University)
Christian Kroer (Columbia University)
Chung-Wei Lee (University of Southern California)
Haipeng Luo (University of Southern California)

More from the Same Authors