Newton-MR: Newton’s Method Without Smoothness or Convexity

September 17, 2019, 9:40 AM - 10:20 AM


Center Hall

Rutgers University

Busch Campus Student Center

604 Bartholomew Rd

Piscataway NJ

Click here for map.

Fred Roosta, University of Queensland

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.