Gauthier Gidel

Biography

I am an assistant professor in the Department of Computer Science and Operations Research (DIRO) at Université de Montréal, a core academic member of Mila – Quebec Artificial Intelligence Institute, and a Canada CIFAR AI Chair.

Previously, I was awarded a Borealis AI Graduate Fellowship, worked at DeepMind and Element AI, and was a Long-Term Visitor at the Simons Institute at UC Berkeley.

My research interests lie at the intersection of game theory, optimization and machine learning.

Current Students

Sadhana Anand

Master's Research - Université de Montréal

Rohan Banerjee

Collaborating Alumni - Polytechnique Montréal

Principal supervisor :

Collaborating Alumni - Université de Montréal

Co-supervisor :

David Dobre

PhD - Université de Montréal

Damien Ferbach

PhD - Université de Montréal

Co-supervisor :

PhD - Université de Montréal

Zichu Liu

PhD - Université de Montréal

Co-supervisor :

Ioannis Mitliagkas

Matt Matthew

Research Intern - Université de Montréal

PhD - Université de Montréal

Co-supervisor :

Aaron Courville

Brice Rauby

PhD - Polytechnique Montréal

Principal supervisor :

Maxime Gasse

brice.rauby@polymlt.ca

Fabrizzio Sabelli

Research Intern - Université de Montréal

Leo Schwinn

Independent visiting researcher - Technical Univeristy of Munich

Tom Stanic

Research Intern - Université de Montréal

Danilo Vucetic

PhD - Université de Montréal

Sophie Xhonneux

PhD - Université de Montréal

Co-supervisor :

Collaborating Alumni - N/A

What Do Synaptic Weight Distributions Tell Us About Learning in the Brain ?

Blog Posts

June 13, 2024

Roman Pogodin

Jonathan Cornford

Arna Ghosh

Gauthier Gidel

Guillaume Lajoie

Blake Richards

Read the article

Publications

Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization

Chris Junchi Li

Angela Yuan

Quanquan Gu

Michael Jordan

We propose a new first-order optimization algorithm --- AcceleratedGradient-OptimisticGradient (AG-OG) Descent Ascent---for separable convex… (see more)-concave minimax optimization. The main idea of our algorithm is to carefully leverage the structure of the minimax problem, performing Nesterov acceleration on the individual component and optimistic gradient on the coupling component. Equipped with proper restarting, we show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings, including bilinearly coupled strongly convex-strongly concave minimax optimization (bi-SC-SC), bilinearly coupled convex-strongly concave minimax optimization (bi-C-SC), and bilinear games. We also extend our algorithm to the stochastic setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings. AG-OG is the first single-call algorithm with optimal convergence rates in both deterministic and stochastic settings for bilinearly coupled minimax optimization problems.

2023-01-01

ICML (published)

Performative Prediction with Neural Networks

Mehrnaz Mofakhami

Ioannis Mitliagkas

2023-01-01

AISTATS (published)

Performative Prediction with Neural Networks

Mehrnaz Mofakhami

Ioannis Mitliagkas

Performative prediction is a framework for learning models that influence the data they intend to predict. We focus on finding classifiers t… (see more)hat are performatively stable, i.e. optimal for the data distribution they induce. Standard convergence results for finding a performatively stable classifier with the method of repeated risk minimization assume that the data distribution is Lipschitz continuous to the model's parameters. Under this assumption, the loss must be strongly convex and smooth in these parameters; otherwise, the method will diverge for some problems. In this work, we instead assume that the data distribution is Lipschitz continuous with respect to the model's predictions, a more natural assumption for performative systems. As a result, we are able to significantly relax the assumptions on the loss function. In particular, we do not need to assume convexity with respect to the model's parameters. As an illustration, we introduce a resampling procedure that models realistic distribution shifts and show that it satisfies our assumptions. We support our theory by showing that one can learn performatively stable classifiers with neural networks making predictions about real data that shift according to our proposed procedure.

2023-01-01

AISTATS (published)

On the Limitations of Elo: Real-World Games, are Transitive, not Additive

Quentin Bertrand

Wojciech M. Czarnecki

Real-world competitive games, such as chess, go, or StarCraft II, rely on Elo models to measure the strength of their players. Since these g… (see more)ames are not fully transitive, using Elo implicitly assumes they have a strong transitive component that can correctly be identified and extracted. In this study, we investigate the challenge of identifying the strength of the transitive component in games. First, we show that Elo models can fail to extract this transitive component, even in elementary transitive games. Then, based on this observation, we propose an extension of the Elo score: we end up with a disc ranking system that assigns each player two scores, which we refer to as skill and consistency. Finally, we propose an empirical validation on payoff matrices coming from real-world games played by bots and humans.

