Optimization Seminar: Yurii Nesterov

Title: Universal Newton Method

Abstract: 

In this talk we present a second-order method for unconstrained minimization of convex functions. It can be applied to functions with Holder continuous Hessians. Our main scheme is the Cubic Regularization of Newton Method, equipped with a special line-search procedure. We show that the global rate of convergence of this scheme depends continuously on the smoothness parameter. Thus, our method can be used even for minimizing functions with discontinuous Hessians. At the same time, the line-search procedure is very efficient: the average number of calls of oracle per iteration is equal to two. We show that for finding a point with small norm of the gradient, the Universal Newton Method must be equipped with a special termination criterion for the line-search, which can be seen as a generalization of Armijo condition.