Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
arXiv:1806.00413
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 rate under similar conditions.
arXiv comment19 pages
References in corpus (7)
- CoCoA: A General Framework for Communication-Efficient Distributed Optimization
- Second-Order Stochastic Optimization for Machine Learning in Linear Time
- A globally convergent incremental Newton method
- Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
- Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms
- Quasi-Newton Methods: Superlinear Convergence Without Line Searches for Self-Concordant Functions
- Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods
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