Unverified Re-invented 2026

Robust Polyak SGD

Implementation & benchmark of arXiv:2607.00207 — Homogenization of $\ell_2$-Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent

Usefulness8/10

Difficulty3/10

Novelty5/10

Optimization Stability Accuracy Sample efficiency Optimizer Training Optimization Dynamical systems Probability

Source paper: Homogenization of $\ell_2$-Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent arXiv:2607.00207 ⓘ · analyzed Aug 29, 2026

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

Idea description

Use a Polyak stepsize computed from the adversarial minibatch loss instead of a fixed learning rate or an inner exact line search. The paper’s dynamics indicate that adversarial SGD has state-dependent curvature and noise, and that Polyak control can avoid the non-monotone behavior caused by anisotropic covariance and ridge mismatch.

Formulas

$$\ell_\epsilon(w;x,y)=\max_{\|\delta\|_2\leq\epsilon}(y-w^\top(x+\delta))^2=(|y-w^\top x|+\epsilon\|w\|_2)^2.$$

$$F_t(w)=\frac{1}{B}\sum_{i=1}^{B}\ell_\epsilon(w;x_i,y_i),\qquad g_t=\nabla F_t(w_t).$$

$$\eta_t=\operatorname{clip}\!\left(\frac{F_t(w_t)-\widehat F_{\star,t}}{\|g_t\|_2^2+\tau},\eta_{\min},\eta_{\max}\right),\qquad w_{t+1}=w_t-\eta_t g_t.$$

$$\widehat F_{\star,t}=\min(\widehat F_{\star,t-1},\operatorname{EMA}_\beta[F_t])-c\,\operatorname{SE}_B(F_t).$$

Mathematical statement

For parameters w, sample (x,y), adversarial radius epsilon, and linear predictor f_w(x)=w^T x, define the residual r=y-w^T x. Maximizing squared error over an l2 perturbation gives the exact robust loss ell_epsilon(w;x,y)=(|r|+epsilon||w||_2)^2. For a minibatch of size B, F_t(w)=B^{-1} sum_i ell_epsilon(w;x_i,y_i), and g_t=gradient F_t(w_t). The Polyak update uses eta_t=(F_t(w_t)-F_star_hat,t)/(||g_t||_2^2+tau), where F_star_hat,t is a conservative estimate of the optimal robust loss and tau>0 prevents division by zero. Because the true optimum is unknown for neural networks, maintain F_star_hat,t as the minimum observed exponential-moving-average loss minus a safety margin proportional to minibatch standard error. Clip eta_t to an empirically chosen interval.

Implementation notes

Integrate this at the optimizer-update stage, after adversarial examples have been generated and before the parameter update. For each minibatch, generate x_adv with the existing PGD or single-step l2 attack, compute the robust loss F_t and gradient g_t, and retain per-example losses to estimate the standard error. Maintain loss_ema=beta*loss_ema+(1-beta)*F_t and set F_star_hat=min(F_star_hat,loss_ema)-c*SE, where SE is the batch standard deviation divided by sqrt(B). Compute eta=(loss_ema-F_star_hat)/(squared_norm(g)+tau), clamp it between eta_min and eta_max, and update parameters with theta=theta-eta*g. First evaluate pure Polyak SGD; then test Polyak scaling on Adam’s normalized direction d=m_hat/(sqrt(v_hat)+eps), using eta=(F-F_star_hat)/(g dot d+tau). The mathematical ingredients are the robust objective and Polyak ratio; beta, c, tau, and clipping limits are empirical. Use a small MLP and linear classifier on MNIST or CIFAR-10 with l2-PGD. Compare fixed-rate SGD, AdamW, and exact backtracking at equal gradient evaluations. Success means fewer robust-loss oscillations, faster robust-loss reduction at equal FLOPs, and equal or higher final PGD accuracy across seeds.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.