Lemma 5, pp. 9–10 — the ellipsoid separation-or-decomposition procedure returns a margin-ε separator or a 3ε-close convex combination of oracle outputs
ProvedApproxOLO.FullInfo.lemma_5There is a universal constant such that the following holds. Let , let be an instance, an -approximation oracle (), , , and a positive integer with
Run the Ellipsoid method for iterations on the feasibility problem
where each iteration, at the current center , queries , cuts with if , otherwise cuts with if , and otherwise declares (4) feasible.
- If the method declares (4) feasible at some iteration, the center of that iteration is a feasible solution of (4).
- If it completes iterations without declaring feasibility, let be the oracle outputs gathered and any optimal solution of Problem (5). Then satisfies
So, with a number of oracle calls logarithmic in the scale, one either separates from with margin or writes a point -close to as a convex combination of extended-oracle outputs.
Formalization Note The constant is quantified once, before the dimension and the instance. The Ellipsoid method is fixed as: start at the unit ball , standard central-cut update (the reused LinearOptimization update formulas, cut vectors and in their sign convention); the paper only cites "the well known Ellipsoid method". is required because the central-cut update has the factor . The feasibility claim is stated for every iteration at which the method would declare feasibility, which includes the first one (the one returned). is Euclidean.
import Mathlib import Definitions.Def_ApproxOLO_FullInfo_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.