Beyond Gradient Descent

Why bother going beyond SGD?

SGD with momentum is the workhorse of deep learning because (a) it scales — one gradient evaluation per step is cheap, (b) noise is a feature, not a bug, on a single-pass training run, and (c) the implicit regularisation of small batches gives free generalisation. Adam and its cousins (AdamW, Lion, Sophia) inherit those advantages and add adaptive per-parameter learning rates.

But: SGD throws away two things.

• Curvature. The Hessian tells you the local geometry — directions where the loss is steep (small step) vs flat (big step). SGD ignores it entirely. On a quadratic with condition number $\kappa$, SGD needs $O(\kappa \log \tfrac{1}{\varepsilon})$ steps; Newton needs $\log\log \tfrac{1}{\varepsilon}$.
• Cross-parameter geometry. Adam's diagonal preconditioner ignores correlations. Natural-gradient methods (K-FAC, Shampoo) recover them block-wise.

When are these worth paying for? When (i) you can afford full-batch or large-batch gradients, (ii) the dimensionality is small enough to store/invert curvature, or (iii) you have no gradient at all and must fall back to function-value methods like CMA-ES and SPSA.

The five contenders

• Newton's method. Use the Hessian $H$ and step $-H^{-1}\nabla f$. Quadratic local convergence. Cost: forming $H$ in $O(d^2)$ and inverting in $O(d^3)$. Impractical for $d$ > ~$10^4$.
• BFGS / L-BFGS. Maintain a low-rank approximation of $H^{-1}$ from past gradients. The workhorse for medium-scale (<1M parameter) DL. scipy.minimize's default; jax.scipy.optimize ships it.
• Natural gradient. Step $-F^{-1}\nabla f$ where $F$ is the Fisher information matrix. Invariant to reparameterisation; the heart of K-FAC and Shampoo. Beats Adam on RNNs / GANs in many settings.
• CMA-ES (evolutionary). Sample a population from a Gaussian; update the mean and covariance toward the best samples. Gradient-free, robust to noise; standard in RL hyperparameter search.
• SPSA (gradient-free finite-difference). Perturb all parameters once with random ±1, estimate the gradient with a single 2-evaluation finite difference. Optimal when only function values are available.

Newton's method, in two lines

Taylor-expand the loss around the current iterate $w_t$:

Minimise this quadratic in $\Delta w$ by setting its gradient to zero. Solving gives $\Delta w = -H^{-1}\nabla f$, which is the Newton step. On a perfect quadratic, one step reaches the optimum; on a smooth function, the rate is quadratic — the error squares each iteration. In practice you must damp: $w_{t+1} = w_t - \alpha_t H^{-1}\nabla f$ with $\alpha_t$ from a line search, and stabilise the Hessian with $H + \lambda I$ when it's not positive-definite (Levenberg–Marquardt).

BFGS — the rank-2 secret to L-BFGS

BFGS maintains a Hessian-inverse approximation $B$ that gets better every step. After observing the step $s_t = w_{t+1} - w_t$ and gradient change $y_t = \nabla f_{t+1} - \nabla f_t$, it updates $B$ by a rank-2 perturbation:

Two properties make this magical:

• Secant condition. The update satisfies $B_{t+1} y_t = s_t$ — i.e. it correctly predicts the curvature you just observed.
• Positive-definiteness preserved. If $B_t \succ 0$ and $s_t^\top y_t > 0$ (curvature condition), then $B_{t+1} \succ 0$.

L-BFGS stores only the last $m$ pairs $(s_t, y_t)$ (typically $m=10$) instead of the full matrix, applying $B \nabla f$ via a two-loop recursion in $O(md)$ time. That's why it scales to millions of parameters when full Newton can't.

Natural gradient — geometry of probability

For a probabilistic model $p_\theta(x)$, the natural gradient preconditions the ordinary gradient with the inverse Fisher information matrix:

The Fisher $F$ is the Hessian of the KL divergence to the current model. Stepping along $-F^{-1}\nabla L$ keeps the KL change between consecutive iterates bounded — the step becomes geometry-aware in the manifold of distributions. Concrete consequences:

