Skip to main content

Conditioning and gradient descent

Gradient descent on a quadratic bowl splits into one simple race per eigenvalue. Derive the largest safe step, the best fixed step and its rate (kappa - 1)/(kappa + 1), and see why rescaling the features turns a slow zigzag into one straight step.
M03.8.4L2 Intermediate25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: M03.8.3 Ill-conditioning in data M03.4 Positive definite matrices and quadratic forms

What you will be able to do
  • Derive that gradient descent on f(x) = x-transpose S x / 2 multiplies each eigen-coordinate by 1 - eta lambda_i per step.
  • State and prove the stability condition eta < 2 / lambda_max.
  • Derive the best fixed step 2 / (lambda_min + lambda_max) and its rate (kappa - 1) / (kappa + 1), and estimate the number of steps it needs.
  • Explain why rescaling the features is a form of preconditioning, and when it is not enough.

The question

Gradient descent with its best fixed step needs 20 steps to cut the error of the running bowl \({2x^2 + 2xy + 2y^2}\) a million-fold. Measure one feature in different units, so that the bowl becomes long and thin, and the same method needs 62 steps, or 691, or more. Nothing about the minimum has changed. What sets the speed, and how do we get it back?

From the last lesson

1. Which cause of ill-conditioning does standardising the features cure?

Show answer

Features on very different scales or in different units. It does not cure features that nearly repeat one another.

2. What is \({\kappa(\mat{A}\T\mat{A} + \alpha\mat{I})}\)?

Show answer

\({(\sigma_1^2 + \alpha)/(\sigma_n^2 + \alpha)}\).

Intuition

Take the bowl \({f(\vect{x}) = \tfrac12\vect{x}\T\mat{S}\vect{x}}\) with the running symmetric matrix \(\mat{S}\), rows \({(2, 1)}\) and \({(1, 2)}\). Its eigenvectors \({\vect{q}_1 = (1, 1)/\sqrt2}\) and \({\vect{q}_2 = (1, -1)/\sqrt2}\) are the axes of the bowl, with curvatures \({\lambda_1 = 3}\) and \({\lambda_2 = 1}\).

Two panels. Left, titled Steps with eta equals 0.3: reddish-purple elliptical contours of the bowl, tilted, with two pale orange lines along the eigenvectors, labelled q1: lambda 1 equals 3 on the steep diagonal and q2: lambda 2 equals 1 on the flat one. Green gradient-descent iterates start at a hollow dot x0 equals (2, 0), jump almost onto the flat axis in one step, then creep along it to the centre. Right, titled Two races, one per eigenvalue: a log-scale plot of the size of each eigen-coordinate against the step t from 0 to 8. The orange line along q1 drops steeply, times 0.1 per step, from about 1 to about 10 to the minus 8; the green line along q2 falls gently, times 0.7 per step.
M03.8.4-F1

Gradient descent with step \({\eta = 0.3}\) on the running bowl. Along the steep axis the error shrinks tenfold each step; along the flat axis only by 0.7. The flat axis decides the speed.

Seen in the bowl’s own axes, gradient descent is not one process but two, one per eigenvector, and the two never interfere. Each is shrunk by its own fixed factor at every step. The steep direction wants a small step, or it overshoots; the flat direction wants a large one, or it crawls. One step size has to serve both, and the ratio of the two curvatures, the condition number, decides how badly they disagree.

Build it up

Step 1. The update. The gradient of \(f\) is \(\mat{S}\vect{x}\) (M04.10 and M03.4.4), so a step of size \(\eta\) is

\[ \vect{x}_{t+1} = \vect{x}_t - \eta\,\mat{S}\vect{x}_t = (\mat{I} - \eta\mat{S})\,\vect{x}_t . \]

The minimum is at \(\vect{0}\), so \(\vect{x}_t\) is also the error.

Step 2. Change to eigen-coordinates. Write \({\mat{S} = \mat{Q}\mat{\Lambda}\mat{Q}\T}\) and \({\vect{y}_t = \mat{Q}\T\vect{x}_t}\), the coordinates of \(\vect{x}_t\) along \(\vect{q}_1, \vect{q}_2\). Multiply the update by \(\mat{Q}\T\) and use \({\mat{Q}\T\mat{Q} = \mat{I}}\):

\[ \begin{aligned} \vect{y}_{t+1} &= \mat{Q}\T(\mat{I} - \eta\,\mat{Q}\mat{\Lambda}\mat{Q}\T)\,\mat{Q}\vect{y}_t \\ &= (\mat{I} - \eta\mat{\Lambda})\,\vect{y}_t . \end{aligned} \]

