Gauthier Gidel

sadhana.anand@mila.quebec

Biographie

Je suis professeur adjoint au Département d’informatique et de recherche opérationnelle (DIRO) de l'Université de Montréal et membre académique principal de Mila – Institut québécois d’intelligence artificielle. J'ai obtenu une bourse Borealis AI destinée aux étudiant·e·s des cycles supérieurs et je suis actuellement titulaire d'une chaire en IA Canada-CIFAR. J'ai travaillé chez DeepMind et Element AI, et j'ai récemment été un visiteur de longue durée au Simons Institute de l’Université de Californie à Berkeley. Mes intérêts de recherche se situent à l'intersection de la théorie des jeux, de l'optimisation et de l'apprentissage automatique.

Étudiants actuels

Sadhana Anand

Maîtrise recherche - UdeM

yuan-chen.chang@mila.quebec

Yuan-Chen Chang

Doctorat - UdeM

David Dobre

Doctorat - UdeM

david-a.dobre@mila.quebec

damien.ferbach@mila.quebec

Nouha Dziri

Visiteur de recherche indépendant - N/A

nouha.dziri@gmail.com

Doctorat - UdeM

Co-superviseur⋅e :

Courtney Paquette

niklas.herbster@gmail.com

Niklas Herbster

Stagiaire de recherche - UdeM

Superviseur⋅e principal⋅e :

Irina Rish

marco.jiralerspong@mila.quebec

Marco Jiralerspong

Doctorat - UdeM

Zichu Liu

Doctorat - UdeM

Co-superviseur⋅e :

Ioannis Mitliagkas

zichu.liu@mila.quebec

Orel Mazor

Collaborateur·rice de recherche - ENS Lyon

orel.mazor@mila.quebec

andjela.mladenovic@mila.quebec

Andjela Mladenovic

Doctorat - UdeM

Co-superviseur⋅e :

Aaron Courville

mehrnaz.mofakhami@mila.quebec

Mehrnaz Mofakhami

Collaborateur·rice de recherche - UdeM

Co-superviseur⋅e :

Ioannis Mitliagkas

Collaborateur·rice de recherche - UdeM

ailin.rasteh@mila.quebec

Leo Schwinn

Visiteur de recherche indépendant - Technical Univeristy of Munich

leo.schwinn@mila.quebec

Tom Stanic

Stagiaire de recherche - UdeM

tom.stanic@mila.quebec

tommaso.tosato@mila.quebec

Tommaso Tosato

Postdoctorat - UdeM

Doctorat - UdeM

danilo.vucetic@mila.quebec

bora.yongacoglu@mila.quebec

Sophie Xhonneux

Doctorat - UdeM

Co-superviseur⋅e :

Collaborateur·rice alumni - N/A

Billets de blogue

13 juin 2024

Que nous apprennent les distributions des coefficients synaptiques au sujet de l’apprentissage dans le cerveau ?

par

Roman Pogodin

Jonathan Cornford

Arna Ghosh

Gauthier Gidel

Guillaume Lajoie

Blake Richards

Lire l'article

Publications

Generalized Natural Gradient Flows in Hidden Convex-Concave Games and Gans

Andjela Mladenovic

Iosif Sakos

Georgios Piliouras

2022-04-24

International Conference on Learning Representations (Accept (Poster))

Online Adversarial Attacks

Avishek Joey Bose

William L. Hamilton

Adversarial attacks expose important vulnerabilities of deep learning models, yet little attention has been paid to settings where data arri… (voir plus)ves as a stream. In this paper, we formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases: attackers must operate under partial knowledge of the target model, and the decisions made by the attacker are irrevocable since they operate on a transient data stream. We first rigorously analyze a deterministic variant of the online threat model by drawing parallels to the well-studied

2022-04-24

International Conference on Learning Representations (Accept (Poster))

On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging

Chris Junchi Li

Yi Ma

Yaodong Yu

Nicolas Loizou

Nicolas Le Roux

Michael I. Jordan

