# Average-case Acceleration for Bilinear Games and Normal Matrices

arXiv: https://arxiv.org/abs/2010.02076 · HTML: https://mlsanity.com/paper/2010.02076/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

## Built on by (most cited first, 5 of 5)

- [Complex Momentum for Optimization in Games](https://mlsanity.com/paper/2102.08431/) (2021)
- [A Nonstochastic Control Approach to Optimization](https://mlsanity.com/paper/2301.07902/) (2023)
- [When is Momentum Extragradient Optimal? A Polynomial-Based Analysis](https://mlsanity.com/paper/2211.04659/) (2022)
- [Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices](https://mlsanity.com/paper/2305.17275/) (2023)
- [Distribution-Aware Algorithm Design with LLM Agents](https://mlsanity.com/paper/2605.14141/) (2026)

## Abstract (arXiv)

Advances in generative modeling and adversarial learning have given rise to renewed interest in smooth games. However, the absence of symmetry in the matrix of second derivatives poses challenges that are not present in the classical minimization framework. While a rich theory of average-case analysis has been developed for minimization problems, little is known in the context of smooth games. In this work we take a first step towards closing this gap by developing average-case optimal first-order methods for a subset of smooth games. We make the following three main contributions. First, we show that for zero-sum bilinear games the average-case optimal method is the optimal method for the minimization of the Hamiltonian. Second, we provide an explicit expression for the optimal method corresponding to normal matrices, potentially non-symmetric. Finally, we specialize it to matrices with eigenvalues located in a disk and show a provable speed-up compared to worst-case optimal algorithms. We illustrate our findings through benchmarks with a varying degree of mismatch with our assumptions.