AI@AUEB talk : "On new variants of multiplicative weights update and mirror descent methods for zero-sum games", by Vangelis Markakis, Tuesday 7 June 2022, 17:15-18:00
We are happy to announce the next (remote) AI@AUEB talk:
Date/time: Tuesday 7 June 2022, 17:15-18:00 (Greek time)
Title: "On new variants of multiplicative weights update and mirror descent methods for zero-sum games"
Speaker: Vangelis Markakis (http://pages.cs.aueb.gr/~markakis/)
Abstract:
Our work focuses on extra gradient learning algorithms for finding Nash equilibria in bilinear zero-sum games. Such algorithms tend to exhibit a stronger performance than simple gradient methods, by having an intermediate and a final gradient step in each iteration. In this talk, we will first give an overview of recently proposed learning algorithms in this context, such as the Optimistic Multiplicative Weights Update method (by Daskalakis, Panageas, 2019) and Optimistic Mirror Descent (by Mertikopoulos et al. 2019). We will then propose a new algorithm, which can be formally considered as a variant of Optimistic Mirror Descent, using a large learning rate for the intermediate gradient step (and interpreted as computing approximate best response strategies against the profile of the previous iteration). Our main theoretical result is that the method guarantees last-iterate convergence to an equilibrium. In particular, we show that the algorithm reaches first an approximate Nash equilibrium, by decreasing the Kullback-Leibler divergence of each iterate, until the method becomes a contracting map, and converges to the exact equilibrium. Furthermore, we present experimental comparisons against the optimistic multiplicative weights update method, and show that our algorithm has significant practical potential since it offers substantial gains in terms of accelerated convergence.
Paper: https://arxiv.org/abs/2106.03579
MS Teams link:
ΑΙ@AUEB Lecture Series aim is to create collaborations, both between AUEB’s Departments and with external bodies and organizations, promoting the work of AUEB members, further strengthening existing collaborations, and possibly attracting additional resources.
To subscribe to the mailing list of AI@AUEB, send a message (with any subject and body) to ai_meetings-subscribe@lists.aueb.gr. To unsubscribe, send a message (with any subject and body) to ai_meetings-unsubscribe@lists.aueb.gr. Only the organizers of AI@AUEB can post messages to the mailing list.
If you have an AUEB account, you can also subscribe to the MS Teams team "AI@AUEB" (team code: r2dtl45). This way you will be able to see the scheduled AI@AUEB talks on your MS Teams calendar. You will also be able to send messages to the members of the team.
