Average-case Acceleration for Bilinear Games and Normal Matrices
This work addresses a gap in average-case analysis for smooth games, which is incremental but important for applications like generative modeling and adversarial learning.
The paper tackled the challenge of developing average-case optimal first-order methods for smooth games, where asymmetry in second derivatives complicates analysis, by deriving optimal methods for zero-sum bilinear games and normal matrices, showing provable speed-ups compared to worst-case algorithms in specific cases.
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.