Week 13: Landscapes and Implicit Bias

High-Dimensional Landscapes#

In 1D and 2D, nonconvex functions look intimidating — peaks, valleys, saddles, sharp ridges. Our intuition from low dimensions suggests that gradient descent should frequently get trapped in poor local minima. Yet deep neural networks routinely train to near-zero training loss with simple first-order methods. Why?

The saddle point prevalence. In high dimensions ($d \gg 1$), critical points of random Gaussian fields (a crude model for loss surfaces) are overwhelmingly saddles, not local minima. A random critical point has roughly equal numbers of positive and negative Hessian eigenvalues. For a critical point to be a local minimum, all $d$ eigenvalues must be nonnegative — an exponentially rare event in truly random landscapes unless the index (the number of negative eigenvalues) is zero.

Intuition. At a saddle, there exists at least one direction of negative curvature — a direction downhill. Gradient descent, with even a small amount of noise (SGDStochastic Gradient Descent), can escape saddles by following these negative-curvature directions. The Hessian at a strict saddle has at least one negative eigenvalue, and gradient noise perturbs the iterate away from the ridge, allowing it to slide down.

Escaping saddles is easy; bad local minima are rarer than we think. This does not mean every critical point in a deep net loss landscape is a global minimum — far from it. But it suggests that for large overparameterised networks, all local minima may be nearly as good as the global minimum. The real challenge is not getting stuck in a bad minimum but navigating the proliferation of saddle points efficiently.

Overparameterisation#

A model is overparameterised when it has more parameters than necessary to fit the training data. In this regime:

• The training loss can be driven to (near) zero — the model interpolates the training data.
• There are infinitely many weight configurations that achieve zero training loss — the set of global minimisers is a high-dimensional manifold, not a discrete set of isolated points.
• Generalisation depends on which of these many solutions the optimiser finds.

Overparameterised linear regression is the simplest example: $\min_w \; \|Xw - y\|_2^2$ with $d > n$. There are infinitely many $w$ that satisfy $Xw = y$ exactly (the nullspace of $X$ has dimension $d - \operatorname{rank}(X)$). Among them, which one does gradient descent find?

Implicit Bias of GD/SD#

Implicit bias is the phenomenon that optimisation algorithms, when run to convergence without explicit regularisation, nevertheless converge to a specific solution among the many minimisers. The algorithm's dynamics itself imposes a preference.

Linear regression with $d > n$. Gradient descent initialised at $w_0 = 0$ on $\min_w \|Xw - y\|_2^2$ converges to:

$w^* = X^T(XX^T)^{-1}y = \arg\min_{Xw = y} \|w\|_2$

This is the minimum $\ell_2$-norm interpolant — among all $w$ that achieve zero training error, GD selects the one with smallest Euclidean norm. The proof: every GD step is a linear combination of the rows of $X$ (since $\nabla f(w) = X^T(Xw - y)$), so the iterates stay in the row space of $X$. The limit is the minimum-norm solution in the row space, which is exactly $X^T(XX^T)^{-1}y$.

Deep linear networks. GD on deep linear networks (composition of weight matrices) with $\ell_2$ loss exhibits an implicit bias toward low-rank solutions — effectively performing nuclear norm regularisation without an explicit regulariser.

Classification with separable data. GD on logistic regression with linearly separable data drives the weights to infinity (to push the sigmoid to 0/1) but the direction $w / \|w\|$ converges to the $\ell_2$ max-margin classifier — the same solution as a hard-margin SVM. This is implicit bias toward maximum margin solutions.

Key point. The optimiser's choice of solution is not random. It is determined by the algorithm (GD vs SGDStochastic Gradient Descent vs AdamAdaptive Moment Estimation (optimizer)), the step size, the initialisation, and the architecture. Understanding this implicit bias helps explain why overparameterised models generalise: the bias guides the optimiser toward solutions with good inductive properties (low norm, max margin, low rank) even when the loss landscape is full of alternatives.

What Convex Theory Still Gives You#

This course spent seven weeks (Weeks 1–7) on convex optimisation. Those tools remain essential, even when your ultimate problem is nonconvex:

