Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.6, pp. 17–18 (corrected phase count) — Algorithm 4.1 finds a small Goldstein subgradient within an explicit number of oracle calls

Proved
NonconvexCost.Complexity.theorem_6_6

by mikedeng1 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

goldstein-subgradientnonconvexity-modulusnonsmooth-optimizationoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Theorem 6.6 (complexity of minimization), with the phase count corrected. Let XXX be a real inner product space, let δ,ϵ>0\delta,\epsilon>0δ,ϵ>0, let C⊂XC\subset XC⊂X be convex, let fff be bounded below on CCC, and let G ⁣:X2→XG\colon X^2\to XG:X2→X be an LLL-bounded directional subgradient map for fff on CCC. Let x0∈Cx_0\in Cx0​∈C satisfy

x∈C, f(x)≤f(x0), ∣y∣≤δ ⟹ x+y∈C,x\in C,\ f(x)\le f(x_0),\ |y|\le\delta\ \Longrightarrow\ x+y\in C,x∈C, f(x)≤f(x0​), ∣y∣≤δ ⟹ x+y∈C,

and suppose fff has finite nonconvexity modulus Λ(δ)\Lambda(\delta)Λ(δ). Start Algorithm 4.1 (nonsmooth minimization, with the bisection line search) at x0x_0x0​ with any Goldstein subgradient g0∈∂δf(x0)g_0\in\partial_\delta f(x_0)g0​∈∂δ​f(x0​). Then within at most

(⌊3(f(x0)−inf⁡Cf)δϵ⌋+1)⋅16L2ϵ2⋅(1+⌊12Λ(δ)ϵ⌋)\Big(\Big\lfloor\frac{3(f(x_0)-\inf_C f)}{\delta\epsilon}\Big\rfloor+1\Big)\cdot\frac{16L^2}{\epsilon^2}\cdot\Big(1+\Big\lfloor\frac{12\Lambda(\delta)}{\epsilon}\Big\rfloor\Big)(⌊δϵ3(f(x0​)−infC​f)​⌋+1)⋅ϵ216L2​⋅(1+⌊ϵ12Λ(δ)​⌋)

calls to Oracle 2.5 the algorithm stops at a point x∈Xx\in Xx∈X with a Goldstein subgradient g∈∂δf(x)g\in\partial_\delta f(x)g∈∂δ​f(x) satisfying ∣g∣≤ϵ|g|\le\epsilon∣g∣≤ϵ.

For weakly convex and difference-of-convex objectives Λ(δ)\Lambda(\delta)Λ(δ) is bounded, and the bound becomes the O(ϵ−4)O(\epsilon^{-4})O(ϵ−4) and O(ϵ−5)O(\epsilon^{-5})O(ϵ−5)-type complexities of the paper, achieved by a deterministic method without any semismoothness assumption.

Formalization Note Corrected. The paper prints the first factor as ⌈3(f(x0)−min⁡f)/(δϵ)⌉\lceil3(f(x_0)-\min f)/(\delta\epsilon)\rceil⌈3(f(x0​)−minf)/(δϵ)⌉. That bound is 000 when f(x0)=min⁡ff(x_0)=\min ff(x0​)=minf, but it fails there: on X=C=RX=C=\mathbb RX=C=R with f≡0f\equiv0f≡0, L=2L=2L=2, ϵ=δ=1\epsilon=\delta=1ϵ=δ=1, G(x,e)=0G(x,e)=0G(x,e)=0 for e≠0e\ne0e=0 and G(x,0)=2G(x,0)=2G(x,0)=2, the run started with g0=G(x0,0)g_0=G(x_0,0)g0​=G(x0​,0) has ∣g0∣>ϵ|g_0|>\epsilon∣g0​∣>ϵ and needs an oracle call. The proof on p. 10 allows at most ⌊3(f(x0)−inf⁡f)/(δϵ)⌋\lfloor3(f(x_0)-\inf f)/(\delta\epsilon)\rfloor⌊3(f(x0​)−inff)/(δϵ)⌋ reductions, hence one more phase, which is the count used here. "min⁡f\min fminf" is the infimum of fff over CCC. The count includes every oracle call (trial points, bisection midpoints, re-initialisations G(x′,0)G(x',0)G(x′,0)), which is stricter than the paper's proof, and the bound still holds. fff is a function on XXX, constrained only on CCC: the oracle identity is required at points of CCC along directions that stay in CCC for small steps. The bisection test uses h(l)+h(r)h(l)+h(r)h(l)+h(r) (Algorithm 3.1 prints f(l)+f(r)f(l)+f(r)f(l)+f(r)).

Preamble
import Mathlib
import Definitions.Def_NonconvexCost_Complexity_Setting
import Definitions.Def_NonconvexCost_Complexity_Algorithm
Formal statement
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
Source
Kong, Lewis, The cost of nonconvexity in deterministic nonsmooth optimization, arXiv:2210.00652v2, pp. 17–18, Theorem 6.6 (corrected phase count)
Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 23, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me