Helper lemmas #
For each outcome ω, if the linear functional g(ω) exceeds threshold t at some point θ in the convex hull of S, then by Lemma 1.15 it also exceeds t at some vertex v ∈ S.
Part (c): Tail probability bound #
Theorem 1.16(c): Sub-Gaussian tail bound over polytope. P(max_{θ ∈ conv(S)} g(ω)(θ) > t) ≤ N · exp(-t²/(2σ²))
Theorem 1.16(c) (alternative formulation with ENNReal.ofReal (S.card * ...)).
Part (a): Expectation bound (one-sided) #
Parametric bound for sup over finset: for any s > 0, E[sup_{v ∈ S} g(ω)(v)] ≤ log(S.card)/s + σ²·s/2.
Theorem 1.16(a): E[max_{θ ∈ conv(S)} g(ω)(θ)] ≤ √σ² · √(2 log N).
Part (b): Expectation bound (absolute value) #
Parametric bound for abs-sup over finset: E[sup_{v ∈ S} |g(ω)(v)|] ≤ log(2·S.card)/s + σ²·s/2.
Theorem 1.16(b): E[max_{θ ∈ conv(S)} |g(ω)(θ)|] ≤ √σ² · √(2 log(2N)).
Part (d): Absolute value tail probability bound #
For each outcome ω, if the absolute value |g(ω)(θ)| exceeds threshold t at some point θ in the convex hull of S, then |g(ω)(v)| also exceeds t at some vertex v ∈ S. This follows by case-splitting on the sign: if g(ω)(θ) > t, use Lemma 1.15 to find v with g(ω)(v) ≥ g(ω)(θ) > t; if g(ω)(θ) < -t, use Lemma 1.15 on -g(ω) to find v with g(ω)(v) ≤ g(ω)(θ) < -t.
Theorem 1.16(d): Sub-Gaussian absolute-value tail bound over polytope. P(max_{θ ∈ conv(S)} |g(ω)(θ)| > t) ≤ 2N · exp(-t²/(2σ²))
Bundled theorem #
Theorem 1.16 (Sub-Gaussian polytope bound).
Let P be a polytope with N vertices and X a sub-Gaussian random vector with variance proxy σ². Then:
- (a) E[max_{θ∈P} θ⊤X] ≤ σ√(2 log N)
- (b) E[max_{θ∈P} |θ⊤X|] ≤ σ√(2 log(2N))
- (c) P(max_{θ∈P} θ⊤X > t) ≤ N · exp(-t²/(2σ²))
- (d) P(max_{θ∈P} |θ⊤X| > t) ≤ 2N · exp(-t²/(2σ²))
Backward-compatible aliases for downstream files #
Alias for SubGaussianPolytope.tail_bound.
Alias for SubGaussianPolytope.tail_bound'.
Alias for SubGaussianPolytope.expectation_max_bound.