Step 3. One race per eigenvalue. \({\mat{I} - \eta\mat{\Lambda}}\) is diagonal, so each coordinate is simply multiplied by its own number:

\[ \begin{aligned} y_{i,t+1} &= (1 - \eta\lambda_i)\,y_{i,t}, \\ y_{i,t} &= (1 - \eta\lambda_i)^t\,y_{i,0} . \end{aligned} \]

With \({\eta = 0.3}\) the factors are \({1 - 0.9 = 0.1}\) and \({1 - 0.3 = 0.7}\), the two slopes in the figure.

Step 4. Plot the factors against the step size. Each factor \({\abs{1 - \eta\lambda_i}}\) falls to 0 at \({\eta = 1/\lambda_i}\) and rises again. The error shrinks only while every factor is below 1, and it shrinks at the pace of the largest.

A graph of the factor per step against the step size eta from 0 to 0.85. A sky-blue line, the absolute value of 1 minus eta, for the flat direction, falls slowly from 1. An orange V-shaped line, the absolute value of 1 minus 3 eta, for the steep direction, falls to 0 at one third and rises again. The larger of the two, shaded green below, is lowest where they cross, at a green dot labelled best eta star equals 0.5, factor 0.5. A horizontal reddish-purple line at 1 and a dotted vertical line at two thirds are labelled eta equals 2 over lambda max equals 2 over 3: no longer shrinks.
M03.8.4-F2

The factor for each eigenvalue of the running bowl, and their maximum. The best step balances the two at \({\eta^* = 0.5}\); beyond \({\eta = 2/3}\) the steep direction grows.

The formal statement

NoteTheorem: gradient descent on a quadratic

Let \(\mat{S}\) be symmetric positive definite with eigenvalues \(\lambda_{\max} = \lambda_1 \ge \dots \ge \lambda_n = \lambda_{\min} > 0\), and \({\kappa = \lambda_{\max}/\lambda_{\min}}\). Gradient descent on \({f(\vect{x}) = \tfrac12\vect{x}\T\mat{S}\vect{x}}\) with a fixed step \({\eta > 0}\) satisfies

\[ \norm{\vect{x}_t} \le \Big(\max_i \abs{1 - \eta\lambda_i}\Big)^t\,\norm{\vect{x}_0} . \]

  1. It converges from every start exactly when \({\eta < 2/\lambda_{\max}}\).
  2. The best fixed step is \({\eta^* = 2/(\lambda_{\min} + \lambda_{\max})}\), with factor \({(\kappa - 1)/(\kappa + 1)}\).

The bound. \(\mat{Q}\) keeps lengths, so \({\norm{\vect{x}_t} = \norm{\vect{y}_t}}\). Each coordinate of \(\vect{y}_t\) is that of \(\vect{y}_0\) times \({(1 - \eta\lambda_i)^t}\), which is at most the largest factor to the power \(t\) in size. Square, add and take the root.

Part 1. Since every \({\lambda_i > 0}\), each factor satisfies \({1 - \eta\lambda_i < 1}\). It is above \({-1}\) exactly when \({\eta\lambda_i < 2}\). The hardest case is \(\lambda_{\max}\), so all factors lie strictly between \({-1}\) and \(1\) exactly when \({\eta < 2/\lambda_{\max}}\). If instead \({\eta \ge 2/\lambda_{\max}}\), a start along \(\vect{q}_1\) keeps or grows its size forever.

Part 2. For \(\lambda\) between \(\lambda_{\min}\) and \(\lambda_{\max}\), the function \({\abs{1 - \eta\lambda}}\) is largest at one of the two ends, so the speed is set by \({\max(\abs{1 - \eta\lambda_{\min}}, \abs{1 - \eta\lambda_{\max}})}\). Below the step where the two meet, the first is the larger, and raising \(\eta\) shrinks it; above that step, the second is the larger, and raising \(\eta\) grows it. So the maximum is smallest where they meet:

\[ \begin{aligned} 1 - \eta\lambda_{\min} &= \eta\lambda_{\max} - 1 \\ \eta^* &= \frac{2}{\lambda_{\min} + \lambda_{\max}} . \end{aligned} \]

The common factor is then

\[ \begin{aligned} 1 - \frac{2\lambda_{\min}}{\lambda_{\min} + \lambda_{\max}} &= \frac{\lambda_{\max} - \lambda_{\min}}{\lambda_{\max} + \lambda_{\min}} \\ &= \frac{\kappa - 1}{\kappa + 1} , \end{aligned} \]

