Lemma 1, p. 6 — the extended approximation oracle: v · c ≤ min over αK, s dominates v on F, ‖v‖ ≤ (α + 2)R
ProvedApproxOLO.FullInfo.lemma_1approximation-algorithmslinear-optimization-oracleonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , be an instance of online linear optimization (compact sets, nonempty, on , on , ), and let be an -approximation oracle for some . For every , the extended oracle output of Eq. (2) satisfies , , and
- for every : if , and if ;
- .
The extended oracle accepts every direction in , not only those in ; it optimizes as well as any point of while returning, alongside the possibly infeasible point , a feasible point that dominates it on every loss/payoff vector.
Formalization Note is the Euclidean norm. Membership in is stated as for some (closed ball), and item 1 as for every .
Preamble
import Mathlib import Definitions.Def_ApproxOLO_FullInfo_Model
Formal statement
namespace ApproxOLO.FullInfo
open Matrix
/-- **Lemma 1 (Extended approximation oracle), Garber, arXiv:1709.03093v1, p. 6.** For every
`c ∈ ℝ^d`, `(v, s) = Ô_K(c)` satisfies `s ∈ K`, `v ∈ K + B(0, (1 + α)R)`, and
1. `v · c ≤ min_{x∈αK} x · c`;
2. `∀ f ∈ F`: `s · f ≤ v · f` if `α ≥ 1` and `s · f ≥ v · f` if `α < 1`;
3. `‖v‖ ≤ (α + 2)R`. -/
theorem lemma_1 {d : ℕ} (K Fs : Set (Vec d)) (R Fb C alpha : ℝ) (O : Vec d → Vec d)
(hinst : IsInstance K Fs R Fb C) (halpha : 0 < alpha) (hO : IsApproxOracle K alpha O)
(c : Vec d) :
(extOracle O alpha R c).2 ∈ K ∧
(∃ k ∈ K, euclNorm ((extOracle O alpha R c).1 - k) ≤ (1 + alpha) * R) ∧
(∀ z ∈ K, (extOracle O alpha R c).1 ⬝ᵥ c ≤ (alpha • z) ⬝ᵥ c) ∧
(∀ f ∈ Fs, (1 ≤ alpha → (extOracle O alpha R c).2 ⬝ᵥ f ≤ (extOracle O alpha R c).1 ⬝ᵥ f) ∧
(alpha < 1 → (extOracle O alpha R c).1 ⬝ᵥ f ≤ (extOracle O alpha R c).2 ⬝ᵥ f)) ∧
euclNorm (extOracle O alpha R c).1 ≤ (alpha + 2) * R := by sorry
end ApproxOLO.FullInfo
Source
Garber, Efficient Online Linear Optimization with Approximation Algorithms, arXiv:1709.03093v1, p. 6, Lemma 1 (Eq. (2))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.