  Optimization is important in machine learning problems, and quasi-Newton
methods have a reputation as the most efficient numerical schemes for smooth
unconstrained optimization. In this paper, we consider the explicit superlinear
convergence rates of quasi-Newton methods and address two open problems
mentioned by Rodomanov and Nesterov. First, we extend Rodomanov and Nesterov's
results to random quasi-Newton methods, which include common DFP, BFGS, SR1
methods. Such random methods adopt a random direction for updating the
approximate Hessian matrix in each iteration. 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.
