# Accumulated Tikhonov Extragradient for Stochastic Games

- ID: 3167
- Canonical URL: https://synthcore.org/idea/3167/accumulated-tikhonov-extragradient-for-stochastic-games
- API JSON: https://synthcore.org/api/idea/3167.json
- API Markdown: https://synthcore.org/api/idea/3167.md
- Verification status: unverified
- Source: [arXiv:2609.04188](https://arxiv.org/abs/2609.04188)
- Category: optimization
- Solves: stability, speedup, generalization
- ML areas: optimizer, gan, training-dynamics
- Math tags: optimization, convex-analysis, stochastic-processes, dynamical-systems
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Treat a two-player neural game as a stochastic monotone operator problem and add an anchor regularizer that makes the current game strongly monotone during early training. Use stochastic extragradient steps inside geometrically decreasing regularization stages, retaining the accumulated anchor rather than resetting it; this should suppress rotational GAN dynamics while avoiding a permanent bias toward the initialization.

## Mathematical statement

The paper's VI is: find x* in a nonempty closed convex set X such that <F(x*), x-x*> >= 0 for every x in X, where F:X->R^n is the game/operator field. Its regularity assumptions are Lipschitz continuity, ||F(x)-F(z)|| <= L||x-z||, and monotonicity, <F(x)-F(z),x-z> >= mu||x-z||^2 with mu >= 0; mu>0 is strong monotonicity. The transferred regularization uses F_lambda(x)=F(x)+lambda(x-x_anchor), where lambda>0 is a stage coefficient and x_anchor is the anchor retained from the previous stage. Since <F_lambda(x)-F_lambda(z),x-z> >= (mu+lambda)||x-z||^2, the regularizer supplies an explicit strong-monotonicity margin even when the original stochastic game is only monotone. The paper's central stochastic residual complexity is O-tilde(L D_0/epsilon + sigma^2 epsilon^-2 (log(L D_0/epsilon))^3), where L is the Lipschitz constant, D_0 is the initial distance to a solution, sigma^2 bounds unbiased oracle variance, and epsilon is the target expected operator residual. The implementation uses this structure as a continuation optimizer: solve each regularized stage approximately, then reduce lambda geometrically.

## Key formulas

- $$x^{*}\in X\quad\text{such that}\quad\langle F(x^{*}),x-x^{*}\rangle\geq 0,\qquad\forall x\in X.$$
- $$\|F(x)-F(z)\|\leq L\|x-z\|,\qquad\langle F(x)-F(z),x-z\rangle\geq\mu\|x-z\|^{2}.$$
- $$F_{\lambda}(x)=F(x)+\lambda(x-x_{\mathrm{anchor}}),\qquad\langle F_{\lambda}(x)-F_{\lambda}(z),x-z\rangle\geq(\mu+\lambda)\|x-z\|^{2}.$$
- $$\widetilde{\mathcal{O}}\left(\frac{LD_{0}}{\varepsilon}+\frac{\sigma^{2}}{\varepsilon^{2}}\left(\log\frac{LD_{0}}{\varepsilon}\right)^{3}\right).$$

## Implementation notes

(1) Integration point: use this as an optimizer for a two-player GAN, actor-critic game, or other saddle-point network. Concatenate the trainable parameters into x=(theta,phi), and define the signed stochastic game operator F(x)=(grad_theta V(theta,phi), -grad_phi V(theta,phi)); exclude batch-normalization statistics and optimizer state from the regularizer. At the beginning of a stage, store x_anchor and choose lambda. Add lambda*(x-x_anchor) to the operator before each parameter update. (2) Pseudocode: initialize x_anchor=x and lambda=lambda_0. For each stage s: run K_s iterations; sample minibatch B1 and compute g1=F_hat(x;B1); set y=Proj_X(x-eta*(g1+lambda*(x-x_anchor))); sample independent minibatch B2 and compute g2=F_hat(y;B2); update x=Proj_X(x-eta*(g2+lambda*(y-x_anchor))). Maintain an exponential moving average r of ||x-y||/eta. When r <= c*lambda, set x_anchor=x, lambda=rho*lambda with rho in [0.2,0.8], and reset r. (3) Compute from the mathematics: lambda is the explicit strong-monotonicity margin. Estimate L with random finite-difference directional probes, estimate sigma^2 from repeated minibatch gradients at a fixed parameter vector, and use eta=0.1/(L_hat+lambda), clipped to a safe interval. The exact theorem constants are not assumed; compare equal stochastic oracle calls. (4) First experiment: train a 2D or 10D bilinear game V(theta,phi)=theta^T A phi, followed by a small MNIST GAN. Compare simultaneous Adam, standard extragradient, and AR at equal gradient evaluations. Measure equilibrium distance, operator residual, gradient variance, cycling amplitude, and FID. Success means faster residual reduction and visibly lower rotational cycling, with no degradation after lambda approaches zero. Ablate fixed lambda, resetting x_anchor each stage, and continuation without extragradient.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.