Week 13: Nonconvex Deep Learning

Your training loss falls, goes flat, then falls again. The flat stretch was not a local minimum. Descent passed close to a saddle point. The surface below is $f(u, v) = (u^2 - 1)^2 + \tfrac{1}{2}(v^2 - 1)^2$: four minima with $f = 0$, four saddles and a peak at the origin. Each run starts on the circle of radius 1.6, with step size $\eta = 0.05$.

Drag the start angle $\varphi$. From $\varphi = 45°$ the path reaches the minimum $(1, 1)$ in 28 steps. Near $\varphi = 0°$ it heads first for the saddle at $(1, 0)$, and the dots pile up before the path turns away. At exactly $\varphi = 0°$ it stops on the saddle.

Why the path stalls near a saddle#

The coordinates descend independently, and the Hessian is diagonal, $\nabla^2 f = \mathrm{diag}(12u^2 - 4,\; 6v^2 - 2)$. A point with $\nabla f = 0$ is a minimum when every eigenvalue is positive, a maximum when every one is negative, and a saddle when the signs are mixed. The origin, with $\mathrm{diag}(-4, -2)$, is a maximum. The point $(1, 0)$, with $\mathrm{diag}(8, -2)$, is a saddle.

Near $(1, 0)$ one step multiplies the offsets:

The $u$ offset dies fast, but the $v$ offset grows only 10% per step, so the time near the saddle grows as $\ln(1/v_0) / \ln 1.1$. Every factor of 10 closer to the axis costs $\ln 10 / \ln 1.1 \approx 24$ extra steps. From $\varphi = 10°$ ($v_0 = 0.28$) the scene takes 48 steps. From $\varphi = 1°$ ($v_0 = 0.028$) it takes 72.

At $\varphi = 0°$, $v$ stays 0. The path converges to the saddle, where the gradient is zero, and a test on $\|\nabla f\|$ reports success at $f = 0.5$. A random start almost never lands on the axis, but nearby starts pay the toll.

The common mistake. A flat stretch in the loss curve is read as a local minimum, and the run is stopped. From $\varphi = 1°$ the loss sits within 0.05 of the saddle value 0.5 for 22 steps, then drops to 0 on its own. A flat loss, or even a zero gradient, does not certify a minimum. A negative Hessian eigenvalue rules one out.

Saddles in high dimensions#

In $D$ dimensions a critical point is a minimum only if all $D$ Hessian eigenvalues are positive. For random Gaussian landscapes that chance decays exponentially with $D$, and critical points well above the lowest loss are almost all saddles. Dauphin et al. (2014) measured the same pattern in small networks. The scene's arithmetic carries over. A negative eigenvalue $-\lambda$ escapes by a factor $1 + \eta\lambda$ per step, so a saddle costs time, not convergence. SGD noise also knocks the iterate off the stalling set.

Overparameterization#

A model is overparameterized when it can interpolate its training data, often with more parameters than examples ($d \gg n$). In practice its local minima are mostly near-global. That is a theorem only in special cases, such as deep linear nets (Kawaguchi, 2016), and an empirical finding elsewhere.

Initialization picks the basin#

The scene's start angle is an initialization. It picks the basin. In a network the weight scale also decides whether signal survives: too small and activations vanish, too large and they explode.

• Xavier/Glorot (tanh, sigmoid): $W_{ij} \sim \mathcal{U}[-a, a]$ with $a = \sqrt{6/(n_{\text{in}} + n_{\text{out}})}$, which keeps activation variance steady across layers.
• He/Kaiming (ReLU): $W_{ij} \sim \mathcal{N}(0, 2/n_{\text{in}})$. The factor 2 compensates for ReLU zeroing half the units.

Normalization as loss-surface shaping#

Batch Normalization (BNBatch Normalization) normalizes activations over a mini-batch. It was introduced against internal covariate shift (Ioffe & Szegedy, 2015), but its gain survives when that shift is re-injected (Santurkar et al., 2018). The benefit is a smoother loss, with a smaller $L$ that allows larger steps. Layer Normalization (LNLayer Normalization) normalizes across the features of each example, at any batch size.

What transfers from convex theory#

Transfers as diagnosis: the step-size scale $\eta \approx 1/L$, momentum (Week 7), adaptive methods (Week 8), gradient clipping (Week 9) and early stopping (Week 10).

Does not transfer: global optimality, predicted convergence rates and convex reformulation.

Knowledge check#

Browser lab: initialization on XOR#

