Quasi-Newton method derivation

Quasi-Newton equation

$$\nabla f(x_k) = \nabla f(x_{k + 1}) + G_{k+1} (x_k - x_{k+1})\\ It feels like it can be regarded as a secant method$$

BFGS method

BFGS is a kind of quasi-Newton method, which mainly uses curvature information to preprocess the gradient to determine the descent direction.

Curvature information is obtained by maintaining a Hessian matrix about the loss function that is gradually approximated using the generalized secant method.

Approximation and Correction

Let $G_{k+1} \approx B_{k+1}$, that is to say, the data calculated using the "secant method" approximates the Hessian matrix. Since it is an approximation, there must be an error. Let's try to correct this error.

$$B_{k+1} = B_k + \nabla B_k\\ (B_{k} is calculated by the secant method)$$

Of course, this is just an assumption. Whether the assumption can really be corrected in this way requires further calculations.

A very interesting feature is: the constructed approximate Hessian matrix $B_k$ must be positive definite;

In Newton's method, if the Hessian matrix is not positive definite, then the objective function does not necessarily decrease. Only positive definite will definitely decrease. The quasi-Newton method just avoids this problem. Since it must be positive definite, the objective function must decrease.

For convenience of description, remember:

$$s_k = x_{k + 1} - x_k\\ y_k = g_{k + 1} - g_k$$

Then there are:

$$y_k = B_{k+1}s_k$$

Decompose $\nabla B_k$:

$$\nabla B_k = a u_ku_k^T + \beta v_kv_k^T$$

As long as the two vectors $u and v$ are solved, then $\nabla B_k$ can be calculated, then $B_{k + 1}$ can be calculated.

Easy to know:

$$\begin{align*} y_k &= B_{k + 1}s_k\\ &= (B_{k} + \nabla B_k)s_k\\ &= (B_k + au_ku_k^T + \beta v_kv_k^T)s_k\\ &= B_ks_k + (au_k^Ts_k)u_k + (\beta v_k^T s_k) v_k\\ \Rightarrow & y_k - B_ks_k = (au_k^T s_k)u_k +(\beta v_k^T s_k)v_k \end{align*}$$

It can be found that this equation is very broad and can solve many solutions. You might as well try a special case (really a random guess condition):

$$au_k^T s_k = 1, \beta v_k^T s_k = -1$$

Then we can derive:

$$u_k = y_k , v_k = B_k s_k$$

As long as a solution can be found, some additional conditions are introduced here, and a pretty good recursion result is obtained. Keep pushing:

$$a = \frac{1}{u_k^T s_k} = \frac{1}{y_k^T s_k}\\ \beta = - \frac{1}{v_k^T s_k} = -\frac{1}{s_k^T B_k s_k}$$

After the push is completed, the final iteration formula is obtained by merging:

$$B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{B_k s_k s_k^T B_k}{s_k B_k s_k}$$

Since the direction of Newton's method is $-H_{k+1}^{-1}g_k$, it is best to directly find the inverse of the Hessian matrix, which is obtained according to the Sherman-Morrison formula:

$$B_{k+1}^{-1} = B_{k}^{-1} + \left(\frac{1}{s_k^T y_k} + \frac{y_k^T B_k^{-1}y_k}{(s_k^T y_k)^2}\right)s_k s_k^T - \frac{1}{s_k^T y_k}(B_k^{-1} y_k s_k^T + s_k y_k^T B_{k}^{-1})$$

Pseudocode

Set the starting point ${\displaystyle \mathbf {x} _{0}}$ and the initial Hessian matrix ${\displaystyle B_{0}}$, repeat the following steps, ${\displaystyle \mathbf {x} _{k}}$ will converge to the solution of the problem:

1. Obtain the descending direction ${\displaystyle \mathbf {p} _{k}}$ by solving the equation ${\mathbf {p} _{k}=-\displaystyle B_{k}\nabla f(\mathbf {x} _{k})}$.

