Proof of Thm 1.1(b), p. 303 — Σ M(s_{1:t}+p₁)·s_t ≤ M(s_{1:T})·s_{1:T} + D|p₁|_∞
ProvedKalaiVempala.Multiplicative.bound_shared_perturbationbe-the-leaderfollow-the-perturbed-leaderonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a decision set whose -diameter is at most , i.e. for all , and let be an argmin oracle for . For every state sequence and every fixed perturbation vector ,
This is the "be the perturbed leader" bound with one perturbation shared by all periods, the special case of Lemma 3.1 of the paper. It is the deterministic half of the proof of Theorem 1.1(b): the perturbation costs at most times its sup norm.
Formalization Note is the Lean norm ‖p₁‖, which on Fin n → ℝ is the sup norm. The bound holds for arbitrary real states; the set , the nonnegativity of and , and the parameters , are not used and are not hypotheses.
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 bound_shared_perturbation {n : ℕ} (Dset : Set (Fin n → ℝ))
(M : (Fin n → ℝ) → (Fin n → ℝ)) (hM : KalaiVempala.Additive.IsArgminOracle Dset M)
(Ddiam : ℝ) (hD : ∀ d ∈ Dset, ∀ d' ∈ Dset, ∑ i, |d i - d' i| ≤ Ddiam)
(s : ℕ → Fin n → ℝ) (T : ℕ) (p₁ : Fin n → ℝ) :
∑ t ∈ Finset.Icc 1 T, M (prefixSum s t + p₁) ⬝ᵥ s t ≤
M (prefixSum s T) ⬝ᵥ prefixSum s T + Ddiam * ‖p₁‖ := by sorry
end KalaiVempala.Multiplicative
Source
Kalai & Vempala, Efficient algorithms for online decision problems, J. Comput. System Sci. 71 (2005), p. 303, proof of Theorem 1.1(b), first display (by Lemma 3.1, p. 300)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.