Explicit Convergence Rates of Greedy and Random Quasi-Newton Methods.

In this paper, we consider quasi-Newton methods and solve two open problems mentioned in Rodomanov and Nesterov's discussion section. First, we extent Rodomanov and Nesterov's results to random general quasi-Newton methods, which include common DFP, BFGS, SR1 methods. Such random methods adopt a random direction for updating the approximate Hessian matrix. Second, we focus on the specific quasi-Newton methods: SR1 and BFGS methods. We provide improved versions of greedy and random methods with provable better explicit (local) superlinear convergence rates. Our analysis is closely related to the approximation of a given Hessian matrix, unconstrained quadratic objective, as well as the general strongly convex, smooth, and strongly self-concordant functions.