Stochastic Variance Reduction for Min-Max Optimization and Variational Inequalities

Ahmet Alacaoglu, Univ. of Wisconsin Madison
January 31, 2023 1:00 pm ESB 4133

Stochastic variance reduction techniques have been influential for developing algorithms for minimization problems in the last decade whereas their use in more general problem templates has been limited. This talk will present a first order algorithm with variance reduction to solve convex-concave finite sum min-max optimization problems. This method converges under the same set of assumptions as the deterministic full-batch extragradient algorithm and attains an optimal complexity bound, improving the results for existing algorithms. I will then describe the generalization of the same idea to different algorithmic templates and more general problem classes such as variational inequalities. I will conclude by preliminary results on the empirical merits of the proposed method.