Theorem 6.6, pp. 17–18 (corrected phase count) — Algorithm 4.1 finds a small Goldstein subgradient within an explicit number of oracle calls
ProvedNonconvexCost.Complexity.theorem_6_6Theorem 6.6 (complexity of minimization), with the phase count corrected. Let be a real inner product space, let , let be convex, let be bounded below on , and let be an -bounded directional subgradient map for on . Let satisfy
and suppose has finite nonconvexity modulus . Start Algorithm 4.1 (nonsmooth minimization, with the bisection line search) at with any Goldstein subgradient . Then within at most
calls to Oracle 2.5 the algorithm stops at a point with a Goldstein subgradient satisfying .
For weakly convex and difference-of-convex objectives is bounded, and the bound becomes the and -type complexities of the paper, achieved by a deterministic method without any semismoothness assumption.
Formalization Note Corrected. The paper prints the first factor as . That bound is when , but it fails there: on with , , , for and , the run started with has and needs an oracle call. The proof on p. 10 allows at most reductions, hence one more phase, which is the count used here. "" is the infimum of over . The count includes every oracle call (trial points, bisection midpoints, re-initialisations ), which is stricter than the paper's proof, and the bound still holds. is a function on , constrained only on : the oracle identity is required at points of along directions that stay in for small steps. The bisection test uses (Algorithm 3.1 prints ).
import Mathlib import Definitions.Def_NonconvexCost_Complexity_Setting import Definitions.Def_NonconvexCost_Complexity_Algorithm
namespace NonconvexCost.Complexity
theorem theorem_6_6 {X : Type*} [NormedAddCommGroup X] [InnerProductSpace ℝ X]
(δ ε L : ℝ) (hδ : 0 < δ) (hε : 0 < ε) (C : Set X) (hC : Convex ℝ C) (f : X → ℝ)
(hbdd : BddBelow (f '' C)) (G : X → X → X) (hG : IsDirSubgradMapOn f G C)
(hL : IsLBounded G L) (x0 : X) (hx0 : x0 ∈ C)
(hsub : ∀ x ∈ C, f x ≤ f x0 → ∀ y : X, ‖y‖ ≤ δ → x + y ∈ C)
(hΛ : nonconvexityModulus f C δ ≠ ⊤) (g0 : X) (hg0 : g0 ∈ goldstein G δ x0) :
∃ n : ℕ,
(n : ℝ) ≤ ((⌊3 * (f x0 - sInf (f '' C)) / (δ * ε)⌋₊ : ℝ) + 1) * (16 * L ^ 2 / ε ^ 2) *
(1 + ⌊12 * (nonconvexityModulus f C δ).toReal / ε⌋₊) ∧
IsDone ε (run f G δ ε x0 g0 n) ∧
(run f G δ ε x0 g0 n).g ∈ goldstein G δ (run f G δ ε x0 g0 n).x := by sorry
end NonconvexCost.Complexity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.