§3, p. 6 — the prescribed gradients satisfy (2.3):
ProvedSlowConvergence.Newton.gradient_lower_boundlower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Let , , and let be the gradients prescribed by (3.4). Then , and for every
which is the requirement (2.3).
This is the inequality that turns the construction into a complexity lower bound: an iterate with can occur only once .
Preamble
import Mathlib import Definitions.Def_SlowConvergence_Newton_Data import Definitions.Def_SlowConvergence_Newton_Pieces open scoped RealInnerProductSpace
Formal statement
namespace SlowConvergence.Newton
/-- Cartis, Gould & Toint, preprint 15 Oct 2009, §3, p. 6, after (3.4): "The first part of (3.4) then
immediately gives (2.3) by construction, since the norm of that vector is at least equal to the absolute
value of its first component." With `η = τ/(4 − 2τ)` (2.10), `1/2 + η = 1/(2 − τ)`, and the prescribed
gradient `g_k` of (3.4) satisfies (2.3): `‖g_k‖ ≥ (1/(k+1))^{1/(2−τ)}` for all `k ≥ 0`. -/
theorem gradient_lower_bound (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) :
1 / 2 + eta τ = 1 / (2 - τ) ∧
∀ k : ℕ, (1 / ((k : ℝ) + 1)) ^ (1 / (2 - τ)) ≤ ‖gk τ k‖ := 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, p. 6, §3, after (3.4); (2.3) and (2.10), p. 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.