The classical convergence theory of smooth convex minimization. For a function that is -strongly convex and -smooth (), gradient descent converges linearly, while Newton's method exhibits its famous two phases: a damped phase in which every backtracking step decreases the objective by a fixed amount , and a quadratically convergent phase in which the scaled gradient norm squares at each step, . Together they give the iteration count of B&V (9.36),
with the Lipschitz constant of the Hessian and the backtracking parameters. This mission formalizes Chapters 9–10 of Boyd & Vandenberghe with every constant exactly as printed — a quantitative theory entirely absent from Mathlib.
theorem ConvexOptimization.newton_two_phase_iteration_bound {n : ℕ} (m M L α β ε : ℝ)
(hm : 0 < m) (hmM : m ≤ M) (hL : 0 < L)
(hα0 : 0 < α) (hα : α < 1 / 2) (hβ0 : 0 < β) (hβ1 : β < 1)
(hε0 : 0 < ε) (hεsmall : ε ≤ m ^ 3 / (2 * L ^ 2))
(f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
(hg : ∀ x, HasGradientAt f (g x) x)
(H : EuclideanSpace ℝ (Fin n) →
EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n))
(hH : ∀ x, HasFDerivAt g (H x) x)
(hHm : ∀ x v, m * ‖v‖ ^ 2 ≤ ⟪H x v, v⟫)
(hHM : ∀ x v, ⟪H x v, v⟫ ≤ M * ‖v‖ ^ 2)
(hHL : ∀ x y, ‖H x - H y‖ ≤ L * ‖x - y‖)
(xstar : EuclideanSpace ℝ (Fin n)) (hstar : IsMinOn f Set.univ xstar)
(x : ℕ → EuclideanSpace ℝ (Fin n))
(hnewton : IsDampedNewtonSequence f g H α β x)
(K : ℕ)
(hK : (f (x 0) - f xstar) /
(α * β * (min 1 (3 * (1 - 2 * α)) * m ^ 2 / L) ^ 2 * m / M ^ 2) +
Real.logb 2 (Real.logb 2 (2 * m ^ 3 / L ^ 2 / ε)) ≤ (K : ℝ)) :
f (x K) - f xstar ≤ ε := by
sorry
The two-phase complexity bound for Newton's method with backtracking — inequality (9.36) of Boyd & Vandenberghe, the goal of this mission.
Let be twice differentiable with gradient field and Hessian field , and assume, for constants and ,
Let be a global minimizer, , fix backtracking parameters , , and let be any damped Newton sequence with backtracking. Put
Then for every accuracy with and every satisfying
the iterate is -optimal:
The two summands are the two phases: at most damped iterations, each buying a fixed decrease , followed by a quadratically convergent phase whose length grows like — six iterations already give . The bound is dimension-free, and its dependence on the accuracy is doubly logarithmic rather than logarithmic, which is the precise sense in which Newton's method outperforms every first-order method.
Formalization Note The hypothesis is stated as ε ≤ m ^ 3 / (2 * L ^ 2); it is needed because the book's count is valid once the quadratic phase has genuinely begun, and for the literal bound (9.36) fails. The quantities and are inlined into the hypothesis on rather than introduced as abbreviations, and is Mathlib's Real.logb 2. The iterates are governed by the mission's damped-Newton predicate, so the conclusion holds for every faithful run. Source: B&V §9.5.3, p. 491, eq. (9.36).
No open leaves. Every sub-goal is proved or awaiting decomposition.