Gauthier Gidel

sadhana.anand@mila.quebec

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

yuan-chen.chang@mila.quebec

Yuan-Chen Chang

PhD - Université de Montréal

david-a.dobre@mila.quebec

PhD - Université de Montréal

damien.ferbach@mila.quebec

Nouha Dziri

Independent visiting researcher - N/A

nouha.dziri@gmail.com

PhD - Université de Montréal

Co-supervisor :

Courtney Paquette

niklas.herbster@gmail.com

Niklas Herbster

Research Intern - Université de Montréal

Principal supervisor :

Irina Rish

marco.jiralerspong@mila.quebec

Marco Jiralerspong

PhD - Université de Montréal

andjela.mladenovic@mila.quebec

Zichu Liu

PhD - Université de Montréal

Co-supervisor :

Ioannis Mitliagkas

zichu.liu@mila.quebec

Andjela Mladenovic

PhD - Université de Montréal

Co-supervisor :

Aaron Courville

mehrnaz.mofakhami@mila.quebec

Mehrnaz Mofakhami

Collaborating researcher - Université de Montréal

Co-supervisor :

Ioannis Mitliagkas

Collaborating researcher - Université de Montréal

ailin.rasteh@mila.quebec

Leo Schwinn

Independent visiting researcher - Technical Univeristy of Munich

leo.schwinn@mila.quebec

Tom Stanic

Master's Research - Université de Montréal

tom.stanic@mila.quebec

tommaso.tosato@mila.quebec

Tommaso Tosato

Postdoctorate - Université de Montréal

PhD - Université de Montréal

danilo.vucetic@mila.quebec

Sophie Xhonneux

PhD - Université de Montréal

Co-supervisor :

Jian Tang

lpxhonneux@gmail.com

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

Huizhuo Yuan

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-07-02

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

Omega: Optimistic EMA Gradients

Stochastic min-max optimization has gained interest in the machine learning community with the advancements in GANs and adversarial training… (see more). Although game optimization is fairly well understood in the deterministic setting, some issues persist in the stochastic regime. Recent work has shown that stochastic gradient descent-ascent methods such as the optimistic gradient are highly sensitive to noise or can fail to converge. Although alternative strategies exist, they can be prohibitively expensive. We introduce Omega, a method with optimistic-like updates that mitigates the impact of noise by incorporating an EMA of historic gradients in its update rule. We also explore a variation of this algorithm that incorporates momentum. Although we do not provide convergence guarantees, our experiments on stochastic games show that Omega outperforms the optimistic gradient method when applied to linear players.

2023-07-01

ICML.cc/2023/Workshop/LXAI_Regular_Deadline (oral)

Raising the Bar for Certified Adversarial Robustness with Diffusion Models

Thomas Altstidl

Bjoern Eskofier

Leo Schwinn

Certified defenses against adversarial attacks offer formal guarantees on the robustness of a model, making them more reliable than empirica… (see more)l methods such as adversarial training, whose effectiveness is often later reduced by unseen attacks. Still, the limited certified robustness that is currently achievable has been a bottleneck for their practical adoption. Gowal et al. and Wang et al. have shown that generating additional training data using state-of-the-art diffusion models can considerably improve the robustness of adversarial training. In this work, we demonstrate that a similar approach can substantially improve deterministic certified defenses. In addition, we provide a list of recommendations to scale the robustness of certified training approaches. One of our main insights is that the generalization gap, i.e., the difference between the training and test accuracy of the original model, is a good predictor of the magnitude of the robustness improvement when using additional generated data. Our approach achieves state-of-the-art deterministic robustness certificates on CIFAR-10 for the

2023-05-16

arXiv (preprint)

arxiv.org

A General Framework for Proving the Equivariant Strong Lottery Ticket Hypothesis

Damien Ferbach

Christos Tsirigotis

Avishek (Joey) Bose

The Strong Lottery Ticket Hypothesis (SLTH) stipulates the existence of a subnetwork within a sufficiently overparameterized (dense) neural … (see more)network that -- when initialized randomly and without any training -- achieves the accuracy of a fully trained target network. Recent works by Da Cunha et. al 2022; Burkholz 2022 demonstrate that the SLTH can be extended to translation equivariant networks -- i.e. CNNs -- with the same level of overparametrization as needed for the SLTs in dense networks. However, modern neural networks are capable of incorporating more than just translation symmetry, and developing general equivariant architectures such as rotation and permutation has been a powerful design principle. In this paper, we generalize the SLTH to functions that preserve the action of the group

2023-04-30

International Conference on Learning Representations (Accept: poster)

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-04-24

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

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

Quentin Bertrand

Wojciech Marian Czarnecki

The Elo score has been extensively used to rank players by their skill or strength in competitive games such as chess, go, or StarCraft II. … (see more)The Elo score implicitly assumes games have a strong additive—hence transitive—component. In this paper, we investigate the challenge of identifying transitive components in games. As a starting point, we show that the Elo score provably fails to extract the transitive component of some elementary transitive games. Based on this observation, we propose an alternative ranking system which properly extracts the transitive components in these games. Finally, we conduct an in-depth empirical validation on real-world game payoff matrices: it shows significant prediction performance improvements compared to the Elo score.

2023-04-24

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

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-31

ICLR.cc/2023/Conference (poster)

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.

2022-12-31

AISTATS (published)

arxiv.org

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-22

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

Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise

Eduard Gorbunov

Marina Danilova

Pavel Dvurechensky

Alexander Gasnikov

2022-10-30

NeurIPS.cc/2022/Conference (accept)

Dissecting adaptive methods in GANs

Samy Jelassi

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-08

ArXiv (preprint)

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

Fabian Pedregosa

The recently developed average-case analysis of optimization methods allows a more fine-grained and representative convergence analysis than… (see more) usual worst-case results. In exchange, this analysis requires a more precise hypothesis over the data generating process, namely assuming knowledge of the expected spectral distribution (ESD) of the random matrix associated with the problem. This work shows that the concentration of eigenvalues near the edges of the ESD determines a problem's asymptotic average complexity. This a priori information on this concentration is a more grounded assumption than complete knowledge of the ESD. This approximate concentration is effectively a middle ground between the coarseness of the worst-case scenario convergence and the restrictive previous average-case analysis. We also introduce the Generalized Chebyshev method, asymptotically optimal under a hypothesis on this concentration and globally optimal when the ESD follows a Beta distribution. We compare its performance to classical optimization algorithms, such as gradient descent or Nesterov's scheme, and we show that, in the average-case context, Nesterov's method is universally nearly optimal asymptotically.

2022-07-18

International Conference on Machine Learning (Accept for Short Presentation)