Week 14: Capstone — Structure Meets Scale

Two Paths#

Every problem in this course falls into one of two archetypes:

The Structure Path (Weeks 1–7). The problem is convex or near-convex, has a modest number of variables (hundreds to low millions), and benefits from high accuracy. Tools:

• Recognise the cone structure: LP, QP, SOCPSecond-Order Cone Program, SDPSemidefinite Program.
• Form KKTKarush–Kuhn–Tucker (optimality conditions) conditions; check a constraint qualification.
• Use Lagrangian duality to verify optimality and get sensitivity information.
• Solve with IPMInterior-Point Method (high accuracy) or proximal/ADMMAlternating Direction Method of Multipliers (large sparse problems).

The Scale Path (Weeks 8–13). The problem has millions to billions of parameters, stochastic gradients, and nonconvexity. Tools:

• First-order: SGDStochastic Gradient Descent, AdamAdaptive Moment Estimation (optimizer), momentum (from intermediate Optim).
• Second-order: L-BFGS for moderate scale with accurate gradients.
• Variance reduction: SVRGStochastic Variance Reduced Gradient for finite-sum structure.
• Geometry: SAMSharpness-Aware Minimization for sharpness avoidance; implicit bias awareness.
• Distributed: data-parallel scaling; learning rate scaling heuristics.

The wrong choice wastes compute. Running IPM on a billion-parameter network is impossible. Running SGDStochastic Gradient Descent on a small convex SDP when you need a certificate of optimality is irresponsible. This capstone asks: can you diagnose which situation you are in?

Case Study A — Structured Convex#

Problem: Robust portfolio optimisation. Minimise $w^T \Sigma w$ (portfolio variance) subject to $\mathbf{1}^T w = 1$, $w \geq 0$, and a robust return constraint:

$\min_{\|\Delta \mu\| \leq \rho} (\mu + \Delta \mu)^T w \geq r_{\text{target}}$

Diagnosis:

• Objective: convex quadratic ($\Sigma \succeq 0$).
• Constraints: linear equality (budget), linear inequalities (no shorting).
• Robust constraint: worst-case return $\mu^T w - \rho \|w\|_2 \geq r_{\text{target}}$, which is $\|w\|_2 \leq (\mu^T w - r_{\text{target}})/\rho$ — a second-order cone constraint (SOCP).
• Variable count: $d$ = number of assets (tens to thousands). Moderate.
• Accuracy requirement: high (investment decisions).

Method choice: Structure path — IPM for SOCP.

• KKT: stationarity involves $\Sigma w + \nu \mathbf{1} - \lambda + \gamma w / \|w\|_2 = 0$.
• Dual: provides shadow prices for the budget constraint (marginal cost of capital) and the return target (cost of demanding higher return).
• Solver: commercial IPM SOCP solver converges to $10^{-8}$ duality gap in milliseconds to seconds.
• Do NOT use: SGD (stochastic noise is meaningless without data samples; the problem is deterministic).

Case Study B — Large Model Training#

Problem: Train a ResNet-50 on ImageNet (1.28M images, 1000 classes, 25M parameters). Objective: $\min_w \frac{1}{n}\sum_{i=1}^n \ell(f_w(x_i), y_i)$ (cross-entropy ERMEmpirical Risk Minimization).

Diagnosis:

• Objective: nonconvex (deep net), finite-sum ($n \approx 1.28 \times 10^6$).
• Parameters: $d \approx 2.5 \times 10^7$.
• Gradients: stochastic (minibatch), noisy.
• Constraints: none (unconstrained).
• Goal: minimise validation error (not training loss to machine precision).

Method choice: Scale path — SGD with momentum + SAM.

• Optimiser: SGDStochastic Gradient Descent with Nesterov momentum. AdamAdaptive Moment Estimation (optimizer) is a reasonable alternative; L-BFGS is infeasible for $d = 2.5 \times 10^7$.
• Batch size: 256–2048, distributed across 4–8 GPUs (data-parallel). Learning rate scaled linearly with batch size.
• SAM: enabled ($\rho \approx 0.05$–$0.1$) to bias toward flatter minima and close the large-batch generalisation gap noted in Week 10.
• Regularisation: weight decay ($10^{-4}$), label smoothing, data augmentation.
• Do NOT use: IPM (too many parameters), full Newton (Hessian too large), SVRG (impractical for $n = 1.28$M with deep nets).

Decision Flow#

Given a new problem, ask these questions in order:

1. Is the problem convex? If yes, look for cone structure (LP/QP/SOCP/SDP) and use IPM or proximal methods. If not, proceed.
2. How many parameters $d$? If $d \lesssim 10^4$, Newton or L-BFGS may be viable. If $d \gtrsim 10^7$, stick to first-order methods.
3. Is the gradient stochastic? If yes, SGD/Adam with appropriate step sizes. If deterministic (e.g., simulation-based), consider BFGS.
4. Is there a finite-sum structure with moderate $n$? SVRG or SAGA may accelerate SGD.
5. Is generalisation a concern? Consider SAM, especially with large batches.
6. Are there multiple coupled blocks? ADMMAlternating Direction Method of Multipliers may decompose the problem naturally.
7. Do you need a certificate (optimality gap, dual bound)? Only convex problems provide reliable certificates — that is a structure-path advantage.

Bridge Out#

