Multiplicative Weights Update: Aspects of Optimism, Chaos and Acceleration (Xiao Wang)

Abstract

Multiplicative Weights Update (MWU) is a fundamental algorithm that has many applications in constrained optimization, game theory, machine learning etc. In recent years, techniques from dynamical systems have been proven significant in analyzing last-iterate convergence and chaos arising from iterations of MWU. We collect our recent progress on different aspects of MWU such as last iterate convergence of its optimistic variant in convex-concave setting, chaotic behavior in coordination and zero-sum games, as well as an accelerated scheme based on Riemannian geometric interpretation of MWU. These results indicate some future work on constrained optimization and online learning, especially from the dynamical and geometric perspectives.

Time

Speaker

Room