# Tikhonov-Stabilized Stochastic Extragradient

- ID: 723
- Canonical URL: https://synthcore.org/idea/723/tikhonov-stabilized-stochastic-extragradient
- API JSON: https://synthcore.org/api/idea/723.json
- API Markdown: https://synthcore.org/api/idea/723.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.11056](https://arxiv.org/abs/2607.11056)
- Category: optimization
- Solves: stability, accuracy, sample-efficiency
- ML areas: optimizer, training-dynamics, gan, rlhf
- Math tags: optimization, convex-analysis, dynamical-systems, stochastic-processes
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace the raw stochastic saddle objective by a strongly convex-strongly concave, quadratically anchored objective before applying stochastic extragradient. For a generator-discriminator or policy-rewarder game, anchor the minimizing and maximizing parameter vectors to reference parameters with opposite signs, suppressing persistent stochastic rotations and improving the quality of the final iterate.

## Mathematical statement

The paper studies the stochastic convex-concave problem \(\min_{x\in\mathcal X}\max_{y\in\mathcal Y}F(x,y)\), where \(F(x,y)=\mathbb E_\zeta[f(x,y;\zeta)]\), \(x\) is the minimizing variable, \(y\) is the maximizing variable, and stochastic first-order oracles are unbiased with bounded variance. Introduce reference points \(x_0\) and \(y_0\), perturbation strength \(\mu>0\), and the regularized game \(F_\mu(x,y)=F(x,y)+\frac{\mu}{2}\|x-x_0\|^2-\frac{\mu}{2}\|y-y_0\|^2\). The added terms make \(F_\mu\) \(\mu\)-strongly convex in \(x\) and \(\mu\)-strongly concave in \(y\), yielding a unique regularized saddle point \((x_\mu^*,y_\mu^*)\) under standard closed-convex feasibility assumptions. Its saddle operator is \(G_\mu(x,y)=[\nabla_xF(x,y)+\mu(x-x_0),-\nabla_yF(x,y)+\mu(y-y_0)]\). The paper establishes an \(\mathcal O(T^{-1/4})\) last-iterate restricted primal-dual-gap rate for the fixed-horizon perturbed stochastic extragradient method; on compact domains this is the ordinary primal-dual gap \(\operatorname{Gap}(x,y)=\max_{v\in\mathcal Y}F(x,v)-\min_{u\in\mathcal X}F(u,y)\).

## Key formulas

- $$\min_{x\in\mathcal X}\max_{y\in\mathcal Y}F(x,y),\qquad F(x,y)=\mathbb E_{\zeta}[f(x,y;\zeta)]$$
- $$F_\mu(x,y)=F(x,y)+\frac{\mu}{2}\lVert x-x_0\rVert^2-\frac{\mu}{2}\lVert y-y_0\rVert^2$$
- $$G_\mu(x,y)=\begin{bmatrix}\nabla_xF(x,y)+\mu(x-x_0)\\-\nabla_yF(x,y)+\mu(y-y_0)\end{bmatrix}$$
- $$\begin{aligned}x_{t+\frac12}&=\Pi_{\mathcal X}\!\left[x_t-\eta\left(g_x(x_t,y_t;\zeta_t)+\mu(x_t-x_0)\right)\right],\\y_{t+\frac12}&=\Pi_{\mathcal Y}\!\left[y_t+\eta\left(g_y(x_t,y_t;\zeta_t)-\mu(y_t-y_0)\right)\right],\\x_{t+1}&=\Pi_{\mathcal X}\!\left[x_t-\eta\left(g_x(x_{t+\frac12},y_{t+\frac12};\zeta'_t)+\mu(x_{t+\frac12}-x_0)\right)\right],\\y_{t+1}&=\Pi_{\mathcal Y}\!\left[y_t+\eta\left(g_y(x_{t+\frac12},y_{t+\frac12};\zeta'_t)-\mu(y_{t+\frac12}-y_0)\right)\right].\end{aligned}$$

## Implementation notes

