Quasi-Newton methods with provable efficiency guarantees

Quasi-Newton methods are very popular in Optimization. They have a long, rich history, and perform extremely well for solving real-life problems. However, almost nothing is known about theoretical efficiency guarantees for these methods. The goal of this work is the advancement of the theory of quasi-Newton methods. This includes both obtaining new convergence estimates for the already existing algorithms and developing new methods with provable efficiency guarantees. In this thesis, we present our results in several directions. First, we provide a new theoretical analysis of local superlinear convergence of classical quasi-Newton methods and establish explicit and non-asymptotic bounds on their rate of convergence. Then, we develop and analyze new quasi-Newton methods which have some advanced features. Specifically, we propose a new family of greedy quasi-Newton methods for which, apart from local superlinear convergence, it is also possible to guarantee the convergence of Hessian approximations. Finally, we study one algorithm which is related to classical quasi-Newton methods, namely, the Ellipsoid Method, and develop a new variant of this method, which has a better dependency on the dimensionality of the problem than the standard one.