Quasi-Newton Methods

Quasi-Newton methods are a class of second-order optimization algorithms that are particularly useful when the function’s Hessian is difficult to compute or not available.

Consider the update rule of the Newton algorithm at the time $t$ as follows:

Here, $H(x)$ is the Hessian of the function $f(x)$ at the point $x$. Recall that the complexity of computing the Hessian is of the order $O(m^2)$ as opposed to the gradient, which is of the order $O(m)$. This means that as the dimensionality ($m$) of $x$ ...