6 papers
Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
Weiming Ou, Xiao Wang
We study optimizing -smooth and -Polyak-Lojasiewicz (PL) objectives with unbiased stochastic gradients under -heavy-tailed noise (). In the unrestricted high-dim…
Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach
Yi Feng, Weiming Ou, Xiao Wang
The remarkable success of the Adam in training neural networks has naturally led to the widespread use of its descent-ascent counterpart, Adam-DA, for solving zero-sum games. Despi…
Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Yi Feng, Kaito Fujii, Stratis Skoulakis +2
Since Polyak's pioneering work, heavy ball (HB) momentum has been widely studied in minimization. However, its role in min-max games remains largely unexplored. As a key component…
Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games
Yi Feng, Ping Li, Ioannis Panageas +1
Last-iterate behaviors of learning algorithms in repeated two-player zero-sum games have been extensively studied due to their wide applications in machine learning and related tas…
Prediction Accuracy of Learning in Games : Follow-the-Regularized-Leader meets Heisenberg
Yi Feng, Georgios Piliouras, Xiao Wang
We investigate the accuracy of prediction in deterministic learning dynamics of zero-sum games with random initializations, specifically focusing on observer uncertainty and its re…
On the Last-iterate Convergence in Time-varying Zero-sum Games: Extra Gradient Succeeds where Optimism Fails
Yi Feng, Hu Fu, Qun Hu +4
Last-iterate convergence has received extensive study in two player zero-sum games starting from bilinear, convex-concave up to settings that satisfy the MVI condition. Typical met…