§3 and §6 — Newton's method can need iterations to reach
ProvedSlowConvergence.Newton.slow_newtonLet . There exist a function and a sequence in with the following properties. Write and .
- is twice continuously differentiable on , bounded below, and its Hessian is bounded: .
- is a run of Newton's method on from : for every , is positive definite and , so is the exact minimizer of the quadratic model (1.2).
- The Hessian is Lipschitz continuous along the path, with one constant: there is such that whenever lie on the same segment .
- Each step achieves exactly the model value (3.8):
- The gradients decay slowly, (2.3): for every ,
- Consequently, for every , if then
i.e. Newton's method needs at least iterates (function evaluations) to produce a gradient of norm at most .
Since 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 for any : 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 "; the construction needs , and for the cases imply the iteration bound for every . The count is posed for the iterates ( of them): as printed, "at least iterations" is off by one. The paper builds on the nonnegative quadrant and remarks that it extends smoothly; here is required on all of . Boundedness of the Hessian is required on all of , which is stronger than AS.1 ("along each segment"); the Lipschitz constant is uniform in . The plane is EuclideanSpace ℝ (Fin 2), is gradient f, is fderiv ℝ (gradient f) and on operators is the operator norm.
import Mathlib open scoped RealInnerProductSpace
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.