Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.8 — level surfaces with ratio σ≥2\sigma \ge \sqrt2σ≥2​ give ∥xk−x∗∥≤hk+1σ\|x_k - x^*\| \le h_{k+1}\sigma∥xk​−x∗∥≤hk+1​σ with hk+1=hkσ2−1/σh_{k+1} = h_k\sqrt{\sigma^2-1}/\sigmahk+1​=hk​σ2−1​/σ

Proved
ShorNonsmooth.LinearRate.linear_rate_of_level_set_ratio

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

level-setslinear-convergencep2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1subgradient-method

Let fff be a convex function on EnE_nEn​ with a unique minimum point x∗x^*x∗, and let gf(x)g_f(x)gf​(x) be any subgradient of fff at xxx. For a starting point x0x_0x0​ choose numbers σ\sigmaσ and h1h_1h1​ with

σ≥2,h1≥∥x0−x∗∥/σ.\sigma \ge \sqrt2, \qquad h_1 \ge \|x_0 - x^*\|/\sigma .σ≥2​,h1​≥∥x0​−x∗∥/σ.

Let Y={y:∥y−x∗∥≤σh1}Y = \{y : \|y - x^*\| \le \sigma h_1\}Y={y:∥y−x∗∥≤σh1​} and assume that every pair of points x,z∈Yx, z \in Yx,z∈Y with f(x)=f(z)≠f(x∗)f(x) = f(z) \ne f(x^*)f(x)=f(z)=f(x∗) satisfies

∥x−x∗∥≤σ ∥z−x∗∥.(2.20)\|x - x^*\| \le \sigma\,\|z - x^*\|. \tag{2.20}∥x−x∗∥≤σ∥z−x∗∥.(2.20)

Then the sequence generated by

xk+1=xk−hk+1gf(xk)∥gf(xk)∥,hk+1=hkσ2−1σ,x_{k+1} = x_k - h_{k+1}\frac{g_f(x_k)}{\|g_f(x_k)\|}, \qquad h_{k+1} = h_k\frac{\sqrt{\sigma^2 - 1}}{\sigma},xk+1​=xk​−hk+1​∥gf​(xk​)∥gf​(xk​)​,hk+1​=hk​σσ2−1​​,

converges to x∗x^*x∗ at a linear rate:

∥xk−x∗∥≤hk+1 σ,k=0,1,2,…(2.21)\|x_k - x^*\| \le h_{k+1}\,\sigma, \qquad k = 0, 1, 2, \dots \tag{2.21}∥xk​−x∗∥≤hk+1​σ,k=0,1,2,…(2.21)

The theorem replaces the angle condition of Theorem 2.7 by a condition on the shape of the level surfaces of fff near the minimum: if they are not too oblong, the subgradient method with geometrically decreasing steps converges geometrically with ratio σ2−1/σ\sqrt{\sigma^2-1}/\sigmaσ2−1​/σ.

Formalization Note The book writes the stepsize rule for "k=0,1,2,…k = 0, 1, 2, \dotsk=0,1,2,…", which would define h1h_1h1​ from an undefined h0h_0h0​ although h1h_1h1​ is chosen; the rule is required for k≥1k \ge 1k≥1. The book's exception "gf(xkˉ)=0g_f(x_{\bar k}) = 0gf​(xkˉ​)=0 for some kˉ\bar kkˉ, i.e. xkˉ=x∗x_{\bar k} = x^*xkˉ​=x∗" is the stop of the method: the sequence then stays at x∗x^*x∗, where (2.21) holds, so the bound is asserted for all kkk.

Preamble
import Mathlib
import Definitions.Def_ShorNonsmooth_LinearRate_SubgradientMethod
Formal statement
namespace ShorNonsmooth.LinearRate

/-- Shor (1985), p. 32, **Theorem 2.8**. Let `f` be convex on `E_n` with unique minimum point
`x*`. For a starting point `x₀` let `σ ≥ √2` and `h₁ ≥ ‖x₀ - x*‖/σ`, let
`Y = {y : ‖y - x*‖ ≤ σ h₁}`, and assume (2.20): `‖x - x*‖ ≤ σ ‖z - x*‖` for every pair
`x, z ∈ Y` with `f(x) = f(z) ≠ f(x*)`. Then the normalized subgradient iterates with stepsizes
`h_{k+1} = h_k √(σ² - 1)/σ` (`k ≥ 1`) satisfy (2.21): `‖x_k - x*‖ ≤ h_{k+1} σ` for all `k`.
The book's exception "`g_f(x_k̄) = 0`, i.e. `x_k̄ = x*`" is the stop of the method; the stopped
sequence stays at `x*`, where the bound holds trivially. -/
theorem linear_rate_of_level_set_ratio {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
    (hf : ConvexOn ℝ Set.univ f) (xs : EuclideanSpace ℝ (Fin n)) (hxs : ShorNonsmooth.SubgradMethod.MinSet f = {xs})
    (x₀ : EuclideanSpace ℝ (Fin n)) (σ : ℝ) (h : ℕ → ℝ)
    (hσ : Real.sqrt 2 ≤ σ) (hh₁ : ‖x₀ - xs‖ / σ ≤ h 1)
    (hY : ∀ x ∈ Metric.closedBall xs (σ * h 1), ∀ z ∈ Metric.closedBall xs (σ * h 1),
      f x = f z → f x ≠ f xs → ‖x - xs‖ ≤ σ * ‖z - xs‖)
    (hrec : ∀ k, 1 ≤ k → h (k + 1) = h k * (Real.sqrt (σ ^ 2 - 1) / σ))
    (g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
    (hg : ∀ x, ShorNonsmooth.AlmostDiff.IsSubgradient f x (g x)) :
    ∀ k, ‖ShorNonsmooth.SubgradMethod.normalizedIter g h x₀ k - xs‖ ≤ h (k + 1) * σ := by sorry

end ShorNonsmooth.LinearRate
Source
Shor, Minimization Methods for Non-Differentiable Functions, Springer 1985, p. 32, Theorem 2.8, (2.20)–(2.21)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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