2. Perform a one-dimensional optimization line search in the ${\displaystyle \mathbf {p} _{k}}$ direction to find the appropriate step size ${\displaystyle \alpha _{k}}$. If the search is complete, then ${\displaystyle \alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ . In practice, an incomplete search is generally sufficient, in which case ${\displaystyle \alpha _{k}}$ only requires that ${\displaystyle \alpha _{k}}$ satisfy the Wolfe condition.

3. Let ${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$, and let ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}.$ (very normal gradient iteration)

4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$ (save the gradient change after iteration)

5. $B_{k+1} = B_{k} + \left(\frac{1}{s_k^T y_k} + \frac{y_k^T B_ky_k}{(s_k^T y_k)^2}\right)s_k s_k^T - \frac{1}{s_k^T y_k}(B_k y_k s_k^T + s_k y_k^T B_{k})$ ($B_k$ here is the inverse of the approximate Hessian matrix)

${\displaystyle f(\mathbf {x} )}$ represents the objective function to be minimized. Convergence can be judged by checking the norm of the gradient ${\displaystyle ||\nabla f(\mathbf {x} _{k})||}$. If ${\displaystyle B_{0}}$ is initialized to ${\displaystyle B_{0}=I}$, the first step will be equivalent to gradient descent, but the subsequent steps will be regulated by ${\displaystyle B_{k}}$ that is approximately a Hessian matrix.

L-BFGS

Benefits of BFGS

It is easy to know that Newton's method actually requires that the initial iteration point and the optimal point are relatively close, otherwise it may converge to other minimum points, so there is such a thing as Newton's fractal.

Well, since the quasi-Newton method is not a complete Newton method, that is to say, its convergence situation does not need to be limited to "closer to the optimal point". In fact, the concept of "very close to the optimal point" is inherently imaginary, so the quasi-Newton method has the convergence speed of the Newton method without so restricting the use area. This is the benefit of BFGS.

Disadvantages of BFGS and L-BFGS

As a Newton method, BFGS needs to save a Hessian matrix for each iteration, with a space complexity of $O(n^2)$. This makes Newton's method (such as BFGS) unable to be applied to modern neural network models with millions of parameters.

If there is a problem, there is a solution, so there is L-BFGS

L-BFGS full name is storage limited BFGS, L refers to limited memory

A very important point in L-BFGS is: the iteration initial value is set to identity matrix

The iteration formula is the same as BFGS:

$$B_{k+1}^{-1} = B_{k}^{-1} + \left(\frac{1}{s_k^T y_k} + \frac{y_k^T B_k^{-1}y_k}{(s_k^T y_k)^2}\right)s_k s_k^T - \frac{1}{s_k^T y_k}(B_k^{-1} y_k s_k^T + s_k y_k^T B_{k}^{-1})$$

~~But, in BFGS, only $s_k and y_k$ are calculated each time, and only $B_{k}^{-1}$ is retained each time, but this $B_{k}^{-1}$ is very large and difficult to save. ~~

(The above statement may or may not be reasonable. My mind is a little confused now)

In order to calculate $B_{k}^{-1}$, it is no longer the sum of all previous $s_k, y_k$ operations, but the most recent m times (this m is artificially specified)

At the k-th iteration, the algorithm obtains $x_k$, and the saved curvature information is $s_i,yi_{(k−1)...(k−m)}$. In order to obtain $H_k$, each iteration of the algorithm needs to select an initial matrix $H_k^0$. This is different from the BFGS algorithm. Next, only the nearest m vectors are used to modify the initial matrix. In practice, the setting of $H^0_k$ is usually as follows:

$$H_k^0 = r_k E\\ r_k = \frac{s_k - 1^T y_{k-1}}{y_{k -1}^T y_{k-1}}$$

Among them, $r_k$ represents the proportion coefficient, which uses the latest curvature information to estimate the size of the real Hessian matrix. This makes the search direction of the current step more ideal and does not run "too far", thus eliminating the step of step search and saving time.

In the L-BFGS algorithm, the method of updating the approximate matrix by saving the curvature information of the last m times is very effective in practice. Although the L-BFGS algorithm is linearly convergent, the cost of each iteration is very small, so the execution speed of the L-BFGS algorithm is still very fast, and since each iteration can guarantee the positive definiteness of the approximate matrix, the robustness of the algorithm is still very strong.

Summary

To summarize the differences between BFGS and L-BFGS:

• When the BFGS algorithm is running, each iteration needs to save an $n×n$ matrix. Nowadays, many machine learning problems are high-dimensional. When n is large, the memory occupied by this matrix is very alarming, and the amount of calculation required is also very large, which makes the traditional BFGS algorithm very unsuitable. L-BFGS is an improved version of this problem. As can be seen from the above, the BFGS algorithm uses the curvature information $(sk,yk)$ to correct $H_k$ to obtain $H_{k+1}$.

• The main idea of the L-BFGS algorithm is: the algorithm only saves the curvature information of the last m iterations to calculate $H_{k+1}$. In this way, the storage space we need changes from $n×n$ to $2m×n$ and usually m<<n .