Proof of Theorem 4.3, p. 10 — Algorithm 4.1 makes at most ⌈3(f(x₀) − min f)/(δε)⌉ reduction steps
ProvedNonconvexCost.Complexity.thm_4_3_reduction_countnonsmooth-optimizationoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let , let be bounded below on , and let satisfy
Let and be arbitrary. Then for every , among the first steps of the run of Algorithm 4.1 from the number of reduction steps (steps at which a trial point has just been accepted) is at most
Each reduction step decreases the objective by at least and the iterates stay in , where is bounded below.
Formalization Note "" is read as the infimum of over (the paper only assumes bounded below). A reduction step is counted by the state machine's re-initialisation phase. No hypothesis on is needed.
Preamble
import Mathlib import Definitions.Def_NonconvexCost_Complexity_Setting import Definitions.Def_NonconvexCost_Complexity_Algorithm
Formal statement
namespace NonconvexCost.Complexity
open Classical in
theorem thm_4_3_reduction_count {X : Type*} [NormedAddCommGroup X] [InnerProductSpace ℝ X]
(δ ε : ℝ) (hδ : 0 < δ) (hε : 0 < ε) (C : Set X) (f : X → ℝ) (hbdd : BddBelow (f '' C))
(G : X → X → X) (x0 : X) (hx0 : x0 ∈ C)
(hsub : ∀ x ∈ C, f x ≤ f x0 → ∀ y : X, ‖y‖ ≤ δ → x + y ∈ C) (g0 : X) (n : ℕ) :
((Finset.range n).filter (fun j => IsReinit (run f G δ ε x0 g0 j))).card ≤
⌈3 * (f x0 - sInf (f '' C)) / (δ * ε)⌉₊ := by sorry
end NonconvexCost.Complexity
Source
Kong, Lewis, The cost of nonconvexity in deterministic nonsmooth optimization, arXiv:2210.00652v2, p. 10, proof of Theorem 4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.