L4 Stochastic Gradient Descent and Newton Methods

Source: Lecture PDF. Page references use PDF page numbers.

Overview

• Stochastic gradient descent (SGD) trades exact gradients for cheaper, noisy updates.
• Newton’s method uses curvature to choose a step, with fast local convergence but greater cost and weaker guarantees far from a minimum.
• Quasi-Newton methods and coordinate rescaling aim to improve the geometry without computing an exact inverse Hessian each iteration.

The opening recap builds on L3 Line Search and Momentum. On p. 5, random restarts change the starting point of independent runs; momentum uses history within a run. Accumulated velocity may carry a trajectory through flat regions or shallow minima, but escape is not guaranteed. p. 6 motivates looking beyond local minima to saddle points in high-dimensional landscapes.

Why full gradients become expensive

Many training objectives average losses over $m$ examples:

$$f(w)=\frac{1}{m}\sum _{i=1}^m{h}_i(w),\nabla f(w)=\frac{1}{m}\sum _{i=1}^m\nabla h_i(w).$$

Every full-gradient update requires all $m$ component gradients. When $m$ is large, this can dominate the cost. See p. 9.

Logistic regression: the label convention changes

Unlike L2’s binary labels, L4 uses $y_i\in \{-1,+1\}$:

$$h_i(w)=\log \left(1+e^{-y_i{w}^T{x}_i}\right),\nabla h_i(w)=-\frac{y_i{x}_i}{1+e^{y_i{w}^T{x}_i}}.$$

The margin $y_i{w}^T{x}_i$ is positive when the score agrees with the label; increasing it reduces the loss. This is the same binary logistic loss after recoding $y_{\pm }=2y_{01}-1$. Source: loss, p. 7 and gradient, p. 8.

Stochastic and mini-batch gradient descent

At iteration $k$, sample a uniform random index $i_k$, or a random mini-batch $B_k$:

$${\hat{g}}_k=\nabla h_{i_k}(w_k)\text{or}{\hat{g}}_k=\frac{1}{|B_k|}\sum _{i\in B_k}\nabla h_i(w_k),w_{k+1}=w_k-{\alpha }_k{\hat{g}}_k.$$

For uniform sampling from the fixed dataset, conditional on the current iterate,

$$\mathbb{E}[{\hat{g}}_k\mid w_k]=\nabla f(w_k).$$

Thus ${\hat{g}}_k=\nabla f(w_k)+{\xi }_k$, with zero-mean sampling noise. The equality is exact for this sampling scheme; the lecture also discusses the population intuition of independent training examples. An individual sampled direction need not decrease the full objective. Source: mini-batches, p. 12 and average-direction intuition, p. 13.

Key takeaway: the noisy path may need more iterations, but each costs much less. Randomness can help move through some difficult regions, and a chosen learning-rate schedule avoids an expensive full-objective line search at every update. Compare total computation, not iteration counts alone.

Stopping with noisy gradients

A tiny gradient from one small batch does not reliably establish stationarity. p. 15 suggests estimating the gradient using a much larger sample and considering changes in parameters or objective values:

$$\Vert \frac{1}{R}\sum _{i\in S_R}\nabla h_i(w_k)\Vert \le \epsilon ,\Vert w_{k+1}-w_k\Vert \le \epsilon ,|f(w_{k+1})-f(w_k)|\le \epsilon .$$

These are diagnostics rather than interchangeable guarantees: tiny learning rates also produce tiny updates, and evaluating the full loss can be costly. Combine sustained evidence of little progress with a computational limit.

Newton’s method: root finding versus optimisation

For a scalar equation $r(w)=0$, replace $r$ by its tangent line and solve that line for its root:

$$0\approx r(w_k)+r^{\prime }(w_k)(w_{k+1}-w_k)⟹w_{k+1}=w_k-\frac{r(w_k)}{r^{\prime }(w_k)}.$$

Key takeaway: the tangent’s horizontal-axis intercept becomes the next iterate. To optimise $f$, apply root finding to $r=f^{\prime }$, giving $w_{k+1}=w_k-f^{\prime }(w_k)/f^{\prime \prime }(w_k)$. Solving $f(w)=0$ and minimising $f(w)$ are different tasks.

Worked example: computing $\sqrt{3}$

For the example introduced on p. 17, set $r(w)=w^2-3$. Then

$$w_{k+1}=\frac{1}{2}\left(w_k+\frac{3}{w_k}\right).$$

