---
kind: concept
slug: concentration-of-measure
title: Concentration of measure
summary: >-
  In high dimension, random points crowd near a shell, so one linear functional can often separate a point or small group from all the others with high probability. One card covers it so far: a review of separation theorems with a one-shot linear corrector for AI errors. It has no new experiments, and its bounds hold only for i.i.d. samples from named distributions.
tags: [high-dimensional-data, measure-concentration, linear-classifier]
papers: ["1801.03421"]
related: [intrinsic-dimension, dimensionality-reduction]
status: draft
updated_at: 2026-11-09
---

## Overview

Concentration of measure is the effect that a function of many random
variables, or a random point in a high-dimensional space, stays close to a
typical value with high probability. For points spread over a high-dimensional
ball or sphere, nearly all the mass sits near the surface and nearly all pairs
of independent unit vectors are almost orthogonal [arxiv:1801.03421 §1]
[arxiv:1801.03421 §2].

The card for this page uses the effect in one direction. If the points are
i.i.d. from a named distribution, then with high probability one point, or a
small group, can be cut off from all the others by a linear functional
[arxiv:1801.03421 §3.1]. The paper calls this a "blessing of dimensionality":
the geometry becomes simpler as the dimension grows. Its results are stated as
probability lower bounds for the separation event. They are not guarantees for
real data, which the paper says cannot be checked in advance [arxiv:1801.03421
§4].

## Variants

Each variant below is a different sample model with a different separating
functional. All four come from the same card.

### Single point in a ball

Let M points be i.i.d. uniform in the unit ball of R^n, and fix a radius
ratio r in (0, 1). The last point is separated from the others by the
functional given by its own direction, with threshold r. The probability that
this holds is at least 1 − r^n − 0.5(M − 1)ρ^n, where ρ = sqrt(1 − r²)
[arxiv:1801.03421 §3.1, Thm. 3.1(a)]. Every point can be separated this way
under the bound in Theorem 3.1(b), and the angle version is in Theorem 3.1(c)
[arxiv:1801.03421 §3.1]. Card: [Blessing of dimensionality](/papers/1801.03421).

No fitting is needed. Corollary 3.1 gives the largest sample size M for which
the separation holds with probability above 1 − ϑ. The paper says this limit
grows at least exponentially with n for fixed ϑ [arxiv:1801.03421 §3.1].

### Product distribution in a cube

Here each coordinate is independent, lies in [0, 1], and has a variance above
a floor σ_0². With R_0² equal to the sum of the coordinate variances, the
paper bounds the norm of each centred point and the inner products between
centred points, for a deviation δ in (0, 2/3) [arxiv:1801.03421 §3.1, Thm.
3.2]. Use this variant when the features are bounded and their variances are
known or can be estimated. The paper states that the results extend to
ellipsoids, Gaussians and weakly dependent variables, but it gives no proof
of these extensions [arxiv:1801.03421 §3.1].

### Groups of m points

Theorem 3.3 separates a set of m points, the tuple, from other points that are
drawn from the same ball. It requires the pairwise inner products inside the
tuple to satisfy correlation bounds β2 and β1 [arxiv:1801.03421 §3.1]. The
separating functional is the normalised mean of the tuple. The paper says
that if the points are uncorrelated, the bound falls as m grows, at rate
O(1/sqrt(m)). If they are positively correlated, the paper says the bound does
not depend on m [arxiv:1801.03421 §3.1]. The paper does not say how to pick
β1 and β2 for real data.

### One-shot linear corrector for errors

This is the applied variant. A deployed system is watched by a legacy
system or by external labels. Each input becomes a point, and the points
where the system is wrong form a set Y. The paper's Algorithm 1 whitens all
recorded points, splits the errors into clusters, and computes one Fisher-type
direction per cluster. Each direction is paired with a threshold equal to the
smallest score in its cluster. An input is flagged when any direction reaches
its threshold [arxiv:1801.03421 alg. 1] [arxiv:1801.03421 §3.3].

The paper argues that such correctors need no retraining and no iteration.
The closed-form solution is the only fitting step. Its stated requirements
include that the method leaves the legacy system's skills unchanged and that
new corrections do not destroy old ones. The correctors can be cascaded
[arxiv:1801.03421 §3.2] [fig. 2]. The method has been used for a pedestrian
detector with n = 2000, in earlier work. The paper shows this only as a
qualitative figure with no numbers in the text [arxiv:1801.03421 §3.2] [fig. 3].

## When to use which

| Situation | Use | Why |
|---|---|---|
| You want a bound on separability for synthetic or whitened data | Single point in a ball | Closed-form functional, no fitting. Bounds need large n and small r^n [arxiv:1801.03421 §3.1] |
| Features are bounded with known or estimated variances | Cube | Theorem 3.2 uses those variances directly [arxiv:1801.03421 §3.1] |
| Errors come in correlated groups | m-tuples | The bound stays flat in m when the points are positively correlated [arxiv:1801.03421 §3.1]. β1 and β2 must still be chosen |
| You must correct a deployed system without retraining it | One-shot corrector | No iteration, and the legacy system is left unchanged [arxiv:1801.03421 §3.2] |
| You need measured accuracy gains | None from this card | The paper has no new experiments. Its only figure is qualitative [arxiv:1801.03421 §3.2] |

The paper compares its corrector against SVMs only on training cost. It states
the SVM worst case as order N³ for N points with quadratic loss, and says
Fisher's discriminant is linear in the number of points [arxiv:1801.03421
§3.1] [arxiv:1801.03421 §3.2]. No accuracy comparison is given.

## Implementation sketch

The first block is the single-point check from Theorem 3.1(a). The second is
the one-shot corrector from Algorithm 1. Both are sketches. Parameters and
trigger conditions that the paper leaves open are marked.

```pseudocode
# One-point separation in the unit ball  [§3.1, Thm. 3.1(a)]
# Input:  points X = [x_1 .. x_M] in R^n, radius ratio r in (0, 1)
# Output: unit functional u, threshold r, and whether the event holds
def point_separation(X, r):
    # The last point's own direction is the functional  [§3.1, Thm. 3.1(a)]
    x_M = X[-1]
    u = x_M / norm(x_M)
    # Event: ‖x_M‖ > r and (x_i, u) < r for every other i  [§3.1]
    ok = norm(x_M) > r and all(dot(x_i, u) < r for x_i in X[:-1])
    return u, r, ok
```

```pseudocode
# One-shot corrector for an error set  [alg. 1, steps 1-2]
# Input:  S (all recorded points), Y (error points, subset of S), p clusters
# Output: list of (unit functional, threshold) pairs
def build_correctors(S, Y, p):
    # Centre on the mean of S  [alg. 1, step 1a]
    mu = average(S)
    S_c, Y_c = S - mu, Y - mu
    # Whiten with the covariance of S  [alg. 1, step 1c]
    # Regularisation trigger and which eigenvectors to keep are not stated
    S_w, Y_w = whiten(S_c), whiten(Y_c)
    # Split error points into p positively correlated clusters  [alg. 1, 2a]
    clusters = cluster_positively_correlated(Y_w, p)
    correctors = []
    for K in clusters:
        rest = S_w minus K
        # Fisher-type direction; no ridge term is stated  [alg. 1, step 2b]
        w = inverse(cov(rest) + cov(K)) @ (mean(K) - mean(rest))
        u = w / norm(w)
        # Threshold: smallest score inside the cluster  [alg. 1, step 2b]
        correctors.append((u, min(dot(u, x) for x in K)))
    return correctors
```

## Contradictions

None across papers. The card has one source, so no two papers disagree.

Within the paper, the card's compile run found two places where the stated
result does not follow from the argument given. First, the second bound in
Corollary 3.1 is not the same expression as solving the union bound of Theorem
3.1(b) for M. A hand check gave a different limit. Second, the union-bound
step for Proposition 2.1 gives a failure probability slightly above ϑ, not
within it. These are the card's checks, not the paper's own statements. Use the
paper's bounds as stated, or derive your own from Theorem 3.1(b), and do not
rely on the exact limits without checking [arxiv:1801.03421 §2] [arxiv:1801.03421
§3.1].

## Pitfalls

- **Bounds can be vacuous.** The first bound in Corollary 3.1 is negative
  unless ϑ > r^n. Check the sign before using it [arxiv:1801.03421 §3.1].
- **Underflow at large n.** Terms such as ρ^n and r^(2n) underflow in double
  precision for n in the thousands. Compute them in log space. This is our
  arithmetic, not the paper's.
- **Independence is assumed.** All theorems need i.i.d. points from the named
  distributions. The paper says to validate the assumption after the fact
  [arxiv:1801.03421 §4].
- **Dimension heuristic.** The paper says that after whitening, a dimension of
  about 100 or more with up to about 10^6 points should give more than 99%
  probability. It calls this a rule of thumb, not a theorem [arxiv:1801.03421 §4].
- **Symbol clash.** m is the tuple size in Theorem 3.3, and the number of kept
  eigenvectors in Algorithm 1, step 1b. Use separate names in code.
- **Eigenvector order.** Step 1b says to keep the m "significant" components
  but does not say whether these are the largest or the smallest eigenvalues.
  The implementation has to decide [arxiv:1801.03421 alg. 1].
- **Fisher form versus tuple mean.** The Fisher-type direction appears only in
  Algorithm 1, step 2b. The tuple functional in Theorem 3.3 is a normalised
  mean [arxiv:1801.03421 §3.1] [arxiv:1801.03421 alg. 1].
- **Unspecified choices.** The paper does not say how to choose the cluster
  count p, the correlation bounds β1 and β2, or the ridge term for the covariance
  inversion in step 2b [arxiv:1801.03421 alg. 1] [arxiv:1801.03421 §3.1].

## Papers

- [Blessing of dimensionality: mathematical foundations of the statistical physics of data](/papers/1801.03421): a review of stochastic separation theorems for uniform ball, cube and m-tuple samples, and a one-shot linear corrector for AI errors. No new experiments.