We study the stochastic bilinear minimax optimization problem, presenting an analysis of the same-sample Stochastic ExtraGradient (SEG) meth… (voir plus)od with constant step size, and presenting variations of the method that yield favorable convergence. In sharp contrasts with the basic SEG method whose last iterate only contracts to a fixed neighborhood of the Nash equilibrium, SEG augmented with iteration averaging provably converges to the Nash equilibrium under the same standard settings, and such a rate is further improved by incorporating a scheduled restarting procedure. In the interpolation setting where noise vanishes at the Nash equilibrium, we achieve an optimal convergence rate up to tight constants. We present numerical experiments that validate our theoretical findings and demonstrate the effectiveness of the SEG method when equipped with iteration averaging and restarting.

2022-03-27

International Conference on Artificial Intelligence and Statistics (Accept (Poster))

On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging

Chris Junchi Li

Yaodong Yu

Nicolas Loizou

Yitong Ma

Nicolas Roux

Michael I. Jordan

2021-12-31

AISTATS (publié)

arxiv.org

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity

Two of the most prominent algorithms for solving unconstrained smooth games are the classical stochastic gradient descent-ascent (SGDA) and … (voir plus)the recently introduced stochastic consensus optimization (SCO) [Mescheder et al., 2017]. SGDA is known to converge to a stationary point for specific classes of games, but current convergence analyses require a bounded variance assumption. SCO is used successfully for solving large-scale adversarial problems, but its convergence guarantees are limited to its deterministic variant. In this work, we introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO under this condition for solving a class of stochastic variational inequality problems that are potentially non-monotone. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size, and we propose insightful stepsize-switching rules to guarantee convergence to the exact solution. In addition, our convergence guarantees hold under the arbitrary sampling paradigm, and as such, we give insights into the complexity of minibatching.

2021-12-06

Conference on Neural Information Processing Systems (Accept (Poster))

Convergence Analysis and Implicit Regularization of Feedback Alignment for Deep Linear Networks

Manuela Girotti

Ioannis Mitliagkas

We theoretically analyze the Feedback Alignment (FA) algorithm, an efficient alternative to backpropagation for training neural networks. We… (voir plus) provide convergence guarantees with rates for deep linear networks for both continuous and discrete dynamics. Additionally, we study incremental learning phenomena for shallow linear networks. Interestingly, certain specific initializations imply that negligible components are learned before the principal ones, thus potentially negatively affecting the effectiveness of such a learning algorithm; a phenomenon we classify as implicit anti-regularization. We also provide initialization schemes where the components of the problem are approximately learned by decreasing order of importance, thus providing a form of implicit regularization.

2021-10-19

arXiv (Cornell University) (prépublication)

arxiv.org

Linear Lower Bounds and Conditioning of Differentiable Games

Recent successes of game-theoretic formulations in ML have caused a resurgence of research interest in differentiable games. Overwhelmingly,… (voir plus) that research focuses on methods and upper bounds on their speed of convergence. In this work, we approach the question of fundamental iteration complexity by providing lower bounds to complement the linear (i.e. geometric) upper bounds observed in the literature on a wide class of problems. We cast saddle-point and min-max problems as 2-player games. We leverage tools from single-objective convex optimisation to propose new linear lower bounds for convex-concave games. Notably, we give a linear lower bound for

2020-11-20

Proceedings of the 37th International Conference on Machine Learning (publié)

Accelerating Smooth Games by Manipulating Spectral Shapes

We use matrix iteration theory to characterize acceleration in smooth games. We define the spectral shape of a family of games as the set co… (voir plus)ntaining all eigenvalues of the Jacobians of standard gradient dynamics in the family. Shapes restricted to the real line represent well-understood classes of problems, like minimization. Shapes spanning the complex plane capture the added numerical challenges in solving smooth games. In this framework, we describe gradient-based methods, such as extragradient, as transformations on the spectral shape. Using this perspective, we propose an optimal algorithm for bilinear games. For smooth and strongly monotone operators, we identify a continuum between convex minimization, where acceleration is possible using Polyak's momentum, and the worst case where gradient descent is optimal. Finally, going beyond first-order methods, we propose an accelerated version of consensus optimization.

2020-06-02

Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (publié)

A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games