after dividing top and bottom by \(\lambda_{\min}\).

How many steps. The error is sure to shrink to a fraction \(\epsilon\) of its start (say \({10^{-6}}\)) once \({\big((\kappa - 1)/(\kappa + 1)\big)^t \le \epsilon}\), that is once

\[ t \ge \frac{\ln(1/\epsilon)}{\ln\big((\kappa + 1)/(\kappa - 1)\big)} \]

steps. For large \(\kappa\), \({\ln\big((\kappa + 1)/(\kappa - 1)\big) \approx 2/\kappa}\) (exercise 3), so

\[ t \approx \frac{\kappa}{2}\,\ln\frac{1}{\epsilon} . \]

The work grows in proportion to the condition number: a bowl ten times thinner costs ten times the steps. The same holds for \({f(\vect{x})} = {\tfrac12\vect{x}\T\mat{S}\vect{x} - \vect{b}\T\vect{x}}\), with \({\vect{x}_t - \mat{S}^{-1}\vect{b}}\) in place of \(\vect{x}_t\).

A log-log graph of the number of steps needed to shrink the error a million-fold, against the condition number from about 1.5 to 1000. The green curve rises in a straight line. Dots mark kappa equals 3: 20 steps, the running bowl; kappa equals 9: 62 steps, the thin bowl; and kappa equals 100: 691 steps. A dashed grey line, kappa over 2 times the natural log of 10 to the 6, about 6.9 kappa, lies on top of the curve.
M03.8.4-F3

Steps of gradient descent with the best fixed step, against \(\kappa\). The count is about \({6.9\,\kappa}\) for a million-fold cut.

Rescaling is preconditioning. Suppose the bowl is the squared error of a model with two uncorrelated, centred features whose standard deviations are 3 and 1. Its matrix is \({\mat{S} = \operatorname{diag}(9, 1)}\), with \({\kappa = 9}\). Divide the first feature by 3. Its weight must then be 3 times larger, \({w_1 = z_1/3}\), and in the new weights

\[ f = \tfrac12\big(9w_1^2 + w_2^2\big) = \tfrac12\big(z_1^2 + w_2^2\big) , \]

a round bowl with \({\kappa = 1}\). Changing the variables by a matrix \(\mat{D}\) turns \(\mat{S}\) into \(\mat{D}\mat{S}\mat{D}\), and choosing \(\mat{D}\) to make that better conditioned is called preconditioning. Standardising features is the simplest kind.

Frontier note: the spectral norm of a weight matrix in deep learning

The map \(\vect{h} \mapsto \mat{W}\vect{h}\) can change the distance between two inputs by at most the factor \({\norm{\mat{W}}_2 = \sigma_1(\mat{W})}\), its Lipschitz constant. By the submultiplicative rule of M03.8.1, a whole network of such layers, with activations like ReLU that never stretch, is bounded by the product of the layers’ spectral norms. Spectral normalisation (Miyato and co-authors, ICLR 2018) divides each weight matrix by an estimate of its \(\sigma_1\), so that every layer has spectral norm 1, and finds that estimate cheaply with one step of the power method (M03.2.4) per update, reusing the vector from the step before. The full theory of step sizes is in M08.3, and the error analysis of algorithms in M10.3.

Worked example

Run gradient descent by hand on the running bowl with the best step.

The eigenvalues are 3 and 1, so \({\eta^* = 2/(1 + 3) = 0.5}\) and the factor is \({(3 - 1)/(3 + 1) = 0.5}\). The matrix of one step is

\[ \begin{aligned} \mat{I} - 0.5\,\mat{S} &= \begin{bmatrix} 1 - 1 & -0.5 \\ -0.5 & 1 - 1 \end{bmatrix} \\ &= \begin{bmatrix} 0 & -0.5 \\ -0.5 & 0 \end{bmatrix} . \end{aligned} \]

Start at \({\vect{x}_0 = (1, 0)}\). Each step swaps the two entries and multiplies them by \({-0.5}\):

\[ \begin{aligned} \vect{x}_1 &= (0,\ -0.5), \\ \vect{x}_2 &= (0.25,\ 0), \\ \vect{x}_3 &= (0,\ -0.125) . \end{aligned} \]

