Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.4, p. 250 — for t ≥ 2n² log(R/r) the ellipsoid method hits X and f(x_t) − min_X f ≤ (2BR/r)·exp(−t/(2n²))

Proved
ConvexOptAlg.Ellipsoid.theorem_2_4

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

convergence-rateconvex-optimizationellipsoid-methodoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Let n≥2n\ge2n≥2 and let X⊂Rn\mathcal X\subset\mathbb R^nX⊂Rn be a convex body (compact, convex, with non-empty interior). Let fff be continuous and convex on X\mathcal XX with values in [−B,B][-B,B][−B,B], and let x∗∈Xx^*\in\mathcal Xx∗∈X be a minimizer of fff on X\mathcal XX. Let r,R>0r,R>0r,R>0 be such that X\mathcal XX is contained in the Euclidean ball E0\mathcal E_0E0​ of center c0c_0c0​ and radius RRR and contains a Euclidean ball of radius rrr. Consider any run (ct,Ht,wt)t≥0(c_t,H_t,w_t)_{t\ge0}(ct​,Ht​,wt​)t≥0​ of the ellipsoid method started from E0\mathcal E_0E0​ (so H0=R2InH_0=R^2\mathrm I_nH0​=R2In​). Then for every integer t≥1t\ge1t≥1 with

t ≥ 2n2log⁡(R/r),t\ \ge\ 2n^2\log(R/r),t ≥ 2n2log(R/r),
  1. some center among c0,…,ct−1c_0,\dots,c_{t-1}c0​,…,ct−1​ lies in X\mathcal XX, and
  2. every xt∈argmin⁡{f(c):c∈{c0,…,ct−1}∩X}x_t\in\operatorname{argmin}\{f(c):c\in\{c_0,\dots,c_{t-1}\}\cap\mathcal X\}xt​∈argmin{f(c):c∈{c0​,…,ct−1​}∩X} satisfies
f(xt)−min⁡x∈Xf(x) ≤ 2BRrexp⁡(−t2n2).f(x_t)-\min_{x\in\mathcal X}f(x)\ \le\ \frac{2BR}{r}\exp\Big(-\frac{t}{2n^2}\Big).f(xt​)−x∈Xmin​f(x) ≤ r2BR​exp(−2n2t​).

The ellipsoid method thus reaches accuracy ε\varepsilonε after O(n2log⁡(1/ε))O(n^2\log(1/\varepsilon))O(n2log(1/ε)) oracle calls, each followed by an update costing O(n2)O(n^2)O(n2) arithmetic operations; this is what makes it a polynomial-time method whenever a separation oracle is available.

Formalization Note

  1. Rn\mathbb R^nRn is Fin n → ℝ; balls are Euclidean, written with the dot product.
  2. n≥2n\ge2n≥2 is added because the update (2.6) contains n2/(n2−1)n^2/(n^2-1)n2/(n2−1) and is defined only for n≥2n\ge2n≥2 (Lemma 2.3 gives it for n≥2n\ge2n≥2).
  3. The existence of x∗x^*x∗ is the book's standing assumption (p. 242).
  4. The page writes {c1,…,ct}\{c_1,\dots,c_t\}{c1​,…,ct​}; the centers queried during ttt iterations, whose cuts produce Et\mathcal E_tEt​, are c0,…,ct−1c_0,\dots,c_{t-1}c0​,…,ct−1​, and the statement uses these.
  5. t≥1t\ge1t≥1 is added: when R=rR=rR=r the threshold is t≥0t\ge0t≥0, and at t=0t=0t=0 no center has been queried, so the nonemptiness claim would fail.
  6. When an oracle answer is ws=0w_s=0ws​=0 (only possible at a minimizer cs∈Xc_s\in\mathcal Xcs​∈X) the run stops, as described in the definition module; the bound then holds trivially for t>st>st>s.
Preamble
import Mathlib
import Definitions.Def_ConvexOptAlg_Ellipsoid_Defs
Formal statement
namespace ConvexOptAlg.Ellipsoid

/-- **Theorem 2.4** (Bubeck, arXiv:1405.4980v2, p. 250). Let `n ≥ 2`, `X ⊂ ℝⁿ` a convex body,
`f : X → [−B, B]` continuous and convex with a minimizer `x∗` on `X`, and `r, R > 0` with
`X` inside the Euclidean ball of center `c₀` and radius `R` and containing a Euclidean ball of
radius `r`. For every run of the ellipsoid method from `E₀ = B(c₀, R)` and every
`t ≥ 2n² log(R/r)` with `t ≥ 1`: some center queried in the first `t` iterations
(`c₀, …, c_{t−1}`) lies in `X`, and every output `x_t` (a minimizer of `f` over those centers
in `X`) satisfies `f(x_t) − min_X f ≤ (2BR/r) exp(−t/(2n²))`.

Indexing: the page writes `{c₁, …, c_t}`; the centers queried in `t` iterations, whose cuts
produce `E_t`, are `c₀, …, c_{t−1}`. -/
theorem theorem_2_4 {n : ℕ} (hn : 2 ≤ n) (X : Set (Fin n → ℝ)) (hX : IsConvexBody X)
    (f : (Fin n → ℝ) → ℝ) (hfcont : ContinuousOn f X) (hfconv : ConvexOn ℝ X f)
    (B : ℝ) (hfB : ∀ x ∈ X, -B ≤ f x ∧ f x ≤ B)
    (r R : ℝ) (hr : 0 < r) (hR : 0 < R) (c0 : Fin n → ℝ) (hXR : X ⊆ euclBall c0 R)
    (z : Fin n → ℝ) (hXr : euclBall z r ⊆ X)
    (xstar : Fin n → ℝ) (hxstar : xstar ∈ X) (hmin : ∀ y ∈ X, f xstar ≤ f y)
    (c : ℕ → Fin n → ℝ) (H : ℕ → Matrix (Fin n) (Fin n) ℝ) (w : ℕ → Fin n → ℝ)
    (hrun : IsEllipsoidRun X f R c0 c H w)
    (t : ℕ) (ht1 : 1 ≤ t) (ht : 2 * (n : ℝ) ^ 2 * Real.log (R / r) ≤ (t : ℝ)) :
    (∃ s < t, c s ∈ X) ∧
      ∀ x : Fin n → ℝ, IsEllipsoidOutput X f c t x →
        f x - f xstar ≤ 2 * B * R / r * Real.exp (-(t : ℝ) / (2 * (n : ℝ) ^ 2)) := by sorry

end ConvexOptAlg.Ellipsoid
Source
Bubeck, arXiv:1405.4980v2, Theorem 2.4, p. 250 (method pp. 249–250, chapter setting p. 244)
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