Axel Olsson: Convergence Analysis of Quasi Newton methods and on the relation to Conjugate Gradient

Abstract

This thesis investigates the convergence properties of a quasi Newton optimization method called mL-BFGS. A proof
of global convergence under the standard assumptions for quasi Newton methods is presented. A new theoretical result
is presented that extends the previous known relation between quasi Newton methods and Conjugate Gradient method.
It shows in particular that if the memory of L-BFGS is defined to the number of unique eigenvalues of a strongly convex
quadratic functions Hessian, and exact line search is used, the L-BFGS have identical iterates as Conjugate Gradient,
for a certain initialization.

The convergence properties of the mL-BFGS algorithm is analyzed analytically as well as through numerical
experiments. The experiments include comparisons with other popular first order methods, Nesterov’s Accelerated
Gradient Descent and the Heavy Ball method. The experiments focuses on how the methods compare, especially when
the gradients are inexact, where artificial noise has been added to the exact gradient. The results of the experiments
shows that momentum has a positive effect on convergence when inexact gradients are used, providing a more robust
behavior compared with the other methods. Furthermore, the experiments show that the mL-BFGS is also more stable
for problems where the Hessian is ill-conditioned and the gradients are inexact. This shows potential for the mL-BFGS
in large scale stochastic optimization, where the gradients are approximated, which introduces noise.