Stochastic variance reduced extragradient methods for solving hierarchical variational inequalities
This work addresses a general optimization problem with hierarchical structure, impacting areas like minimax and Nash equilibrium, but it is incremental as it extends existing variance reduction techniques to this specific setting.
The paper tackles the problem of solving hierarchical variational inequalities with finite-sum smooth operators by introducing stochastic variance reduced extragradient methods, achieving proven convergence rates and complexity statements for the first time in both Euclidean and Bregman setups.
We are concerned with optimization in a broad sense through the lens of solving variational inequalities (VIs) -- a class of problems that are so general that they cover as particular cases minimization of functions, saddle-point (minimax) problems, Nash equilibrium problems, and many others. The key challenges in our problem formulation are the two-level hierarchical structure and finite-sum representation of the smooth operators in each level. For this setting, we are the first to prove convergence rates and complexity statements for variance-reduced stochastic algorithms approaching the solution of hierarchical VIs in Euclidean and Bregman setups.