• Reparameterisation invariance. If you change the parameter coordinates, the natural-gradient update transforms the same way the parameters do, so the actual update on the distribution is the same. Vanilla gradient is not invariant; this is why SGD is so sensitive to choice of activation scales.
• K-FAC. Approximates $F$ as block-diagonal with Kronecker-factored blocks, making the inverse tractable for big nets. Adopted in older DeepMind RL papers; Shampoo (Anil et al., 2020) is the modern descendant, used in some 2024–2025 LLM pretraining runs.
• TRPO / NPG. Trust-region policy optimisation is natural-gradient policy improvement — still the cleanest derivation of why on-policy RL needs a KL constraint.

Race them on a 2-D loss

Gradient-free: CMA-ES and SPSA

Suppose you can compute $f(w)$ but not $\nabla f(w)$. This is the regime for RL hyperparameter search, simulator-based design, hardware-in-the-loop tuning, and certain quantum experiments. Two algorithms dominate.

CMA-ES (Covariance Matrix Adaptation Evolution Strategy). Maintain a Gaussian search distribution $\mathcal{N}(m_t, \sigma_t^2 C_t)$. At each generation:

• Sample a population of $\lambda$ candidates;
• Evaluate $f$ at each; sort by fitness;
• Recombine the top $\mu$ to form the new mean $m_{t+1}$;
• Adapt $\sigma_t$ (step size) based on the cumulative evolution path's length;
• Adapt $C_t$ to align with successful directions.

The adaptive covariance is what makes CMA-ES competitive — it learns the local conditioning from successes and failures without computing a Hessian.

SPSA (Simultaneous Perturbation Stochastic Approximation). Pick a random $\pm 1$ vector $\Delta_t$ (Rademacher); evaluate $f$ at $w_t \pm c_t \Delta_t$; estimate the gradient with a single 2-point finite difference:

Two function evaluations per step, regardless of dimension. That's the magic: where ordinary finite differences cost $2d$ evaluations, SPSA pays a fixed 2. The trade-off is variance: you need many steps and shrinking $a_t, c_t$ to converge, but the per-step cost is dimension-independent.

When to use what

• L-BFGS. Smooth full-batch losses up to ~1M parameters. Typical use: physics-informed nets, small-data fine-tunes, numerical methods.
• K-FAC / Shampoo (natural gradient). Big nets, stable training. Adopted by labs running very-large LLMs and RNNs where Adam plateaus.
• CMA-ES. Black-box hyperparameter search; reward-shaped RL; tasks where the gradient is noisy or unavailable.
• SPSA. Hardware-in-the-loop tuning, simulator-based design where every evaluation is a forward simulation. Quantum-circuit optimisation popularised it.
• Stick with SGD/Adam. Mini-batch DL with millions of parameters and a stochastic gradient. Cost of computing $H$ exceeds the gain.

Comparison table

Practical recipes

• Physics-informed nets, neural PDEs. Use L-BFGS for the final tightening after a few thousand Adam steps — Adam reaches the basin, L-BFGS finishes the descent inside it. This is the standard PINN recipe.
• Large-scale RL. Natural-gradient TRPO for stability; PPO is the cheaper first-order approximation with a clipped KL surrogate. Use Shampoo if you can afford it on the policy network.
• Hyperparameter / architecture search. CMA-ES if you have a few dozen continuous hyperparameters and can afford $\sim 100$ evaluations. Bayesian optimisation for fewer evaluations on cheaper-to-evaluate spaces.
• Quantum / analog hardware. SPSA is the standard variational-quantum-eigensolver (VQE) optimiser precisely because each "evaluation" requires running a quantum circuit.
• LLM pretraining. Stay with AdamW (or Lion) unless you've measured a real benefit from Shampoo. The bookkeeping for second-order methods at LLM scale is non-trivial.

Reading list

• Nocedal & Wright, Numerical Optimization, 2nd ed. The standard reference for Newton, BFGS, line search, trust regions.
• Amari (1998) — Natural Gradient Works Efficiently in Learning. The paper that started the natural-gradient line.
• Martens & Grosse (2015) — Optimizing Neural Networks with Kronecker-factored Approximate Curvature (K-FAC).
• Anil, Gupta, Koren, Singer (2020) — Shampoo: Preconditioned Stochastic Tensor Optimization. Modern second-order for big nets.
• Hansen (2016) — The CMA Evolution Strategy: A Tutorial. The reference for CMA-ES.
• Spall (1992) — Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation. The original SPSA paper.