The length halves every step, \({\norm{\vect{x}_t} = 0.5^t}\), because both eigen-coordinates are multiplied by a factor of size 0.5: by \({1 - 0.5 \times 3 = -0.5}\) along \(\vect{q}_1\), which flips its sign, and by \({1 - 0.5 \times 1 = 0.5}\) along \(\vect{q}_2\). A million-fold cut needs \({0.5^t \le 10^{-6}}\), that is \({t = 20}\).

The limit is \({2/\lambda_{\max} = 2/3}\). With \({\eta = 0.7}\) the steep factor is \({1 - 2.1 = -1.1}\), and the error grows by 10% a step along \(\vect{q}_1\).

Left: the tilted elliptical contours of f equals one half x transpose S x, with the green gradient-descent path from a hollow dot x0 at (1, 0) to x1 at (0, minus 0.5), to x2 at (0.25, 0) and onwards, closing in on the centre in a shrinking zigzag. Right: a table with the step t from 0 to 5, the iterate x t, and its length: (1, 0) length 1; (0, minus 0.5) length 0.5; (0.25, 0) length 0.25; (0, minus 0.125) length 0.125; (0.0625, 0) length 0.0625; (0, minus 0.03125) length 0.03125.
M03.8.4-F4

The first five steps with \({\eta = 0.5}\). The iterate alternates between the two axes and its length halves every time.

Code

Gradient descent from scratch, with a counter, on the three bowls of this lesson.

import numpy as np

def descend(S, x0, eta, tol=1e-6, max_steps=100_000):
    """Gradient descent on x^T S x / 2. Returns the number of steps to shrink ||x|| by tol, or None."""
    x = np.array(x0, dtype=float)
    start = np.linalg.norm(x)
    for k in range(1, max_steps + 1):
        x = x - eta * (S @ x)
        size = np.linalg.norm(x)
        if size <= tol * start:
            return k
        if size > 1e6 * start:          # clearly diverging
            return None
    return None

def best_step(S):
    lam = np.linalg.eigvalsh(S)
    return 2 / (lam[0] + lam[-1]), (lam[-1] - lam[0]) / (lam[-1] + lam[0])

S = np.array([[2.0, 1.0], [1.0, 2.0]])
thin = np.diag([9.0, 1.0])
rescaled = np.eye(2)                    # the thin bowl after dividing feature 1 by 3

for name, M, x0 in [("running bowl", S, [1, 0]), ("thin bowl", thin, [1, 2.5]), ("rescaled", rescaled, [3, 2.5])]:
    eta, rate = best_step(M)
    print(f"{name:13s} kappa={np.linalg.cond(M):.0f}  eta*={eta:.2f}  factor={rate:.2f}  steps={descend(M, x0, eta)}")

print("running bowl, eta=0.1 (safe, slow):", descend(S, [1, 0], 0.1), "steps")
print("running bowl, eta=0.7 (too big):   ", descend(S, [1, 0], 0.7))
running bowl  kappa=3  eta*=0.50  factor=0.50  steps=20
thin bowl     kappa=9  eta*=0.20  factor=0.80  steps=62
rescaled      kappa=1  eta*=1.00  factor=0.00  steps=1
running bowl, eta=0.1 (safe, slow): 128 steps
running bowl, eta=0.7 (too big):    None

The hand trace, and the step counts of the formula against \(\kappa\):

x = np.array([1.0, 0.0])
for k in range(4):
    print(k, x, np.linalg.norm(x))
    x = x - 0.5 * (S @ x)

import math
for kappa in [3, 9, 100, 1000]:
    exact = math.ceil(math.log(1e-6) / math.log((kappa - 1) / (kappa + 1)))
    print(f"kappa={kappa:5d}: {exact:5d} steps;  kappa/2 * ln(1e6) = {kappa / 2 * math.log(1e6):7.1f}")
0 [1. 0.] 1.0
1 [ 0.  -0.5] 0.5
2 [0.25 0.  ] 0.25
3 [ 0.    -0.125] 0.125
kappa=    3:    20 steps;  kappa/2 * ln(1e6) =    20.7
kappa=    9:    62 steps;  kappa/2 * ln(1e6) =    62.2
kappa=  100:   691 steps;  kappa/2 * ln(1e6) =   690.8
kappa= 1000:  6908 steps;  kappa/2 * ln(1e6) =  6907.8

Explore

