LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A variance-sensitive bound for bounded empirical suprema

Statement

Let $X_{1}, \dots, X_{n}$ be iid with law $P$ , $n \geq 1$ , and let $F$ be a finite or countable class of measurable real functions containing $0$ . Suppose $∣ f ∣ \leq B$ everywhere and $P f^{2} \leq s^{2}$ for all $f \in F$ , with finite $B, s \geq 0$ . Put $Z = \sup_{f \in F} \sum_{i = 1}^{n} (f (X_{i}) - P f), W = \sup_{f \in F} \sum_{i = 1}^{n} f (X_{i})^{2}, m = E W .$ For every $x > 0$ , $P (Z > E Z + 2 \sqrt{(8 m + 4 n s^{2}) x} + \sqrt{8} B x) \leq e^{- x} .$ The bound uses second moments, not only variances. All suprema are measurable by countability. No choice axiom is assumed.

Facts & Assumptions

Given: The iid sample, countable class containing zero, and boundedness and second-moment hypotheses in the Statement.

[F1]

Independent random elements have product joint law and Fubini's theorem for L^1 functions on a sigma-finite product allow coordinatewise integration and independent ghost coordinates on the finite product law.

[F2]

Jensen's inequality for expectation gives Jensen's inequality for convex functions; Dominated convergence permits bounded limits under integration.

[F3]

Markov's inequality for random variables turns exponential-moment bounds into tail bounds. Logarithm and exponential obey their usual derivative rules (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, The exponential function is smooth and $(\exp)^{'} = \exp$ ).

Proof

Given: The objects and hypotheses in the Statement. First take a finite class and $B > 0$ ; the case $B = 0$ is immediate.

1.1F1F2F3algebra

For positive bounded $U$ bounded away from zero, define $Ent (U) = E [U \log U] - E U \log E U$ . The function $Φ (u, a) = u \log (u / a) - u + a$ is jointly convex: its Hessian quadratic form is $(d u - (u / a) d a)^{2} / u \geq 0$ . Direct differentiation in $a$ gives $Ent (U) = \inf_{a > 0} E Φ (U, a)$ , attained at $a = E U$ . If $E_{i}$ integrates coordinate $i$ , the product identity $Ent (U) = E_{- i} {Ent}_{i} (U) + {Ent}_{- i} (E_{i} U)$ is obtained by adding and subtracting $E [(E_{i} U) \log (E_{i} U)]$ . Joint convexity gives ${Ent}_{j} (E_{i} U) \leq E_{i} {Ent}_{j} (U)$ for $j \neq i$ : apply Jensen to $Φ (E_{i} U, E_{i} E_{j} U)$ and integrate coordinate $j$ . Induction in the product identity proves tensorization $Ent (U) \leq E \sum_{i} {Ent}_{i} (U)$ . All integrations here are on finite product laws.

2.1F1F2step 1.1algebra

