Some Methods of Speeding Up the Convergence of Iteration Methods

Consider minimizing a smooth function $f(\mathbf{x})$. Standard gradient descent updates the parameters by stepping opposite to the gradient:

$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)$

where $\alpha$ is the learning rate. On a perfectly round bowl (equal curvature in every direction), this works beautifully — each step heads straight for the bottom.

But most real problems are not round bowls. Loss surfaces in machine learning are typically elongated valleys: steep in some directions (high curvature) and gentle in others (low curvature). The ratio of the largest to smallest curvature is the condition number $\kappa = L / \mu$.

On such landscapes, gradient descent faces a dilemma: a learning rate large enough to make progress along the gentle direction overshoots across the steep direction, causing oscillation. A learning rate small enough to avoid oscillation makes progress painfully slow along the gentle direction.

The convergence rate of gradient descent on a strongly convex quadratic is $\rho_{\text{GD}} = \frac{\kappa - 1}{\kappa + 1}$. When $\kappa = 100$, this is $0.98$ — meaning each step reduces the error by only 2%. You need roughly $\kappa$ steps to halve the error.

Polyak's insight was beautifully simple: add a fraction of the previous update to the current one. Instead of deciding where to go based only on the slope right here, you also look at where you were already heading.

Think of it as giving the optimizer memory. Gradient descent is memoryless — it forgets its entire history at every step. Momentum gives it a one-step memory: "I was heading this way, so unless the gradient strongly disagrees, keep going."

When gradients consistently point in the same direction (along the valley floor), the momentum term accumulates and the effective step size grows — the optimizer accelerates. When gradients keep reversing sign (the zig-zag walls), the momentum term and the gradient partially cancel each other, dampening the oscillation automatically.

An equivalent and more common formulation uses a velocity variable $\mathbf{v}$:

$\mathbf{v}_{k+1} = \beta \mathbf{v}_k - \alpha \nabla f(\mathbf{x}_k)$ $\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{v}_{k+1}$

Here $\mathbf{v}$ is the velocity of the "heavy ball". At each step, the velocity decays by $\beta$ (friction) and gains a push from the negative gradient (gravity). The parameter update then simply follows the velocity.

This form makes the physics clearer: $\beta$ close to 1 means low friction (the ball keeps rolling a long time); $\beta = 0$ recovers vanilla gradient descent (no inertia at all).

Polyak's method is modeled on Newton's second law. A ball on a surface experiences gravity (the gradient) and friction (the decay $\beta$). The continuous-time equation is:

$\mathbf{x}''(t) + \gamma \mathbf{x}'(t) + \nabla f(\mathbf{x}(t)) = 0$

This is the equation of a damped harmonic oscillator. The $\gamma$ friction term prevents the ball from overshooting the minimum and oscillating forever. The key insight is that the second-order dynamics (acceleration, not just velocity) allow the system to use curvature information implicitly, even though we never compute the Hessian.

On a quadratic $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T A \mathbf{x}$, the eigenvalues of $A$ are the curvatures in each direction. Without momentum, convergence along each eigendirection proceeds independently at rate $|1 - \alpha \lambda_i|$. The optimal step size must compromise between the fastest ($\lambda_{\max} = L$) and slowest ($\lambda_{\min} = \mu$) directions.

With momentum, the convergence factor becomes $\frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1}$ — the square root transforms the condition number. This is the difference between $O(\kappa)$ and $O(\sqrt{\kappa})$ iterations: a quadratic-to-linear improvement in the dependence on problem difficulty.

Polyak derived the optimal hyperparameters for strongly convex quadratics. Given the smallest eigenvalue $\mu$ and largest eigenvalue $L$ of the Hessian:

$\alpha^* = \frac{4}{(\sqrt{L} + \sqrt{\mu})^2} \qquad \beta^* = \left(\frac{\sqrt{L} - \sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}}\right)^2$

In practice, $\mu$ and $L$ are unknown, so practitioners use the common heuristic $\beta = 0.9$ (sometimes 0.99). This works because most landscapes in deep learning are highly ill-conditioned ($\kappa \gg 1$), where $\beta^*$ approaches 1 anyway.

The learning rate $\alpha$ interacts with $\beta$: higher momentum allows a larger effective step size. A useful mental model is that momentum amplifies the learning rate by a factor of roughly $\frac{1}{1 - \beta}$: with $\beta = 0.9$, the effective learning rate is 10× the nominal rate.

There is another way to see the velocity form. Unrolling the recurrence $\mathbf{v}_{k+1} = \beta \mathbf{v}_k - \alpha \nabla f(\mathbf{x}_k)$ gives:

$\mathbf{v}_{k+1} = -\alpha \sum_{i=0}^{k} \beta^{k-i} \nabla f(\mathbf{x}_i)$

The velocity is an exponentially weighted sum of all past gradients, with recent gradients weighted most. This is an exponential moving average — the same tool used in signal processing to smooth noisy data.

This view explains why momentum helps with noisy (stochastic) gradients: the averaging smooths out the noise while preserving the consistent signal. In stochastic gradient descent, each mini-batch gradient is a noisy estimate; momentum effectively averages over multiple mini-batches.

Polyak's momentum is the seed from which the modern optimizer tree grew. The relationship is direct and traceable:

• Vanilla SGD: $\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)$ — no memory.
• SGD + Momentum (Polyak, 1964): adds $\beta(\mathbf{x}_k - \mathbf{x}_{k-1})$ — one-step memory.
• Nesterov Momentum (1983): evaluates gradient at $\mathbf{x}_k + \beta \mathbf{v}_k$ — "look before you leap."
• Adam (2014): momentum on both first moment ($\beta_1$) and second moment ($\beta_2$) of the gradient.

The entire trajectory from SGD to Adam is a sequence of increasingly sophisticated ways to use gradient history — and it all started with one extra term in Polyak's update rule.