Week 13: Landscapes and Implicit Bias

High-dimensional loss surfaces#

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 surfaces 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 surface 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 surface 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 uses 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.

Read the gaps above as a work plan, not a disclaimer. The stationary-point guarantee without a destination, the nonlinear implicit bias without a general theorem, the flatness–generalization link without a proof, the lazy-vs-feature-learning split — each names a place where convex tools stop transferring and a thesis begins. Weeks 1–12 gave you the transferable half (conditioning diagnostics, convex subproblem solvers, dual bounds); the capstone in Week 14 asks you to say, for your problem, which half you are standing in.

Knowledge Check#

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()

print("Notice: GD's distance to the minimum-norm solution reaches 0.0000 and its norm matches |w*| = 4.7801, while a random interpolant fits the same data with norm 6.9173.")

Key takeaways#

• In high dimensions critical points are overwhelmingly saddles, and gradient noise escapes them. Bad local minima are rarer than low-dimensional intuition suggests.
• Overparameterisation makes the zero-loss solution set a high-dimensional manifold, so generalisation depends on which interpolant the optimiser picks.
• Implicit bias: gradient descent from zero on underdetermined least squares converges to the minimum $\ell_2$-norm interpolant; on separable logistic regression it converges to the maximum-margin direction; on deep linear networks to low-rank solutions.
• The bias is determined by the algorithm, step size, initialisation, and architecture, not by the loss alone.
• Convex theory still transfers as diagnostics: step size from the smoothness constant, conditioning, convex subproblems inside ADMM and IPM, and dual lower bounds.
• The honest gaps are which minimum SGD reaches, implicit bias for nonlinear networks, flatness versus generalisation, and the difference between lazy and feature-learning regimes.

Further reading#

• Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar & Nathan Srebro, "The Implicit Bias of Gradient Descent on Separable Data" (JMLR, 2018) — the max-margin result.
• Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov & Nathan Srebro, "Geometry of Optimization and Implicit Regularization in Deep Learning" (2017) — a survey of implicit bias.
• Ian Goodfellow, Yoshua Bengio & Aaron Courville, Deep Learning (MIT Press, 2016) — the nonconvex-optimisation chapter this lecture departs from.