Speed, robustness and risk

Momentum methods converge faster than gradient descent. When the gradients are noisy, they also amplify the noise more. How much more depends on two choices: how the noise is modelled, and what is measured. This note gives three precise answers for the simplest problem where everything has a closed form, a quadratic:

• an average-case answer, the $H_2$ norm;
• a worst-case answer, the $H_\infty$ norm;
• a risk-sensitive answer that sits between the two.

The playground further down lets you move a tuning around and watch all three change.

There are two punchlines. The first is an identity: the risk-sensitive measure is finite exactly up to a threshold $\theta^\star = d/H_\infty^2$, which is set by the worst-case gain. The second is a tuning: RS-HB, a heavy-ball method I introduced in Gürbüzbalaban, Math. Oper. Res. 2025. It converges faster than Nesterov's method and is exactly as robust to worst-case noise as any method in the family can be.

1. The problem and the methods

We minimize the quadratic

where $Q$ is symmetric with eigenvalues $\mu = \lambda_1 \le \dots \le \lambda_d = L$, $\mu > 0$, and $\kappa = L/\mu$ is the condition number. The minimizer is $x^\star = 0$, and the suboptimality is $f(x) - f^\star = \tfrac12 x^\top Q x$.

The generalized momentum method (GMM) has three parameters: a stepsize $\alpha > 0$ and two momentum parameters $\beta, \nu \ge 0$. It uses the gradient only through a noisy estimate $\nabla f(y_k) + w_k$:

The vector $w_k$ is the gradient error at step $k$. The family contains the classical methods as special cases:

• $\beta = \nu = 0$ is gradient descent (GD);
• $\nu = 0$ is Polyak's heavy ball (HB);
• $\nu = \beta$ is Nesterov's accelerated gradient (NAG);
• a particular choice with $\nu \ne \beta$ is the triple momentum method (TMM).

The playground uses $d = 2$, $Q = \mathrm{diag}(\mu, L)$ and $\mu = 1$. Little is lost by this simplification. The worst-case gain and the threshold $\theta^\star$ depend only on the two extreme eigenvalues, whatever $d$ is. For the average-case and risk measures, each interior eigenvalue only adds one more term of the same form.

2. Speed

Without noise ($w_k = 0$), the iterates converge to $x^\star$ linearly. In the eigenbasis of $Q$, each coordinate follows its own scalar recursion. For the coordinate along eigenvalue $\lambda$, that recursion has the characteristic polynomial

The rate $\rho$ is the largest modulus of a root of these polynomials, taken over the eigenvalues of $Q$. The error then behaves like $\rho^k$, up to a polynomial factor when two roots coincide. The tuning is stable when $\rho < 1$.

Rates close to $1$ are hard to compare by eye, so I measure speed instead by

which is roughly the number of iterations needed to cut the error by a factor of $e$ (since $\rho^s \approx e^{-1}$). The fastest tunings of each classical method are as follows:

3. How noise enters: one curve per direction

Now switch the noise back on. Along an eigenvector $u_i$ of $Q$ with eigenvalue $\lambda = \lambda_i$, the coordinate $x^{(i)}_k = u_i^\top x_k$ obeys

This is a linear, time-invariant filter, so it is natural to look at it frequency by frequency. I take the output to be $z^{(i)}_k = \sqrt{\lambda/2}\; x^{(i)}_k$, because this choice gives

The transfer function from the noise $w^{(i)}$ to the output $z^{(i)}$ is then

Its modulus has a concrete meaning. Feed in the error $w^{(i)}_k = \cos(\omega k)$. Once the transients have died out, $z^{(i)}_k$ is a cosine of the same frequency $\omega$ with amplitude $|G_\lambda(e^{i\omega})|$. So $|G_\lambda(e^{i\omega})|^2$ is the factor by which the algorithm multiplies the power of the noise at frequency $\omega$ along that direction. Panel A of the playground plots this gain curve for $\lambda = \mu$ and $\lambda = L$ over $\omega \in [0, \pi]$; the curve is symmetric in $\omega$, so the other half adds nothing.

Two frequencies have a plain meaning:

• $\omega = 0$ is a constant error, that is, a bias;
• $\omega = \pi$ is an error that flips sign at every step.

At $\omega = 0$ the gain does not depend on the tuning at all. Since $1 - b_\lambda + c_\lambda = \alpha\lambda$,

There is a reason that needs no algebra. A constant error $w$ moves the fixed point of every such method to the point where $\lambda x + w = 0$, which is the minimizer of the perturbed problem. The suboptimality there is $w^2/(2\lambda)$, and no choice of parameters can change it. Keep the number $1/(2\mu)$ in mind: it will come back as a floor.

4. Three ways to measure noise amplification

Each of the three measures below is a norm of the same gain curves. They differ in what they assume about $w_k$.

Average case: the $H_2$ norm

Suppose the errors are i.i.d. Gaussian, $w_k \sim \mathcal N\big(0, \tfrac{\sigma^2}{d} I_d\big)$, so that $\mathbb E\|w_k\|^2 = \sigma^2$. Then the iterates do not converge. Instead they settle into a stationary distribution around $x^\star$. White noise has the same power at every frequency, so the output power is the average of the gain curve:

The playground reports $J = \|G\|_{H_2}^2$, the area under the gain curves. Up to normalization, this is the noise amplification studied in Aybat, Fallah, Gürbüzbalaban and Ozdaglar, SIAM J. Optim. 2020.

Worst case: the $H_\infty$ norm

Now let the errors be deterministic and chosen by an adversary who knows the tuning. The only constraint is finite energy, $\|w\|^2 = \sum_{k \ge 0} \|w_k\|^2 < \infty$. Start the method at the optimum, $x_0 = x_{-1} = x^\star$, so that all of the suboptimality is caused by the noise. The robustness of the tuning is the worst ratio of total damage to the energy spent:

$H_\infty$ is the induced $\ell_2$ gain of the system from the noise $w$ to the output $z$. By Parseval's identity it equals the peak of the gain curves:

Gürbüzbalaban, Math. Oper. Res. 2025 gives this maximum in closed form for every GMM tuning, and shows that only the two extreme eigenvalues $\mu$ and $L$ can attain it. There is an equivalent reading that does not mention frequencies. $H_\infty^2$ is the smallest constant $c^2$ such that

holds for every horizon $K$ and every sequence of errors, where $F_0$ depends only on the initialization. Dividing by $K$ turns this into a $1/K$ bound for the averaged iterate, with the contributions of the initialization and of the noise kept separate.

What does the worst noise look like? The supremum is not attained, but it is approached by a decaying cosine,

where $u_\star$ is the eigenvector and $\omega_\star$ the frequency at which the peak occurs. In other words, the adversary puts all of its energy where the filter resonates. For the named tunings on this page, the peak sits at one of the two ends of the frequency range:

• For the robust tunings, the peak is at $\omega_\star = 0$ along the flattest direction ($\lambda = \mu$). The worst error is a slowly fading bias.
• For Polyak's heavy ball and the fastest GD, the peak is at $\omega_\star = \pi$ along the steepest direction ($\lambda = L$). The worst error flips sign at every step. For these tunings, the roots for that mode lie on the negative real axis, so the mode itself alternates in sign and resonates with such an error.

Interior peaks also occur. For example, heavy ball with $\alpha = 1/L$ and $\beta = 0.95$ peaks at $\omega_\star \approx 1.06$; try it.

The floor. Since $|G_\mu(1)|^2 = 1/(2\mu)$ for every tuning, the peak can never be lower than that:

Several tunings attain this floor: GD with $\alpha = 1/L$, Nesterov's method, RS-GD and RS-HB. Polyak's heavy ball and the fastest GD have $H_\infty^2 = \kappa/(2\mu)$, which is $\kappa$ times the floor. In panel B, the "Worst case" axis shows $H_\infty^2$ divided by the floor, so the floor is $1$.

In between: the risk-sensitive index

Go back to random noise, but now care about rare bad runs, not only about the mean. Let

be the suboptimality accumulated up to step $K$. For a risk-aversion parameter $\theta > 0$, the risk-sensitive index is

Two remarks explain this definition.

• It is an entropic risk. The quantity $\tfrac1t \log \mathbb E\, e^{tX}$ is the entropic risk of a random cost $X$ at aversion $t$. Because of the exponential, large values of $X$ weigh more than their probability alone would suggest. As $t$ increases, the entropic risk moves from the mean of $X$ (as $t \to 0$) toward its essential supremum (as $t \to \infty$). Here it is applied to the accumulated cost and normalized per step.
• The normalization by $2\sigma^2$ makes $\theta$ independent of the noise level. $S_K$ scales like $\sigma^2$, so the place where $R(\theta)$ becomes infinite does not depend on $\sigma^2$.

Expanding $\log \mathbb E\, e^{tX} = t\,\mathbb E X + \tfrac{t^2}{2}\mathrm{Var}\,X + O(t^3)$ shows what $\theta$ adds to the mean:

So $R(0)$ is the average-case answer from the $H_2$ subsection, and the first correction is the long-run variance of the accumulated cost. I call $R(\theta) - R(0)$ the risk premium.

For quadratics with Gaussian noise, Gürbüzbalaban, Syed and Aybat, J. Nonlinear Var. Anal. 2026 compute $R(\theta)$ exactly. The original characterization is a $2d \times 2d$ Riccati equation. The paper decouples it into $d$ equations of size $2 \times 2$, each solvable by hand, and gives an equivalent integral form over frequencies:

where

The wall. The integral form shows why $R(\theta)$ breaks down at $\theta^\star$. The logarithm requires $|G|^2 < d/\theta$ at every frequency; in words, the gain curves must stay below the horizontal line at height $d/\theta$. Raising $\theta$ lowers that line. The moment the line touches the peak $H_\infty^2$, the integral diverges and the risk becomes infinite. So the worst-case gain sets the budget of risk aversion a tuning can afford. Panel A draws the line $d/\theta$, and panel C draws $R(\theta)$ up to the wall.

What the wall means for tails. The same paper proves a large-deviation principle for the time-averaged suboptimality:

Because $R$ is finite exactly up to $\theta^\star$, the ratio $I(s)/s$ tends to $\theta^\star/(2\sigma^2)$ as $s \to \infty$. Large values of the averaged suboptimality are therefore exponentially unlikely, and $\theta^\star$ is their decay rate. In this sense, a smaller $H_\infty$ means lighter tails. On the test problem ($\kappa = 100$, $d = 2$, $\mu = 1$), the floor is $H_\infty^2 = 1/2$. Every tuning at the floor has $\theta^\star = 4$, while Polyak's heavy ball and the fastest GD have $\theta^\star = 0.04$.

5. RS-HB: fast and optimally robust

The table in section 2 suggests a trade-off: Polyak's heavy ball is the fastest, but it is also the most fragile. RS-HB, from Gürbüzbalaban, Math. Oper. Res. 2025 (Proposition 4.3), shows that much of this speed can be kept at the robustness floor. It is a heavy-ball method ($\nu = 0$) with

The name stands for robustly stable heavy ball, after the paper's title. The paper proves two things about this tuning:

• $H_\infty^2 = 1/(2\mu)$, the floor;
• its rate is $\rho = 1 - \sqrt{2}/\sqrt{\kappa} + O(1/\kappa)$.

Nesterov's rate is $1 - 1/\sqrt\kappa$, so for large $\kappa$, RS-HB needs about $1/\sqrt2$ as many iterations at the same worst-case robustness. At $\kappa = 100$, $a = 1.324$ and RS-HB needs 7.55 iterations per $e$-fold, against Nesterov's 10. For comparison, the family $\alpha = a^2/L$, $\beta = (1 - a/\sqrt\kappa)^2$ gives $\rho = 1 - 1/\sqrt\kappa$ at $a = 1$, and Polyak's tuning is close to $a = 2$.

RS-HB does not win on every measure. Two caveats are worth stating:

• It is not the fastest tuning at the floor. A numerical search over all three parameters finds tunings at the floor with about 6.1 iterations per $e$-fold. Those tunings have no closed form; RS-HB is the explicit one. Panel B shows the whole frontier.
• Its average-case cost is higher than Nesterov's. At $\kappa = 100$ the two have the same $H_\infty$, but RS-HB's $J$ is larger, 0.053 against 0.018. Its risk at $\theta = 2$ is also larger, 0.030 against 0.011. The two measures rank these tunings differently, which is the reason for having more than one.

For $\kappa < 32$, outside the range of the proposition, the playground uses $a = 1$.

6. The playground

At the top of the playground you choose the condition number and a named tuning. Below that, sliders set $\alpha L$, $\beta$ and $\nu$, with a choice of family: $\nu = 0$ (heavy ball), $\nu = \beta$ (Nesterov-type), or free $\nu$. Further sliders set the noise level $\sigma^2$ and the risk aversion $\theta$. The red stop on the $\theta$ slider marks the current tuning's wall $\theta^\star$. The readouts underneath are the quantities defined above.

• Panel A plots the gain curves $|G_\mu|^2$ and $|G_L|^2$ on a log scale.
  • Their mean over frequency is $J$, and their peak is $H_\infty^2$.
  • The dashed curves are the tilted gains $-\tfrac{d}{\theta}\log\big(1 - \tfrac{\theta}{d}|G|^2\big)$. Their mean over frequency, summed over the two modes and multiplied by $\sigma^2/d$, is $R(\theta)$.
  • The tilted curves blow up where the solid curves meet the line $d/\theta$.
  • The inset shows the roots of the two characteristic polynomials inside the unit circle. A root close to the circle produces a sharp peak.
• Panel B is the speed–risk map. The horizontal axis is speed, $s$. The vertical axis is one of three measures: $H_\infty^2$ divided by the floor ("Worst case"), $J$ ("Average"), or $R(2)$ ("Risk, θ = 2"). Each curve is a frontier: the smallest value of the measure that one family (GD, heavy ball, Nesterov-type, or all of GMM) can reach at a given speed. The frontiers were computed with the paper's solver. You can drag the ring along a frontier, and the sliders follow.
• Panel C is the risk budget: $R(\theta)$ from small $\theta$ up to the wall, with the risk-neutral level $R(0)$ marked.

7. What to try

1. RS-HB against Nesterov. The page opens on RS-HB at $\kappa = 100$; now press Nesterov. In panel A, both $\lambda = \mu$ curves peak on the floor at $\omega = 0$, so both tunings have the wall $\theta^\star = 4$. The difference is the $\lambda = L$ curve. RS-HB's has a bump near $\omega = \pi/2$, about half as high as the floor, and Nesterov's does not; that bump accounts for most of RS-HB's larger $J$. In exchange, RS-HB needs 7.6 iterations per $e$-fold, against Nesterov's 10.
2. Polyak's heavy ball. Press HB (fastest). It needs 5.5 iterations per $e$-fold, but the $\lambda = L$ curve now peaks at $\omega = \pi$, at 100 times the floor. The wall drops to $0.04$, and at the default $\theta = 2$ the risk is infinite.
3. Walk along a frontier. In panel B, switch between Worst case, Average and Risk, θ = 2, and drag the ring along a frontier. The all GMM frontier stays at the floor down to about 6 iterations per $e$-fold, then rises steeply: the last bit of speed costs a factor of $\kappa$ in worst-case damage.
4. Find the wall. Raise $\theta$ until its slider reaches the red stop. In panel A, the line $d/\theta$ comes down to meet the peak, and the dashed curves blow up there.
5. An interior resonance. Choose ν = 0, set $\alpha L = 1$ and $\beta = 0.95$. The peak moves to an interior frequency, and the roots in the inset approach the unit circle.

What this page does not show

Everything above is exact, but only for quadratics with Gaussian noise. The papers go further:

• For smooth, strongly convex functions, the closed forms become bounds certified by small matrix inequalities.
• The JNVA paper treats biased noise and gives finite-time, high-probability guarantees.
• Can and Gürbüzbalaban design risk-averse tunings based on entropic risk and the entropic value at risk.