1 citations · 1 across the 7 of their papers we have counts for
11 papers
Linear Last-Iterate Convergence Rates for Optimistic Learning in Harmonic Games
John Lazarsfeld, Anas Barakat, Jacob Abernethy +4
We prove that the last iterate of Optimistic Follow-The-Regularized-Leader (OFTRL) converges at a linear rate to a Nash equilibrium in multiplayer harmonic games. Our result holds…
Arbitrarily Slow Polynomial Convergence of Fictitious Play
Jacob Abernethy, John Lazarsfeld, Andre Wibisono
We show that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. For every integer , we construct a payoff matrix with $(k+1)^2…
When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation
John Lazarsfeld, Anas Barakat, Georgios Piliouras +2
This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which th…
Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play
John Lazarsfeld, Georgios Piliouras, Ryann Sim +1
This paper investigates the sublinear regret guarantees of two non-no-regret algorithms in zero-sum games: Fictitious Play, and Online Gradient Descent with constant stepsizes. In…
Online Learning in Stabilized Linear Dynamical Games with Adversarial Disturbances
Anas Barakat, John Lazarsfeld, Georgios Piliouras +1
We study online learning in linear dynamical games where multiple strategic agents act on a shared state evolving according to a linear dynamical system subject to adversarial dist…
Optimism Without Regularization: Constant Regret in Zero-Sum Games
John Lazarsfeld, Georgios Piliouras, Ryann Sim +1
This paper studies the optimistic variant of Fictitious Play for learning in two-player zero-sum games. While it is known that Optimistic FTRL -- a regularized algorithm with a bou…
Optimistic Online Learning in Symmetric Cone Games
Anas Barakat, Wayne Lin, John Lazarsfeld +1
We introduce symmetric cone games (SCGs), a broad class of multi-player games where each player's strategy lies in a generalized simplex (the trace-one slice of a symmetric cone).…
Game Dynamics and Equilibrium Computation in the Population Protocol Model
Dan Alistarh, Krishnendu Chatterjee, Mehrdad Karrabi +1
We initiate the study of game dynamics in the population protocol model: agents each maintain a current local strategy and interact in pairs uniformly at random. Upon each inte…
Simple Opinion Dynamics for No-Regret Learning
John Lazarsfeld, Dan Alistarh
We study a cooperative multi-agent bandit setting in the distributed GOSSIP model: in every round, each of agents chooses an action from a common set, observes the action's cor…
Fast Convergence of -Opinion Undecided State Dynamics in the Population Protocol Model
Talley Amir, James Aspnes, Petra Berenbrink +4
We analyze the convergence of the -opinion Undecided State Dynamics (USD) in the population protocol model. For =2 opinions it is well known that the USD reaches consensus wi…
Approximate Majority With Catalytic Inputs
Talley Amir, James Aspnes, John Lazarsfeld
Population protocols are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitabilit…