Learn Before
Concept

Broyden-Fletcher-Goldfarb-Shanno Algorithm Update Rule

Recall that Newton's update is given by θ=θ0H1θJ(θ0)\theta^\ast=\theta_0-H^{-1}\nabla_{\theta}J(\theta_0) where HH is the Hessian of JJ with respect to θ\theta evaluated at θ0\theta_0.

The approach adopted by the BFGS algorithm is to approximate the inverse with a matrix MtM_t that is iteratively refined by low-rank updates to become a better approximation of H1H^{-1}.

Once the inverse Hessian approximation MtM_t is updated, the direction of descent ρt\rho_t is determined by ρt=Mtgt\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: θt+1=θt+ϵρt\theta_{t+1}=\theta_t + \epsilon^{\ast}\rho_t.

0

1

Updated 2026-06-07

Tags

Data Science