TheoremStatement: AI-adaptedProof: AI-generated

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.

Convex Lipschitz concentration — Theorem 6.5

PDF p. 34: Theorem 6.5, equation (6.4); PDF p. 35: Theorem 6.5, equation (6.4)

Statement

Let $d \geq 1$ be an integer and $X = (X_{1}, \dots, X_{d})$ a vector of independent random variables taking values in $[0, 1]$ on a probability space with probability $P$ . Let $f : [0, 1]^{d} \to R$ be convex and 1-Lipschitz for Euclidean distance $∥ x - y ∥_{2} = (\sum_{i = 1}^{d} (x_{i} - y_{i})^{2})^{1 / 2}$ . Thus convexity means $f ((1 - λ) x + λ y) \leq (1 - λ) f (x) + λ f (y)$ for $x, y$ in the cube and $0 \leq λ \leq 1$ , and 1-Lipschitz means $∣ f (x) - f (y) ∣ \leq ∥ x - y ∥_{2}$ for such $x, y$ .

Let $M f (X)$ be a median of $f (X)$ , meaning that $P (f (X) \leq M f (X)) \geq 1 / 2$ and $P (f (X) \geq M f (X)) \geq 1 / 2$ . Then, for every $t > 0$ , $P (f (X) > M f (X) + t) \leq 2 e^{- t^{2} / 4}$ .

Statement references

Coordinate metric, convexity and Lipschitz constants

Independent random elements

Random elements and real random variables

Probability measures and probability spaces

Convex Lipschitz concentration with its coordinate metric

Facts & Assumptions

[F1]

For independent $[0, 1]$ -valued coordinates, a convex Euclidean $L$ -Lipschitz function with $L > 0$ , a median $m$ , and $t > 0$ , the upper-tail probability is at most $2 e^{- t^{2} / (4 L^{2})}$ (Convex Lipschitz concentration with its coordinate metric).

[F2]

Convexity and the Lipschitz condition use the stated Euclidean coordinate metric (Independent-entry coordinates, convexity and Lipschitz constants).

Proof

Given: The independent coordinates, convex 1-Lipschitz function, median $M f (X)$ , and $t > 0$ in the statement.

Goal: Prove the stated upper-tail bound.

1.1givenF1F2

The hypotheses give a convex function on the coordinate cube with Euclidean Lipschitz bound $L = 1$ and independent $[0, 1]$ -valued coordinates. The number $M f (X)$ satisfies both median inequalities required by [F1].

2.1F1step 1.1algebra∎

Apply [F1] with $L = 1$ , $m = M f (X)$ and the given $t > 0$ . The exponent becomes $- t^{2} / 4$ , yielding $P (f (X) > M f (X) + t) \leq 2 e^{- t^{2} / 4}$ , as claimed.

Source notes

The article attributes this concentration result to Boucheron, Lugosi and Massart, Theorem 7.12. Its displayed function domain uses $n$ after introducing $d$ coordinates; the statement above uses $d$ consistently. The article reference records attribution, while [F1] supplies the argument.

Depends on

Used by · 1

Median–mean gap for convex Lipschitz concentration

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

Sources

Expander graphs are globally synchronizing · PDF pp. 34–35, Theorem 6.5 and equation (6.4)