Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients

Abstract

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.

19 pages

References in corpus (1)

• Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Cited by in corpus (12)

• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• Acceleration with a Ball Optimization Oracle
• Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses
• Deterministic Inequalities for Smooth M-estimators
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• Convex optimization based on global lower second-order models
• Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization
• RSN: Randomized Subspace Newton
• Asynchronous Parallel Stochastic Quasi-Newton Methods
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters