Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
This provides a theoretical foundation for using Newton's method in non-strongly convex settings, potentially benefiting optimization in machine learning applications like logistic regression.
The paper tackles the problem of Newton's method requiring strong convexity or Lipschitz gradients for global linear convergence, showing it converges linearly for functions with stable Hessians, such as logistic regression, even with approximate Hessians and subproblem solutions.
We show that Newton's method converges globally at a linear rate for objective functions whose Hessians are stable. This class of problems includes many functions which are not strongly convex, such as logistic regression. Our linear convergence result is (i) affine-invariant, and holds even if an (ii) approximate Hessian is used, and if the subproblems are (iii) only solved approximately. Thus we theoretically demonstrate the superiority of Newton's method over first-order methods, which would only achieve a sublinear $O(1/t^2)$ rate under similar conditions.