5 papers
Heavy-Tailed First-Order Optimization for Polyak-Łojasiewicz Condition: High-Dimensional Minimax Bounds, High-Probability Guarantee, and Fixed-Dimensional Improvements
Weiming Ou, Xiao Wang
We study smooth Polyak--Łojasiewicz (PL) optimization with conditionally unbiased stochastic gradients satisfying \[ \mathbb E\!\left[ \|G_t-\nabla f(x_t)\|^α\mid\mathcal F_{t-1} \…
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…