Stochastic Hamiltonian Gradient Methods for Smooth Games
Jul 12, 2020
Speakers
Nicolas Loizou
Speaker · 0 followers
Hugo Berard
Speaker · 0 followers
Alexia Jolicoeur-Martineau
Speaker · 0 followers
Pascal Vincent
Speaker · 1 follower
Simon Lacoste-Julien
Speaker · 1 follower
Ioannis Mitliagkas
Speaker · 0 followers
About
The analysis of smooth games has attracted attention, motivated by the success of adversarial formulations. The Hamiltonian method is a lightweight second-order approach that recasts the problem in terms of a minimization objective. Consensus optimization can be seen as a generalization: it mixes a Hamiltonian term with the original game dynamics. This family of Hamiltonian methods has shown promise in literature. However, they come with no guarantees for stochastic games. Classic stochastic extragradient and mirror-prox methods require averaging over a compact domain to achieve convergence. Recent variance-reduced first-order schemes focus on unbounded domains, but stop short of proving last-iterate convergence for bilinear matrix games. We analyze the stochastic Hamiltonian method and a novel variance-reduced variant of it and provide the first set of last-iterate convergence guarantees for stochastic unbounded bilinear games. More generally, we provide convergence guarantees for a family of stochastic games, notably including some non-convex ones. We supplement our analysis with experiments on a stochastic bilinear game, where our theory is shown to be tight, and simple adversarial machine learning formulations.The analysis of smooth games has attracted attention, motivated by the success of adversarial formulations. The Hamiltonian method is a lightweight second-order approach that recasts the problem in terms of a minimization objective. Consensus optimization can be seen as a generalization: it mixes a Hamiltonian term with the original game dynamics. This family of Hamiltonian methods has shown promise in literature. However, they come with no guarantees for stochastic games. Classic stochastic ext…
Categories
Mathematics
Category · 2.4k presentations
AI & Data Science
Category · 10.8k presentations
Software & Programming
Category · 1k presentations
About ICML 2020
The International Conference on Machine Learning (ICML) is the premier gathering of professionals dedicated to the advancement of the branch of artificial intelligence known as machine learning. ICML is globally renowned for presenting and publishing cutting-edge research on all aspects of machine learning used in closely related areas like artificial intelligence, statistics and data science, as well as important application areas such as machine vision, computational biology, speech recognition, and robotics. ICML is one of the fastest growing artificial intelligence conferences in the world. Participants at ICML span a wide range of backgrounds, from academic and industrial researchers, to entrepreneurs and engineers, to graduate students and postdocs.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Graph neural induction of value iteration
Watch later
Andreea Deac, …
DeepMind at WiML Un-worskhop
Watch later
Nonstationary Nonseparable Random Fields
Watch later
Kangrui Wang, …
On the Global Optimality of Model-Agnostic Meta-Learning
Watch later
Online Learning with Imperfect Hints
Watch later
Bi-Level Graph Neural Networks for Drug-Drug Interaction Prediction
Watch later
Yunsheng Bai, …