Starting from $w_0=2$ gives $w_1=1.75$ and $w_2\approx 1.732143$. Each step solves a local linear approximation to $r$, without needing a symbolic square-root formula.

Newton optimisation: minimise a local quadratic model

Let $g_k=\nabla f(w_k)$ and $Q_k={\nabla }^{2}f(w_k)$. Taylor’s approximation gives

$$q_k(p)=f(w_k)+g_k^{T}p+\frac{1}{2}{p}^T{Q}_{k}p.$$

Setting its gradient to zero yields

$$Q_k{p}_k=-g_k,p_k=-Q_k^{-1}{g}_k,w_{k+1}=w_k+p_k.$$

When $Q_k\succ 0$, this stationary point is the quadratic model’s unique minimiser. The pure Newton step uses ${\alpha }_k=1$ along $p_k$. In computation, solve the linear system rather than explicitly forming the inverse.

Key takeaway: the Hessian adjusts movement for curvature in different directions. Newton minimises a local quadratic model, which need not match the true function well far from the current point. This extends L1’s Taylor approximation.

Fast convergence is local

Near a minimiser $w^{\ast }$ with positive definite Hessian, Newton can converge quadratically under suitable smoothness assumptions (including a locally Lipschitz Hessian) and a sufficiently close starting point:

$$\Vert w_{k+1}-w^{\ast }\Vert \le C\Vert w_k-w^{\ast }{\Vert }^2.$$

This describes how quickly a small error shrinks; it is not a guarantee of reaching a minimum from any initial point.

Why Newton can fail

• Cost: a dense $n\times n$ Hessian requires $O(n^2)$ storage; a general dense factorisation/solve costs $O(n^3)$. See p. 24.
• Undefined step: the required second derivatives may not exist, or the Hessian may be singular.
• Wrong direction: an indefinite Hessian can produce an ascent direction.
• Poor initialisation: the local model may give unhelpful steps or cycling.

Key takeaway: the left example concerns root finding for $r(w)=w^3-2w+2$. Starting at $0$, Newton cycles $0\to 1\to 0$. The right diagram shows an optimisation step following an unsuitable quadratic model. Both illustrate why fast local behaviour does not imply global convergence.

When is Newton’s direction descent?

For $g_k\ne 0$ and $Q_k\succ 0$,

$$g_k^T{p}_k=-g_k^T{Q}_k^{-1}{g}_k<0.$$

Positive definiteness makes the inverse positive definite too. Without it, the sign is not assured. Source: p. 26.

Qualification to the slide: a twice-differentiable local minimum need only have a positive semidefinite Hessian. Positive definiteness is an additional condition, not automatic; $f(w)=w^4$ at $0$ is a simple counterexample.

Quasi-Newton methods and rescaling

p. 28 motivates an intermediate update:

$$w_{k+1}=w_k-{\alpha }_k{H}_k{g}_k.$$

Here $H_k$ approximates the inverse Hessian. The goal is a more useful direction than $-g_k$ at lower cost than an exact Newton step. If $H_k\succ 0$ and $g_k\ne 0$, then $-H_k{g}_k$ is descent. This lecture introduces the motivation; it does not yet derive a quasi-Newton update rule.

Key takeaway: elongated contours can make steepest descent zigzag. Rescaling coordinates can make the contours rounder and the optimisation easier, even though the underlying minimum is unchanged.

On p. 30, set $w=Au$ with invertible $A$ and define $g(u)=f(Au)$. Then $w^{\ast }=A{u}^{\ast }$ and $g(u^{\ast })=f(w^{\ast })$.

Short derivation of the connection: the chain rule gives ${\nabla }_{u}g(u)=A^T{\nabla }_{w}f(w)$. A gradient step in $u$, converted back to $w$, becomes

$$u_{k+1}=u_k-\alpha A^T\nabla f(w_k)⟹w_{k+1}=w_k-\alpha A{A}^T\nabla f(w_k).$$

So rescaling induces a matrix-scaled gradient step. Equivalent optimisation problems can have very different steepest-descent trajectories.

Important results

• Uniformly sampled component/mini-batch gradients are unbiased estimates of the full empirical gradient.
• SGD makes each update cheaper; a noisy gradient changes how we assess convergence.
• Newton root finding uses $r/r^{\prime }$; Newton optimisation uses $f^{\prime }/f^{\prime \prime }$ or solves $Q_k{p}_k=-g_k$.
• Positive definite curvature ensures Newton’s direction is descent; quadratic convergence needs local assumptions.
• Quasi-Newton methods seek useful curvature scaling at lower cost; rescaling explains why the geometry matters.