Interactive
Three ways to reach a saddle point
Minimizing over one variable while maximizing over another is what robust learning, adversarial training, and constrained problems all come down to — and the plain gradient method fails at it. This page races three methods to a saddle point under stochastic gradients and computes, exactly, how fast each one gets there and how much noise it lets through.
Start with Coupling dominates. Gradient descent-ascent spirals outward: the coupling term b·x·y acts as a pure rotation, and a gradient step on a rotation always lands a little farther from the center. Extragradient looks one step ahead before it moves and damps the rotation; SAPD extrapolates the dual gradient with momentum θ and does the same with one gradient of each kind per iteration instead of two.
Then drag the stepsize. Every rate ρ falls and every amplification J rises — the same speed–robustness trade-off that governs momentum methods, now for primal–dual dynamics. Raise the gradient noise and the runs stop converging and hover at a distance of about σ·J from the saddle, which is what J means. Turn the momentum θ down toward zero and SAPD degrades toward gradient descent-ascent.
Interactive · three ways to reach a saddle point
| Method | Rate ρ | Amplification J | RMS distance, last 80 steps |
|---|---|---|---|
| gradient descent-ascent | 1.031 (diverges) | ∞ | 776.632 |
| extragradient | 0.870 | 0.310 | 0.067 |
| SAPD | 0.881 | 0.355 | 0.072 |
ρ is the spectral radius of each method’s iteration matrix (per iteration; smaller is faster, and ρ ≥ 1 means the iterates spiral away). J is the root-mean-square distance to the saddle at stationarity when each gradient is corrupted by unit-variance noise — the H₂ norm, from the discrete Lyapunov equation — so the noisy run should hover near σ·J. Gradient descent-ascent sees the coupling b as a pure rotation and diverges once the stepsize exceeds 2μ/(μ² + b²); extragradient looks one step ahead and damps the rotation at the price of a second gradient per iteration; SAPD extrapolates the dual gradient with momentum θ and takes one gradient of each kind. Turn the stepsize up and every ρ falls while every J rises: the same speed–robustness trade-off as for momentum methods, here for primal–dual dynamics.
Reaching a saddle point is a question of damping a rotation; doing it fast and doing it quietly pull in opposite directions, and the frontier between them can be computed.
The methods and the trade-off are developed in SIAM J. Optim. 2024, J. Mach. Learn. Res. 2024, and NeurIPS 2022: the first introduces SAPD, characterizes the stepsizes and momentum for which it converges at a given rate, and shows that rate and robustness to gradient noise cannot be optimized together — the Pareto frontier between them; the second gives high-probability and risk-averse guarantees for a single run of SAPD rather than for the average run; the third extends the method to non-convex–concave problems. The wider thread is on the research page.
To reference this page:
@misc{gurbuzbalaban2026saddle,
title = {Three ways to reach a saddle point, interactively},
author = {G{\"u}rb{\"u}zbalaban, Mert},
year = {2026},
howpublished = {\url{https://mert-g.org/playground/saddle-point/}}
}