Let $Z_{i}^{'}$ replace $X_{i}$ by an independent copy and put $V_{+} = \sum_{i} E_{i}^{'} (Z - Z_{i}^{'})_{+}^{2}$ . Jensen for the logarithm gives ${Ent}_{i} (e^{t Z}) \leq {Cov}_{i} (e^{t Z}, t Z)$ for $t > 0$ . A fresh-copy expansion expresses this covariance as $\frac{t}{2} E_{i, i^{'}} [(e^{t Z} - e^{t Z_{i}^{'}}) (Z - Z_{i}^{'})]$ . Swap the two copies to restrict to $Z > Z_{i}^{'}$ and use $1 - e^{- t a} \leq t a$ for $a \geq 0$ . Tensorization from step 1.1 then yields $Ent (e^{t Z}) \leq t^{2} E [e^{t Z} V_{+}]$ . Choose the first maximizing function $f_{*}$ for $Z$ in a fixed finite ordering. Since $Z - Z_{i}^{'} \leq f_{*} (X_{i}) - f_{*} (X_{i}^{'})$ , the bound $(a - b)^{2} \leq 2 a^{2} + 2 b^{2}$ gives $V_{+} \leq 2 W + 2 n s^{2}$ .

2.2F2F3step 1.1algebra

Write $c = B^{2}$ and $W_{i} = \sup_{f} \sum_{j \neq i} f (X_{j})^{2}$ . Choosing a common maximizer for $W$ shows $0 \leq Δ_{i} = W - W_{i} \leq c$ and $\sum_{i} Δ_{i} \leq W$ . Use the conditional variational formula of step 1.1 with comparator $e^{a W_{i}}$ , which is independent of coordinate $i$ . With $ψ (u) = e^{u} - u - 1$ , it gives ${Ent}_{i} (e^{a W}) \leq E_{i} [e^{a W} ψ (- a Δ_{i})]$ . Convexity and $ψ (0) = 0$ imply $ψ (- a Δ_{i}) \leq (Δ_{i} / c) ψ (- a c)$ . Tensorization therefore implies, for $L (a) = \log E e^{a W}$ , $a L^{'} (a) - L (a) \leq ψ (- a c) L^{'} (a) / c$ , or $(1 - e^{- a c}) L^{'} (a) \leq c L (a)$ . If $m = 0$ , $W = 0$ almost surely and the following bound is immediate. Otherwise differentiating $L (a) / (e^{a c} - 1)$ shows it is nonincreasing; its limit at zero is $m / c$ . Thus $L (a) \leq (m / c) (e^{a c} - 1) \leq 2 a m$ whenever $0 \leq a c \leq 1 / 2$ , where the last scalar inequality follows by integrating $e^{u} \leq 2$ on $[0, 1 / 2]$ .

3.1F2F3step 2.1step 2.2algebra

Put $H (t) = \log E e^{t Z}$ and $D = t H^{'} (t) - H (t)$ , and let $E_{t}$ denote integration against density $e^{t Z - H (t)}$ . Step 2.1 gives $D \leq 2 t^{2} E_{t} W + 2 t^{2} n s^{2}$ . Jensen under this tilted law applied to $e^{a W} / e^{t Z - H (t)}$ gives $a E_{t} W \leq L (a) + D$ ; indeed its expectation under the tilt is $E e^{a W}$ , while the expectation of its logarithm is $a E_{t} W - D$ . Taking $a = 4 t^{2}$ and using step 2.2 yields $D \leq (8 m + 4 n s^{2}) t^{2}$ for $0 < t \leq 1 / (\sqrt{8} B)$ . Integrating $(H (t) / t)^{'} = D / t^{2}$ from zero proves $\log E e^{t (Z - E Z)} \leq A t^{2}$ , where $A = 8 m + 4 n s^{2}$ .

4.1F2F3step 3.1algebra∎

Put $b = \sqrt{8} B$ . If $A > 0$ , choose $t = \sqrt{x} / (\sqrt{A} + b \sqrt{x}) < 1 / b$ . Markov's inequality and step 3.1 show that a deviation of size $A t + x / t$ has probability at most $e^{- x}$ . Since $A t + x / t \leq 2 \sqrt{A x} + b x$ , the stated tail bound follows. The case $A = 0$ follows by taking $t ↑ 1 / b$ in the same exponential bound. Finally enumerate a countable class with zero first and increase its finite initial subclasses. Their $Z, W$ increase to the displayed suprema and are bounded by $2 n B, n B^{2}$ ; bounded convergence passes the exponential bounds and their expectations to the limit. The same Chernoff argument proves the assertion for the countable class.

Depends on

Used by

Correct-scale slab bound for multivariate trimming Proposition

Dependency tree · two levels

45 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Boucheron, Bousquet, Lugosi and Massart, Moment Inequalities for Functions of Independent Random Variables, Section 3, pp. 9-16 (standard reference, not scraped)