This module’s interactive, the condition explorer, lives in lesson M03.8.2. The thinness of its ellipse of solutions is measured by the same kind of ratio, \(\sigma_1/\sigma_2\); for a symmetric positive definite \(\mat{S}\) the singular values are the eigenvalues, so it is the \(\kappa\) that sets the zigzag here. Try the Identity and Nearly parallel presets and compare their read-outs. One caution: gradient descent on a least-squares loss \({\tfrac12\norm{\mat{A}\vect{w} - \vect{y}}^2}\) walks on the bowl of \(\mat{A}\T\mat{A}\), whose condition number is \({\kappa(\mat{A})^2}\) (M03.8.2).

Pitfalls

Two panels. The left panel, marked with a cross and titled Raw features: a zigzag, shows tall narrow reddish-purple ellipses of the bowl S equals diag(9, 1), kappa equals 9, and a green path from a hollow dot at the upper right that bounces from side to side across the narrow direction while creeping down the long axis, with the note 62 steps for a million-fold cut. The right panel, marked with a tick and titled Rescaled: straight in, shows round circles of the bowl after feature 1 is divided by 3, kappa equals 1, and a single green segment from the hollow start straight to the centre, with the note one step with eta equals 1.
M03.8.4-F5

Wrong beside right. On the thin bowl the best fixed step zigzags across the steep direction and needs 62 steps; after rescaling, one step reaches the minimum.

“If it is slow, take bigger steps.”

The step size is capped by the steepest direction: beyond \(2/\lambda_{\max}\) the error grows along \(\vect{q}_1\). On the running bowl \({\eta = 0.7}\) diverges, although it is only 40% above the best step. The flat direction stays slow because the steep one forbids the step it would need. Deep Learning (section 4.3.1) describes the same trade-off for the Hessian of a loss.

“The zigzag is a bug in the step size.”

The zigzag is the steep coordinate flipping sign, \({1 - \eta\lambda_{\max} < 0}\), and it happens at the best fixed step itself. A smaller step removes it but makes the flat coordinate slower still. Only changing the shape of the bowl, by rescaling or by a method that uses curvature (M08.5), removes the trade-off.

“After standardising, gradient descent is always fast.”

Standardising makes every feature’s variance 1, so for two standardised features with correlation \(r\) the bowl’s matrix is the correlation matrix, with eigenvalues \({1 + r}\) and \({1 - r}\) and \({\kappa = (1 + r)/(1 - r)}\). Two features with \({r = 0.99}\) still give \({\kappa = 199}\). Rescaling cures units, not near-repeats, exactly as in M03.8.3.

Check yourself

Recall

1. In eigen-coordinates, what does one step of gradient descent on \(\tfrac12\vect{x}\T\mat{S}\vect{x}\) do?

Show answer

It multiplies the coordinate along \(\vect{q}_i\) by \({1 - \eta\lambda_i}\), each independently of the others.

2. For which step sizes does gradient descent converge on a positive definite quadratic?

Show answer

For \({0 < \eta < 2/\lambda_{\max}}\).

3. What are the best fixed step and its factor per step?

Show answer

\({\eta^* = 2/(\lambda_{\min} + \lambda_{\max})}\), giving the factor \({(\kappa - 1)/(\kappa + 1)}\).

4. Roughly how does the number of steps grow with \(\kappa\)?

Show answer

In proportion to it: about \({(\kappa/2)\ln(1/\epsilon)}\) steps to shrink the error to a fraction \(\epsilon\) of its start, about \({6.9\,\kappa}\) for a million-fold cut.

5. Why is rescaling the features a form of preconditioning?

Show answer

Changing the variables by a diagonal matrix \(\mat{D}\) turns the bowl’s matrix \(\mat{S}\) into \(\mat{D}\mat{S}\mat{D}\); a good choice of \(\mat{D}\) lowers its condition number and so speeds up gradient descent.

Exercises

1. ★ For \({\mat{S} = \operatorname{diag}(4, 1)}\), find the range of stable steps, the best fixed step, its factor, and the number of steps for a million-fold cut.

Show solution

\({\lambda_{\max} = 4}\), so the steps with \({0 < \eta < 0.5}\) are stable. The best step is \({2/(1 + 4) = 0.4}\), and the factors are \({1 - 1.6 = -0.6}\) and \({1 - 0.4 = 0.6}\), both of size \({0.6 = (4 - 1)/(4 + 1)}\). Then \({0.6^t \le 10^{-6}}\) needs \({t \ge 6\ln 10/\ln(1/0.6) \approx 27.05}\), so 28 steps.

2. ★★ Run gradient descent on the running saddle, \(\mat{S}\) with rows \({(1, 2)}\) and \({(2, 1)}\) and eigenvalues 3 and \({-1}\). Show that for every \({\eta > 0}\) the coordinate along the eigenvector for \({-1}\) grows, and say what that means.

