While second-order optimization algorithms, such as Newton's Method, offer the theoretical advantage of using curvature to determine step sizes, they are generally impractical for deep neural networks. The primary limitation is the prohibitive computational cost associated with the Hessian matrix, $$\mathbf{H}$$. For a model with $$d$$ parameters, the Hessian requires storing $$\mathcal{O}(d^2)$$ entries, and computing it via backpropagation is excessively expensive, making the direct application of pure second-order methods infeasible for large-scale deep learning tasks.

Claude

First-order optimization algorithms rely solely on the value and gradient of the objective function. In contrast, second-order optimization algorithms also utilize information about the function's curvature, often represented by the Hessian matrix. By accounting for curvature, these methods can automatically adjust the optimization step, providing a way to circumvent the difficulties of manually tuning a learning rate.

Second-Order Optimization Algorithm

Dive into Deep Learning

Newton's Method is a second-order optimization algorithm that relies on the second-order Taylor expansion of a multivariate function $$f(\mathbf{x})$$. By taking the expansion $$f(\mathbf{x} + \boldsymbol{\epsilon}) = f(\mathbf{x}) + \boldsymbol{\epsilon}^	op 
abla f(\mathbf{x}) + \frac{1}{2} \boldsymbol{\epsilon}^	op \mathbf{H} \boldsymbol{\epsilon} + \mathcal{O}(\|\boldsymbol{\epsilon}\|^3)$$, where $$\mathbf{H} = 
abla^2 f(\mathbf{x})$$ is the Hessian matrix, and setting the derivative with respect to the update step $$\boldsymbol{\epsilon}$$ to zero ($$
abla f(\mathbf{x}) + \mathbf{H} \boldsymbol{\epsilon} = 0$$), the algorithm derives the optimal update step as $$\boldsymbol{\epsilon} = -\mathbf{H}^{-1} 
abla f(\mathbf{x})$$. This approach requires computing and inverting the Hessian matrix to directly jump toward the function's minimum.

Newton's Method

The Conjugate Gradients is a method faster than the method of steepest descent, and it avoids calculation of the inverse Hessian required by Newton's Method. 
Instead of undoing direction search progress made previously and recalculating each step, the method of conjugate gradients looks for a search direction that is conjugate to the previous line search direction.

At t iteration, the next search direction is:
$$d_t = \nabla _\theta f(\theta) + \beta _t d_{t-1}$$
Where $\beta _t$ is a coefficient that controls the direction.
Two popular ways to calculate $\beta _t$ are:
Fletcher-Reeves:
$$\beta _t = \frac{\nabla _\theta f(\theta _t)^\top \nabla _\theta f(\theta _t)}{\nabla _\theta f(\theta _{t-1})^\top \nabla _\theta f(\theta _{t-1})}$$
Polak-Ribière:
$$\beta _t = \frac{(\nabla _\theta f(\theta _t) - \nabla_\theta f(\theta _{t-1}))^\top \nabla _\theta f(\theta _t)}{\nabla _\theta f(\theta _{t-1})^\top \nabla _\theta f(\theta _{t-1})}$$

Learn Before

Related