Convergence of $ ext{log}(1/psilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis

Many algorithms struggle to efficiently solve large zero-sum games, especially when high accuracy is needed. This is because their performance is often analyzed in worst-case scenarios, which are unrealistic and can lead to overly pessimistic estimations. A key problem is dependence on “condition number” like quantities which can be exponentially large in game size.

This paper tackles these issues by employing “smoothed analysis,” a more realistic way to evaluate algorithms that considers small, random perturbations of the game. The authors show that several gradient-based algorithms (OGDA, EGDA, Iterative smoothing) have a polynomial smoothed complexity, meaning their number of iterations increases polynomially with game size, accuracy, and the magnitude of the perturbation. This implies they are practical even for high-accuracy solutions, unlike what worst-case analysis suggests. The study also connects convergence rate to the stability of the game’s equilibrium under perturbations.