Show solution

The derivation of steps 1 to 3 never used positive definiteness, so the coordinate along the eigenvector for \({\lambda = -1}\) is multiplied by \({1 - \eta(-1) = 1 + \eta > 1}\) each step. Unless it is exactly 0 at the start, it grows like \({(1 + \eta)^t}\): the iterates slide off the saddle along \({(1, -1)/\sqrt2}\), downhill for ever, because \(f\) has no minimum. This is the escape seen in the interactive of M03.4.

3. ★★★ Show that \({\ln\big((\kappa + 1)/(\kappa - 1)\big)} \approx {2/\kappa}\) for large \(\kappa\), and deduce the step count \({t \approx (\kappa/2)\ln(1/\epsilon)}\).

Show solution

Write \(\frac{\kappa + 1}{\kappa - 1} = \frac{1 + 1/\kappa}{1 - 1/\kappa}\), so its logarithm is \({\ln(1 + h) - \ln(1 - h)}\) with \({h = 1/\kappa}\). The Taylor series of M04.8 give \({\ln(1 + h) = h - h^2/2 + \dots}\) and \({\ln(1 - h) = -h - h^2/2 - \dots}\), so the difference is \({2h + }\) terms in \(h^3\), about \(2/\kappa\). The steps needed satisfy

\[ \begin{aligned} t &\ge \frac{\ln(1/\epsilon)}{\ln\big((\kappa + 1)/(\kappa - 1)\big)} \\ &\approx \frac{\ln(1/\epsilon)}{2/\kappa} = \frac{\kappa}{2}\ln\frac{1}{\epsilon} . \end{aligned} \]

For \({\kappa = 100}\) and \({\epsilon = 10^{-6}}\) this gives 690.8, against the exact count of 691.

Summary card

On a quadratic bowl, gradient descent runs one race per eigenvalue, and \(\kappa\) sets the pace.

The anchor figure again: gradient-descent iterates on the tilted bowl of S dropping quickly onto the flat eigenvector and creeping along it, beside the two eigen-coordinates shrinking by 0.1 and 0.7 per step on a log scale.
M03.8.4-F1

Steep races finish fast; flat races decide.

  • \({\vect{x}_{t+1}} = {(\mat{I} - \eta\mat{S})\vect{x}_t}\); along \(\vect{q}_i\): multiply by \({1 - \eta\lambda_i}\).
  • Stable exactly when \({0 < \eta < 2/\lambda_{\max}}\).
  • Best fixed step \({\eta^* = 2/(\lambda_{\min} + \lambda_{\max})}\), factor \({(\kappa - 1)/(\kappa + 1)}\), about \({(\kappa/2)\ln(1/\epsilon)}\) steps.
  • Rescaling features is preconditioning: \(\mat{S} \to \mat{D}\mat{S}\mat{D}\).

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

  • Gilbert Strang, Lecture 22: Gradient descent: downhill to a minimum, MIT OpenCourseWare 18.065 (Spring 2018). Its example is \({F = \tfrac12(x^2 + by^2)}\): for small \(b\) the path zigzags towards the origin and each step multiplies by \({(b - 1)/(b + 1)}\).
  • Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, section 4.3.1: the condition number of the Hessian measures how much the second derivatives differ, gradient descent performs poorly when it is large, the step must be small enough not to overshoot in the steep directions; figure 4.6 shows the path bouncing between the walls of a quadratic whose Hessian has condition number 5.
  • Takeru Miyato, Toshiki Kataoka, Masanori Koyama and Yuichi Yoshida, Spectral Normalization for Generative Adversarial Networks, ICLR 2018. Section 2.1: the spectral norm as the Lipschitz constant of a linear layer (6), the product bound over layers (7) and the normalisation \({\mat{W}/\sigma(\mat{W})}\) (8); section 2.2: estimating \({\sigma(\mat{W})}\) by power iteration; appendix A: reusing the vector from the step before, so that one round of power iteration per update was enough.

Next. The module ends here. M03.9, Markov matrices, graphs and PageRank, uses the max-norm of M03.8.1 to bound eigenvalues; M08.3 develops step sizes for general losses, and M10.3 the error analysis of algorithms.

This lesson unlocks

M03.9 Markov matrices, graphs and PageRank M08.3 Gradient descent and step sizes (planned) M10.3 Conditioning and error analysis (planned)

Your progress is saved in this browser only. No account, no tracking.
Back to top