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

Abstract

Multiplicative Weights Update (MWU) is afundamental algorithm that has many applications in constrained optimization,game theory, machine learning etc. In recent years, techniques from dynamicalsystems have been proven significant in analyzing last-iterate convergence andchaos arising from iterations of MWU. We collect our recent progress ondifferent aspects of MWU such as last iterate convergence of its optimisticvariant in convex-concave setting, chaotic behavior in coordination andzero-sum games, as well as an accelerated scheme based on Riemannian geometricinterpretation of MWU. These results indicate some future work on constrainedoptimization and online learning, especially from the dynamical and geometricperspectives.

Time

2021-06-18  17:00-17:30   

Speaker

Xiao Wang, Shanghai University of Finance and Economics

Room

Guangdong Hotel Shanghai