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
∙
01/10/2023
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps
In this paper we present a first-order method that admits near-optimal c...
research
∙
11/03/2022
Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization
We propose an adaptive variance-reduction method, called AdaSpider, for ...
research
∙
10/18/2022
STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games
Min-max optimization problems involving nonconvex-nonconcave objectives ...
research
∙
07/18/2022
Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games
The study of learning in games has thus far focused primarily on normal ...
research
∙
11/29/2021
Optimal No-Regret Learning in General Games: Bounded Regret with Unbounded Step-Sizes via Clairvoyant MWU
In this paper we solve the problem of no-regret learning in general game...
research
∙
11/05/2021
Online Learning in Periodic Zero-Sum Games
A seminal result in game theory is von Neumann's minmax theorem, which s...
research
∙
10/10/2021
Transaction Fees on a Honeymoon: Ethereum's EIP-1559 One Month Later
Ethereum Improvement Proposal (EIP) 1559 was recently implemented to tra...
research
∙
07/28/2021
On the Approximability of Multistage Min-Sum Set Cover
We investigate the polynomial-time approximability of the multistage ver...
research
∙
06/08/2021
Efficient Online Learning for Dynamic k-Clustering
We study dynamic clustering problems from the perspective of online lear...
research
∙
02/21/2021
Dynamical Analysis of the EIP-1559 Ethereum Fee Market
Participation in permissionless blockchains results in competition over ...
research
∙
12/15/2020
Evolutionary Game Theory Squared: Evolving Agents in Endogenously Evolving Zero-Sum Games
The predominant paradigm in evolutionary game theory and more generally ...
research
∙
11/05/2020
Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent
We consider a natural model of online preference aggregation, where sets...
research
∙
09/21/2020
The Complexity of Constrained Min-Max Optimization
Despite its important applications in Machine Learning, min-max optimiza...
research
∙
03/04/2020
The Online Min-Sum Set Cover Problem
We consider the online Min-Sum Set Cover (MSSC), a natural and intriguin...
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
∙
11/20/2019
Node Max-Cut and Computing Equilibria in Linear Weighted Congestion Games
Computing an equilibrium of a game is of central interest in Algorithmic...
research
∙
05/29/2019