Lemma 9, p. 14 — for i.i.d. standard exponentials, P(Σ_{e≤N} max_i R_e(i) > 6N log n) ≤ e^{−N}
ProvedLimitedSwitching.HighProb.lemma_9concentrationexponential-distributionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be integers and let be i.i.d. standard exponential random variables. Then
The maximum of standard exponentials has mean about . The lemma says that a sum of independent such maxima exceeds six times its order of magnitude only with exponentially small probability in . In Theorem 8 it controls the total perturbation over the epochs.
Formalization Note The rows are indexed by under the product of copies of the -fold exponential product law. The probability is the outer measure of the event.
Preamble
import Mathlib import Definitions.Def_LimitedSwitching_HighProb_Setting open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace LimitedSwitching.HighProb
theorem lemma_9 {N n : ℕ} [NeZero n] (hN : 2 ≤ N) (hn : 2 ≤ n) :
(Measure.pi (fun _ : Fin N => expLaw n))
{R | 6 * (N : ℝ) * Real.log n < ∑ e, Finset.univ.sup' Finset.univ_nonempty (R e)}
≤ ENNReal.ofReal (Real.exp (-(N : ℝ))) := by sorry
end LimitedSwitching.HighProb
Source
Altschuler & Talwar, Online learning over a finite action set with limited switching, arXiv:1803.01548v2, p. 14, Lemma 9; proof p. 29, Appendix D
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.