460 citations · 783 across the 30 of their papers we have counts for
35 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…
Complexity of Non-Log-Concave Sampling in Fisher Information
Sinho Chewi, Andre Wibisono
We study the query complexity of obtaining a relative Fisher information guarantee for sampling from a log-smooth non-log-concave distribution; this is a sampling analog of finding…
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…
The Geometry of Efficient Nonconvex Sampling
Santosh S. Vempala, Andre Wibisono
We present an efficient algorithm for uniformly sampling from an arbitrary compact body from a warm start under isoperimetry and a natural volume…
Extragradient Type Methods for Riemannian Variational Inequality Problems
Zihao Hu, Guanghui Wang, Xi Wang +3
Riemannian convex optimization and minimax optimization have recently drawn considerable attention. Their appeal lies in their capacity to adeptly manage the non-convexity of the o…