2023-01-01

AISTATS (published)

arxiv.org

Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top

Eduard Gorbunov

Samuel Horváth

Peter Richtárik

Byzantine-robustness has been gaining a lot of attention due to the growth of the interest in collaborative and federated learning. However,… (see more) many fruitful directions, such as the usage of variance reduction for achieving robustness and communication compression for reducing communication costs, remain weakly explored in the field. This work addresses this gap and proposes Byz-VR-MARINA - a new Byzantine-tolerant method with variance reduction and compression. A key message of our paper is that variance reduction is key to fighting Byzantine workers more effectively. At the same time, communication compression is a bonus that makes the process more communication efficient. We derive theoretical convergence guarantees for Byz-VR-MARINA outperforming previous state-of-the-art for general non-convex and Polyak-Lojasiewicz loss functions. Unlike the concurrent Byzantine-robust methods with variance reduction and/or compression, our complexity results are tight and do not rely on restrictive assumptions such as boundedness of the gradients or limited compression. Moreover, we provide the first analysis of a Byzantine-tolerant method supporting non-uniform sampling of stochastic gradients. Numerical experiments corroborate our theoretical findings.

2023-01-01

International Conference on Learning Representations (published)

Momentum Extragradient is Optimal for Games with Cross-Shaped Spectrum

Junhyung Lyle Kim

Anastasios Kyrillidis

Fabian Pedregosa

Google Research

The extragradient method has recently gained a lot of attention, due to its convergence behavior on smooth games. In games, the eigenvalues … (see more)of the Jacobian of the vector field are distributed on the complex plane, exhibiting more convoluted dynamics compared to minimization. In this work, we take a polynomial-based analysis of the extragradient with momentum for optimizing games with \emph{cross-shaped} spectrum on the complex plane. We show two results: first, the extragradient with momentum exhibits three different modes of convergence based on the hyperparameter setup: when the eigenvalues are distributed

2022-11-23

NeurIPS.cc/2022/Workshop/OPT (poster)

Dissecting adaptive methods in GANs

Samy Jelassi

David Dobre

Arthur Mensch

Yuanzhi Li

Adaptive methods are a crucial component widely used for training generative adversarial networks (GANs). While there has been some work to … (see more)pinpoint the “marginal value of adaptive methods” in standard tasks, it remains unclear why they are still critical for GAN training. In this paper, we formally study how adaptive methods help train GANs; inspired by the grafting method proposed in Agarwal et al. (2020), we separate the magnitude and direction components of the Adam updates, and graft them to the direction and magnitude of SGDA updates respectively. By considering an update rule with the magnitude of the Adam update and the normalized direction of SGD, we empirically show that the adaptive magnitude of Adam is key for GAN training. This motivates us to have a closer look at the class of normalized stochastic gradient descent ascent (nSGDA) methods in the context of GAN training. We propose a synthetic theoretical framework to compare the performance of nSGDA and SGDA for GAN training with neural networks. We prove that in that setting, GANs trained with nSGDA recover all the modes of the true distribution, whereas the same networks trained with SGDA (and any learning rate configuration) suffer from mode collapse. The critical insight in our analysis is that normalizing the gradients forces the discriminator and generator to be updated at the same pace. We also experimentally show that for several datasets, Adam’s performance can be recovered with nSGDA methods.

2022-10-09

ArXiv (preprint)

Only tails matter: Average-Case Universality and Robustness in the Convex Regime

Leonardo Cunha

Fabian Pedregosa

Damien Scieur

Courtney Paquette

2022-06-28

Proceedings of the 39th International Conference on Machine Learning (published)

Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime

Leonardo Cunha

Fabian Pedregosa

Damien Scieur

Courtney Paquette

2022-06-20

ArXiv (preprint)

Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise

Eduard Gorbunov

Marina Danilova

David Dobre

Pavel Dvurechensky

Alexander Gasnikov

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

Chris Junchi Li

Yaodong Yu

Nicolas Loizou

Yitong Ma

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… (see more)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-01-01

AISTATS (published)

arxiv.org

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

Nicolas Loizou

Two of the most prominent algorithms for solving unconstrained smooth games are the classical stochastic gradient descent-ascent (SGDA) and … (see more)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.