Oracle Complexity of Second-Order Methods for Smooth Convex Optimization

Yossi Arjevani, Ohad Shamir, Ron Shiff

Second-order methods, which utilize gradients as well as Hessians to optimize a given function, are of major importance in mathematical optimization. In this work, we prove tight b…