Train a 2-layer MLP on XOR from He and from tiny initial weights. All-zero weights are a stationary point but not a minimum, so watch for a plateau at $\ln 2 \approx 0.69$.

import numpy as np
import matplotlib.pyplot as plt

# Try np.random.seed(1): He init stalls at ln 2 / 2 = 0.35. One unit dies and no unit fires on two inputs.
# A 4-unit net is not overparameterized.
np.random.seed(0)

def relu(x): return np.maximum(0, x)
def drelu(x): return (x > 0).astype(float)
def sigmoid(x): return 1 / (1 + np.exp(-x))

X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]]).T
y = np.array([[0, 1, 1, 0]])

def init_weights(d_in, d_hid, d_out, scale_fn):
    W1 = scale_fn(d_in, d_hid)
    b1 = np.zeros((d_hid, 1))
    W2 = scale_fn(d_hid, d_out)
    b2 = np.zeros((d_out, 1))
    return W1, b1, W2, b2

def forward(W1, b1, W2, b2, X):
    z1 = W1 @ X + b1; a1 = relu(z1)
    z2 = W2 @ a1 + b2; a2 = sigmoid(z2)
    return z1, a1, z2, a2

def compute_loss(a2, y):
    return -np.mean(y * np.log(a2 + 1e-12) + (1 - y) * np.log(1 - a2 + 1e-12))

def train(W1, b1, W2, b2, X, y, eta, K):
    losses = []
    for _ in range(K):
        z1, a1, z2, a2 = forward(W1, b1, W2, b2, X)
        losses.append(compute_loss(a2, y))
        dz2 = a2 - y
        dW2 = dz2 @ a1.T / 4; db2 = np.mean(dz2, axis=1, keepdims=True)
        dz1 = (W2.T @ dz2) * drelu(z1)
        dW1 = dz1 @ X.T / 4; db1 = np.mean(dz1, axis=1, keepdims=True)
        W1 -= eta * dW1; b1 -= eta * db1
        W2 -= eta * dW2; b2 -= eta * db2
    return losses

d_in, d_hid, d_out = 2, 4, 1
K, eta = 2000, 0.5

loss_he = train(*init_weights(d_in, d_hid, d_out,
    lambda i, o: np.random.randn(o, i) * np.sqrt(2.0 / i)), X, y, eta, K)

loss_small = train(*init_weights(d_in, d_hid, d_out,
    lambda i, o: np.random.randn(o, i) * 0.01), X, y, eta, K)

plt.figure(figsize=(8, 5))
plt.plot(loss_he, label="He init (√(2/n_in))", linewidth=1.5)
plt.plot(loss_small, label="Small randn × 0.01", linewidth=1.5)
plt.xscale("log"); plt.yscale("log"); plt.xlabel("Iteration"); plt.ylabel("Loss")
plt.title("XOR: He vs tiny init")
plt.legend(); plt.grid(True, alpha=0.3); plt.show()

print(f"Plateau: {sum(abs(l - np.log(2)) < 0.01 for l in loss_small)} steps within 0.01 of ln 2")
print(f"Final loss  He={loss_he[-1]:.4f}  small-init={loss_small[-1]:.4f}")
print("Notice: the tiny-weight run starts next to the all-zero stationary point. It sits on a plateau near ln 2 before it leaves.")

Key takeaways#

• A critical point is a saddle when its Hessian has eigenvalues of both signs. Gradient descent stalls near one but leaves along the negative direction.
• Near a saddle with curvature $-\lambda$, each factor of 10 closer to its stable set costs about $\ln 10 / \ln(1 + \eta\lambda)$ extra steps. A plateau is not a minimum.
• In high dimensions saddles outnumber minima. In overparameterized nets most minima are near-global in practice.
• Initialization picks the basin, normalization smooths the surface, and convex theory transfers as diagnosis, not as guarantees.

Further reading#

• Ian Goodfellow, Yoshua Bengio & Aaron Courville, Deep Learning (MIT Press, 2016). Chapter 8 covers nonconvex optimization, saddle points and initialization.
• Yann Dauphin et al., "Identifying and Attacking the Saddle Point Problem in High-Dimensional Non-Convex Optimization" (NeurIPS 2014). Why saddles dominate high-dimensional landscapes.
• Kaiming He, Xiangyu Zhang, Shaoqing Ren & Jian Sun, "Delving Deep into Rectifiers" (ICCV 2015). He initialization for ReLU networks.
• Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas & Aleksander Madry, "How Does Batch Normalization Help Optimization?" (NeurIPS 2018). The loss-smoothing account of BatchNorm.