Optimization

How we actually find model parameters: gradient descent and its variants, convergence theory, and practical tricks.

Table of contents

1. First-order vs second-order methods
2. Gradient descent (batch)
3. Stochastic and mini-batch SGD
4. Momentum and Nesterov
5. Adaptive learning rate methods
6. Second-order methods (Newton, quasi-Newton)
7. Learning rate schedules
8. Convergence theory (overview)
9. Practical optimization tips
10. Coordinate descent

1. First-order vs second-order methods

Most deep learning uses first-order. Classical ML in medium-scale uses L-BFGS or IRLS.

2. Gradient descent (batch)

2.1 Algorithm

Initialize $\mathbf{w}_0$. At each step $t$:

where $\eta_t > 0$ is the learning rate (step size).

Intuition: negative gradient points in the direction of steepest decrease. GD takes a step of size $\eta_t$ in that direction.

2.2 Why step in the negative gradient direction?

First-order Taylor expansion:

To decrease $f$ most per unit of $\|\boldsymbol{\delta}\|$: choose $\boldsymbol{\delta} \propto -\nabla f(\mathbf{w})$ (steepest descent direction, from Cauchy-Schwarz).

2.3 Convergence for $L$-smooth convex functions

A function is $L$-smooth if $\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\| \leq L\|\mathbf{x}-\mathbf{y}\|$ (Lipschitz gradients, bounded curvature).

With $\eta = 1/L$:

This is $O(1/T)$ convergence — to get $\varepsilon$-accurate, need $T = O(1/\varepsilon)$ iterations.

2.4 Convergence for strongly convex functions

A function is $\mu$-strongly convex if $\nabla^2 f \succeq \mu\mathbf{I}$ everywhere ($\mu > 0$).

With step $\eta = 1/L$, GD converges linearly (exponentially fast):

Condition number $\kappa = L/\mu$: higher $\kappa$ → slower convergence. Ridge regression adds $\lambda\mathbf{I}$ which increases $\mu$ and reduces $\kappa$ → faster convergence.

2.5 Learning rate sensitivity

Optimal $\eta$ requires knowing $L$ (Lipschitz constant of gradient), which is usually estimated via line search or set empirically.

3. Stochastic and mini-batch SGD

3.1 Motivation

Batch GD evaluates $\nabla f(\mathbf{w}) = \frac{1}{n}\sum_i \nabla \ell_i(\mathbf{w})$ over all $n$ samples per step — expensive for large $n$.

Stochastic GD (SGD): use gradient of one random sample as an estimate:

$\nabla \ell_{i_t}(\mathbf{w})$ is an unbiased estimator of $\nabla f(\mathbf{w})$: $\mathbb{E}[\nabla \ell_{i_t}] = \nabla f$.

3.2 Mini-batch SGD

Compromise: use a batch of $B$ samples (batch size):

• Gradient variance: $\propto \sigma^2/B$. Larger batch → less noise → more stable updates.
• Cost per step: $O(B \cdot p)$. Number of steps to see all data once (epoch) = $n/B$.
• Hardware: larger batches allow better GPU parallelism, but may require adjusting learning rate.

Linear scaling rule: if you multiply batch size by $k$, multiply learning rate by $k$ (empirically works in certain regimes).

3.3 SGD vs batch GD tradeoffs

Noise as regularizer: SGD's gradient noise prevents convergence to sharp minima (which tend to generalize poorly) — an implicit regularization effect observed empirically.

3.4 Epoch vs iteration

• Iteration: one gradient update.
• Epoch: one full pass through the training data ($n/B$ iterations).

4. Momentum and Nesterov

4.1 SGD with momentum

Problem with vanilla SGD: slow convergence in directions with low curvature (gradient zig-zags across narrow valleys).

Momentum accumulates a velocity vector:

$\beta \in [0,1)$ is the momentum coefficient (typically 0.9). Velocity is an exponentially weighted moving average of past gradients.

Effect: accelerates in consistent directions, dampens oscillations across the valley.

Effective step size in consistent direction: if gradient is always the same $\mathbf{g}$, velocity converges to $\mathbf{v} = \frac{\eta}{1-\beta}\mathbf{g}$, so effective step = $\frac{\eta}{1-\beta}$ times the learning rate.

4.2 Nesterov accelerated gradient (NAG)

Improvement: compute gradient at the look-ahead position:

Theoretical convergence for smooth convex functions: $O(1/T^2)$ vs $O(1/T)$ for vanilla GD.

5. Adaptive learning rate methods

5.1 Motivation

Different parameters can have very different scales and gradient magnitudes. A single learning rate is suboptimal. Adaptive methods maintain per-parameter learning rates.

5.2 AdaGrad

Accumulate squared gradients:

Effect: large learning rate for infrequent (sparse) features, small for frequent ones. Good for sparse data (NLP, embeddings). Problem: $G_{t,j}$ only grows → learning rate monotonically decreases → may stop learning.

5.3 RMSProp

Fix AdaGrad's vanishing lr with exponentially decaying average:

5.4 Adam (Adaptive Moment Estimation)

Most widely used in practice. Maintains both first and second moment estimates:

