Bousquet condition (3): for suprema of sums
Provedsum_sup_sub_leconcentrationorderprobability
Bousquet's structural condition (3) for suprema of sums. Let over a nonempty finite family and the leave-coordinate--out supremum, with all . Then . Holds for the supremum of sums with NO monotonicity / self-bounding assumption beyond — the 'drop one coordinate from the maximiser' estimate the entropy-method route needs.
Preamble
import Mathlib.Algebra.Order.BigOperators.Group.Finset import Mathlib.Order.CompleteLattice.Finset import Mathlib.Data.Finset.Max import Mathlib.Tactic open Finset
Formal statement
theorem sum_sup_sub_le
{ι S : Type*} [DecidableEq ι] [Fintype ι] [Fintype S] [Nonempty S]
(X : ι → S → ℝ) (hX : ∀ i s, 0 ≤ X i s)
(Z : ℝ) (Zk : ι → ℝ)
(hZ : Z = Finset.univ.sup' Finset.univ_nonempty (fun s => ∑ i, X i s))
(hZk : ∀ k, Zk k = Finset.univ.sup' Finset.univ_nonempty (fun s => ∑ i ∈ Finset.univ.erase k, X i s)) :
∑ k, (Z - Zk k) ≤ Z := by sorrySource
Bousquet 2002 C.R.Acad.Sci.334:495-500 §3 (condition (3)); Klein–Rio 2005 Ann.Probab.33 §3 (arXiv:math/0506594); BLM Concentration Inequalities §11.2.