Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5, pp. 9–10 — the ellipsoid separation-or-decomposition procedure returns a margin-ε separator or a 3ε-close convex combination of oracle outputs

Proved
ApproxOLO.FullInfo.lemma_5

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

approximation-algorithmsellipsoid-methodp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1separation-oracle

There is a universal constant c>0c>0c>0 such that the following holds. Let d≥2d\ge2d≥2, let K,F,R,F,C\mathcal K,\mathcal F,R,F,CK,F,R,F,C be an instance, OK\mathcal O_{\mathcal K}OK​ an α\alphaα-approximation oracle (α>0\alpha>0α>0), x∈Rdx\in\mathbb R^dx∈Rd, ε∈(0,(α+2)R]\varepsilon\in(0,(\alpha+2)R]ε∈(0,(α+2)R], and NNN a positive integer with

N≥c d2ln⁡((α+1)R+∥x∥ε).N\ge c\,d^2\ln\Big(\frac{(\alpha+1)R+\|x\|}{\varepsilon}\Big).N≥cd2ln(ε(α+1)R+∥x∥​).

Run the Ellipsoid method for NNN iterations on the feasibility problem

find w∈Rd:(x−z)⋅w≥ε  ∀z∈αK,∥w∥≤1,(4)\text{find }w\in\mathbb R^d:\quad (x-z)\cdot w\ge\varepsilon\ \ \forall z\in\alpha\mathcal K,\qquad\|w\|\le1,\tag{4}find w∈Rd:(x−z)⋅w≥ε  ∀z∈αK,∥w∥≤1,(4)

where each iteration, at the current center www, queries (v,s)=O^K(−w)(v,s)=\hat{\mathcal O}_{\mathcal K}(-w)(v,s)=O^K​(−w), cuts with v−xv-xv−x if (x−v)⋅w<ε(x-v)\cdot w<\varepsilon(x−v)⋅w<ε, otherwise cuts with www if ∥w∥>1\|w\|>1∥w∥>1, and otherwise declares (4) feasible.

  1. If the method declares (4) feasible at some iteration, the center www of that iteration is a feasible solution of (4).
  2. If it completes NNN iterations without declaring feasibility, let v1,…,vNv_1,\dots,v_Nv1​,…,vN​ be the oracle outputs gathered and (a1,…,aN)(a_1,\dots,a_N)(a1​,…,aN​) any optimal solution of Problem (5). Then p=∑i=1Naivip=\sum_{i=1}^Na_iv_ip=∑i=1N​ai​vi​ satisfies
∥x−p∥≤3ε.\|x-p\|\le3\varepsilon.∥x−p∥≤3ε.

So, with a number of oracle calls logarithmic in the scale, one either separates xxx from CH(αK)\mathrm{CH}(\alpha\mathcal K)CH(αK) with margin ε\varepsilonε or writes a point 3ε3\varepsilon3ε-close to xxx as a convex combination of extended-oracle outputs.

Formalization Note The constant ccc is quantified once, before the dimension and the instance. The Ellipsoid method is fixed as: start at the unit ball B(0,1)\mathcal B(0,1)B(0,1), standard central-cut update (the reused LinearOptimization update formulas, cut vectors x−vx-vx−v and −w-w−w in their sign convention); the paper only cites "the well known Ellipsoid method". d≥2d\ge2d≥2 is required because the central-cut update has the factor d2/(d2−1)d^2/(d^2-1)d2/(d2−1). The feasibility claim is stated for every iteration at which the method would declare feasibility, which includes the first one (the one returned). ∥⋅∥\|\cdot\|∥⋅∥ is Euclidean.

Preamble
import Mathlib
import Definitions.Def_ApproxOLO_FullInfo_Model
Formal statement
namespace ApproxOLO.FullInfo

open Matrix

/-- **Lemma 5 (Separation-or-Decomposition via the Ellipsoid method), Garber,
arXiv:1709.03093v1, pp. 9–10.** There is a universal constant `c > 0` such that the following
holds for every `d ≥ 2`, instance, `α > 0`, oracle, `x ∈ ℝ^d`, `ε ∈ (0, (α + 2)R]` and positive
integer `N ≥ c d² ln(((α+1)R + ‖x‖)/ε)`. Run the Ellipsoid method of Lemma 5 on Problem (4)
(from `B(0, 1)`) for `N` iterations.
* If it declares Problem (4) feasible at iteration `k < N`, the iterate `w_k` is a feasible
  solution of (4): `(x − z) · w_k ≥ ε` for all `z ∈ αK`, and `‖w_k‖ ≤ 1`.
* If it completes `N` iterations without declaring feasibility, then for every optimal solution
  `(a_1, …, a_N)` of Problem (5) over the gathered oracle outputs `v_1, …, v_N`, the point
  `p = Σ_i a_i v_i` satisfies `‖x − p‖ ≤ 3ε`. -/
theorem lemma_5 : ∃ c : ℝ, 0 < c ∧ ∀ (d : ℕ), 2 ≤ d →
    ∀ (K Fs : Set (Vec d)) (R Fb C alpha : ℝ) (O : Vec d → Vec d) (x : Vec d) (eps : ℝ)
      (N : ℕ),
    IsInstance K Fs R Fb C → 0 < alpha → IsApproxOracle K alpha O →
    0 < eps → eps ≤ (alpha + 2) * R → 1 ≤ N →
    c * (d : ℝ) ^ 2 * Real.log (((alpha + 1) * R + euclNorm x) / eps) ≤ (N : ℝ) →
    (∀ k < N, ellFeasibleAt O alpha R x eps k →
      (∀ z ∈ K, eps ≤ (x - alpha • z) ⬝ᵥ (ellIter O alpha R x eps k).1) ∧
        euclNorm (ellIter O alpha R x eps k).1 ≤ 1) ∧
    ((∀ k < N, ¬ ellFeasibleAt O alpha R x eps k) →
      ∀ a : Fin N → ℝ, IsSimplexOpt (fun i => (ellOut O alpha R x eps i).1) x a →
        euclNorm (x - ∑ i, a i • (ellOut O alpha R x eps i).1) ≤ 3 * eps) := by sorry

end ApproxOLO.FullInfo
Source
Garber, Efficient Online Linear Optimization with Approximation Algorithms, arXiv:1709.03093v1, pp. 9–10, Lemma 5 (Problems (4) and (5))
Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

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