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²))
ProvedConvexOptAlg.Ellipsoid.theorem_2_4convergence-rateconvex-optimizationellipsoid-methodoracle-complexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let and let be a convex body (compact, convex, with non-empty interior). Let be continuous and convex on with values in , and let be a minimizer of on . Let be such that is contained in the Euclidean ball of center and radius and contains a Euclidean ball of radius . Consider any run of the ellipsoid method started from (so ). Then for every integer with
- some center among lies in , and
- every satisfies
The ellipsoid method thus reaches accuracy after oracle calls, each followed by an update costing arithmetic operations; this is what makes it a polynomial-time method whenever a separation oracle is available.
Formalization Note
- is
Fin n → ℝ; balls are Euclidean, written with the dot product. - is added because the update (2.6) contains and is defined only for (Lemma 2.3 gives it for ).
- The existence of is the book's standing assumption (p. 242).
- The page writes ; the centers queried during iterations, whose cuts produce , are , and the statement uses these.
- is added: when the threshold is , and at no center has been queried, so the nonemptiness claim would fail.
- When an oracle answer is (only possible at a minimizer ) the run stops, as described in the definition module; the bound then holds trivially for .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.