Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3 and §6 — Newton's method can need ⌊ε−(2−τ)⌋\lfloor \varepsilon^{-(2-\tau)} \rfloor⌊ε−(2−τ)⌋ iterations to reach ∥g∥≤ε\|g\| \le \varepsilon∥g∥≤ε

Proved
SlowConvergence.Newton.slow_newton

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

lower-boundnewton-methodnonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity

Let 0<τ<10 < \tau < 10<τ<1. There exist a function f:R2→Rf : \mathbb R^2 \to \mathbb Rf:R2→R and a sequence (xk)k≥0(x_k)_{k \ge 0}(xk​)k≥0​ in R2\mathbb R^2R2 with the following properties. Write g(x)=∇f(x)g(x) = \nabla f(x)g(x)=∇f(x) and H(x)=∇2f(x)H(x) = \nabla^2 f(x)H(x)=∇2f(x).

  1. fff is twice continuously differentiable on R2\mathbb R^2R2, bounded below, and its Hessian is bounded: sup⁡y∥H(y)∥<∞\sup_y \|H(y)\| < \inftysupy​∥H(y)∥<∞.
  2. (xk)(x_k)(xk​) is a run of Newton's method on fff from x0=0x_0 = 0x0​=0: for every kkk, H(xk)H(x_k)H(xk​) is positive definite and H(xk)(xk+1−xk)=−g(xk)H(x_k)(x_{k+1} - x_k) = -g(x_k)H(xk​)(xk+1​−xk​)=−g(xk​), so xk+1x_{k+1}xk+1​ is the exact minimizer of the quadratic model (1.2).
  3. The Hessian is Lipschitz continuous along the path, with one constant: there is LLL such that ∥H(y)−H(z)∥≤L∥y−z∥\|H(y) - H(z)\| \le L\|y - z\|∥H(y)−H(z)∥≤L∥y−z∥ whenever y,zy, zy,z lie on the same segment [xk,xk+1][x_k, x_{k+1}][xk​,xk+1​].
  4. Each step achieves exactly the model value (3.8):
f(xk+1)=f(xk)+g(xk)T(xk+1−xk)+12(xk+1−xk)TH(xk)(xk+1−xk).f(x_{k+1}) = f(x_k) + g(x_k)^T(x_{k+1}-x_k) + \tfrac12 (x_{k+1}-x_k)^T H(x_k)(x_{k+1}-x_k).f(xk+1​)=f(xk​)+g(xk​)T(xk+1​−xk​)+21​(xk+1​−xk​)TH(xk​)(xk+1​−xk​).
  1. The gradients decay slowly, (2.3): for every k≥0k \ge 0k≥0,
∥g(xk)∥  ≥  (1k+1)12−τ.\|g(x_k)\| \;\ge\; \Big(\frac1{k+1}\Big)^{\frac1{2-\tau}} .∥g(xk​)∥≥(k+11​)2−τ1​.
  1. Consequently, for every ε∈(0,1)\varepsilon \in (0,1)ε∈(0,1), if ∥g(xk)∥≤ε\|g(x_k)\| \le \varepsilon∥g(xk​)∥≤ε then
k+1  ≥  ⌊1ε2−τ⌋,k + 1 \;\ge\; \Big\lfloor \frac{1}{\varepsilon^{2-\tau}} \Big\rfloor ,k+1≥⌊ε2−τ1​⌋,

i.e. Newton's method needs at least ⌊ε−(2−τ)⌋\lfloor \varepsilon^{-(2-\tau)} \rfloor⌊ε−(2−τ)⌋ iterates (function evaluations) x0,…,xkx_0, \dots, x_kx0​,…,xk​ to produce a gradient of norm at most ε\varepsilonε.

Since τ\tauτ is arbitrary, the worst-case iteration count of Newton's method on twice continuously differentiable functions with bounded Hessians that are Lipschitz along the path is not better than O(ε−2+τ)O(\varepsilon^{-2+\tau})O(ε−2+τ) for any τ>0\tau > 0τ>0: Newton's method may be as slow as steepest descent. Property 4 makes the conclusion apply also when Newton's method is embedded in a trust-region or linesearch globalization, since every unit step is then accepted.

Formalization Note The paper states the result "for any τ>0\tau > 0τ>0"; the construction needs τ<1\tau < 1τ<1, and for ε<1\varepsilon < 1ε<1 the cases τ<1\tau < 1τ<1 imply the iteration bound for every τ>0\tau > 0τ>0. The count is posed for the iterates x0,…,xkx_0, \dots, x_kx0​,…,xk​ (k+1k + 1k+1 of them): as printed, "at least ⌊1/ε2−τ⌋\lfloor 1/\varepsilon^{2-\tau}\rfloor⌊1/ε2−τ⌋ iterations" is off by one. The paper builds fff on the nonnegative quadrant and remarks that it extends smoothly; here fff is required on all of R2\mathbb R^2R2. Boundedness of the Hessian is required on all of R2\mathbb R^2R2, which is stronger than AS.1 ("along each segment"); the Lipschitz constant is uniform in kkk. The plane is EuclideanSpace ℝ (Fin 2), ggg is gradient f, HHH is fderiv ℝ (gradient f) and ∥⋅∥\|\cdot\|∥⋅∥ on operators is the operator norm.

