Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 6.6, p. 18 — each line search of Algorithm 4.1 terminates within 1 + ⌊12Λ(δ)/ε⌋ oracle calls

Proved
NonconvexCost.Complexity.thm_6_6_line_search_calls

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

line-searchnonconvexity-modulusoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let δ,ϵ>0\delta,\epsilon>0δ,ϵ>0, let C⊂XC\subset XC⊂X be convex, let GGG be a directional subgradient map for fff on CCC, and suppose fff has finite nonconvexity modulus Λ(δ)\Lambda(\delta)Λ(δ) on CCC. Let x∈Cx\in Cx∈C and g∈Xg\in Xg∈X with ∣g∣>ϵ|g|>\epsilon∣g∣>ϵ, put g^=g/∣g∣\hat g=g/|g|g^​=g/∣g∣, x(t)=x+(t−δ)g^x(t)=x+(t-\delta)\hat gx(t)=x+(t−δ)g^​, x′=x(0)x'=x(0)x′=x(0), h(t)=f(x(t))−ϵt/2h(t)=f(x(t))-\epsilon t/2h(t)=f(x(t))−ϵt/2 and h+′(t)=⟨G(x(t),g^),g^⟩−ϵ/2h'_+(t)=\langle G(x(t),\hat g),\hat g\rangle-\epsilon/2h+′​(t)=⟨G(x(t),g^​),g^​⟩−ϵ/2, and suppose x′∈Cx'\in Cx′∈C and f(x)−f(x′)<δϵ/3f(x)-f(x')<\delta\epsilon/3f(x)−f(x′)<δϵ/3. Then

  1. h+′h'_+h+′​ given by the oracle formula is the right derivative of hhh at every point of [0,δ)[0,\delta)[0,δ), and
  2. the bisection method on [0,δ][0,\delta][0,δ] (Corollary 5.6 with σ=ϵ/6\sigma=\epsilon/6σ=ϵ/6) terminates within
1+⌊12Λ(δ)ϵ⌋1+\Big\lfloor\frac{12\Lambda(\delta)}{\epsilon}\Big\rfloor1+⌊ϵ12Λ(δ)​⌋

evaluations of h+′h'_+h+′​, i.e. one of the first 1+⌊12Λ(δ)/ϵ⌋1+\lfloor12\Lambda(\delta)/\epsilon\rfloor1+⌊12Λ(δ)/ϵ⌋ evaluations is negative.

Multiplying this by the number of line searches gives the complexity of Algorithm 4.1.

Formalization Note In the run of Algorithm 4.1 the hypothesis x′∈Cx'\in Cx′∈C follows from the standing assumption on x0x_0x0​ (iterates satisfy f(x)≤f(x0)f(x)\le f(x_0)f(x)≤f(x0​) and ∣x′−x∣=δ|x'-x|=\delta∣x′−x∣=δ); it is stated here directly. Each evaluation is one oracle call, and that call also returns G(x(t),g^)G(x(t),\hat g)G(x(t),g^​), so no further call is needed to obtain the new subgradient.

Preamble
import Mathlib
import Definitions.Def_NonconvexCost_Complexity_Setting
import Definitions.Def_NonconvexCost_Complexity_Algorithm
Formal statement
namespace NonconvexCost.Complexity

theorem thm_6_6_line_search_calls {X : Type*} [NormedAddCommGroup X] [InnerProductSpace ℝ X]
    (δ ε : ℝ) (hδ : 0 < δ) (hε : 0 < ε) (C : Set X) (hC : Convex ℝ C) (f : X → ℝ)
    (G : X → X → X) (hG : IsDirSubgradMapOn f G C)
    (hΛ : nonconvexityModulus f C δ ≠ ⊤) (x g : X) (hx : x ∈ C)
    (hx' : lsPoint δ x g 0 ∈ C) (hg : ε < ‖g‖)
    (hdec : f x - f (lsPoint δ x g 0) < δ * ε / 3) :
    IsRightDerivOn (lsFun f δ ε x g) (lsDeriv G δ ε x g) 0 δ ∧
      ¬ NoStopWithin (lsFun f δ ε x g) (lsDeriv G δ ε x g) 0 δ
        (1 + ⌊12 * (nonconvexityModulus f C δ).toReal / ε⌋₊) := by sorry

end NonconvexCost.Complexity
Source
Kong, Lewis, The cost of nonconvexity in deterministic nonsmooth optimization, arXiv:2210.00652v2, p. 18, proof of Theorem 6.6
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