Corollary 5.6, p. 13 (line search complexity) — bisection terminates within 1 + ⌊2M/σ⌋ evaluations
ProvedNonconvexCost.Complexity.corollary_5_6concave-deviationline-searchoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let have a finite right derivative at every point of , finite concave deviation on , and average rate of decrease
Then the number of evaluations of required before the bisection method, Algorithm 3.1, terminates is no more than
that is, among the first evaluations at least one is negative.
This is the univariate complexity bound that, applied on segments of length , gives the cost of each line search in Algorithm 4.1.
Formalization Note The existence of the finite right derivative on is added so that the evaluated values are real numbers.
Preamble
import Mathlib import Definitions.Def_NonconvexCost_Complexity_Setting
Formal statement
namespace NonconvexCost.Complexity
open Set
theorem corollary_5_6 (h h' : ℝ → ℝ) (p q : ℝ) (hpq : p < q) (hder : IsRightDerivOn h h' p q)
(hM : concaveDeviation h (Icc p q) ≠ ⊤) (hσ : 0 < -((h q - h p) / (q - p))) :
¬ NoStopWithin h h' p q
(1 + ⌊2 * (concaveDeviation h (Icc p q)).toReal / (-((h q - h p) / (q - p)))⌋₊) := by sorry
end NonconvexCost.Complexity
Source
Kong, Lewis, The cost of nonconvexity in deterministic nonsmooth optimization, arXiv:2210.00652v2, p. 13, Corollary 5.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.