1. Integration point: modify the optimizer step for any two-player neural game, such as a GAN generator-discriminator pair, adversarial policy-versus-rewarder training, or a min-max robustness objective. Let \(x\) be the minimizing network parameters and \(y\) the maximizing network parameters. Store frozen reference copies \(x_0,y_0\), initially equal to the parameters at the beginning of the training window. Add the quadratic penalties directly to gradients if memory is important; for unconstrained neural parameters, the projections \(\Pi_{\mathcal X}\) and \(\Pi_{\mathcal Y}\) are identity maps. 2. Pseudocode: sample minibatches \(\zeta_t,\zeta'_t\); compute \(g_x,g_y\) at \((x_t,y_t)\); set \(x_h=x_t-\eta[g_x+\mu(x_t-x_0)]\) and \(y_h=y_t+\eta[g_y-\mu(y_t-y_0)]\); recompute gradients at \((x_h,y_h)\) using the second minibatch; update \(x\leftarrow x_t-\eta[g_x^h+\mu(x_h-x_0)]\) and \(y\leftarrow y_t+\eta[g_y^h-\mu(y_h-y_0)]\). Detach the midpoint parameters from the first gradient graph. 3. Mathematical quantities versus estimates: \(\mu\) is the designed strong-convexity/concavity coefficient, while \(g_x,g_y\) are minibatch estimates of \(\nabla_xF,\nabla_yF\); no Hessians are required. For a known horizon \(T\), initialize \(\mu=cT^{-1/4}\) after parameter normalization and tune \(c\) over \(\{0.01,0.03,0.1,0.3\}\); tune \(\eta\) under the same gradient-stability range as baseline extragradient. 4. First experiment: train small DCGANs on CIFAR-10 or a two-dimensional bilinear game with additive minibatch noise, comparing Adam, stochastic extragradient, and the anchored method at equal gradient evaluations. Record final-iterate losses, gradient norms, parameter oscillation \(\|\theta_{t+1}-\theta_t\|\), and a held-out game residual. Success means lower variance and lower final game residual, fewer divergence events, and improved FID or robust reward at equal compute; on the bilinear test, the last-iterate norm should decrease rather than orbit around the saddle.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built and numerically verified Tikhonov-stabilized stochastic extragradient for a noisy bilinear saddle game. The deterministic contraction ratio matched the spectral prediction to below 3e-16 across all anchor strengths; the stochastic stationary mean-square radius decreased monotonically with μ and agreed with the corrected Lyapunov prediction within 3.4–6.6%. The μ=0 same-noise identity was exact, while at σ=0.3 and μ=0.2 the anchored method reduced tail mean norm from 0.4203 to 0.2795 and mean step size from 0.2110 to 0.1729 versus baseline SEG.

### Mechanism check

- Verdict: Built and numerically verified Tikhonov-stabilized stochastic extragradient for a noisy bilinear saddle game. The deterministic contraction ratio matched the spectral prediction to below 3e-16 across all anchor strengths; the stochastic stationary mean-square radius decreased monotonically with μ and agreed with the corrected Lyapunov prediction within 3.4–6.6%. The μ=0 same-noise identity was exact, while at σ=0.3 and μ=0.2 the anchored method reduced tail mean norm from 0.4203 to 0.2795 and mean step size from 0.2110 to 0.1729 versus baseline SEG.
- Confidence: 9/10
- Limitations: Only a two-dimensional bilinear game was tested, with the reference point equal to the true saddle and fixed step size; no neural GAN, nonconvex game, constrained projection, adaptive reference window, or wall-clock/FLOP comparison was evaluated.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/307/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/307/bench_report.json)
- [report.md](https://synthcore.org/code/307/report.md)
- [report_bench_2026-08-31T004910.md](https://synthcore.org/code/307/report_bench_2026-08-31T004910.md)
- [results.json](https://synthcore.org/code/307/results.json)
- [verify_tikhonov.py](https://synthcore.org/code/307/verify_tikhonov.py)
- [Download all files as ZIP](https://synthcore.org/download/307)

## Disclaimer

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