Timezone: »
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.
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 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
-
2023 Poster: Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning »
Sébastien Lachapelle · Tristan Deleu · Divyat Mahajan · Ioannis Mitliagkas · Yoshua Bengio · Simon Lacoste-Julien · Quentin Bertrand -
2023 Poster: Can We Scale Transformers to Predict Parameters of Diverse ImageNet Models? »
Boris Knyazev · DOHA HWANG · Simon Lacoste-Julien -
2023 Poster: Unlocking Slot Attention by Changing Optimal Transport Costs »
Yan Zhang · David Zhang · Simon Lacoste-Julien · Gertjan Burghouts · Cees Snoek -
2023 Poster: CrossSplit: Mitigating Label Noise Memorization through Data Splitting »
Jihye Kim · Aristide Baratin · Yan Zhang · Simon Lacoste-Julien -
2021 Poster: Structured Convolutional Kernel Networks for Airline Crew Scheduling »
Yassine Yaakoubi · Francois Soumis · Simon Lacoste-Julien -
2021 Poster: Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets »
Thomas Kerdreux · Lewis Liu · Simon Lacoste-Julien · Damien Scieur -
2021 Spotlight: Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets »
Thomas Kerdreux · Lewis Liu · Simon Lacoste-Julien · Damien Scieur -
2021 Spotlight: Structured Convolutional Kernel Networks for Airline Crew Scheduling »
Yassine Yaakoubi · Francois Soumis · Simon Lacoste-Julien -
2020 Poster: Linear Lower Bounds and Conditioning of Differentiable Games »
Adam Ibrahim · Waïss Azizian · Gauthier Gidel · Ioannis Mitliagkas -
2020 Poster: On Relativistic f-Divergences »
Alexia Jolicoeur-Martineau -
2020 Poster: A Unified Theory of Decentralized SGD with Changing Topology and Local Updates »
Anastasiia Koloskova · Nicolas Loizou · Sadra Boreiri · Martin Jaggi · Sebastian Stich -
2019 : Poster discussion »
Roman Novak · Maxime Gabella · Frederic Dreyer · Siavash Golkar · Anh Tong · Irina Higgins · Mirco Milletari · Joe Antognini · Sebastian Goldt · Adín Ramírez Rivera · Roberto Bondesan · Ryo Karakida · Remi Tachet des Combes · Michael Mahoney · Nicholas Walker · Stanislav Fort · Samuel Smith · Rohan Ghosh · Aristide Baratin · Diego Granziol · Stephen Roberts · Dmitry Vetrov · Andrew Wilson · César Laurent · Valentin Thomas · Simon Lacoste-Julien · Dar Gilboa · Daniel Soudry · Anupam Gupta · Anirudh Goyal · Yoshua Bengio · Erich Elsen · Soham De · Stanislaw Jastrzebski · Charles H Martin · Samira Shabanian · Aaron Courville · Shorato Akaho · Lenka Zdeborova · Ethan Dyer · Maurice Weiler · Pim de Haan · Taco Cohen · Max Welling · Ping Luo · zhanglin peng · Nasim Rahaman · Loic Matthey · Danilo J. Rezende · Jaesik Choi · Kyle Cranmer · Lechao Xiao · Jaehoon Lee · Yasaman Bahri · Jeffrey Pennington · Greg Yang · Jiri Hron · Jascha Sohl-Dickstein · Guy Gur-Ari -
2019 Poster: State-Reification Networks: Improving Generalization by Modeling the Distribution of Hidden Representations »
Alex Lamb · Jonathan Binas · Anirudh Goyal · Sandeep Subramanian · Ioannis Mitliagkas · Yoshua Bengio · Michael Mozer -
2019 Poster: Multi-objective training of Generative Adversarial Networks with multiple discriminators »
Isabela Albuquerque · Joao Monteiro · Thang Doan · Breandan Considine · Tiago Falk · Ioannis Mitliagkas -
2019 Poster: Unreproducible Research is Reproducible »
Xavier Bouthillier · César Laurent · Pascal Vincent -
2019 Oral: Unreproducible Research is Reproducible »
Xavier Bouthillier · César Laurent · Pascal Vincent -
2019 Oral: Multi-objective training of Generative Adversarial Networks with multiple discriminators »
Isabela Albuquerque · Joao Monteiro · Thang Doan · Breandan Considine · Tiago Falk · Ioannis Mitliagkas -
2019 Oral: State-Reification Networks: Improving Generalization by Modeling the Distribution of Hidden Representations »
Alex Lamb · Jonathan Binas · Anirudh Goyal · Sandeep Subramanian · Ioannis Mitliagkas · Yoshua Bengio · Michael Mozer -
2018 Poster: Learning Representations and Generative Models for 3D Point Clouds »
Panagiotis Achlioptas · Olga Diamanti · Ioannis Mitliagkas · Leonidas Guibas -
2018 Poster: Convergent Tree Backup and Retrace with Function Approximation »
Ahmed Touati · Pierre-Luc Bacon · Doina Precup · Pascal Vincent -
2018 Oral: Learning Representations and Generative Models for 3D Point Clouds »
Panagiotis Achlioptas · Olga Diamanti · Ioannis Mitliagkas · Leonidas Guibas -
2018 Oral: Convergent Tree Backup and Retrace with Function Approximation »
Ahmed Touati · Pierre-Luc Bacon · Doina Precup · Pascal Vincent -
2017 Poster: A Closer Look at Memorization in Deep Networks »
David Krueger · Yoshua Bengio · Stanislaw Jastrzebski · Maxinder S. Kanwal · Nicolas Ballas · Asja Fischer · Emmanuel Bengio · Devansh Arpit · Tegan Maharaj · Aaron Courville · Simon Lacoste-Julien -
2017 Talk: A Closer Look at Memorization in Deep Networks »
David Krueger · Yoshua Bengio · Stanislaw Jastrzebski · Maxinder S. Kanwal · Nicolas Ballas · Asja Fischer · Emmanuel Bengio · Devansh Arpit · Tegan Maharaj · Aaron Courville · Simon Lacoste-Julien