We consider differentiable games where the goal is to find a Nash equilibrium. The machine learning community has recently started using var… (voir plus)iants of the gradient method (GD). Prime examples are extragradient (EG), the optimistic gradient method (OG) and consensus optimization (CO), which enjoy linear convergence in cases like bilinear games, where the standard GD fails. The full benefits of theses relatively new methods are not known as there is no unified analysis for both strongly monotone and bilinear games. We provide new analyses of the EG's local and global convergence properties and use is to get a tighter global convergence rate for OG and CO. Our analysis covers the whole range of settings between bilinear and strongly monotone games. It reveals that these methods converge via different mechanisms at these extremes; in between, it exploits the most favorable mechanism for the given problem. We then prove that EG achieves the optimal rate for a wide class of algorithms with any number of extrapolations. Our tight analysis of EG's convergence rate in games shows that, unlike in convex minimization, EG may be much faster than GD.

2020-06-02

International Conference on Artificial Intelligence and Statistics (inconnu)

Minimax Theorem for Latent Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets

D. Balduzzi

Wojciech M. Czarnecki

M. Garnelo

Yoram Bachrach

Adversarial training, a special case of multi-objective optimization, is an increasingly useful tool in machine learning. For example, two-p… (voir plus)layer zero-sum games are important for generative modeling (GANs) and for mastering games like Go or Poker via self-play. A classic result in Game Theory states that one must mix strategies, as pure equilibria may not exist. Surprisingly, machine learning practitioners typically train a \emph{single} pair of agents -- instead of a pair of mixtures -- going against Nash's principle. Our main contribution is a notion of limited-capacity-equilibrium for which, as capacity grows, optimal agents -- not mixtures -- can learn increasingly expressive and realistic behaviors. We define \emph{latent games}, a new class of game where agents are mappings that transform latent distributions. Examples include generators in GANs, which transform Gaussian noise into distributions on images, and StarCraft II agents, which transform sampled build orders into policies. We show that minimax equilibria in latent games can be approximated by a \emph{single} pair of dense neural networks. Finally, we apply our latent game approach to solve differentiable Blotto, a game with an infinite strategy space.

2020-02-13

ArXiv (prépublication)

arxiv.org

Non-normal Recurrent Neural Network (nnRNN): learning long time dependencies while improving expressivity with transient dynamics

Giancarlo Kerg

Kyle Goyette

Maximilian Puelma Touzel

A recent strategy to circumvent the exploding and vanishing gradient problem in RNNs, and to allow the stable propagation of signals over lo… (voir plus)ng time scales, is to constrain recurrent connectivity matrices to be orthogonal or unitary. This ensures eigenvalues with unit norm and thus stable dynamics and training. However this comes at the cost of reduced expressivity due to the limited variety of orthogonal transformations. We propose a novel connectivity structure based on the Schur decomposition and a splitting of the Schur form into normal and non-normal parts. This allows to parametrize matrices with unit-norm eigenspectra without orthogonality constraints on eigenbases. The resulting architecture ensures access to a larger space of spectrally constrained matrices, of which orthogonal matrices are a subset. This crucial difference retains the stability advantages and training speed of orthogonal RNNs while enhancing expressivity, especially on tasks that require computations over ongoing input sequences.

2019-05-27

PolyPublie (accepté)

Negative Momentum for Improved Game Dynamics

Reyhane Askari Hemmat

Rémi Le Priol

Games generalize the single-objective optimization paradigm by introducing different objective functions for different players. Differentiab… (voir plus)le games often proceed by simultaneous or alternating gradient updates. In machine learning, games are gaining new importance through formulations like generative adversarial networks (GANs) and actor-critic systems. However, compared to single-objective optimization, game dynamics are more complex and less understood. In this paper, we analyze gradient-based methods with momentum on simple games. We prove that alternating updates are more stable than simultaneous updates. Next, we show both theoretically and empirically that alternating gradient updates with a negative momentum term achieves convergence in a difficult toy adversarial problem, but also on the notoriously difficult to train saturating GANs.

2019-04-10

International Conference on Artificial Intelligence and Statistics (publié)