Lemma 6, p. 11 — if min_i (x − v_i) · w ≤ ε for every unit w, an optimal point p of Problem (5) satisfies ‖p − x‖ ≤ ε
ProvedApproxOLO.FullInfo.lemma_6approximation-algorithmsconvex-geometryminimum-norm-pointp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix , vectors with , and . Suppose that for every Euclidean unit vector ,
Let be an optimal solution of Problem (5), i.e. a minimizer of over the probability simplex. Then the point satisfies
The lemma converts the absence of a separating direction with margin into an explicit convex combination of the that is -close to ; it is the decomposition half of the separation-or-decomposition procedure (Lemma 5).
Formalization Note is Euclidean, and a unit vector is one of Euclidean norm 1. is implicit in the page's and in the simplex constraint of Problem (5).
Preamble
import Mathlib import Definitions.Def_ApproxOLO_FullInfo_Model
Formal statement
namespace ApproxOLO.FullInfo
open Matrix
/-- **Lemma 6, Garber, arXiv:1709.03093v1, p. 11.** Fix `x ∈ ℝ^d`, vectors `v_1, …, v_N ∈ ℝ^d`
(`N ≥ 1`) and `ε > 0`. If for every (Euclidean) unit vector `w`,
`min_{i∈{1,…,N}} (x − v_i) · w ≤ ε`, then for every optimal solution `(a_1, …, a_N)` of
Problem (5) the point `p = Σ_i a_i v_i` satisfies `‖p − x‖ ≤ ε`. -/
theorem lemma_6 {d N : ℕ} (hN : 1 ≤ N) (x : Vec d) (v : Fin N → Vec d) (eps : ℝ)
(heps : 0 < eps) (hmin : ∀ w : Vec d, euclNorm w = 1 → ∃ i, (x - v i) ⬝ᵥ w ≤ eps)
(a : Fin N → ℝ) (ha : IsSimplexOpt v x a) :
euclNorm (∑ i, a i • v i - x) ≤ eps := by sorry
end ApproxOLO.FullInfo
Source
Garber, Efficient Online Linear Optimization with Approximation Algorithms, arXiv:1709.03093v1, p. 11, Lemma 6 (Problem (5), p. 10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.