Journal
MATHEMATICAL PROGRAMMING
Volume 178, Issue 1-2, Pages 327-360Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-018-1293-1
Keywords
Smooth convex optimization; Oracle complexity
Ask authors/readers for more resources
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 bounds on the oracle complexity of such methods for smooth convex functions, or equivalently, the worst-case number of iterations required to optimize such functions to a given accuracy. In particular, these bounds indicate when such methods can or cannot improve on gradient-based methods, whose oracle complexity is much better understood. We also provide generalizations of our results to higher-order methods.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available