A Central Limit Theorem for Algorithmic Estimator of Saddle Point

Abstract: In this work, we study the asymptotic randomness of an algorithmic estimator of the saddle point of a globally convex-concave and locally strongly-convex strongly-concave objective. Specifically, we show that the averaged iterates of a Stochastic Extra-Gradient (SEG) method for a Saddle Point Problem (SPP) converges almost surely to the saddle point and follows a Central Limit Theorem (CLT) with optimal covariance under martingale-difference noise and the state(decision)-dependent Markov noise. To ensure the stability of the algorithm dynamics under the state-dependent Markov noise, we propose a variant of SEG with truncated varying sets. Interestingly, we show that a state-dependent Markovian data sequence can cause Stochastic Gradient Descent Ascent (SGDA) to diverge even if the target objective is strongly-convex strongly-concave. The main novelty of this work is establishing a CLT for SEG for a stochastic SPP, especially under sate-dependent Markov noise. This is the first step towards online inference of SPP with numerous potential applications including games, robust strategic classification, and reinforcement learning. We illustrate our results through numerical experiments.