Preamble
import Mathlib

open scoped RealInnerProductSpace
Formal statement
namespace SlowConvergence.Newton

/-- Cartis, Gould & Toint, *On the complexity of steepest descent, Newton's and regularized Newton's
methods for nonconvex unconstrained optimization*, preprint 15 Oct 2009, §3, pp. 6–9 (the `f_2` example)
and §6, pp. 15–16: Newton's method can need `⌊ε^{−(2−τ)}⌋` iterations to reach `‖g‖ ≤ ε`.

For every `τ ∈ (0, 1)` there is a function `f : ℝ² → ℝ` that is twice continuously differentiable,
bounded below, with bounded Hessian, and a run `x_0 = 0, x_1, …` of Newton's method on `f` (at every
iterate the Hessian `H(x_k)` is positive definite and `H(x_k)(x_{k+1} − x_k) = −∇f(x_k)`, i.e. the unit
Newton step minimizing the quadratic model (1.2)), such that
* the Hessian is Lipschitz continuous along every segment `[x_k, x_{k+1}]`, with one constant for all `k`;
* (3.8) `f(x_{k+1}) = m_k(x_{k+1})`, the value of the quadratic model (1.2) at the new iterate;
* (2.3) `‖∇f(x_k)‖ ≥ (1/(k+1))^{1/(2−τ)}` for all `k ≥ 0`;
* for every `ε ∈ (0, 1)`, an iterate `x_k` with `‖∇f(x_k)‖ ≤ ε` has `k + 1 ≥ ⌊ε^{−(2−τ)}⌋`, i.e. at least
  `⌊1/ε^{2−τ}⌋` iterates (function evaluations) `x_0, …, x_k` are needed.

Formalization Note: the paper says "for any τ > 0"; the construction needs `τ < 1`, and the `τ < 1`
cases imply the iteration bound for all `τ > 0` when `ε < 1`. The count is `k + 1` (iterates
`x_0, …, x_k`), because as printed ("at least ⌊1/ε^{2−τ}⌋ iterations") it is off by one. The paper
builds `f` on the nonnegative quadrant and says it extends smoothly; here `f` is required on all of `ℝ²`.
Boundedness of the Hessian is required on all of `ℝ²` (AS.1 asks it along the segments). -/
theorem slow_newton (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) :
    ∃ f : EuclideanSpace ℝ (Fin 2) → ℝ,
      ContDiff ℝ 2 f ∧ BddBelow (Set.range f) ∧
      (∃ M : ℝ, ∀ y, ‖fderiv ℝ (gradient f) y‖ ≤ M) ∧
      ∃ x : ℕ → EuclideanSpace ℝ (Fin 2), x 0 = 0 ∧
        (∀ k, (∀ v : EuclideanSpace ℝ (Fin 2), v ≠ 0 → 0 < ⟪fderiv ℝ (gradient f) (x k) v, v⟫) ∧
          fderiv ℝ (gradient f) (x k) (x (k + 1) - x k) = -gradient f (x k)) ∧
        (∃ L : ℝ, ∀ k, ∀ y ∈ segment ℝ (x k) (x (k + 1)), ∀ z ∈ segment ℝ (x k) (x (k + 1)),
          ‖fderiv ℝ (gradient f) y - fderiv ℝ (gradient f) z‖ ≤ L * ‖y - z‖) ∧
        (∀ k, f (x (k + 1)) = f (x k) + ⟪gradient f (x k), x (k + 1) - x k⟫
          + 1 / 2 * ⟪fderiv ℝ (gradient f) (x k) (x (k + 1) - x k), x (k + 1) - x k⟫) ∧
        (∀ k : ℕ, (1 / ((k : ℝ) + 1)) ^ (1 / (2 - τ)) ≤ ‖gradient f (x k)‖) ∧
        (∀ ε : ℝ, 0 < ε → ε < 1 → ∀ k : ℕ, ‖gradient f (x k)‖ ≤ ε →
          (⌊ε ^ (-(2 - τ))⌋₊ : ℝ) ≤ k + 1) := by sorry

end SlowConvergence.Newton
Source
Cartis, Gould & Toint, On the complexity of steepest descent, Newton's and regularized Newton's methods, preprint 15 Oct 2009, pp. 6–9, §3 (the f_2 example, AS.1 and (3.1)–(3.8)); pp. 15–16, §6; (1.2), p. 1; (2.3), p. 3
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me