Fred Roosta, University of Queensland

Abstract

Establishing global convergence of the classical Newton’s method has long been limited to making restrictive assumptions on (strong) convexity as well as Lipschitz continuity of the gradient/Hessian. We show  that two simple modifications of the classical Newton’s method result in an algorithm, called Newton-MR, which is almost indistinguishable from its classical counterpart but it can readily be applied to invex problems. By introducing a weaker notion of joint regularity of Hessian and gradient, we show that Newton-MR converges even in the absence of the traditional smoothness assumptions. We then turn to theoretically study the stability of Newton-MR under Hessian perturbations, which allows one to design efficient variants for large-scale problems where the curvature information is suitably approximated.

Video