Lemma 7, p. 12 — Algorithm 2 terminates with an infeasible projection ỹ onto CH(αK) that is 3ε-close to a convex combination of oracle outputs
ProvedApproxOLO.FullInfo.lemma_7There is a universal constant (the constant of Lemma 5 that sets the number of Ellipsoid iterations in each call) such that the following holds. Let , let be an instance, an -approximation oracle (), and . Then Algorithm 2 on input terminates, and every terminating run returns a point , a distribution and extended-oracle outputs , with as prescribed in Lemma 5, such that
So is an infeasible projection of onto in the sense of Eq. (3), and it lies within of an explicit convex combination of oracle outputs; this is the projection step of Algorithm 3.
Formalization Note The page also states that Algorithm 2 terminates after at most iterations. That count does not follow from the proof (which gives , up to ) and a hand trace in dimension one (where the ellipsoid method is bisection) enters the loop more often than it allows, so the printed iteration bound is replaced by termination (existence of a complete run); see the moderation notes. The "Moreover" clause of the page (distance and query-count bounds) is not part of this statement. Each call of the procedure of Lemma 5 may use its own iteration budget , a positive integer at least for the current . The Ellipsoid method is the one fixed in the model (start , central cuts); as in Lemma 5. is Euclidean.
import Mathlib import Definitions.Def_ApproxOLO_FullInfo_Model
namespace ApproxOLO.FullInfo
open Matrix
/-- **Lemma 7, Garber, arXiv:1709.03093v1, p. 12 (items 1–2, with termination).** There is a
universal constant `c > 0` (the constant of Lemma 5 that fixes the number of Ellipsoid
iterations per call) such that for every `d ≥ 2`, instance, `α > 0`, oracle, `y ∈ ℝ^d` and
`ε ∈ (0, (α + 2)R]`: Algorithm 2 on `(y, ε)` has a complete (terminating) run, and every
complete run returns `ỹ`, `(a_1, …, a_N)` and oracle outputs `{(v_i, s_i)}` with
1. `‖ỹ − z‖² ≤ ‖y − z‖²` for all `z ∈ CH(αK)`;
2. `‖p − ỹ‖ ≤ 3ε` for `p = Σ_i a_i v_i`. -/
theorem lemma_7 : ∃ c : ℝ, 0 < c ∧ ∀ (d : ℕ), 2 ≤ d →
∀ (K Fs : Set (Vec d)) (R Fb C alpha : ℝ) (O : Vec d → Vec d) (y : Vec d) (eps : ℝ),
IsInstance K Fs R Fb C → 0 < alpha → IsApproxOracle K alpha O →
0 < eps → eps ≤ (alpha + 2) * R →
(∃ out : Alg2Out d, IsAlg2Run c O alpha R y eps out) ∧
∀ out : Alg2Out d, IsAlg2Run c O alpha R y eps out →
(∀ z ∈ scaledHull K alpha, euclNorm (out.yt - z) ^ 2 ≤ euclNorm (y - z) ^ 2) ∧
euclNorm (∑ i, out.a i • (out.pts i).1 - out.yt) ≤ 3 * eps := by sorry
end ApproxOLO.FullInfo
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.