research
∙
06/27/2023
Semi Bandit Dynamics in Congestion Games: Convergence to Nash Equilibrium and No-Regret Guarantees
In this work, we introduce a new variant of online gradient descent, whi...
share
research
∙
05/23/2023
Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria
The works of (Daskalakis et al., 2009, 2022; Jin et al., 2022; Deng et a...
research
∙
01/26/2023
On the Convergence of No-Regret Learning Dynamics in Time-Varying Games
Most of the literature on learning in games has focused on the restricti...
research
∙
01/05/2023
Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
Adversarial team games model multiplayer strategic interactions in which...
research
∙
10/11/2022
On Scrambling Phenomena for Randomly Initialized Recurrent Networks
Recurrent Neural Networks (RNNs) frequently exhibit complicated dynamics...
research
∙
08/03/2022
Efficiently Computing Nash Equilibria in Adversarial Team Markov Games
Computing Nash equilibrium policies is a central problem in multi-agent ...
research
∙
04/25/2022
Accelerated Multiplicative Weights Update Avoids Saddle Points almost always
We consider non-convex optimization problems with constraint that is a p...
research
∙
03/22/2022
Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games
We show that, for any sufficiently small fixed ϵ > 0, when both players ...
research
∙
03/22/2022
On Last-Iterate Convergence Beyond Zero-Sum Games
Most existing results about last-iterate convergence of learning dynamic...
research
∙
11/07/2021
Teamwork makes von Neumann work: Min-Max Optimization in Two-Team Zero-Sum Games
Motivated by recent advances in both theoretical and applied aspects of ...
research
∙
10/20/2021
Independent Natural Policy Gradient Always Converges in Markov Potential Games
Multi-agent reinforcement learning has been successfully applied to full...
research
∙
06/03/2021
Combinatorial Algorithms for Matching Markets via Nash Bargaining: One-Sided, Two-Sided and Non-Bipartite
This paper is an attempt to deal with the recent realization (Vazirani, ...
research
∙
06/03/2021
Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
Potential games are arguably one of the most important and widely studie...
research
∙
10/11/2020
Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev
Sampling is a fundamental and arguably very important task with numerous...
research
∙
06/17/2020
Efficient Statistics for Sparse Graphical Models from Truncated Samples
In this paper, we study high-dimensional estimation from truncated sampl...
research
∙
03/18/2020
Logistic-Regression with peer-group effects via inference in higher order Ising models
Spin glass models, such as the Sherrington-Kirkpatrick, Hopfield and Isi...
research
∙
03/02/2020
Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systems
The expressivity of neural networks as a function of their depth, width ...
research
∙
02/26/2020
Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently
Non-negative matrix factorization (NMF) is a fundamental non-convex opti...
research
∙
02/17/2020
Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
In a recent series of papers it has been established that variants of Gr...
research
∙
12/09/2019
Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
Understanding the representational power of Deep Neural Networks (DNNs) ...
research
∙
05/08/2019
Regression from Dependent Observations
The standard linear and logistic regression models assume that the respo...
research
∙
02/19/2019
On the Convergence of EM for truncated mixtures of two Gaussians
Motivated by a recent result of Daskalakis et al. DGTZ18, we analyze the...
research
∙
07/11/2018
Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
Motivated by applications in Game Theory, Optimization, and Generative A...
research
∙
07/11/2018
The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
Motivated by applications in Optimization, Game Theory, and the training...
research
∙
10/30/2017
Rock-Paper-Scissors, Differential Games and Biological Diversity
We model a situation in which a collection of species derive their fitne...
research
∙
10/20/2017