Proof of Theorem 4.3, p. 9 — an insufficient-decrease trial gives average slope < −ε/6, and any t with h′₊(t) < 0 yields g′ ∈ ∂δf(x) with ⟨g′, g⟩ < |g|²/2
ProvedNonconvexCost.Complexity.thm_4_3_line_search_outcomegoldstein-subgradientline-searchnonsmooth-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , , and let with . Put , , , and on . Suppose the trial step fails the sufficient-decrease test, . Then:
- the average slope of on satisfies
- for every with , the vector is a Goldstein subgradient, , and .
This is the step of the proof of Theorem 4.3 that turns a successful line search into the input of Lemma 4.2.
Formalization Note That the bisection actually reaches such a is a separate statement (the per-line-search bound, proof of Theorem 6.6); here is any point of where the oracle formula for is negative.
Preamble
import Mathlib import Definitions.Def_NonconvexCost_Complexity_Setting import Definitions.Def_NonconvexCost_Complexity_Algorithm
Formal statement
namespace NonconvexCost.Complexity
open Set
open scoped RealInnerProductSpace
theorem thm_4_3_line_search_outcome {X : Type*} [NormedAddCommGroup X] [InnerProductSpace ℝ X]
(f : X → ℝ) (G : X → X → X) (δ ε : ℝ) (hδ : 0 < δ) (hε : 0 < ε) (x g : X)
(hg : ε < ‖g‖) (hdec : f x - f (lsPoint δ x g 0) < δ * ε / 3) :
(lsFun f δ ε x g δ - lsFun f δ ε x g 0) / (δ - 0) < -(ε / 6) ∧
∀ t ∈ Icc (0 : ℝ) δ, lsDeriv G δ ε x g t < 0 →
G (lsPoint δ x g t) (‖g‖⁻¹ • g) ∈ goldstein G δ x ∧
⟪G (lsPoint δ x g t) (‖g‖⁻¹ • g), g⟫ < ‖g‖ ^ 2 / 2 := by sorry
end NonconvexCost.Complexity
Source
Kong, Lewis, The cost of nonconvexity in deterministic nonsmooth optimization, arXiv:2210.00652v2, p. 9, proof of Theorem 4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.