Gradient descent, Newton-like

1 General

Robert Grosse, Second-Order Optimization is a beautiful introduction as part of CSC2541 Topics in Machine Learning: Neural Net Training Dynamics. There is a whole series (Grosse 2021a, 2021b, 2021c) of IMO beautifully written lectures on this.

2 One-dimensional Newton

The basic case is simple; we get into difficulties with the multidimensional stuff in a moment. From school one might remember that classic so-called Newton method for iteratively improving a guessed location $x_k$ for a root of a 1-dimensional function $g:\mathbb{R}\to \mathbb{R}$:

$$x_{k+1}=x_k-\frac{g\left(x_k\right)}{g^{\prime }\left(x_k\right)}$$

Under the assumption that it is twice continuously differentiable, we can find stationary points—zeros of the derivative—of a function $f:\mathbb{R}\to \mathbb{R}$. (i.e. extrema and saddle points, which might in fact be minima.) $$x_{k+1}=x_k-\frac{f^{\prime }\left(x_k\right)}{f^{″}\left(x_k\right)}$$

How and why does this work again? Loosely, the argument is that we can use the Taylor expansion of a function to produce a locally quadratic model for the function, which might be not at all globally quadratic.

3 Multidimensional Newton

Returning to the objective with a multidimensional argument $f:{\mathbb{R}}^n\to \mathbb{R},$ Taylor’s theorem for twice continuously differentiable functions tells us that $$\begin{array}{rl}f(x+p)& =f(x)+{\mathrm{\nabla }}^{\mathrm{\top }}f(x+p)p+\frac{1}{2}{p}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x+p)p+p^{\mathrm{\top }}R(x+p)p\end{array}$$ and $\underset{p\to 0}{lim}R(x+p)=0$.

Putting the remainder in Cauchy form, this tells us $$f(x+p)=f(x)+\mathrm{\nabla }{f}^{\mathrm{\top }}(x)p+\frac{1}{2}{p}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x+tp)p$$ for some $t\in (0,1)$.

Generally, we might take a local quadratic model for $f$ at $x+p$ as $$\mathrm{\nabla }f(x+p)\simeq m_x(p)=f(x)+\mathrm{\nabla }{f}^{\mathrm{\top }}(x)p+\frac{1}{2}{p}^{\mathrm{\top }}{\mathrm{\nabla }}^{2}f(x)p$$ for some $t\in (0,1)$.

If we ignore some subtleties and imagined this quadratic model was true, it would have an extremum where the directional derivative of this model vanished, i.e. $ m_x(p)$ where $\mathrm{\nabla }{m}_x(p):=\mathrm{\nabla }f(x)+{\mathrm{\nabla }}^{2}f(x)p$. This would be satisfied at $$\begin{array}{rl}\mathrm{\nabla }f(x)+{\mathrm{\nabla }}^{2}f(x)p& =0\\ \mathrm{\nabla }f(x)& =-{\mathrm{\nabla }}^{2}f(x)p\\ p& =-[{\mathrm{\nabla }}^{2}f(x){]}^{-1}\mathrm{\nabla }f(x)\end{array}$$

From this we get the multidimensional Newton update rule, by choosing for each $x_k$ the locally optimal $p$ quadratic approximation: $$x_{k+1}=x_k-{\left[{\mathrm{\nabla }}^{2}f\left(x_k\right)\right]}^{-1}\mathrm{\nabla }f\left(x_k\right),n\ge 0$$

In practice the quadratic model is not true (or we would be done in one step) and we would choose a more robust method that by using a trust region or line-search algorithm to handle the divergence between the model and its quadratic approximation. Either way the quadratic approximation would be used, which would mean that the inverse Hessian matrix ${\left[{\mathrm{\nabla }}^{2}f\left(x_k\right)\right]}^{-1}$ would be important.

🏗 Unconstrained assumption, need for saddle points not just extrema with Lagrange methods, positive-definiteness etc.

4 Gauss-Newton

A reasonably clear Stackeschange answer that will do for now: Difference between Newton’s method and Gauss-Newton method.

5 Generalized Gauss-Newton

NB ⚠️⛔️☣️: This sections is vague half-arsed notes of dubious accuracy.

The generalized Gauss-Newton approximation (GGN) (Martens and Grosse 2015). replaces an expensive second order derivative by a product of first order derivatives. Used in (Foong et al. 2019; Immer, Korzepa, and Bauer 2021).

6 Fisher method

I haven’t actually worked out what this is yet, nor whether it relates or is filed correctly there. But I think that it is natural gradient descent.

7 Quasi Newton methods

Secant conditions and approximations to the Hessian. Let’s say we are designing a second-order update method. See e.g. Nocedal and Wright (2006).

In BFGS the approximate Hessian $B_k$ is used in place of the true Hessian.

Given the displacement $s_k$ and the change of gradients $y_k$, the secant equation requires that the symmetric positive definite matrix $B_{k+1}$ map $s_k$ into $y_k.$

$$H_k(x^{(k)}-x^{(k-1)})=\mathrm{\nabla }f(x^{(k)})-\mathrm{\nabla }f(x^{(k-1)})$$

… We hope to get from this the secant condition.

$$B_{k+1}{s}_k=y_k$$

TODO: compare and contrast to the Wolfe conditions on step length.

🏗

8 Hessian free

Second order optimisation that does not require the Hessian matrix to be given explicitly. I should work out the boundaries of this definition. Does it include Quasi Newton? CGD? Intersect with? Overlap? 🏗

Andre Gibiansky wrote an example for coders.

9 Stochastic

See stochastic 2nd order gradient descent for some bonus complications.

10 Incoming

• Quasi-Newton methods: L-BFGS

11 References