△ Mechanism confirmed, baseline not beaten 2026

Tikhonov-Stabilized Stochastic Extragradient

Implementation & benchmark of arXiv:2607.11056 — Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems

Usefulness7/10

Difficulty4/10

Novelty6/10

Optimization Stability Accuracy Sample efficiency Optimizer Training dynamics Gan Rlhf Optimization Convex analysis Dynamical systems Stochastic processes

Source paper: Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems arXiv:2607.11056 ⓘ · analyzed Aug 30, 2026

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

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.

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}$$

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)$.

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

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significantly worse ✗

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 9/10

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.

Agent confidence: 9/10

Baseline: SEG: tail mean norm 0.4203, last norm 0.4628, tail mean step 0.2110 at eta=0.35, sigma=0.3
Idea: Tikhonov SEG (mu=0.2): tail mean norm 0.2795, last norm 0.3100, tail mean step 0.1729; deterministic rho=0.8664 versus baseline rho=0.9447
Math checks: Deterministic predicted/observed rho absolute error <=2.3e-16; stochastic predicted-versus-observed stationary mean-square relative error 3.4%-6.6%; exact mu=0 update difference 0

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.

How to run: python3 verify_tikhonov.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.11056) Sep 2, 2026

Significantly WORSE than the tuned baseline (+16.5%, p=0.0081, wins 0 / 8 paired seeds).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 7.235
Idea mean: 8.4309
Effect (Δ): 1.196 (+16.5%; negative = idea better)
Wins: 0 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±13.0%
Mechanism: Confirmed ✓
Practical effect: Hurts
Baseline tuning: swept over 6 configs

Limitations:

Only the built-in optimizer-appropriate tabular track was tested; no neural GAN or nonconvex two-player saddle benchmark was evaluated. Wall-clock efficiency was not separately measured, and the implementation uses two forward/backward passes plus a separately instantiated midpoint model per minibatch. The idea sweep used three paired learning-rate/mu configurations rather than a full Cartesian mu sweep.

How to run: python3 bench_experiment.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 10/10

Implemented Tikhonov-stabilized stochastic extragradient on the structurally appropriate tabular Friedman regression track with the shared mlp_tiny architecture and paired eight-seed evaluation. The mechanism signature showed smaller late update magnitude, but test MSE was significantly worse than tuned Adam: 8.4309 versus 7.2350, paired delta +1.1960, permutation p=0.0081. Thus the claimed benchmark improvement was not observed.

Baseline: Adam, best cfg lr=0.01 weight_decay=0.0: mean test MSE 7.234962344169617, std 0.7865574747580145
Idea: Tikhonov stochastic extragradient, best cfg lr=0.003 mu=0.03: mean test MSE 8.430913209915161, std 1.2543495879025823
Mechanism signature: Observed idea last-step norm mean 0.05618664820621863 and anchor distance mean 3.2610279242386264; baseline final parameter norm mean 9.708892703056335; confirmed=true, but this did not improve the independent task metric.
Paired delta: idea - baseline = +1.1959508657455444; 0/8 idea wins; permutation p=0.0081

Benchmark result