• Step-size tuning: The Lipschitz constant $L$ and strong convexity parameter $\mu$ bound the safe step size. Even for nonconvex problems in the interpolating regime, the smoothness constant guides convergence.
• Conditioning diagnostics: Ill-conditioned Hessians slow all methods — first-order, second-order, and stochastic. The convex analysis of conditioning transfers directly.
• Structured subproblems: In ADMM, IPM, and proximal methods, the subproblems are often convex even when the overall problem is not. Each subproblem solver leverages convex guarantees.
• Dual bounds: The dual of a nonconvex problem is always convex and always provides a lower bound (weak duality). These lower bounds certify optimality or reveal infeasibility.

Honest Gaps#

The theoretical understanding of deep learning optimisation is incomplete:

• No full theory of deep net training. We can prove that SGD converges to a stationary point for smooth nonconvex objectives (gradient norm $\to 0$), but we cannot guarantee which local minimum (or saddle) it reaches, nor can we predict generalisation from optimisation dynamics alone.

• Implicit bias in nonlinear networks. For deep nonlinear networks, the implicit bias is understood only in restricted settings (homogeneous activations like ReLU, specific initialisation scales, gradient flow limit). The general case remains an active research area.

• Sharpness vs flatness. As Week 12 discussed, the relationship between geometric flatness and generalisation is empirical, not proven.

• The scaling regime matters. The "lazy training" regime (where weights barely move and the network behaves like its linearisation, the NTK) has different dynamics from the "feature learning" regime where weights change substantially. Our convex tools transfer well to the lazy regime; the feature-learning regime is where the gaps are largest.

These gaps are not reasons to abandon convex theory — they are the frontier that makes optimisation research exciting. Every tool in this course has a role in navigating that frontier.

Browser lab#

For underdetermined least squares ($X \in \mathbb{R}^{20 \times 50}$, $d = 50 > n = 20$), demonstrate that GD initialised at $w_0 = 0$ converges to the minimum $\ell_2$-norm solution. Compare GD's final weights with the analytic min-norm solution from pinv.

import numpy as np
import matplotlib.pyplot as plt

np.random.seed(42)
n, d = 20, 50
X = np.random.randn(n, d)
w_opt = np.random.randn(d)
y = X @ w_opt + 0.05 * np.random.randn(n)  # underdetermined: d > n

# Analytic minimum-norm solution
w_pinv = X.T @ np.linalg.solve(X @ X.T + 1e-10 * np.eye(n), y)
# Alternatively: w_pinv = np.linalg.pinv(X) @ y

# GD from zero
eta = 0.05
n_steps = 2000
w_gd = np.zeros(d)
path_loss = []
path_dist = []  # distance to min-norm solution

for _ in range(n_steps):
    g = X.T @ (X @ w_gd - y) / n
    w_gd = w_gd - eta * g
    path_loss.append(0.5 * np.sum((X @ w_gd - y)**2) / n)
    path_dist.append(np.linalg.norm(w_gd - w_pinv))

print(f"Final GD loss: {path_loss[-1]:.2e}")
print(f"Distance GD to min-norm: {path_dist[-1]:.4f}")
print(f"|GD norm|: {np.linalg.norm(w_gd):.4f}, |min-norm|: {np.linalg.norm(w_pinv):.4f}")

# Random interpolant for comparison
# Any solution w = w_pinv + v where Xv = 0 is also an interpolant
null_vec = np.random.randn(d)
null_vec = null_vec - X.T @ np.linalg.solve(X @ X.T + 1e-10 * np.eye(n), X @ null_vec)
w_random_interp = w_pinv + 5.0 * null_vec / np.linalg.norm(null_vec)
print(f"|random interpolant norm|: {np.linalg.norm(w_random_interp):.4f}")
print(f"Random interpolant loss: {0.5 * np.sum((X @ w_random_interp - y)**2) / n:.2e}")

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))

ax1.semilogy(path_loss, "b-", linewidth=1)
ax1.set_xlabel("Iteration")
ax1.set_ylabel("Training loss (log scale)")
ax1.set_title("GD converges to zero loss")
ax1.grid(True, alpha=0.3)

ax2.semilogy(path_dist, "r-", linewidth=1)
ax2.set_xlabel("Iteration")
ax2.set_ylabel("$\|\|w_k - w^*_{\min}\|\|$ (log scale)")
ax2.set_title("GD approaches min-norm solution")
ax2.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()