Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Gradient Descent and Numerical Optimization › Visualizing Gradient Descent on a Conditioned Quadratic

Michael BrenndoerferOctober 25, 20267 min read

Machine Learning from ScratchAll chapters

Part 3 of 15Model Fundamentals and Diagnostics

Chapter 30Gradient Descent and Numerical Optimization › Visualizing Gradient Descent on a Conditioned Quadratic

Reading section 5 of 10 · Visualizing Gradient Descent on a Conditioned Quadratic · 7 minSection 5 of 10 · 7 min

Section 5 of 10 · 7 min read

Gradient Descent and Numerical Optimization › Visualizing Gradient Descent on a Conditioned QuadraticSection view · Sections in this chapter5 / 10 ↓

Sections in this chapter10

Reading tools Definitions, links & notes

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Notes & comments

Notes & commentsLeave notes and join the discussionSelection toolbarShow comment actions when selecting text. Turn off for the browser menu only.Comment indicatorsShow small counts beside annotated passagesPassage highlightsGently shade annotated text selections

We use two diagonal quadratic objectives with known minima to inspect the update paths. For a two-entry parameter vector, define

J(\theta)=\tfrac12(a_1\theta_1^2+a_2\theta_2^2).

The positive coefficients $a_1$ and $a_2$ are the curvatures along the coordinate axes. The gradient is $(a_1\theta_1,a_2\theta_2)$ , the Hessian is $\mathrm{diag}(a_1,a_2)$ , and the unique minimizer is the origin. Here $a_1\ge a_2>0$ , so the condition number is $a_1/a_2$ .

PythonIn [3]
CollapseExpandimport numpy as np

# Two diagonal quadratics: J(theta) = 0.5 * (a1 * theta1^2 + a2 * theta2^2)
# The Hessian is diag(a1, a2), so the condition number is a1 / a2 exactly.
well = np.array([2.0, 1.0])
ill = np.array([100.0, 1.0])


def objective(theta, a):
    """Scalar objective value for a diagonal quadratic."""
    return 0.5 * np.sum(a * theta**2)


def gradient(theta, a):
    """Exact gradient: component j is a_j * theta_j."""
    return a * theta


def run_gd(theta0, a, eta, steps):
    """Plain gradient descent, recording the full path for plotting."""
    theta = np.array(theta0, dtype=float)
    path = [theta.copy()]
    history = [objective(theta, a)]
    for _ in range(steps):
        theta = theta - eta * gradient(theta, a)
        path.append(theta.copy())
        history.append(objective(theta, a))
    return np.array(path), np.array(history)


theta0 = np.array([1.0, 1.0])

# Stable step for both problems: eta < 2 / lambda_max is required.
stability_info = []
for name, a in [("well", well), ("ill", ill)]:
    eta_max = 2.0 / a.max()
    stability_info.append((name, a, eta_max))

ConsoleOut [4]
CollapseExpandwell: curvature=[2. 1.], kappa=2, stability limit eta<1.000
ill: curvature=[100.   1.], kappa=100, stability limit eta<0.020

PythonIn [5]
CollapseExpand# Use one common learning rate that is stable for the ill-conditioned problem,
# and observe how the two curvature vectors respond at that absolute rate.
eta = 1.0 / 100.0  # equals 1 / lambda_max of the ill-conditioned case
steps = 200
path_well, hist_well = run_gd(theta0, well, eta, steps)
path_ill, hist_ill = run_gd(theta0, ill, eta, steps)

ConsoleOut [6]
CollapseExpandAfter 200 steps at eta=0.01:
  well-conditioned  J = 9.285e-03  ||theta|| = 1.351e-01
  ill-conditioned   J = 8.975e-03  ||theta|| = 1.340e-01

At this common step size, the final objectives are about $0.009285$ for the well-conditioned problem and $0.008975$ for the ill-conditioned problem. Their parameter norms are about $0.135129$ and $0.133980$ , respectively. The ill-conditioned run is slightly closer in this experiment because its steep coordinate reaches zero after one update, while both shallow coordinates end at $0.99^{200}\approx0.133980$ . These results do not show faster convergence for the well-conditioned run. Here the objective is $J(\theta) = \tfrac{1}{2}(a_1\theta_1^2 + a_2\theta_2^2)$ , with:

$\theta_1, \theta_2$ : the two parameters
$a_1, a_2$ : the curvatures along the two axes
$\eta = 0.01$ : the learning rate
$\kappa = a_1/a_2$ : the condition number
$J$ : the objective value at the final iterate
$\|\theta\|$ : the Euclidean norm of the final parameter vector, which shrinks toward zero as the iterates approach the minimum

