Proof of Theorem 6.6, p. 18 — each line search of Algorithm 4.1 terminates within 1 + ⌊12Λ(δ)/ε⌋ oracle calls
ProvedNonconvexCost.Complexity.thm_6_6_line_search_callsline-searchnonconvexity-modulusoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be convex, let be a directional subgradient map for on , and suppose has finite nonconvexity modulus on . Let and with , put , , , and , and suppose and . Then
- given by the oracle formula is the right derivative of at every point of , and
- the bisection method on (Corollary 5.6 with ) terminates within
evaluations of , i.e. one of the first evaluations is negative.
Multiplying this by the number of line searches gives the complexity of Algorithm 4.1.
Formalization Note In the run of Algorithm 4.1 the hypothesis follows from the standing assumption on (iterates satisfy and ); it is stated here directly. Each evaluation is one oracle call, and that call also returns , so no further call is needed to obtain the new subgradient.
Preamble
import Mathlib import Definitions.Def_NonconvexCost_Complexity_Setting import Definitions.Def_NonconvexCost_Complexity_Algorithm
Formal statement
namespace NonconvexCost.Complexity
theorem thm_6_6_line_search_calls {X : Type*} [NormedAddCommGroup X] [InnerProductSpace ℝ X]
(δ ε : ℝ) (hδ : 0 < δ) (hε : 0 < ε) (C : Set X) (hC : Convex ℝ C) (f : X → ℝ)
(G : X → X → X) (hG : IsDirSubgradMapOn f G C)
(hΛ : nonconvexityModulus f C δ ≠ ⊤) (x g : X) (hx : x ∈ C)
(hx' : lsPoint δ x g 0 ∈ C) (hg : ε < ‖g‖)
(hdec : f x - f (lsPoint δ x g 0) < δ * ε / 3) :
IsRightDerivOn (lsFun f δ ε x g) (lsDeriv G δ ε x g) 0 δ ∧
¬ NoStopWithin (lsFun f δ ε x g) (lsDeriv G δ ε x g) 0 δ
(1 + ⌊12 * (nonconvexityModulus f C δ).toReal / ε⌋₊) := by sorry
end NonconvexCost.Complexity
Source
Kong, Lewis, The cost of nonconvexity in deterministic nonsmooth optimization, arXiv:2210.00652v2, p. 18, proof of Theorem 6.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.