University of Michigan - Ann Arbor

San Diego State University

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})}$$

Conjugate Gradients

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Deep Learning

Algorithm of The Conjugate Gradient Method

If the objective is not assured to be quadratic, it is not guaranteed the conjugate directions stay at the minimum for previous directions. Therefore, the nonlinear conjugate gradients algorithm resets occasionally when the conjugate gradients method restarts the line search. To make the best of nonlinear conjugate gradients, we can initialize the optimization with stochastic gradient descent for a few iterations.

Learn Before

Related