Each coordinate contracts by $1-\eta a_j$ per iteration. At $\eta=0.01$ , the well-conditioned factors are $0.98$ and $0.99$ , while the ill-conditioned factors are $0$ and $0.99$ . The shallow coordinate therefore moves identically in both runs; the difference in their final objectives comes from the small residual steep coordinate in the well-conditioned run. To assess the advantage available from conditioning, we would also need to compare appropriate step choices for each problem.

PythonIn [7]
CollapseExpand# Prepare contour data once; the following cells only present these values.
plot_axis = np.linspace(-1.1, 1.1, 300)
contour_x, contour_y = np.meshgrid(plot_axis, plot_axis)
contour_well = 0.5 * (well[0] * contour_x**2 + well[1] * contour_y**2)
contour_ill = 0.5 * (ill[0] * contour_x**2 + ill[1] * contour_y**2)
levels_well = np.geomspace(0.001, 1.5, 12)
levels_ill = np.geomspace(0.001, 50.5, 14)

VisualizationOut [8]
CollapseExpand

Contour plot of the condition-number-2 quadratic with a curved path from (1,1) toward the origin, ending near (0.018,0.134). — Path from (1, 1) on the condition-number-2 quadratic at the common learning rate 0.01. The two coordinate multipliers are 0.98 and 0.99, so the path curves toward the vertical axis and remains away from the origin after two hundred updates.

VisualizationOut [9]
CollapseExpand

Elongated quadratic contours with a path that moves from (1,1) to (0,0.99), then follows the vertical axis to about (0,0.134). — Path from the same starting point on the condition-number-100 quadratic at learning rate 0.01. The steep coordinate reaches zero after one update; the shallow coordinate has the same 0.99 multiplier as in the other run, so later points lie on the vertical axis.

The second path reaches the vertical axis after one update. Both runs then have the same shallow-coordinate contraction, so different contour shapes alone do not establish a convergence-rate advantage at this common conservative learning rate.

VisualizationOut [10]
CollapseExpand

Logarithmic objective histories for two hundred updates. The ill-conditioned curve drops sharply after the first update, then both curves decrease gradually and finish near 0.009. — Objective histories at the common learning rate 0.01. The ill-conditioned objective falls about 3.75 decades, versus 2.21 for the well-conditioned objective, because its steep-coordinate contribution vanishes immediately. Both remaining shallow coordinates contract by 0.99, producing similar late-stage decreases.

The common rate deliberately gives both shallow coordinates the same multiplier. To see the convergence available to each problem, we now apply the same curvature-based rule, $\eta=1/\lambda_{\max}$ , separately. This gives rates 0.5 and 0.01, respectively, while keeping the starting point and update budget fixed. The change in rate is explicit: we are comparing one common rate rule, rather than one common absolute rate.

PythonIn [11]
CollapseExpandrate_well = 1.0 / well.max()
rate_ill = 1.0 / ill.max()
path_well_rule, hist_well_rule = run_gd(theta0, well, rate_well, steps)
path_ill_rule, hist_ill_rule = run_gd(theta0, ill, rate_ill, steps)
assert np.linalg.norm(path_well_rule[-1]) < np.linalg.norm(path_ill_rule[-1])

ConsoleOut [12]
CollapseExpandRule eta=1/lambda_max, same start and 200 updates:
  kappa=2:   eta=0.500, objective=1.936e-121, norm=6.223e-61
  kappa=100: eta=0.010, objective=8.975e-03, norm=1.340e-01

With this rule the well-conditioned shallow coordinate has multiplier 0.5, while the ill-conditioned one still has multiplier 0.99. This is a conditioning-dependent rate difference on the stated quadratics. Newton uses the full curvature matrix instead: since the Hessian is constant and positive definite, one full step reaches the minimizer in exact arithmetic.

PythonIn [13]
CollapseExpanddef newton_step(theta, a):
    """One Newton step using the exact diagonal Hessian."""
    H = np.diag(a)
    return theta - np.linalg.solve(H, gradient(theta, a))


theta_n = newton_step(theta0, ill)

ConsoleOut [14]
CollapseExpandNewton from [1. 1.] on the ill-conditioned problem:
  one step -> theta = [0. 0.]
  objective = 0.000e+00
  gradient norm = 0.000e+00

The displayed Newton solution has zero objective and gradient to the reported numerical precision. The code solves a linear system with the exact diagonal Hessian. This example confirms the one-step algebra for this positive-definite quadratic; it does not establish one-step convergence for arbitrary objectives or immunity to floating-point conditioning.

Comments

Add to the conversation

A question, a correction, or an example from your own work.

No comments yet. Be the first to share your thoughts!

Comments

Add to the conversation

Stay up to date