Click here to flash read.
For min-max optimization and variational inequalities problems (VIP)
encountered in diverse machine learning tasks, Stochastic Extragradient (SEG)
and Stochastic Gradient Descent Ascent (SGDA) have emerged as preeminent
algorithms. Constant step-size variants of SEG/SGDA have gained popularity,
with appealing benefits such as easy tuning and rapid forgiveness of initial
conditions, but their convergence behaviors are more complicated even in
rudimentary bilinear models. Our work endeavors to elucidate and quantify the
probabilistic structures intrinsic to these algorithms. By recasting the
constant step-size SEG/SGDA as time-homogeneous Markov Chains, we establish a
first-of-its-kind Law of Large Numbers and a Central Limit Theorem,
demonstrating that the average iterate is asymptotically normal with a unique
invariant distribution for an extensive range of monotone and non-monotone
VIPs. Specializing to convex-concave min-max optimization, we characterize the
relationship between the step-size and the induced bias with respect to the
Von-Neumann's value. Finally, we establish that Richardson-Romberg
extrapolation can improve proximity of the average iterate to the global
solution for VIPs. Our probabilistic analysis, underpinned by experiments
corroborating our theoretical discoveries, harnesses techniques from
optimization, Markov chains, and operator theory.
No creative common's license