Quasi-Newton Methods: Approximating the Hessian

As we saw with Newton's method, incorporating curvature information via the Hessian matrix can significantly accelerate convergence towards a minimum. However, the practical application of Newton's method in large-scale machine learning often hits a wall due to the computational burden of forming and inverting the Hessian matrix at every iteration. For a model with $N$ parameters, the Hessian is an $N \times N$ matrix, requiring $O(N^2)$ storage and typically $O(N^3)$ computation to invert. When $N$ is in the millions or billions, this becomes completely infeasible.

This is where Quasi-Newton methods come into play. They offer a clever compromise: retain the superlinear convergence benefits associated with second-order information without explicitly computing, storing, or inverting the Hessian. The central idea is to build up an approximation of the Hessian, or more commonly, its inverse, using only information from successive gradient evaluations and parameter updates.

The Core Idea: Iterative Approximation

Instead of calculating $\nabla^2 f(x_k)$ directly, Quasi-Newton methods maintain a matrix $B_k$ that approximates the Hessian $\nabla^2 f(x_k)$, or a matrix $H_k$ that approximates the inverse Hessian $(\nabla^2 f(x_k))^{-1}$. The update step then looks similar to Newton's method, but uses the approximation:

• Using Hessian approximation $B_k$: Solve $B_k p_k = -\nabla f(x_k)$ for the search direction $p_k$, then update $x_{k+1} = x_k + \alpha_k p_k$.
• Using inverse Hessian approximation $H_k$: Directly compute the search direction $p_k = -H_k \nabla f(x_k)$, then update $x_{k+1} = x_k + \alpha_k p_k$.

The matrix $H_k$ is often preferred in practice as it avoids solving a linear system at each step, replacing it with a simpler matrix-vector multiplication. The step size $\alpha_k$ is usually determined by a line search procedure, ensuring sufficient decrease in the objective function.

The Secant Condition: Linking Gradients to Curvature

How is the approximation $B_k$ or $H_k$ updated from one iteration to the next? The essence lies in the secant condition (also known as the Quasi-Newton condition).

Let's define the change in parameters and gradients between two iterations:

$$s_k = x_{k+1} - x_k$$ $$y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$$

Recall from calculus that for a quadratic function, the Hessian relates the change in gradient to the change in position: $\nabla f(x_{k+1}) - \nabla f(x_k) = \nabla^2 f (x_{k+1} - x_k)$. Quasi-Newton methods enforce a similar relationship for the next approximation, $B_{k+1}$. We require that the new approximation correctly maps the step just taken ($s_k$) to the observed change in gradient ($y_k$):

$$B_{k+1} s_k = y_k \quad \text{(Secant condition for Hessian approximation)}$$

Equivalently, if we are approximating the inverse Hessian $H_k$, the condition becomes:

$$H_{k+1} y_k = s_k \quad \text{(Secant condition for inverse Hessian approximation)}$$

This condition uses the readily available gradient information ($y_k$) and parameter change ($s_k$) from the latest step to impose a constraint on the updated approximation. It effectively incorporates information about the function's curvature along the direction $s_k$.

Updating the Approximation Matrix

The secant condition provides one constraint, but it doesn't uniquely determine the entire matrix $B_{k+1}$ or $H_{k+1}$. Different Quasi-Newton methods arise from different choices for how to update the matrix while satisfying the secant condition. Generally, the update is formulated as adding a low-rank correction to the current approximation:

$$B_{k+1} = B_k + \Delta B_k$$ $$H_{k+1} = H_k + \Delta H_k$$

The specific form of the update term ($\Delta B_k$ or $\Delta H_k$) defines the particular algorithm. Popular choices aim to:

1. Satisfy the secant condition.
2. Maintain symmetry (since the true Hessian is symmetric).
3. Maintain positive definiteness (to ensure descent directions, especially when approximating $H_k$).
4. Be computationally inexpensive (often involving rank-one or rank-two updates).
5. Be "close" to the previous approximation $B_k$ or $H_k$ in some sense, embodying the idea of gradual refinement.

The most successful and widely used update formula resulting from these principles is the Broyden–Fletcher–Goldfarb–Shanno (BFGS) update, which we will detail in the next section. Its memory-efficient variant, Limited-memory BFGS (L-BFGS), is a workhorse algorithm for large-scale machine learning optimization problems.

In essence, Quasi-Newton methods cleverly sidestep the computational bottleneck of Newton's method by building curvature information incrementally through gradient differences. They represent a powerful class of algorithms that often converge much faster than first-order methods, especially on problems where curvature plays a significant role, without incurring the prohibitive cost of exact second-order approaches.