https://machinelearningmastery.com/bfgs-optimization-in-python/

University of Michigan - Ann Arbor

- Broyden-Fletcher-Goldfarb-Shanno algorithm attempts to bring some of the advantages of Newton's method without the computational burden, referred to as Quasi-Newton Methods.
- A limitation of Newton’s method is that it requires the calculation of the inverse of the Hessian matrix. This is a computationally expensive operation and may not be stable depending on the properties of the objective function.
- Quasi-Newton methods are second-order optimization algorithms that approximate the inverse of the Hessian matrix using the gradient, meaning that the Hessian and its inverse do not need to be available or calculated precisely for each step of the algorithm.

BFGS Optimization Algorithm

- Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the family of quasi-Newton methods that approximates the Broyden–Fletcher–Goldfarb–Shanno algorithm (BFGS) using a limited amount of computer memory. 
- Like the original BFGS, L-BFGS uses an estimate of the inverse Hessian matrix to steer its search through variable space, but where BFGS stores a dense n X n approximation to the inverse Hessian (n being the number of variables in the problem), L-BFGS stores only a few vectors that represent the approximation implicitly. 

Limited-memory BFGS

- Recall that Newton's update is given by 
   $\theta^\ast=\theta_0-H^{-1}\nabla_{\theta}J(\theta_0)$ 
    where H is the Hessian of J with respect to $\theta$ evaluated at $\theta_0$. 
- The approach adopted by BFGS algorithm is to approximate the inverse with a matrix $M_t$ that is iteratively refined by low-rank updates to become a better approximation of $H^{-1}$.
- Once the inverse Hessian approximation $M_t$ is updated, the direction of descent $\rho_t$ is determined by $\rho_t=M_tg_t$. 
- A line search is performed in this direction to determine the size of the step, $\epsilon^{\ast}$, taken in this direction. The final update to the parameters is given by: $\theta_{t+1}=\theta_t + \epsilon^{\ast}\rho_t$.


Learn Before

Related