This course sits at the intersection of two traditions:

• Convex optimisation (Boyd): structured, certifiable, exact. The language of KKT, duality, and cones is the lingua franca of operations research, control theory, and any domain where a guarantee matters more than scale.

• ML training (Bottou, Nesterov, modern deep learning): stochastic, nonconvex, scale-first. The toolkit of SGDStochastic Gradient Descent, adaptive methods, variance reduction, and sharpness-aware training runs the largest models ever built.

What transfers forward:

• RL policy gradients: REINFORCE and PPO gradients are stochastic and high-variance — the variance reduction ideas from Week 9 apply, and the step-size tuning lessons from intermediate Optim transfer directly.
• Generative model training: Diffusion models and VAEs are trained with Adam on massive datasets — the large-batch and sharpness discussions from Weeks 10 and 12 are immediately relevant.
• Any ML project: The checklist above applies every time you start a new training run. Diagnose before you optimise.

The goal of this capstone — and this course — is not to make you an expert in every method, but to give you a mental map. When you encounter a hard optimisation problem, you now know which region of the map to zoom into.

Browser lab#

A dual dashboard: (1) Spectral PSD projection — check whether a nearly-PSD matrix is feasible for an SDP and measure the projection residual. (2) Train a small nonconvex model with GD vs SAM-style steps; report final loss and a sharpness proxy (max loss increase in a random direction within radius $\rho$).

import numpy as np

# --- Part 1: SDP feasibility / PSD projection ---
np.random.seed(123)
n = 5
M = np.random.randn(n, n)
M = M + M.T  # symmetric

# Make M nearly but not quite PSD by shifting eigenvalues
evals, evecs = np.linalg.eigh(M)
evals_shifted = evals.copy()
evals_shifted[0] = -0.5  # one negative eigenvalue
M_indef = evecs @ np.diag(evals_shifted) @ evecs.T

print("=== Part 1: SDP feasibility / PSD projection ===")
evals_indef = np.linalg.eigvalsh(M_indef)
print(f"Original eigenvalues: {np.round(evals_indef, 4)}")
print(f"PSD? {np.all(evals_indef >= -1e-10)}")

# Project onto PSD cone
evals_pos = np.maximum(evals_indef, 0)
M_proj = evecs @ np.diag(evals_pos) @ evecs.T
residual = np.linalg.norm(M_indef - M_proj, 'fro')
print(f"Projection residual ||M - proj(M)||_F: {residual:.4f}")
print(f"Projected eigenvalues: {np.round(np.linalg.eigvalsh(M_proj), 4)}")
print(f"Projected matrix is PSD: {np.all(np.linalg.eigvalsh(M_proj) >= -1e-10)}")

# --- Part 2: Sharpness proxy on a small nonconvex model ---
print("\n=== Part 2: GD vs SAM on nonconvex problem ===")

def model(w, x):
    return w[0] * x**3 + w[1] * x**2 + w[2] * x + w[3]

def loss_fn(w, X, y):
    pred = model(w, X)
    return 0.5 * np.mean((pred - y)**2)

def grad_fn(w, X, y):
    pred = model(w, X)
    err = pred - y
    n = len(X)
    return np.array([
        np.mean(err * X**3),
        np.mean(err * X**2),
        np.mean(err * X),
        np.mean(err)
    ])

def sharpness_proxy(w, X, y, rho=0.1, n_dir=100):
    """Estimate max loss increase in a rho-ball via random directions."""
    L0 = loss_fn(w, X, y)
    max_inc = 0.0
    for _ in range(n_dir):
        d = np.random.randn(len(w))
        d = d / (np.linalg.norm(d) + 1e-12)
        L_pert = loss_fn(w + rho * d, X, y)
        max_inc = max(max_inc, L_pert - L0)
    return max_inc

# Generate synthetic data
np.random.seed(42)
X = np.random.uniform(-2, 2, 200)
w_true = np.array([0.3, -1.5, 0.5, 2.0])
y = model(w_true, X) + 0.3 * np.random.randn(200)

eta = 0.02
rho_sam = 0.1
n_steps = 500

# GD
w_gd = np.array([0.0, 0.0, 0.0, 0.0])
for _ in range(n_steps):
    w_gd = w_gd - eta * grad_fn(w_gd, X, y)

# SAM
w_sam = np.array([0.0, 0.0, 0.0, 0.0])
for _ in range(n_steps):
    g = grad_fn(w_sam, X, y)
    eps_dir = g / (np.linalg.norm(g) + 1e-12)
    g_sam = grad_fn(w_sam + rho_sam * eps_dir, X, y)
    w_sam = w_sam - eta * g_sam

loss_gd = loss_fn(w_gd, X, y)
loss_sam = loss_fn(w_sam, X, y)
sharp_gd = sharpness_proxy(w_gd, X, y, rho=0.1)
sharp_sam = sharpness_proxy(w_sam, X, y, rho=0.1)

print(f"GD  final: loss={loss_gd:.6f}, sharpness proxy={sharp_gd:.6f}")
print(f"SAM final: loss={loss_sam:.6f}, sharpness proxy={sharp_sam:.6f}")
print(f"SAM loss vs GD: {loss_sam - loss_gd:+.6f}")
print(f"SAM sharpness vs GD: {sharp_sam - sharp_gd:+.6f} (negative = flatter)")