Concentration of measure

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 1801.03421 §1 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 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²) 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) 1801.03421 §3.1. Card: Blessing of dimensionality.

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 ϑ 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 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 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 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 1801.03421 alg. 1 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 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 1801.03421 §3.2 fig. 3.

When to use which

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] 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.

# 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

# 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 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 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 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 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 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 1801.03421 §3.1 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 1801.03421 alg. 1 1801.03421 §3.1.

Papers

• Blessing of dimensionality: mathematical foundations of the statistical physics of data: 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.