Theorem 5.2, p. 11 — k ≥ 1 non-terminating bisection evaluations force (h(q) − h(p))/(q − p) ≥ (s′₊(p) − s′₋(q))/k
ProvedNonconvexCost.Complexity.theorem_5_2concave-deviationline-searchoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and with convex and convex on . Suppose has a finite right derivative at every , and has finite right derivative at and left derivative at . If the bisection method, Algorithm 3.1, evaluates times without terminating (the first evaluations, at and then at the successive midpoints, are all nonnegative), then
Thus if decreases on average over , the number of evaluations before termination is bounded by the variation of the derivative of a convexifying perturbation.
Formalization Note The finiteness of the one-sided derivatives is added (the page writes them without comment). The bisection keeps when , as in (5.3).
Preamble
import Mathlib import Definitions.Def_NonconvexCost_Complexity_Setting
Formal statement
namespace NonconvexCost.Complexity
open Set
theorem theorem_5_2 (h h' s : ℝ → ℝ) (p q : ℝ) (hpq : p < q) (hs : ConvexOn ℝ (Icc p q) s)
(hhs : ConvexOn ℝ (Icc p q) (h + s)) (hder : IsRightDerivOn h h' p q) (sp sq : ℝ)
(hsp : HasDerivWithinAt s sp (Icc p q) p) (hsq : HasDerivWithinAt s sq (Icc p q) q)
(k : ℕ) (hk : 1 ≤ k) (hrun : NoStopWithin h h' p q k) :
(sp - sq) / k ≤ (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. 11, Theorem 5.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.