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

By Sai Praneeth Karimireddy, Sebastian U. Stich, Martin Jaggi. 2018

63 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Simon Lacoste-Julien
2. Peter Richtárik
3. Martin Jaggi
4. Francis R. Bach
5. Nicolas Loizou
6. Sebastian Pokutta
7. Mark W. Schmidt
8. Issam Hadj Laradji

In Computational Mechanics

1. Simon Lacoste-Julien
2. Martin Jaggi
3. Peter Richtárik
4. Sebastian Pokutta
5. Francis R. Bach
6. Mark W. Schmidt
7. Sebastian U. Stich
8. Sharan Vaswani

In Numerical Analysis

1. Simon Lacoste-Julien
2. Martin Jaggi
3. Mark W. Schmidt
4. Francis R. Bach
5. Sebastian Pokutta
6. Alejandro Carderera
7. Issam Hadj Laradji
8. Sharan Vaswani

In Optimization & Training

1. Simon Lacoste-Julien
2. Peter Richtárik
3. Francis R. Bach
4. Nicolas Loizou
5. Sebastian Pokutta
6. Mark W. Schmidt
7. Issam Hadj Laradji
8. Martin Jaggi

Citations in the corpus

• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “If we set b g = b s = n and τ = 0, we obtain the rate which matches the deterministic rate (Karimireddy et al., 2018, Theorem 2) up to a constant factor of 2.”
• Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, background): “Globally convergent second-order methods have also been proposed to solve such problems [21], but the number of Newton steps needed being bounded only by L/λ, they lead to a solution in O(L/λ (nd + min(n, d)(3))).”
• Second-order Conditional Gradients (2020, methodology): “This condition is similar in spirit to Condition C in (Karimireddy et al., 2018a).”
• A Distributed Second-Order Algorithm You Can Trust (2018, methodology): “model is often a quadratic model (Conn et al., 2000; Karimireddy et al., 2018), although cubic models can also be used (Nesterov & Polyak, 2006).”