Alphabeta Math
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 with its coordinate metric

Statement

Let d≥1, and let X=(X1,…,Xd) have independent random coordinates taking values in [0,1] on a probability space with probability P. Equip [0,1]d with the Euclidean distance ∥x−y∥2=(∑i=1d(xi−yi)2)1/2. Suppose f:[0,1]d→R is quasi-convex and L-Lipschitz for some L>0. Here quasi-convex means that every sublevel set {x:f(x)≤a} is convex, and L-Lipschitz means ∣f(x)−f(y)∣≤L∥x−y∥2 for all x,y in the cube. Let m be a median of f(X), meaning P(f(X)≤m)≥1/2 and P(f(X)≥m)≥1/2. Then, for every t>0, P(f(X)>m+t)≤2e−t2/(4L2) and P(f(X)<m−t)≤2e−t2/(4L2). Every convex function is quasi-convex, so the conclusion applies in particular to convex f.

External input

Boucheron, Lugosi and Massart, Theorem 7.12, gives the two stated median tail bounds with exponent −s2/4 for a quasi-convex Euclidean 1-Lipschitz function of independent [0,1]-valued coordinates. This imported theorem is used as a premise; its proof is not reconstructed here.

Facts & Assumptions

[F1]

The external input above supplies both tails for positive deviations s and Euclidean 1-Lipschitz quasi-convex functions.

[F2]

The coordinate metric and convex-function and Lipschitz conventions are as in Independent-entry coordinates, convexity and Lipschitz constants; convex subsets of Euclidean space are as in A convex subset of ℝᵐ contains every line segment between two of its points.

Proof

Given: The hypotheses and a median m in the statement.

Goal: Establish both scaled tail bounds and the convex special case.

1.1givenF2

Put g=f/L and mg=m/L. Since L>0, the sublevel sets of g are sublevel sets of f, and the Lipschitz inequality for f shows that g is Euclidean 1-Lipschitz. Dividing the two median inequalities by the positive constant shows that mg is a median of g(X).

2.1F1F2step 1.1∎

Apply [F1] to g with s=t/L>0. The events g(X)>mg+t/L and g(X)<mg−t/L are respectively the two events in the conclusion, giving the displayed bounds. If f is convex, its defining inequality shows that each sublevel set is convex; hence it is quasi-convex and the same bounds apply.

Depends on

Used by · 2

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.

External dependencies

Concentration Inequalities: A Nonasymptotic Theory of Independence · Section 7.5, Theorem 7.12, printed p. 222, PDF p. 231

For independent random variables $X_1,\ldots,X_d$ taking values in $[0,1]$ and a quasi-convex function $g:[0,1]^d\to\mathbb R$ satisfying $|g(x)-g(y)|\le\|x-y\|_2$, each of the probabilities $\mathbb P(g(X)>m_g+s)$ and $\mathbb P(g(X)<m_g-s)$ is at most $2e^{-s^2/4}$ for $s>0$, where $m_g$ is a median of $g(X)$.

Hypotheses: Independent $[0,1]$-valued coordinates; quasi-convexity; Lipschitz constant at most one for Euclidean distance; positive deviation; a median.

Reading limits: The theorem statement and preceding Euclidean metric and quasi-convexity conventions were read in the linked PDF. Its proof was not independently reconstructed or verified; no whole-book reading is claimed.

Sources