First moment (mean): $\mathbf{m}_t = \beta_1 \mathbf{m}_{t-1} + (1-\beta_1)\nabla f(\mathbf{w}_t)$ Second moment (variance): $\mathbf{v}_t = \beta_2 \mathbf{v}_{t-1} + (1-\beta_2)(\nabla f(\mathbf{w}_t))^2$ (elementwise)

Bias correction (accounts for initialization at zero):

Update:

Default hyperparameters: $\eta=0.001$, $\beta_1=0.9$, $\beta_2=0.999$, $\varepsilon=10^{-8}$.

Intuition: like momentum (first moment), but adapts step size by second moment (variance of recent gradients). Large gradient variance → small step (cautious in noisy directions).

AdamW: Adam + decoupled weight decay. Standard in modern DL training. Adds $-\lambda\mathbf{w}$ to update directly (not through gradient), properly implementing L2 regularization.

5.5 Comparison table

6. Second-order methods (Newton, quasi-Newton)

6.1 Newton's method

Use quadratic approximation:

Minimize over $\boldsymbol{\delta}$: $\boldsymbol{\delta}^\star = -\mathbf{H}^{-1}\nabla f$.

Update: $\mathbf{w}_{t+1} = \mathbf{w}_t - \mathbf{H}_t^{-1}\nabla f(\mathbf{w}_t)$.

Quadratic convergence near optimum: number of correct digits roughly doubles per step.

Problem: inverting $\mathbf{H} \in \mathbb{R}^{p\times p}$ costs $O(p^3)$ — impractical for large $p$.

6.2 L-BFGS (Limited-memory BFGS)

BFGS approximates $\mathbf{H}^{-1}$ via rank-1 updates using gradient differences. L-BFGS stores only the last $m$ (typically 5–20) gradient/position pairs, costing $O(mp)$ per step.

Used in sklearn's LogisticRegression(solver='lbfgs') and scipy.optimize.minimize(method='L-BFGS-B').

6.3 IRLS (Iteratively Reweighted Least Squares)

Newton's method applied to GLMs (logistic regression) can be rewritten as a weighted least squares problem at each iteration. sklearn's LogisticRegression(solver='newton-cg').

7. Learning rate schedules

7.1 Constant learning rate

Simple, often used with Adam. May oscillate near optimum.

7.2 Step decay

Reduce lr by a factor every $k$ epochs: $\eta_t = \eta_0 \cdot \gamma^{\lfloor t/k \rfloor}$.

7.3 Exponential decay

$\eta_t = \eta_0 \cdot e^{-\lambda t}$.

7.4 Cosine annealing

Smoothly decays from \eta_\max to \eta_\min. Often paired with warm restarts (restart at peak periodically).

7.5 Linear warmup + decay

Ramp learning rate up for first few steps/epochs, then decay. Important for large-batch training and transformers.

7.6 Reduce on plateau

Reduce lr when monitored metric stops improving. keras.callbacks.ReduceLROnPlateau.

8. Convergence theory (overview)

8.1 Summary for different function classes

8.2 Saddle points in non-convex optimization

Non-convex functions (neural nets) have saddle points — zero gradient, not a minimum. Second-order methods can get stuck; SGD's noise helps escape. Saddle points are less problematic in practice than once feared (high-dimensional saddles are usually surrounded by directions that lead downward).

8.3 Local minima in neural networks

Modern evidence: many local minima in deep networks have similar (near-optimal) loss values. The harder problem is plateaus and saddle points early in training.

9. Practical optimization tips

9.1 Gradient checking

Numerically verify gradient implementation:

Use $\varepsilon \approx 10^{-5}$. Match to within relative error $< 10^{-4}$.

9.2 Feature scaling and conditioning

GD on unscaled features can be very slow: gradient points toward steepest descent direction in feature space, which may zig-zag across poorly scaled dimensions. Always scale features (StandardScaler, MinMaxScaler) before gradient-based optimization.

9.3 Gradient clipping

For exploding gradients (especially in RNNs): if $\|\nabla f\| > \text{threshold}$, scale it: $\nabla f \leftarrow \frac{\text{threshold}}{\|\nabla f\|}\nabla f$.

9.4 Initialization

Weights initialized at zero → symmetric neurons learn the same features in neural nets. Use random initialization; scale to control gradient magnitude.

9.5 Batch size and learning rate tradeoff

Large-batch training is studied in "large-batch optimization" literature.

10. Coordinate descent

Optimize one parameter (or block of parameters) at a time:

Convergence: for convex functions with separable non-smooth terms (like L1), coordinate descent with cyclic or random updates converges.

Used for: Lasso (per-coordinate soft-thresholding has closed form), SVM dual (SMO algorithm updates one pair of dual variables at a time).

# Coordinate descent for Lasso (simplified)
import numpy as np

def lasso_coordinate_descent(X, y, lam, n_iter=1000):
    n, p = X.shape
    w = np.zeros(p)
    for _ in range(n_iter):
        for j in range(p):
            r = y - X @ w + X[:, j] * w[j]  # partial residual
            z = X[:, j] @ r / n              # unconstrained update
            w[j] = np.sign(z) * max(abs(z) - lam / (2*n), 0)  # soft threshold
    return w

*File: notes/04_optimization.md — next: notes/05_evaluation_and_validation.md*