Lemma 3.2, pp. 300–301 — [0,1/ε]ⁿ and v+[0,1/ε]ⁿ overlap in at least a (1 − ε|v|₁) fraction
ProvedKalaiVempala.Additive.lemma_3_2follow-the-perturbed-leadermeasure-theoryonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Overlap of translated cubes. Let , let , and let with . Then the cubes and overlap in at least a fraction of the volume of :
Equivalently, if is uniformly distributed on , then . In the analysis of Follow the Perturbed Leader this says that the laws of and , uniform on cubes shifted by , agree on all but an fraction.
Formalization Note The fraction is the probability, under the uniform law perturbLaw n ε on from OracleRO.ApproxFPL.FPL, of the set . The left side is ENNReal.ofReal (1 - ε|v|₁), which is when , so the statement is then trivially true, as on the page. The hypothesis is added because the cube has side .
Preamble
import Mathlib import Definitions.Def_OracleRO_ApproxFPL_FPL import Definitions.Def_KalaiVempala_Additive_Setting open MeasureTheory OracleRO.ApproxFPL
Formal statement
namespace KalaiVempala.Additive
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.Additive
Source
Kalai & Vempala, Efficient algorithms for online decision problems, J. Comput. System Sci. 71 (2005), pp. 300–301, Lemma 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.