Timezone: »

 
Poster
Stochastic Hamiltonian Gradient Methods for Smooth Games
Nicolas Loizou · Hugo Berard · Alexia Jolicoeur-Martineau · Pascal Vincent · Simon Lacoste-Julien · Ioannis Mitliagkas

Thu Jul 16 07:00 AM -- 07:45 AM & Thu Jul 16 06:00 PM -- 06:45 PM (PDT) @ Virtual
in Poster Session 42 »

The success of adversarial formulations in machine learning has brought renewed motivation for smooth games. In this work, we focus on the class of stochastic Hamiltonian methods and provide the first convergence guarantees for certain classes of stochastic smooth games. We propose a novel unbiased estimator for the stochastic Hamiltonian gradient descent (SHGD) and highlight its benefits. Using tools from the optimization literature we show that SHGD converges linearly to the neighbourhood of a stationary point. To guarantee convergence to the exact solution, we analyze SHGD with a decreasing step-size and we also present the first stochastic variance reduced Hamiltonian method. Our results provide the first global non-asymptotic last-iterate convergence guarantees for the class of stochastic unconstrained bilinear games and for the more general class of stochastic games that satisfy a ``sufficiently bilinear" condition, notably including some non-convex non-concave problems. We supplement our analysis with experiments on stochastic bilinear and sufficiently bilinear games, where our theory is shown to be tight, and on simple adversarial machine learning formulations.

Keywords: Convex Optimization · Game Theory and Mechanism Design · Generative Adversarial Networks · Non-convex Optimization · Optimization - Non-convex
[ Slides] 

Author Information

Nicolas Loizou (Mila, Université de Montréal)
Hugo Berard (Université de Montreal)
Alexia Jolicoeur-Martineau (Mila)
Pascal Vincent (U Montreal)
Simon Lacoste-Julien (Mila, University of Montreal & Samsung SAIL Montreal)
Simon Lacoste-Julien

Simon Lacoste-Julien is an associate professor at Mila and DIRO from Université de Montréal, and Canada CIFAR AI Chair holder. He also heads part time the SAIT AI Lab Montreal from Samsung. His research interests are machine learning and applied math, with applications in related fields like computer vision and natural language processing. He obtained a B.Sc. in math., physics and computer science from McGill, a PhD in computer science from UC Berkeley and a post-doc from the University of Cambridge. He spent a few years as a research faculty at INRIA and École normale supérieure in Paris before coming back to his roots in Montreal in 2016 to answer the call from Yoshua Bengio in growing the Montreal AI ecosystem.

Ioannis Mitliagkas (MILA, UdeM)

More from the Same Authors