Lemma 3.2, p. 300 — the cubes [0,1/ε]ⁿ and v+[0,1/ε]ⁿ overlap in at least a (1 − ε|v|₁) fraction
ProvedKalaiVempala.Lazy.lemma_3_2follow-the-perturbed-leaderlebesgue-measureonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Overlap of shifted cubes. Let and let be the uniform probability measure on the cube . For every ,
That is, the cubes and overlap in at least a fraction of their volume. In this mission it gives the update bound of FLL.
Formalization Note The fraction is the -measure of the overlap, written in ℝ≥0∞; when the left side is and the claim is trivial, as on the page. is perturbLaw n ε from OracleRO.ApproxFPL.FPL. The statement is identical to Lemma 3.2 of the companion mission on FPL(), restated because draft items cannot import each other.
Preamble
import Mathlib import Definitions.Def_OracleRO_ApproxFPL_FPL import Definitions.Def_KalaiVempala_Lazy_Setting open MeasureTheory OracleRO.ApproxFPL
Formal statement
namespace KalaiVempala.Lazy
theorem lemma_3_2 {n : ℕ} (ε : ℝ) (hε : 0 < ε) (v : Fin n → ℝ) :
ENNReal.ofReal (1 - ε * ∑ i, |v i|) ≤
perturbLaw n ε {x | x - v ∈ Set.Icc (0 : Fin n → ℝ) (fun _ => ε⁻¹)} := by sorry
end KalaiVempala.Lazy
Source
Kalai & Vempala, Efficient algorithms for online decision problems, J. Comput. System Sci. 71 (2005), p. 300, Lemma 3.2 (proof p. 301)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.