Skip to main content
PathsHoeffding finite-sum bound

Theorem trail

Hoeffding finite-sum bound

The bounded independent-sum theorem used inside learning bounds.

Open topicExplore AtlasClaim evidenceEvidence panel

Record

Research Record

A compact audit view for the theorem before the full source, proof, diagnostic, and failure-mode sections.

Claim scope
theorem
Evidence level
Exact Lean wrapper
Source precision
reviewed / A
Diagnostics
2 items
Exercises
1 exercise
Failure checks
2 checks
Open Atlas traceOpen evidence recordJump to sourcesJump to failures

Theorem Statement

Bounded variables are sub-Gaussian after centering. Once each centered variable has sub-Gaussian MGF parameter , independence lets those parameters add across the finite sum.

Assumptions

  • finite independent family
  • each variable is almost surely bounded in an interval
  • epsilon >= 0

Proof Sketch

Center each bounded variable, apply Hoeffding's lemma to each MGF, multiply MGFs by independence, and optimize the Chernoff parameter. The width terms add as .

Proof Obligations

Independent bounded centered summands

assumption

Verify each summand is bounded in its stated interval and the centered variables are independent before multiplying MGFs.

Adaptive or dependent sampling invalidates the product-MGF proof step and needs martingale-style conditions instead.

MGF product before Chernoff optimization

proof step

Apply Hoeffding's lemma to each summand, multiply the bounds by independence, and then optimize the Chernoff parameter.

Optimizing a tail parameter before establishing the summed MGF bound hides the independence assumption.

One-sided centered finite-sum scope

boundary

This trail covers the one-sided centered finite-sum theorem; average-form, iid, and two-sided wrappers need separate claim statements.

Collapsing all Hoeffding variants into one trail can create false source and Lean coverage claims.

Adaptive data needs martingale concentration

boundary

Before applying finite-sum Hoeffding, verify the summands are independent; learner-history or adaptive sampling should route to martingale concentration instead.

Using iid Hoeffding on adaptive diagnostic data can make uncertainty estimates look much sharper than the assumptions allow.

Source Locators

High-Dimensional Statistics (2019)

proof

Chapter 2 — Basic tail and concentration bounds

wainwright-2019:ch2

kind
chapter
review
reviewed / A
extract
manual

Chapter-level canonical support for bounded-variable Hoeffding bounds derived from sub-Gaussian MGF control.

High-Dimensional Statistics (2019)

proof

Proposition 2.5 — Hoeffding bound

wainwright-2019:prop2.5

kind
proposition
review
reviewed / A
extract
manual
number
2.5

Anchor: Hoeffding bound

Reviewed proposition-level support for the bounded-variable Hoeffding bound used by the finite-sum trail.

Curated Trace

  1. 1
    Bounded to sub-Gaussianupstream lemma

    Each centered bounded summand receives an MGF upper bound.

    Checkpoint

    Check the interval width for every summand.

  2. 2
    Independence productaggregation

    Independence lets the MGF of the sum factor into a product.

    Checkpoint

    This is the exact assumption that adaptive sampling breaks.

  3. 3
    Optimize lambdatail conversion

    Chernoff's method converts the summed MGF bound into a probability bound.

    Checkpoint

    The exponent must scale as epsilon squared divided by summed widths.

  4. 4
    Finite-sum Hoeffdingtheorem

    The proof chain yields the one-sided centered finite-sum statement.

    Checkpoint

    Two-sided and average-form variants require separate wrappers.

Failure Modes

One-sided centered finite-sum scope

This trail covers the one-sided centered finite-sum theorem; average-form, iid, and two-sided wrappers need separate claim statements.

Risk: Collapsing all Hoeffding variants into one trail can create false source and Lean coverage claims.

Check: This trail covers the one-sided centered finite-sum theorem; average-form, iid, and two-sided wrappers need separate claim statements.

Adaptive data needs martingale concentration

Before applying finite-sum Hoeffding, verify the summands are independent; learner-history or adaptive sampling should route to martingale concentration instead.

Risk: Using iid Hoeffding on adaptive diagnostic data can make uncertainty estimates look much sharper than the assumptions allow.

Check: Before applying finite-sum Hoeffding, verify the summands are independent; learner-history or adaptive sampling should route to martingale concentration instead.