Eq. (7), p. 303 — E[M(s_{1:t−1}+p)·s_t] = ∫ (M(s_{1:t}+y)·s_t) e^{−ε(|y+s_t|₁−|y|₁)} dμ(y)
ProvedKalaiVempala.Multiplicative.eq_7change-of-variablesfollow-the-perturbed-leaderlaplace-distributionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be the FPL* perturbation law on (density ), let be measurable, let and . Then
The identity compares FPL*, which uses , with the "be the perturbed leader" algorithm, which uses : the two expectations differ only through the ratio of the densities of at and at .
Formalization Note The identity holds for every measurable and every real state sequence: the oracle property, the nonnegativity of and the parameters are not used and are not hypotheses. Measurability of is added, as in every statement of the mission, because the expectations presuppose it. The condition makes .
Preamble
import Mathlib import Definitions.Def_OracleRO_ApproxFPL_FPL import Definitions.Def_KalaiVempala_Multiplicative_Setting open MeasureTheory OracleRO.ApproxFPL
Formal statement
namespace KalaiVempala.Multiplicative
theorem eq_7 {n : ℕ} (M : (Fin n → ℝ) → (Fin n → ℝ)) (hMmeas : Measurable M)
(s : ℕ → Fin n → ℝ) (ε : ℝ) (hε : 0 < ε) (t : ℕ) (ht : 1 ≤ t) :
∫ x, M (prefixSum s (t - 1) + x) ⬝ᵥ s t ∂(laplaceLaw n ε) =
∫ y, (M (prefixSum s t + y) ⬝ᵥ s t) *
Real.exp (-(ε * (∑ i, |y i + s t i| - ∑ i, |y i|))) ∂(laplaceLaw n ε) := by sorry
end KalaiVempala.Multiplicative
Source
Kalai & Vempala, Efficient algorithms for online decision problems, J. Comput. System Sci. 71 (2005), p. 303, display (7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.