d the dimension, an integer. All estimates assume d >= 64.
S^{d-1} the unit sphere {u in R^d : |u| = 1}
sigma_d uniform probability on S^{d-1}
|v| Euclidean norm
<u,v> the dot product
log natural logarithm; the base changes only constants
C a positive absolute constant. It may grow from line to line
but never depends on d, eps, L, or on the learner.
X ~ N(0,I_d) d independent standard normal coordinates
A => B "A implies B"
The signal is an unknown unit vector s in R^d. At each step j, nature
draws a fresh row X_j ~ N(0, I_d) and reveals the exact label
Y_j = <X_j, s>. With all d rows kept, s = A^{-1} Y almost surely. A
machine with 2^M states (M bits) reads (X_j, Y_j) each step, updates its
state, stops by a pre-agreed horizon T, and outputs a unit vector s-hat
from its final state and fresh randomness.
When s is uniform on the sphere, how large must T be for
s-hat to be within angle eps of s with probability at least 2/3, if M is
far smaller than d^2?
ANSWER, proved below.
If M = o(d^2) and 0 < eps <= 1/10, then for all large enough d
T >= c * d * log(1/eps)
for an absolute constant c > 0.
"M = o(d^2)" means M/d^2 -> 0. "Absolute" means the constant does not
depend on d, eps, M, or on how clever the machine is. The phrase "large
enough d" hides a threshold that may depend on how fast M/d^2 goes to 0.
Memory-sample tradeoffs are known in restricted models. Steinhardt and
Duchi proved minimax lower bounds for memory-bounded sparse linear
regression. Raz proved that learning a parity over a finite field
requires quadratic memory or exponentially many samples. Sharan,
Sidford, and Valiant obtained an Omega(d log(1/eps)) lower bound for
Gaussian regression with d^2/4 bits and bounded noise. Dagan, Kur, and
Shamir proved quadratic-space lower bounds for approximate null vectors
and for stable solutions of random linear systems. The present argument
concerns exact labels, o(d^2) memory, and unrestricted computation per
step.
./steinhardt-duchi-2015.pdf
./raz-2016.pdf
./raz-2017.pdf
./ssv-2019.pdf
./dagan-kur-shamir-2019.pdf
Give the analyst one extra random projection B s (B independent, about
d/2 rows), unseen by the machine. If the machine's state still carries
much information about s after B s is revealed, it encodes something no
d/2-dimensional shadow shows. Exact observations make that encoding
expensive.
The strategy is one sentence: prove a bound for one block of fresh rows, then add the per-block bounds along the stream.
DEFINITION 1 (finite-state learner). Fix d and eps. A learner is:
(a) a finite set of states with at most 2^M elements;
(b) an initial state, possibly random, chosen before any data and
independent of s and of all rows;
(c) for each step j and each state v, a randomized rule that reads
(v, X_j, Y_j) and produces a new state, or says "stop";
(d) for each state v and each index j, a randomized output rule
producing a unit vector s-hat.
The stopping time tau is the first step at which the learner stops, and
tau <= T always. The output uses only the state held at time tau, the
index tau, and fresh randomness.
Five remarks are used repeatedly.
(1) Computation inside a rule is free. Only states cost bits. The
machine may do any amount of clever processing in one step, and the
lower bound still applies.
(2) The machine cannot choose X_j and cannot revisit a row. Anything
it wants later must be inside the state now.
(3) A shared random seed may be chosen once, independent of
everything. Conditioning on the seed precedes averaging at the end.
(4) A randomized rule may be replaced by a fixed one by drawing all of
its coins in advance. The joint law of (state path, tau, output)
does not change, so the success probability does not change.
Iterating over finitely many rules, some fixed realization of all
the coins still succeeds with probability at least p - delta for
any delta > 0. This is how to pass from a randomized learner to a
deterministic one.
(5) A learner that stops early may idle: keep drawing fresh rows and
ignore them. So "stops by T" and "runs for exactly T steps" are
interchangeable, at the cost of a few extra states used to
remember where it stopped.
With s uniform on the sphere,
P{ arccos(<s-hat, s>) <= eps } >= 2/3,
the probability taken over s, the rows, and the learner's randomness.
Success at least 2/3 for every
fixed s implies success at least 2/3 on average over s, by integrating.
So a lower bound proved under the average hypothesis also rules out
worst-case learners. The average case is proved, which is stronger.
The proof never looks inside the machine. It only counts bits. The
currency is information, measured in nats (natural-log units). Entropy
in nats and mutual information follow Shannon (1948).
./shannon-1948.pdf
If W takes finitely many values with probabilities p(w),
H(W) = - sum_w p(w) log p(w).
Facts.
(E1) H(W) >= 0, with equality exactly when W is constant.
(E2) H(W) <= log(number of values of W). So a state set of size 2^M
has entropy at most M log 2.
(E3) H(W) <= E[ - log q(W) ] for any probability q on the values of W.
This is the cross-entropy inequality, and it is just Jensen
applied to the concave log.
Suppose the learner stops at some index tau in
{0,1,...,T} and the pair (tau, state at tau) is kept. There are at most
T+1 possible indices and at most 2^M states, so at most (T+2) 2^M values.
By (E2), every padded state satisfies
H <= h_T := M log 2 + log(T + 2). (2.1)
For probability laws P and Q on the same space,
with P absolutely continuous with respect to Q,
D(P || Q) = E_P log (dP/dQ),
and D(P||Q) = +infinity otherwise. Always D(P||Q) >= 0, with equality
exactly when P = Q.
For jointly distributed S and W, with W finite,
I(S; W) = D( P_{S,W} || P_S x P_W ),
which is zero exactly when S and W are independent. When W is finite,
I(S; W) <= H(W). (2.2)
For a third variable Z,
I(S; W | Z) = E_Z D( P_{S,W | Z} || P_{S | Z} x P_{W | Z} ).
Two facts used without comment.
(I1) Symmetry: I(S;W) = I(W;S).
(I2) I(S;W) is the expected number of nats by which knowing W reduces
the uncertainty about S.
TOOL A (chain rule).
I(S; (Z, W)) = I(S; Z) + I(S; W | Z).
TOOL B (data processing). If the law of Z given (S,W) does not depend on
S, then
I(S; Z) <= I(S; W).
In particular this covers Z = f(W) for a fixed function f. Post-
processing cannot create information.
TOOL C (the variational bound). Let Q and R be probabilities with Q
absolutely continuous with respect to R, and let F >= 0 be measurable
with E_R F <= 1. Then
D(Q || R) >= E_Q log F. (2.3)
Proof. Put R' = (F / E_R F) R, which is a probability law. Then
D(Q || R) = D(Q || R') + E_Q log (dR'/dR)
>= E_Q log (F / E_R F)
>= E_Q log F,
using D >= 0 and E_R F <= 1. For unbounded F apply the bound to
min(F, n) and let n -> infinity; the left side does not move.
TOOL D (a consequence of Tool C). If D(Q||R) < infinity, then
E_Q log(1 + F) <= D(Q || R) + log 2. (2.4)
Proof. Apply (2.3) to the test (1+F)/2, whose R-expectation is at most
one. This gives E_Q log((1+F)/2) <= D(Q||R), and
log((1+F)/2) = log(1+F) - log 2.
Let 0 <= a, c <= 1, and write Bern(p) for
the law of a coin with heads probability p. Then
D( Bern(a) || Bern(c) ) >= a log(1/c) - log 2. (2.5)
Proof. Write the divergence out:
a log(a/c) + (1-a) log((1-a)/(1-c))
= a log(1/c) + (1-a) log(1/(1-c))
+ [ a log a + (1-a) log(1-a) ]
>= a log(1/c) - log 2,
because the middle term is nonnegative and the bracket is minus the
entropy of a coin, which is at least -log 2.
Write sigma_q for uniform probability on S^{q-1}, the unit sphere in R^q.
There are three facts, and each one is proved.
LEMMA 1 (spherical caps). Let q >= 2. For every z in S^{q-1} and every
r > 0,
sigma_q{ u in S^{q-1} : |u - z| <= r } <= r^{q-1}. (3.1)
In particular, if the angle between u and z is at most eps then
|u - z| = 2 sin(angle / 2) <= eps, so an angular cap of radius eps has
mass at most eps^{q-1}.
Proof. If r >= 1, the right side of (3.1) is at least 1 and there is
nothing to prove. Assume 0 < r < 1 and rotate so that z is the north
pole (0, ..., 0, 1). Two ingredients.
(i) A point u of the chordal cap satisfies
|u - z|^2 = 2 - 2 u_q <= r^2, so u_q >= 1 - r^2/2 >= 1/2.
On the part of the sphere where u_q >= 1/2, the sphere may be written
as a graph over the first q-1 coordinates. The area element of
that graph is 1/u_q <= 2. So the cap has area at most twice the
volume of its shadow. The shadow lies in the ball of radius r in
R^{q-1}: the first q-1 coordinates of u - z are the first q-1
coordinates of u, and their squared length is at most |u - z|^2.
Hence
area(cap) <= 2 * v_{q-1} * r^{q-1},
where v_{q-1} is the volume of the unit ball in R^{q-1}.
(ii) The whole sphere has area at least 2 v_{q-1}. Each open hemisphere
projects onto the whole unit ball of R^{q-1}, and on a hemisphere
the area element 1/u_q is at least 1.
Divide and use rotational invariance of sigma_q. Done.
LEMMA 2 (affine tubes). Let V be an affine subspace of R^d of dimension
j. For 0 < r <= 1,
sigma_d{ u : dist(u, V) <= r } <= C^d r^{d-1-j}. (3.2)
If the law of the signal has instead a density at most L with respect to
sigma_d, the same bound holds with an extra factor L.
Proof. Take a point u on the sphere with dist(u, V) <= r <= 1, and pick v
in V with |u - v| <= r. Then |v| <= 1 + r <= 2. So only the part of V
inside the ball of radius 2 is relevant, and that part is a j-dimensional
set of diameter at most 4. Cover it by at most (C/r)^j balls of radius r
with centers c in V.
Only the centers whose ball meets the sphere matter, and for those
| |c| - 1 | <= r. For any u on the sphere with |u - c| <= 2r, the
triangle inequality gives
| u - c/|c| | <= |u - c| + | |c| - 1 | <= 2r + r = 3r.
So every point of the tube lies in a spherical ball of radius 3r, and
Lemma 1 gives measure at most
(C/r)^j * (3r)^{d-1} = C^d r^{d-1-j}.
Absorb 3^{d-1} and C^j into C^d, using j <= d. When this exceeds 1, use
the trivial bound 1 and enlarge C. Done.
LEMMA 3 (residual spheres). Let S ~ sigma_d, and let G be an independent
b x d matrix of independent standard normal entries, with 0 <= b <= d-2.
Let P be the orthogonal projection onto ker G, and put
R = |P S|.
Then, given (G, GS), the signal S is uniform on the set
{ u : Gu = GS, |u| = 1 },
which is a sphere of dimension d-b-1, lying in the affine space GS + ker G,
with centre P S and radius R. For b = 0 the matrix is empty, there is no
conditioning, and R = 1 always.
For 1 <= b <= d-2 the laws are explicit:
R^2 ~ Beta( (d-b)/2 , b/2 ), (3.3)
E R^2 = (d-b)/d, Var(R^2) = 2 b (d-b) / (d^2 (d+2)). (3.4)
Two consequences are used below. For 0 < r0 < 1,
P{ R < r0 } <= b / ( d (1 - r0^2) ). (3.5)
And when 0 <= b <= d/2,
P{ R < 1/2 } <= 8/(d+2), and P{ R < 1/2 } <= 90/d. (3.6)
Proof. The case b = 0 is immediate: conditioning on nothing changes
nothing and the residual radius is one. Suppose b >= 1.
Write Z for a standard normal vector in R^d and S = Z/|Z|. Split Z into
its parts Z_row in the row space of G, of dimension b, and Z_ker in ker G,
of dimension d-b. These two parts are independent, and their squared
lengths are independent chi-squared variables with b and d-b degrees of
freedom. Therefore
R^2 = |Z_ker|^2 / ( |Z_row|^2 + |Z_ker|^2 )
has the beta law (3.3), which gives (3.4) by the beta mean and variance
formulas. Given G and GS the row-space part of S is pinned down, and the
kernel part is uniform on its sphere of radius R. That is the stated
description, and rotational invariance of the normal law gives the
uniformity.
For (3.5), 1 - R^2 has mean b/d and is nonnegative, so Markov's
inequality gives
P{ R < r0 } = P{ 1 - R^2 > 1 - r0^2 }
<= (b/d) / (1 - r0^2).
For the first half of (3.6), assume b <= d/2. Then E R^2 >= 1/2 and
Var(R^2) <= 2 (d^2/4) / (d^2 (d+2)) = 1/(2(d+2)).
Chebyshev's inequality at distance 1/4 from the mean gives
P{ |R^2 - E R^2| >= 1/4 } <= 16 Var(R^2) <= 8/(d+2), and on the
complement R^2 >= E R^2 - 1/4 >= 1/4.
For the second half of (3.6), still with b <= d/2, apply Chebyshev to the
two chi-squares. |Z_ker|^2 has mean d-b >= d/2 and variance at most 2d,
while |Z|^2 has mean d and variance 2d. Hence
P{ |Z_ker|^2 < d/3 } <= 2d / (d/6)^2 = 72/d,
P{ |Z|^2 > 4d/3 } <= 2d / (d/3)^2 = 18/d.
Outside both events, R^2 >= (d/3)/(4d/3) = 1/4. Sum. Done.
This is the heart of the whole argument. The analyst learns the projection
GS. Inside the remaining sphere, an accurate answer still needs a lot of
information.
LEMMA 4 (information on a residual sphere). Let S ~ sigma_d and let V be
a random variable with values in a Borel space, jointly distributed with
S. Let G be an independent b x d standard Gaussian matrix with
0 <= b <= d-2. Let S-hat be a unit vector produced from V by a kernel
that is conditionally independent of (S,G) given V. Write
p = P{ arccos( <S-hat, S> ) <= eps }, R = |P S|.
Let 2 eps < r0 <= 1. If alpha := p - P{ R < r0 } is positive, then
I( S ; V | G, GS ) >= alpha (d-b-1) log( r0/(2 eps) ) - log 2. (3.7)
Proof. Put Z = (G, GS) and compare two joint laws of (S, V, Z).
The true law: the actual one.
The comparison law: first draw Z with its true law, then draw S and V
independently from their true conditional laws given Z.
Both laws have the same Z-marginal, so the divergence between them is
exactly I(S;V|Z). Now generate S-hat from V by the same kernel in both
laws. Conditioned on (S,V) the two laws agree, so the divergence does not
change. It is still I(S;V|Z).
Fix the side information Z. Suppose R >= r0 and fix a value of S-hat. If
the set of successful points on the fiber is nonempty, pick one, call it
u0. Any other successful fiber point u satisfies
|u - u0| <= |u - S-hat| + |u0 - S-hat| <= 2 eps,
by the triangle inequality together with angular success. Rescale the
fiber sphere to unit radius: in those units the success set lies in a
chordal ball of radius 2 eps / R <= 2 eps / r0 < 1. By Lemma 1 the
conditional mass of the success set is at most (2 eps / r0)^{d-b-1}.
In the comparison law, S-hat and S are conditionally independent given Z,
so conditional on Z the probability of success and R >= r0 is at most
that same quantity. In the true law it is at least alpha. Mapping the
pair (S-hat, S) to the indicator of this event can only reduce the
divergence, so by (2.5)
I(S;V|Z) >= D( Bern(alpha) || Bern(c) ) >= alpha log(1/c) - log 2,
with c = (2 eps / r0)^{d-b-1}. This is (3.7). When c = 0 there is
nothing to prove, because alpha <= 1. Done.
Lemma 4 has a constant alpha, a radius r0 and a dimension b. One set of numbers is fixed now, the ones the proof of the theorem
uses, and the result is written out.
COROLLARY 5 (the endpoint, in numbers). Suppose
S ~ sigma_d, G is an independent b x d standard Gaussian matrix
with 0 <= b <= d/2, V is any random variable jointly distributed
with S, and S-hat is a unit vector produced from V by a kernel
conditionally independent of (S,G) given V.
Suppose 0 < eps <= 1/10 and P{ arccos(<S-hat,S>) <= eps } >= 3/5. Then
for all d >= 40,
I( S ; V | G, GS ) >= (1/2)(d-b-1) log(1/(5 eps)) - log 2. (4.1)
Proof. Take r0 = 1/2 in Lemma 4. The first half of (3.6) gives
P{ R < 1/2 } <= 8/(d+2), so
alpha >= 3/5 - 8/(d+2) >= 1/2 for d >= 40.
Next convert a chordal radius into an angular radius. On a unit sphere a
chordal ball of radius r is contained in an angular cap of radius
2 arcsin(r/2). With r = 2 eps/r0 = 4 eps, the angular radius is
2 arcsin(2 eps) <= 5 eps for 0 < eps <= 1/10,
because arcsin(x) <= 1.02 x for 0 <= x <= 0.2. By Lemma 1 the cap has
mass at most (5 eps)^{d-b-1}. Put this into (3.7) and use alpha >= 1/2.
A useful size check. Since b <= d/2, d-b-1 >= d/2 - 1, and since
eps <= 1/10,
log(1/(5 eps)) = log(1/eps) - log 5
>= (1 - log 5 / log 10) log(1/eps)
>= 0.3 log(1/eps).
So (4.1) says
I( S ; V | G, GS ) >= 0.15 d log(1/eps) - log 2 (4.2)
for all large d. The endpoint is linear in d and linear in log(1/eps).
That is the whole point.
LEMMA 6 (raw data cannot beat the endpoint quickly). Let 0 < eps <= 1/10
and let an estimator see all the exact measurements from b independent
Gaussian rows, with b <= floor(d/2), plus independent randomness, when
S ~ sigma_d. Then its angular success probability is at most
8/(d+2) + (5 eps)^{d-b-1}. (4.3)
In particular, for eps <= 1/10 this is below 3/5 once d is large. So a
learner that stops by T <= floor(d/2) cannot succeed with probability
3/5, even if it keeps every raw row it has seen.
Proof. For d <= 4 the two numerical bounds are not useful, so assume
d >= 5; then b <= d/2 <= d-2 and Lemma 3 applies. Condition on all the
data. Given the data, the estimator is conditionally independent of S,
and the conditional law of S is the residual sphere of Lemma 3 with
radius R.
On the event R >= 1/2, fix a value of the output. Two successful fiber
points are both within distance eps of that output, so they are within
2 eps of each other. Rescale the fiber sphere to unit radius by dividing
all distances by R. In those units the success set lies in a chordal ball
of radius 2 eps / R <= 4 eps. By the angular conversion of Corollary 5,
that ball sits inside an angular cap of radius 5 eps, so by Lemma 1 its
mass on the fiber sphere of dimension d-b-1 is at most (5 eps)^{d-b-1}.
Add the failure probability 8/(d+2) from (3.6).
For the last claim, suppose the learner stops by T <= floor(d/2). Grant
it, for free, the first floor(d/2) rows and labels, including any it did
not use. Its output is a kernel of those data plus independent
randomness, so the bound (4.3) applies with b = floor(d/2). There
d-b-1 >= d/2 - 1 >= 1, and 5 eps <= 1/2, so the second term is at most
(1/2)^{d/2-1}, and
8/(d+2) + (1/2)^{d/2-1} < 3/5
for all large d. Done.
Corollary 5 says the final state must contain about d log(1/eps) nats of
information about S, even after the analyst is told GS. This part says
that stopping early cannot buy that information for free.
LEMMA 7 (output capacity). Fix d and suppose a learner has success
probability at least p0 >= 0 under the uniform prior, with horizon T and
memory M. Then
p0 <= (T+1) 2^M eps^{d-1}. (5.1)
Proof. Condition on the shared seed, if there is one, and work in the
conditional experiment. There are at most T+1 possible stopping indices
and at most 2^M states, so at most (T+1) 2^M pairs (j, v) of "stopped
at index j in state v".
Fix such a pair. Let nu_{j,v} be the law of the output it produces, and
let r_{j,v}(s) be the probability, given S = s, that the learner ever
reaches that pair. The pair contributes to the success probability
integral over s of r_{j,v}(s) *
[ integral over u of 1{ arccos(<u,s>) <= eps } nu_{j,v}(du) ]
sigma_d(ds).
The inner bracket is the mass of an angular cap of radius eps around the
fixed centre s, which by Lemma 1 and rotational invariance is at most
eps^{d-1}. It does not depend on nu_{j,v}. Since r_{j,v}(s) <= 1, the
whole contribution is at most eps^{d-1}.
Sum over the at most (T+1) 2^M pairs. Averaging the conditional success
over the seed gives the same bound for the mixture, because a mixture of
numbers each at most eps^{d-1} is at most eps^{d-1}. Done.
LEMMA 8 (the early clock). Put beta = log(1/eps), and note beta >=
log 10 > 2 because eps <= 1/10. On the branch T <= d beta, if
M = o(d^2), then
beta = o(d), T = o(d^2), h_T = o(d^2), (5.2)
with h_T = M log 2 + log(T+2) as in (2.1).
Proof. The success probability p0 is at least 3/5 by hypothesis, so
log(1/p0) <= log 2. Write eps^{d-1} = e^{-(d-1) beta}. By (5.1),
(d-1) beta <= M log 2 + log(T+1) + log(1/p0).
On the branch, T + 1 <= d beta + 1 <= 2 d beta for d >= 2, and
log beta <= beta because beta > 2. Hence
(d-2) beta <= M log 2 + log(2 d) + log(1/p0).
Divide by d and let d grow. The left side is (1 - 2/d) beta. The right
side is M log 2 / d + (log 2 + log d)/d + log(1/p0)/d. The first term is
o(d) because M = o(d^2), and the other two are o(1). So beta = o(d).
Then T <= d beta = o(d^2), and
h_T = M log 2 + log(T+2) = o(d^2) + log(o(d^2)) = o(d^2).
Done. The point of (5.2) is this: on the branch where the theorem is not
already proved, every padded state has far fewer than d^2 bits of
entropy, so the block bound below will apply with room to spare.
Everything so far was about one signal. Information bounds need many
signals at once, tied together by the same observations.
Fix a probability density p = f sigma_d relative to
the uniform sphere, with 0 <= f <= L < infinity. Fix integers k >= 1,
t >= 2 and ell >= 1. Draw:
S ~ p,
A a k x d standard Gaussian matrix, independent of S,
Y = A S,
W a finite-valued message drawn from a kernel of (A,Y) that is
conditionally independent of S given (A,Y),
B an ell x d standard Gaussian matrix, independent of everything.
B is the analyst's projection. The machine never sees B. What is measured is
information about S in W after the analyst has learned B S.
Given the data (A,Y), draw t independent signals
S_1, ..., S_t from the conditional law of S given (A,Y). Draw them
independently of W. Call them replicas.
The replicas are all equal in distribution but not independent: they all
satisfy A S_i = Y with the same matrix A, and once the data are forgotten
that common event ties them together. This dependence is what the proof
harvests.
Why a replica is a fair copy. Conditionally on (A,Y):
the original S is drawn from the posterior,
the replica S_i is drawn from the same posterior,
and W is drawn from a kernel of (A,Y) alone.
Hence (S_i, W) has the same joint law as (S, W) for every i. This is the
one property the inequality of Lemma 9 needs. (It is often called the
Nishimori identity: resampling from the posterior leaves the joint law of
data and signal untouched.)
Let Q be the joint law of the tuple
(S_1, ..., S_t). Let p be its one-signal marginal, which is the same for
every coordinate.
total correlation K = D( Q || p x p x ... x p ).
K measures how far the tuple is from t independent signals. It is the
"unprojected" dependence.
Let phi_B(s) = B s. Let p_B be the law of phi_B(S) when S ~ p. Let U_i =
phi_B(S_i). Define
projected correlation K' = E_B D( Q_{U|B} || p_B x ... x p_B ),
where Q_{U|B} is the conditional law of (U_1,...,U_t) given B. K' is the
dependence that survives after the analyst's projection.
Total correlation D(Q || p x ... x p) was introduced by Watanabe
(1960); its measure-theoretic chain rules are in Austin's survey.
./austin-2020.pdf
LEMMA 9 (replica information inequality). Let t >= 1. Let (S_1,...,S_t)
have joint law Q, all coordinates with the same marginal p, and suppose
K = D(Q || p x ... x p) is finite. Let B be independent of the tuple and
let (B,s) -> phi_B(s) be a measurable map, with K' defined as above. Let
W be finite-valued, suppose every pair (S_i, W) has the same law as
(S_1, W), and suppose B is independent of the whole tuple and of W. Then
t I( S_1 ; W | B, phi_B(S_1) ) <= H(W) + K - K', (6.1)
and also 0 <= K' <= K.
Proof. There are two chain-rule identities, one before the projection and
one after, and then a subtraction.
Define K_W, the total correlation conditional on W, by
K_W = E_W D( Q_{S_1..S_t | W} || (Q_{S_1|W}) x ... x (Q_{S_t|W}) ).
All coordinates have the same conditional marginal given W, so the product
is well defined. Decomposing the divergence of (S_1,...,S_t,W) from
(p x ... x p) x Q_W in the two possible orders gives the first identity:
t I(S_1 ; W) = I( (S_1,...,S_t) ; W ) + K - K_W. (6.2)
To see it, compute the left side as sum over i of I(S_i;W), use that all
these are equal, and use
K - K_W = sum_i I(S_i ; W) - I( (S_1,...,S_t) ; W ),
which is just the definitions of K and K_W written as differences of
entropies.
Both sides of (6.2) are finite: the divergence being decomposed is at most
K + H(W), so every nonnegative term in the chain rule is finite.
Now repeat the same argument after projecting, conditionally on B. Define
K'_W in the obvious way, with the same formula as K_W but using the
projected coordinates and conditioning on (B,W). The second identity is
t I( phi_B(S_1) ; W | B )
= I( (U_1,...,U_t) ; W | B ) + K' - K'_W. (6.3)
Two comparisons between the primed and unprimed quantities.
Relation (6.4). Fix B and apply the coordinatewise map
(s_1,...,s_t) -> (B s_1, ..., B s_t) to both laws inside the
divergence. The image of Q is Q_{U|B}; the image of the product
p x ... x p is the product p_B x ... x p_B. A divergence cannot
increase when the same map is applied to both of its arguments, so
D(Q_{U|B} || p_B x ... x p_B) <= D(Q || p x ... x p) = K for every
B. Average over B and get K' <= K. The same map, applied
conditionally on W and then averaged over B, gives K'_W <= K_W.
Relation (6.5). Since B is independent of S_1 and W, and
phi_B(S_1) is determined by (B,S_1),
I( S_1 ; W | B, phi_B(S_1) ) = I(S_1;W) - I(U_1;W|B). (6.5)
This is the standard identity I(X;Y|Z) = I(X;Y) - I(X;Z) +
I(X;Z|Y) with Z = (B, phi_B(S_1)): the two terms involving B alone
vanish because B is independent of (S_1,W).
Now subtract (6.3) from (6.2) and divide by t. The left side becomes
(6.5)'s right side, that is t I(S_1;W|B,phi_B(S_1)). The right side is
I( (S_i) ; W ) - I( (U_i) ; W | B ) + (K - K') - (K_W - K'_W).
The first difference is I( (S_i) ; W | B, (U_i) ): conditioning on B
changes nothing because B is independent of the tuple and W, and then
(U_i) is a function of (B,(S_i)), so subtracting its information is the
same as conditioning on it. Therefore
t I(S_1;W|B,phi_B(S_1))
= I( (S_i) ; W | B, (U_i) ) + (K - K') - (K_W - K'_W).
The first term is at most H(W), because conditioning never increases
entropy. The last bracket is nonnegative by (6.4). This proves (6.1),
and (6.4) gives 0 <= K' <= K.
COROLLARY 10 (the block inequality). In the block experiment above, with
t posterior replicas, suppose K is finite. Then
t I( S ; W | B, B S ) <= H(W) + K - K'. (6.6)
Proof. Apply Lemma 9 to the replica tuple. Every pair (S_i, W) has the
same law as (S, W), and B is independent of the tuple and of W. The left
side of (6.1) is the left side of (6.6) because (B,S) and (B,S_1) have the
same law.
The rest of the proof is now a single task. Bound K - K'. Finiteness of K, so that (6.6) is meaningful, comes first; the loss of
correlation for the specific dimensions k = 2 floor(d/16), t = k+1,
ell = 4k.
This is the geometric heart. Exact labels mean that the several replicas
satisfy A S_1 = ... = A S_t exactly. The exact law of that event is needed,
with its normalization, because a normalization error of even one power of
d would destroy the whole argument.
Only the spherical base is used. Write
sigma_d uniform probability on S^{d-1},
nu = f sigma_d with 0 <= f <= L < infinity, a finite measure.
It is convenient not to require nu to be a probability until the probability division below.
Fix k with 1 <= k <= d-2 and let A be a k x d matrix of full row rank.
Put
Sigma = A A^T (k x k, positive definite),
q(s) = s^T A^T Sigma^{-1} A s for s in R^d,
E_A = { y in R^k : y^T Sigma^{-1} y < 1 }.
q(s) is the squared length of the projection of s onto the row space of A.
In particular 0 <= q(s) <= |s|^2, so on the sphere q(s) < 1 exactly when s
is not in the row space of A.
The set {s in S^{d-1} : As = y} is, for y in E_A, a sphere of dimension
d-k-1 lying in the affine space A^{-1}y, with centre A^T Sigma^{-1} y and
radius sqrt(1 - q(A^T Sigma^{-1} y)). Write sigma_{A,y} for uniform
probability on it.
The pushforward of sigma_d under A has a Lebesgue
density on R^k, supported on the closed ellipsoid closure of E_A, and on
E_A it equals
p^0_A(y) = [ Gamma(d/2) / ( pi^{k/2} Gamma((d-k)/2) ) ]
* (1 - q_A(y))^{(d-k-2)/2} / sqrt(det Sigma), (7.1)
where q_A(y) = y^T Sigma^{-1} y.
Proof of (7.1). Let Z be standard normal in R^d and S = Z/|Z|. Split Z
into its row-space part Z_1 and its kernel part Z_2 (d-k coordinates). Put
w = A Z_1 in R^k, r = |Z_2|.
Then w ~ N(0, Sigma), r^2 is chi-squared with d-k degrees of freedom, and
the two are independent. Also |Z|^2 = w^T Sigma^{-1} w + r^2, so
Y := A S = w / sqrt( w^T Sigma^{-1} w + r^2 ).
Eliminate r: from Y = w/|Z| follows |Z| = r / s with s := sqrt(1 - q_A(Y)),
and hence w = r Y / s. For fixed r the map Y -> w is a change of
variables, and its Jacobian is not simply a power of r/s, because s depends
on Y. Compute it. Let B = dw/dY. Then
B = (r/s) I + r Y (grad(1/s))^T,
a rank-one update of a multiple of the identity, so
det B = (r/s)^k ( 1 + <Y , s grad(1/s)> ).
Now q_A(Y) = Y^T Sigma^{-1} Y, so grad(q_A) = 2 Sigma^{-1} Y and
<Y, grad(q_A)/2> = q_A(Y). Since 1/s = (1-q_A)^{-1/2},
s grad(1/s) = grad(q_A) / (2 (1 - q_A)),
and therefore 1 + <Y, s grad(1/s)> = 1 + q_A/(1-q_A) = 1/(1-q_A). Hence
det B = (r/s)^k / (1 - q_A(Y)) = r^k (1 - q_A(Y))^{-(k+2)/2}.
The joint density of (w,r) at (r Y/s, r) is the normal density of w times
the chi-square density of r. In the normal density,
w^T Sigma^{-1} w = |Z|^2 q_A(Y) = r^2 q_A(Y) / (1 - q_A(Y)),
so the total exponent in r is
- r^2 q_A/(2(1-q_A)) - r^2/2 = - r^2 / ( 2 (1 - q_A(Y)) ).
Multiply the Jacobian, the normal density and the chi-square density. The
powers of r combine into r^{d-1}, and integrating r over (0, infinity)
contributes Gamma(d/2) 2^{(d-2)/2} (1-q_A)^{d/2}. The powers of (1-q_A)
are therefore -(k+2)/2 + d/2 = (d-k-2)/2, and the constants assemble into
exactly (7.1). Done.
Two features of (7.1) that later proofs use: p^0_A is continuous on the
open ellipsoid E_A, and it is bounded there, because the exponent
(d-k-2)/2 is nonnegative when k <= d-2.
THE FIBER MEASURE, AND WHY (7.1) IS THE RIGHT NORMALIZATION. On the open
set of full-row-rank A define, for y in E_A, the finite measure on the
fiber {s in S^{d-1} : As = y}
lambda_{A,y}(ds) = f(s) / ( |S^{d-1}| * j_A(s) ) dvol_{d-k-1}(s),
j_A(s) = det( Sigma )^{1/2} * sqrt(1 - q(s)) = det( Sigma )^{1/2} *
(distance from s to the row space of A).
dvol_{d-k-1} is the induced surface measure on the fiber. Two things
about lambda_{A,y}.
Normalization. lambda_{A,y}(S^{d-1}) = p_A(y), where
p_A(y) = p^0_A(y) * h_A(y), h_A(y) = int f d sigma_{A,y}.
Indeed the fiber is a sphere of radius sqrt(1-q_A(y)), so its surface
measure is |S^{d-k-1}| (1-q_A(y))^{(d-k-1)/2}, while j_A equals
det(Sigma)^{1/2} (1-q_A(y))^{1/2}. Also
|S^{d-k-1}| / |S^{d-1}| = pi^{-k/2} Gamma(d/2) / Gamma((d-k)/2).
Dividing gives exactly (7.1) times h_A(y).
Conditional law. mu_{A,y} := lambda_{A,y} / p_A(y) is the
posterior law of the signal given As = y, when the prior is nu.
This is the whole reason for writing (7.1) as a general formula rather than
as a table of constants: (7.1) and the fiber measure are the same object,
and the identity below is a statement about them.
The map s -> (As, direction inside the fiber) is a smooth change of
variables on the complement of the row space of A, which is a set of zero
sigma_d measure. Hence for every nonnegative measurable h,
int h(s) nu(ds) = int_{R^k} int h(s) lambda_{A,y}(ds) dy. (7.2)
Equation (7.2) is the coarea identity in this setting, and it already
contains (7.1): take h = 1 to recover p_A.
Let t >= 2 and m = t-1. For a tuple u = (u_1,...,u_t) of points in R^d
write
D_u = [ u_2 - u_1 , u_3 - u_1 , ... , u_t - u_1 ] (d x m),
F_u = span of the columns of D_u,
J(u) = det( D_u^T D_u )^{1/2}.
J is the volume of the parallelepiped spanned by the m differences, and it
also has a geometric reading: by Gram-Schmidt,
J(u) = product_{i=2}^{t} dist( u_i , aff(u_1, ..., u_{i-1}) ), (7.3)
the product of the successive simplex heights. So J(u) > 0 exactly when
u_1,...,u_t are affinely independent, and J(u) = 0 otherwise.
For two distinct points v, w the difference v - w has A(v-w) ~ N(0,
|v-w|^2 I_k), whose density at the origin is (2pi)^{-k/2} |v-w|^{-k}. That
is the inverse-volume factor for two points. With m differences each row
of A D_u is Gaussian with covariance D_u^T D_u, so the density of A D_u at
the zero matrix is
w_{k,m}(u) = (2pi)^{-km/2} J(u)^{-k}. (7.4)
That factor is what the identity below has to produce.
LEMMA 11 (the inverse simplex volume is finite). Let 2 <= t <= d-1 and
m = t-1, and let 1 <= k with k + m <= d-2. Then
int J(u)^{-k} sigma_d^{otimes t}(du) < infinity, (7.5)
and also int J(u)^{-(k+1)} sigma_d^{otimes t}(du) < infinity when
k + m <= d-3.
Proof. Take the factors of (7.3) one at a time, from the last back to the
first. Condition on u_1,...,u_{i-1}. Their affine span is an affine
subspace of dimension at most i-2. By Lemma 2, with j = i-2,
sigma_d{ u_i : dist(u_i, aff(u_1,..,u_{i-1})) <= r }
<= C^d r^{d-1-(i-2)} = C^d r^{d-i+1}, 0 < r <= 1.
Also the distance is at most 2. For a nonnegative random variable X with
X <= 2,
E X^{-k} = 2^{-k} + k int_0^1 r^{-k-1} P{X < r} dr
<= 1 + k C^d int_0^1 r^{d-i+1-k-1} dr.
The integral is finite exactly when d - i + 1 > k, that is, i < d - k + 1.
Since i <= t = m+1 and k + m <= d-2, i <= d-1-k < d+1-k. So every
factor has a finite k-th inverse moment, uniformly in the preceding points.
Multiply the conditional bounds together, integrating the last point first
and working backwards. This proves (7.5). Replace k by k+1 for the last
clause.
As a byproduct, J > 0 sigma_d^{otimes t}-almost surely, so the tuple is
affinely independent almost surely. There is no need for a separate proof:
a zero J would make the expectation infinite.
THEOREM 12 (the equal-label finite measure). Let k >= 1, m >= 1,
t = m+1, and k + m <= d-2. Let nu = f sigma_d with 0 <= f <= L < infinity.
Let p^0_A, p_A, sigma_{A,y} and mu_{A,y} be as previously, and D_u, F_u, J as before. For every nonnegative Borel function H = H(A, y, u_1,...,u_t),
int gamma_{k,d}(dA) int_{R^k} p_A(y)^t
int H(A, y, u) mu_{A,y}^{otimes t}(du) dy
= (2pi)^{-km/2} int J(u)^{-k} nu^{otimes t}(du)
int H(A, A u_1, u) gamma_{k,d}^{F_u}(dA). (7.6)
gamma_{k,d}^{F} is the law of a k x d matrix whose rows are
independent standard Gaussians inside F^perp, the orthogonal complement
of F = F_u.
The left side picks a matrix A and a common label y, with
the label weighted by p_A(y)^t, and then picks the t signals independently
from the posterior mu_{A,y}. The right side picks the t signals first and
then picks a Gaussian matrix that annihilates all their differences, with
the inverse-volume weight (7.4).
Both sides are finite measures in (A,y,u), not normalized probabilities.
Their total masses agree, and the identity says they agree as measures.
The arguments below prove it, and extract the probability statement.
First (7.6) is proved in the base case nu = sigma_d. The general nu = f
sigma_d then follows by multiplying both sides by a nonnegative function,
which completes the argument.
The desired identity is a statement about the
exact constraint A u_1 = ... = A u_t. Such a constraint cannot be inserted
directly; it has zero measure under gamma_{k,d}. So it is relaxed to
"approximately equal" and then passed to the limit.
Fix a nonnegative auxiliary function phi on R^k with total integral 1,
supported in the unit ball, and put phi_eta(z) = eta^{-k} phi(z/eta). The
choice of phi does not matter; a ball or a Gaussian both work.
Fix a bounded continuous function H(A, y, u), compactly supported as a
function of A, whose A-support lies inside the open set of full-row-rank
matrices. For eta > 0 define
I_eta = int sigma_d^{otimes t}(du) int gamma_{k,d}(dA)
H(A, A u_1, u) product_{i=2}^{t} phi_eta( A(u_i - u_1) ). (7.7)
The test is H evaluated at the pinned label A u_1, not an arbitrary
function of (u,A). That choice is what will let the label y appear freely
on the left of (7.6) while it stays pinned to A u_1 on the right. The
plan is to compute the limit of I_eta as eta -> 0 in two ways; the two
limits must agree, and that agreement is (7.6) for this test H.
Fix A of full row rank. By (7.2), applied to each
coordinate separately,
sigma_d(du_i) = p^0_A(y_i) sigma_{A,y_i}(du_i) dy_i ,
y_i = A u_i.
Insert this for every i. The factor phi_eta(A(u_i - u_1)) becomes
phi_eta(y_i - y_1). So
I_eta = int gamma_{k,d}(dA) int ... int
H(A, y_1, u) product_{i=2}^{t} phi_eta(y_i - y_1)
product_{i=1}^{t} p^0_A(y_i) sigma_{A,y_i}(du_i) dy_i,
with the y-integrals over R^k for each i. The pinned label A u_1 has
simply been renamed y_1, which is what it is.
For fixed A and fixed first label y_1, this is an average over y_2,...,y_t
with respect to an approximate identity centred at y_1. As eta -> 0, each
y_i with i >= 2 tends to y_1, so p^0_A(y_i) -> p^0_A(y_1) and the measure
sigma_{A,y_i} tends weakly to sigma_{A,y_1}. This uses exactly the two
properties proved earlier: p^0_A is continuous on the open
ellipsoid, and the fibre law depends continuously on the label. The
contribution from labels outside the ellipsoid is handled by the
convention p^0_A = 0 there, so it drops out.
Hence
I_eta -> int gamma_{k,d}(dA) int_{R^k} (p^0_A(y))^t
int H(A, y, u) sigma_{A,y}^{otimes t}(du) dy. (7.8)
The label y_1 has become the common label y in the limit, and H is
continuous, so this is legitimate.
Fix a compact set K of full-row-rank
matrices on which H is supported. On K,
M := sup_{A in K} sup_{y} p^0_A(y) < infinity,
because p^0_A is bounded on the ellipsoid and continuous in A. For each
i >= 2, the y_i-integral of phi_eta(y_i - y_1) p^0_A(y_i) is at most M.
What is left is at most
||H||_inf * M^{t-1} * p^0_A(y_1),
which is integrable over y_1 because p^0_A has total integral 1. So
dominated convergence applies, and no quantity in the argument depends on
eta.
Now compute the same I_eta by fixing the tuple first.
Take u = (u_1,...,u_t) affinely independent, so rank D_u
= m; by Lemma 11 this holds for sigma_d^{otimes t}-almost every u. Put
F = F_u and D = D_u for short.
Let Z = A D, in R^{k x m}. Because the rows of A are independent standard
Gaussians, the rows of Z are independent, each N(0, D^T D) in R^m. So the
law of Z has Lebesgue density
rho_u(Z) = (2pi)^{-km/2} det(D^T D)^{-k/2}
exp( - tr( Z^T (D^T D)^{-1} Z ) / 2 ).
The second factor is at most 1, so
rho_u(Z) <= rho_u(0) = (2pi)^{-km/2} det(D^T D)^{-k/2}
= (2pi)^{-km/2} J(u)^{-k} = w_{k,m}(u), (7.9)
and the total integral of rho_u over R^{k x m} is 1.
Given Z, the matrix
A = A_0 + Z (D^T D)^{-1} D^T
is standard Gaussian exactly when A_0 is standard Gaussian with rows in
F^perp, drawn independently of Z. (The second term sends every column
direction of D to the prescribed column of Z; the first term is the free
part, which lives in the orthogonal complement.) Write gamma^F for the law
of A_0.
Therefore, for any bounded function Psi of Z,
int gamma_{k,d}(dA) Psi(A D) = int rho_u(Z) Psi(Z) dZ. (7.10)
Apply this to Psi(Z) = product_{i=2}^{t} phi_eta(Z_{:,i-1}) times
Psi_eta(Z) = int H( A_0 + Z (D^T D)^{-1} D^T ,
( A_0 + Z (D^T D)^{-1} D^T ) u_1 , u )
gamma^F(dA_0).
At Z = 0 the perturbation vanishes, so Psi_eta(0) equals Psi_0 exactly,
where
Psi_0 = int H( A_0 , A_0 u_1 , u ) gamma^F(dA_0).
Because H is continuous and bounded, also Psi_eta(Z) -> Psi_0 as Z -> 0.
Define
Phi_eta(u) = int rho_u(Z) product_{i=2}^{t} phi_eta(Z_{:,i-1})
Psi_eta(Z) dZ.
This is the conditional expectation of H over A given the tuple u, with
the approximate identity weighting. The identity (7.10) says
I_eta = int sigma_d^{otimes t}(du) Phi_eta(u).
As eta -> 0, the weight product phi_eta concentrates on Z = 0. For each
fixed u, then,
Phi_eta(u) -> rho_u(0) Psi_0
= (2pi)^{-km/2} J(u)^{-k}
int H(A, A u_1, u) gamma_{k,d}^{F_u}(dA).
And the domination is immediate: |Phi_eta(u)| <= ||H||_inf, because rho_u
has total mass 1 and Psi_eta is bounded by ||H||_inf. So dominated
convergence in u applies, and
I_eta -> (2pi)^{-km/2} int J(u)^{-k}
int H(A, A u_1, u) gamma_{k,d}^{F_u}(dA)
sigma_d^{otimes t}(du). (7.11)
The right side is finite by Lemma 11, applied with the given k and m.
The limit of a sequence of numbers does not
depend on how it is computed, so (7.8) and (7.11) have the same value.
For every bounded continuous H supported on full-row-rank matrices,
int gamma_{k,d}(dA) int_{R^k} (p^0_A(y))^t
int H(A, y, u) sigma_{A,y}^{otimes t}(du) dy
= (2pi)^{-km/2} int J(u)^{-k}
int H(A, A u_1, u) gamma_{k,d}^{F_u}(dA) sigma_d^{otimes t}(du). (7.12)
This is (7.6) with nu = sigma_d, restricted to such tests H.
Now that (7.12) is proved for bounded continuous tests, three steps
complete the theorem.
Both sides of (7.12) are finite measures. Read (7.12) as a statement about
two nonnegative Borel measures on the open set of full-row-rank matrices,
times R^k for the label, times (S^{d-1})^t for the tuple:
L(dA, dy, du) = gamma_{k,d}(dA) (p^0_A(y))^t dy sigma_{A,y}^{otimes t}(du),
R(dA, dy, du) = w_{k,m}(u) sigma_d^{otimes t}(du) gamma_{k,d}^{F_u}(dA)
(times the deterministic label y = A u_1).
Then (7.12) says int H dL = int H dR for every bounded continuous H
supported on full-row-rank matrices. Both total masses are finite:
int dL = int gamma_{k,d}(dA) int_{R^k} (p^0_A(y))^t dy
<= E_gamma [ (sup_y p^0_A(y))^{t-1} ] < infinity.
The last expectation is finite because sup_y p^0_A = C det(A A^T)^{-1/2}
and det(A A^T) is a product of k independent chi-squares with degrees
d, d-1, ..., d-k+1, whose negative powers have finite expectation as long
as the degrees stay above 0. For R,
int dR = (2pi)^{-km/2} int J(u)^{-k} sigma_d^{otimes t}(du)
< infinity
by Lemma 11. So both are finite Borel measures on a second-countable
space. Both are carried in a bounded set: L because p^0_A vanishes outside
the ellipsoid E_A, and R because its label is A u_1 with |u_1| = 1. Finite
Borel measures on a metric space, carried in a bounded set, are determined
by their integrals against bounded continuous functions. Therefore L = R
as measures,
and (7.12) holds for every nonnegative Borel H. (This is the standard
monotone class argument: the class of H for which the identity holds
contains bounded continuous functions and is closed under increasing
limits.)
For the prior density, let nu = f sigma_d with
0 <= f <= L < infinity. The function (u_1,...,u_t) -> product_i f(u_i) is
nonnegative and measurable, so multiplying the identity of measures L = R
by it preserves the identity.
On the left, at a label y with h_A(y) > 0,
int product_i f(u_i) sigma_{A,y}^{otimes t}(du) = h_A(y)^t ,
by definition of h_A. Together with p_A = p^0_A h_A this turns
(p^0_A(y))^t sigma_{A,y}^{otimes t}(du)
into
p_A(y)^t * ( f sigma_{A,y} / h_A(y) )^{otimes t}(du)
= p_A(y)^t mu_{A,y}^{otimes t}(du).
On the right the same multiplication by product_i f(u_i) turns
sigma_d^{otimes t}(du) into nu^{otimes t}(du).
Where h_A(y) = 0 the quotient defining
mu_{A,y} does not exist. Handle this once and for all by declaring the
left side to be
int gamma_{k,d}(dA) int_{R^k} int H(A,y,u) lambda_{A,y}^{otimes t}(du) dy, (7.13)
with lambda_{A,y} the unnormalized fibre measure from 7.1. The two
descriptions coincide wherever p_A(y) > 0, because there lambda_{A,y} =
p_A(y) mu_{A,y}, and both are zero where p_A(y) = 0, because lambda then
has total mass zero. So (7.13) is unambiguous, and (7.6) holds with it.
This is (7.6), and Theorem 12 is proved.
STEP 3 (what is still owed). The identity (7.6) is a statement about finite
measures. To get a probability statement, division by p_A(y)^m is required, which
is legitimate only where p_A(y) > 0. The probability division does that with truncated
divisions and monotone convergence, and the finiteness of the left side of
(7.6) then forces p_A(A u_1) > 0 for almost every (A,u) under the reference
measure R. Nothing extra has to be proved about density versions: a zero
would make the right side infinite and would contradict the finite left
side.
Theorem 12 is an identity of finite measures. To read it as a statement
about probabilities, both sides are divided by p_A(y)^m. That is legal
only where p_A(y) > 0, so the equation is truncated and the truncation is released.
Let nu = f sigma_d be a probability, with 0 <= f <= L < infinity. Let
H >= 0 be Borel. For an integer n >= 1 put
H_n(A, y, u) = H(A, y, u) * 1{ p_A(y) >= 1/n } * p_A(y)^{-m}.
This is Borel and nonnegative, so (7.6) applies to it. Insert it and
simplify. The only simplification needed is
p_A(y)^t * p_A(y)^{-m} = p_A(y)^{t-m} = p_A(y),
and t - m = 1 is exactly where the choice t = m+1 is spent. The result is
int gamma_{k,d}(dA) int_{p_A >= 1/n} p_A(y)
int H(A,y,u) mu_{A,y}^{otimes t}(du) dy
= (2pi)^{-km/2} int J(u)^{-k} nu^{otimes t}(du)
int H(A, A u_1, u) 1{ p_A(A u_1) >= 1/n } p_A(A u_1)^{-m}
gamma_{k,d}^{F_u}(dA). (8.2)
BOTH SIDES INCREASE IN n. The indicator 1{p_A >= 1/n} increases with n,
and all integrands are nonnegative, so monotone convergence applies on
each side separately.
The left side of (8.2) increases to
int gamma_{k,d}(dA) int_{R^k} p_A(y)
int H(A,y,u) mu_{A,y}^{otimes t}(du) dy. (8.3L)
This is finite for every bounded H, because int p_A(y) dy = 1 and
int H mu_{A,y}^{otimes t}(du) <= ||H||_inf. It is the expectation of H
under the replica law Q: draw A, draw Y from the density p_A, draw the t
replicas independently from the posterior mu_{A,Y}. So (8.3L) equals
E_Q[H].
The right side of (8.2) increases to
(2pi)^{-km/2} int J(u)^{-k} nu^{otimes t}(du)
int H(A, A u_1, u) p_A(A u_1)^{-m} gamma_{k,d}^{F_u}(dA), (8.3R)
allowing the value +infinity. Since (8.2) is an equality for every n and
the left side converges to the finite number E_Q[H], the right side
converges to a finite number as well.
Take H = 1. Then
E_Q[1] = 1 = (2pi)^{-km/2} E_R [ J(U)^{-k} p_A(A U_1)^{-m} ],
under the reference law R defined in (8.4) below. The left side is
finite. Also J(U) > 0 for R-almost every U by Lemma 11. A finite
expectation of a nonnegative quantity that is positive almost surely
forces the remaining factor to be positive almost surely. So
p_A(A U_1) > 0 for R-almost every (A, U). (8.3P)
This is the only place where positivity of the projected density at the
actual label is used, and it is a consequence, not an assumption. No
density-version lemma is required anywhere.
Combining (8.3L) and (8.3R) and dropping the truncation gives, for every
nonnegative Borel H
E_Q[H] = (2pi)^{-km/2} int J(u)^{-k} nu^{otimes t}(du)
int H(A, A u_1, u) p_A(A u_1)^{-m}
gamma_{k,d}^{F_u}(dA). (8.3)
For later use, the same identity with every integral written out is:
int gamma_{k,d}(dA) int_{R^k} p_A(y)
int H(A,y,u) mu_{A,y}^{otimes t}(du) dy
= (2pi)^{-km/2} int J(u)^{-k} nu^{otimes t}(du)
int H(A, A u_1, u) p_A(A u_1)^{-m}
gamma_{k,d}^{F_u}(dA). (8.4)
So (8.4) is (8.3) written out in full, and it holds for every nonnegative
Borel H. Define R by
R(dA, du) = nu^{otimes t}(du) gamma_{k,d}^{F_u}(dA).
R is a probability law: draw t independent signals from nu, then draw a
Gaussian matrix annihilating their differences. Then (8.4) reads
E_Q[ H ] = (2pi)^{-km/2} E_R [ J(U)^{-k} p_A(A U_1)^{-m} H ], (8.5)
for every nonnegative Borel H, where U = (U_1,...,U_t) under R. So
dQ/dR = (2pi)^{-km/2} J^{-k} p_A(A U_1)^{-m}. (8.6)
Taking H = 1 in (8.5) gives the normalizing identity
1 = (2pi)^{-km/2} E_R [ J(U)^{-k} p_A(A U_1)^{-m} ]. (8.7)
This is the probability statement sought: not a statement about
measures with arbitrary total mass, but an exact identity for the Laplace
transform of the inverse simplex volume against the actual projected prior
density at the actual label.
COROLLARY 13 (replica likelihood, and the correlation it controls). Let
nu = f sigma_d be a probability with 0 <= f <= L < infinity, let k >= 1,
m >= 1, t = m+1 and k+m <= d-2, and let Q be the posterior replica law as in Lemma 9. Put
K = D( Q || nu^{otimes t} ),
the total correlation of the tuple. Then
K <= -(km/2) log(2pi) - k E_Q log J(U) - m E_Q log p_A(A U_1). (8.8)
Proof. By (8.6), dQ/dR exists and is of the stated form. Forgetting A in
R leaves nu^{otimes t}: the law of t independent draws from nu. A relative
entropy cannot increase under the map that forgets A, so
K = D( Q || nu^{otimes t} ) <= D( Q || R ).
Now use the definition of relative entropy and (8.6):
D(Q || R) = E_Q log( dQ/dR )
= (km/2) log(1/(2pi)) - k E_Q log J - m E_Q log p_A(A U_1).
Substituting gives (8.8). Done.
The term -k E log J is the one that cancels: the block bound builds an observable test whose logarithm produces
+k log J against the projected data, and the two annihilate. The term
-m E log p_A(A Y) is the awkward one; the density comparison below handles
it. Reading (8.8) alone, one might worry that E log p_A could be very
negative, making the bound vacuous. It cannot: p_A is a probability
density on R^k, so E_{Y ~ p_A} log p_A(Y) = -h(p_A) and the entropy h(p_A)
is at most the entropy of the ellipsoid's volume, so the term is bounded by
a constant times k log d. This is recorded properly below, where all the
logarithms are shown to be integrable.
The replica law Q and the reference law R make exactly
the same statement about the tuple, in two different orders. Q says: draw
first the labels, then the signals on the fiber. R says: draw first the
signals, then a matrix that makes the labels equal. The density (8.6) is
the exact exchange rate between those two descriptions, and it is finite
and positive almost surely.
Corollary 13 bounds K by an expression containing log J and log p_A(A Y).
A bound containing the logarithm of something that can be zero or infinite
is worthless, so both terms are checked before use.
The reason to check this now rather than later: the block bound takes logarithms of
a test function and adds and subtracts these quantities. That algebra is
legitimate only if every term has a finite expectation. Once that is known
expectations can be computed freely.
Fact E1. Let f be a probability density on R^k whose support has Lebesgue
measure V. Then its differential entropy h(f) = -int f log f satisfies
0 <= h(f) <= log V. (9.1)
Both halves are one-line arguments. Expand -int f log f as
D( f dy || V^{-1} 1_E dy ) + log V, where E is the support. The
divergence of a law from another probability law is nonnegative, and the
uniform law on E has density V^{-1} on E. So h(f) >= 0 and h(f) <= log V.
(The divergence is +infinity if f is not a density of the uniform law; that
only helps.)
Fact E2. Let Sigma be a k x k positive definite matrix coming from
Sigma = A A^T with A a k x d standard Gaussian matrix, k <= d. Then
E log det Sigma <= k log d and E |log det Sigma| < infin. (9.2)
For the upper bound, det Sigma^(1/k) <= tr(Sigma)/k by the inequality
between geometric and arithmetic means applied to the eigenvalues, and
E tr(Sigma) = k d, so by Jensen applied to log,
E log det Sigma = k E log det(Sigma)^{1/k}
<= k log( E tr(Sigma) / k ) = k log d.
For the absolute value, Gram-Schmidt writes det Sigma as a product of k
independent chi-squares with degrees d, d-1, ..., d-k+1. Each factor is
positive almost surely, and the logarithm of a chi-square with nu >= 1
degrees of freedom is integrable in both directions: near zero because
int_0^{a} |log x| x^{nu/2 - 1} dx < infinity for nu > 0,
and near infinity because log x <= x. Summing over the k factors proves
integrability. This is a standard Wishart Gram-Schmidt computation.
The tuple is u = (u_1,...,u_t) with t = m+1 points on the sphere, so each
simplex height in (7.3) is at most 2 and
log^+ J(u) = max{0, log J(u)} <= m log 2. (9.3)
That is the upper bound, and it needs nothing. For the lower bound, use
Lemma 11: J^{-k} has finite expectation under sigma_d^{otimes t}. For a
nonnegative random variable X,
E log^-(1/X) = E max{0, -log X} = int_0^infinity P{X <= e^{-s}} ds.
Apply this with X = J. Since J^{-k} >= 0 and J > 0 almost surely,
P{ J <= e^{-s} } = P{ J^{-k} >= e^{ks} } <= e^{-ks} E J^{-k}.
Therefore
E log^- J <= E J^{-k} int_0^infinity e^{-ks} ds = E J^{-k} / k,
(9.4)
which is finite by Lemma 11. Combining (9.3) and (9.4),
E_Q |log J(U)| < infinity. (9.5)
Under the replica law Q, the label Y has density p_A on R^k. Hence the
two signs are the entropy of p_A:
E_Q [ -log p_A(Y) ] = h( p_A(y) dy ),
E_Q [ +log p_A(Y) ] = - h( p_A(y) dy ). (9.6)
The support of p_A is the ellipsoid E_A, whose Lebesgue volume is
V_A = v_k det(Sigma)^{1/2} . (9.7)
By Fact E1 with V = V_A,
0 <= E_Q [ -log p_A(Y) ] <= log v_k + (1/2) log det Sigma, (9.8)
and by Fact E2 the right side has finite expectation. Also, by the
left-hand inequality in (9.8), E_Q log p_A(Y) = -h <= 0 always. Hence
E_Q |log p_A(A Y)| < infinity. (9.9)
The same argument applies to the Gaussian base and to any prior density
f with 0 <= f <= L, because p_A <= L p^0_A keeps 1/p_A bounded below only
where it is already positive, and where p_A is positive the support is
still the ellipsoid.
The block bound uses a standard Gaussian G with ell rows and m columns, with
ell > m. Gram-Schmidt writes
det(G^T G) = V_1 V_2 ... V_m , V_i ~ chi^2_{ell - i + 1},
(9.10)
independent, the degrees being ell, ell-1, ..., ell-m+1 in the order of
the components. Two consequences.
First, for an even integer k with ell - m + 1 > k,
Z_{k,m} := E det(G^T G)^{-k/2}
= prod_{j=1}^{k/2} 1/( ell - m - 2j + 1 ) < infinity.
(9.11)
The product formula comes from E V^{-1} = 1/(nu - 2) for V ~ chi^2_nu with
nu > 2, applied k/2 times; the displays are all elementary integrations
of the chi-square density. With ell = 4k and m = k, ell - m + 1 =
3k + 1 > k, so all the denominators in (9.11) are at least 1. In
particular Z_{k,m} is finite and positive.
Second, by Jensen applied to log,
(1/2) E log det(G^T G) <= (m/2) log( ell ). (9.12)
Indeed, det(G^TG)^{1/m} <= tr(G^TG)/m and E tr(G^TG) = ell m, so
E log det(G^TG) <= m log(ell m / m) = m log ell.
The estimates are put together.
LEMMA 14 (everything is finite). Let nu = f sigma_d be a probability with
0 <= f <= L < infinity, and let k, m, t = m+1 satisfy k + m <= d-2. Under
the replica law Q and the reference law R:
(i) E_Q log J(U) is finite.
(ii) E_Q log p_A(A Y) is finite, and it equals -h(p_A).
(iii) The total correlation K = D(Q || nu^{otimes t}) is finite, and
satisfies (8.8) with no qualification.
(iv) E_Q [ log p_A(A Y) ] <= (1/2) E log det Sigma.
Proof. (i) is (9.5). (ii) is (9.9). For (iii), the right side of (8.8)
is a sum of three terms: a constant, -k E log J, and -m E log p_A. Terms
one and two are finite by (i), and term three is finite by (ii). So the
bound is a genuine real number. For (iv), (9.6) and the right-hand
inequality in (9.8). Done.
In (8.8) the last term is
-m E_Q log p_A(A Y) and E_Q log p_A <= 0, so that term is nonnegative:
it makes the bound on K worse, not better. In the block-bound argument, the comparison with
an observable test produces the same term with the opposite sign, and the
two cancel. That cancellation is the heart of the Gaussian block bound.
For the rest of the proof fix
k = 2 floor(d/16), m = k, t = m + 1, ell = 4k. (10.1)
For d >= 64, k >= 8 and k >= d/32. The hypotheses used below
hold, with room to spare:
k + m = 2k <= d/8 <= d - 2,
ell - m = 3k >= k (room for the selector below),
ell - m + 1 = 3k + 1 > k (so Z_{k,m} is finite).
The block experiment is the one already fixed. Let nu = f sigma_d be a
probability with 0 <= f <= L < infinity. Draw S ~ nu, a k x d standard
Gaussian matrix A, the label Y = A S, a finite-valued message W from a
kernel of (A,Y) that is conditionally independent of S given (A,Y), and an
ell x d standard Gaussian matrix B independent of everything.
The claim is
t I(S;W | B, B S) <= H(W) + C k m + m ( C k + C log(2 + log L) ),
(10.2)
which after dividing by t = m+1 reads
I(S;W | B, B S) <= H(W)/t + C k + C log(2 + log L). (10.3)
Everything on the right is small: H(W) <= M log 2 where M is the number of
memory bits, and Ck + C log(2 + log L) is linear in d.
Draw the replicas and write U_i = B S_i for the projected signals. The
analyst, seeing only (B, U_1,...,U_t), can compute
B D_u = [ U_2 - U_1 , U_3 - U_1 , ... , U_t - U_1 ].
Almost surely this has rank m: the tuple is affinely independent almost
surely by Lemma 11, and B restricted to F_u is a standard Gaussian map on
an m-dimensional space.
CHOOSING C_0. Since ell - m = 3k >= k, the orthogonal complement of the
columns of B D_u inside R^ell has dimension at least k. Choose
C_0 = C_0(B D_u),
a k x ell matrix with orthonormal rows, all orthogonal to the columns of
B D_u. Make the choice measurable: project the standard basis, run
Gram-Schmidt, keep the first k successful rows, and use a fixed rule on
the null set of rank failures.
DEFINE
A_tilde = C_0 B .
This is a k x d matrix known to the analyst. Two properties matter.
(P1) A_tilde s = 0 for every s in F_u. Reason: the rows of C_0 kill
col(B D_u) = B F_u.
(P2) A_tilde S_i = C_0 U_1 for every i, because S_i - S_1 lies in F_u and
B(S_i - S_1) lies in col(B D_u), which C_0 kills. So A_tilde gives
all replicas the SAME label, namely C_0 U_1.
Property (P2) is the point. The analyst can see a matrix A_tilde and a
common label C_0 U_1 for the t replicas. That is exactly the structure the
equal-label theorem describes, except that the matrix is observable rather
than the true one.
Let G be an ell x m standard Gaussian matrix and let Z_{k,m} be the
constant of (9.11). Put
Lambda = (2pi)^{-km/2} / Z_{k,m}
* det( (B D_u)^T (B D_u) )^{-k/2}
* p_{A_tilde}( C_0 U_1 )^{-m}. (10.4)
Every factor is a function of (B, U_1,...,U_t) alone. So Lambda is
observable.
Let E = D_u (D_u^T D_u)^{-1/2}, an orthonormal basis of
F_u, and let G = B E. Then B D_u = (B E)(D_u^T D_u)^{1/2}, so
det( (B D_u)^T (B D_u) ) = det( D_u^T D_u ) * det( G^T G )
= J(u)^2 * det( G^T G ), (10.5)
and G is a standard Gaussian ell x m matrix. Also, by (P2),
C_0 U_1 = A_tilde S_1 , (10.6)
so the last factor of (10.4) evaluates the projected prior density of
A_tilde at the projected label of a replica.
LEMMA 15 (the test is normalized). For every fixed B, the conditional
expectation of Lambda given B, computed under the law that draws t
independent signals from nu and then projects them, equals one.
Proof. Work conditionally on B. By Lemma 16 below, conditionally on the
projected tuple, A_tilde is a draw from gamma^F_{k,d} and is independent
of G. Therefore
E[ Lambda | B ] = (2pi)^{-km/2} / Z_{k,m}
* E[ J(U)^{-k} det(G^T G)^{-k/2} p_{A_tilde}(A_tilde U_1)^{-m} ]
= (2pi)^{-km/2} / Z_{k,m}
* E[ J(U)^{-k} E_{A_tilde ~ gamma^F}( p_{A_tilde}(A_tilde U_1)^{-m} ) ]
* E[ det(G^T G)^{-k/2} ].
The last factor is Z_{k,m} by definition (9.11) and the independence of
Lemma 16. The middle line, after inserting (2pi)^{-km/2} and comparing
with (8.7), is exactly one. Indeed (8.7) reads
1 = (2pi)^{-km/2} E_{U ~ nu^{otimes t}} [ J(U)^{-k}
E_{A ~ gamma^F_{U}}( p_A(A U_1)^{-m} ) ],
which is the same statement. So E[Lambda | B] = 1. Done.
LEMMA 16 (the conditional law of the observable matrix). This statement is
used inside the proof of Lemma 15 and recorded just after that use,
so that the preceding argument reads in one pass. Conditionally on (B, U):
(a) A_tilde has law gamma^F_{k,d};
(b) A_tilde is independent of G = B E.
These are the two facts just used.
Fix B. Let Q_B be the conditional law of the projected tuple U given B
under the replica experiment, and let R_B = p_B^{otimes t} be the product
of the marginal laws of B S when S ~ nu. By definition of K',
K'(B) = D( Q_B || R_B ).
Lemma 15 says that Lambda, as a function of U, has R_B-expectation one.
Apply the variational bound (2.3) with F = Lambda:
K'(B) >= E_{Q_B} log Lambda.
Average over B:
K' >= E log Lambda. (10.7)
All such logarithms are integrable by Lemma 14 and by (9.11), (9.12),
so this is a legitimate inequality between real numbers.
Take logarithms in (10.4), using (10.5) and (10.6):
log Lambda = -(km/2) log(2pi) - log Z_{k,m}
- k log J(U)
- (k/2) log det(G^T G)
- m log p_{A_tilde}(A_tilde S_1). (10.8)
Compare (10.8) with the correlation bound (8.8):
K <= -(km/2) log(2pi) - k E log J(U) - m E log p_A(A S_1). (10.9)
Subtract (10.7) from (10.9). The terms -(km/2)log(2pi) cancel, and the
terms -k E log J cancel exactly. What is left is
K - K' <= log Z_{k,m} + (k/2) E log det(G^T G)
+ m E [ log p_{A_tilde}(A_tilde S_1)
- log p_A(A S_1) ]. (10.10)
Now bound the first two terms on the right of (10.10).
Term one. Every factor in (9.11) is at most 1, so 0 < Z_{k,m} <= 1 and
log Z_{k,m} <= 0.
Term two. By (9.12) with ell = 4k,
(k/2) E log det(G^T G) <= (k m / 2) log(ell) <= C k m. (10.11)
Therefore
K - K' <= C k m + m * Delta, (10.12)
where
Delta = E [ log p_{A_tilde}(A_tilde S_1) - log p_A(A S_1) ] (10.13)
is the only quantity left to bound. It compares two projected prior
densities, each evaluated at the label produced by its own matrix acting on
a signal drawn from nu. In the first case the matrix is the observable
A_tilde = C_0 B; in the second it is the true A.
Everything up to that point was exact. The dyadic argument above bounds Delta.
Delta from (10.13) must be bounded. Start with the uniform base f = 1, where
everything is explicit, and then add the prior density.
THE EXACT ENTROPY OF A UNIFORM-BASE PROJECTION. Fix a full-row-rank k x d
matrix M with Sigma = M M^T, and let p^0_M be its projected density, given
by (7.1). Its differential entropy is
h(p^0_M) = - int p^0_M(y) log p^0_M(y) dy . (10.14)
Substitute (7.1). Two pieces come out.
The easy pieces. The factors in (7.1) give
- log c_{d,k} with c_{d,k} = Gamma(d/2)/(pi^{k/2}Gamma((d-k)/2)),
+ (1/2) log det Sigma,
- ((d-k-2)/2) * int p^0_M(y) log(1 - q_M(y)) dy .
Only the middle line involves M.
The integral. Write y = Sigma^{1/2} z. Then q_M(y) = |z|^2 and
p^0_M(y) dy = c_{d,k} (1 - |z|^2)^{(d-k-2)/2} dz on the unit ball of R^k,
so the integral is the expectation of log(1 - |Z|^2) where the density of
|Z|^2 is a Beta((d-k)/2, k/2). Hence it equals
psi((d-k)/2) - psi(d/2), (10.15)
where psi is the logarithmic derivative of Gamma. The identity is
int_0^1 u^{a-1}(1-u)^{b-1} log u du = B(a,b)(psi(a) - psi(a+b)), applied
with a = (d-k)/2 and b = k/2, together with the normalization check which
is exactly the statement that p^0_M integrates to one.
Therefore
h(p^0_M) = K(d,k) + (1/2) log det Sigma_M , (10.16)
where K(d,k) is the same number for every M. This is the whole content of
the entropy computation: for the uniform base, the only way the matrix
enters the entropy of its projected density is through log det Sigma.
With nu = sigma_d, the two terms of Delta are
E_Q log p_A(A S_1) = - h(p^0_A) = -K(d,k) - (1/2) log det Sigma_A ,
E log p_{A_tilde}(A_tilde S_1) = - E h(p^0_{A_tilde})
= -K(d,k) - (1/2) E log det Sigma_{A_tilde} .
The K(d,k) terms cancel. What is left is a difference of expected
log-determinants:
Delta = (1/2) ( E log det Sigma_A - E log det Sigma_{A_tilde} ). (10.17)
By Gram-Schmidt,
E log det Sigma_A = sum_{i=1}^{k} [ psi((d-i+1)/2) + log 2 ],
E log det Sigma_{A_tilde} = sum_{i=1}^{k} [ psi((d-m-i+1)/2) + log 2 ],
because A has k x d i.i.d. standard Gaussian entries while A_tilde has
rows in a subspace of dimension d-m.
Use the standard estimate for the digamma function: psi is increasing and
concave with psi'(x) <= 1/x, so for a > 0,
psi(x + a) - psi(x) <= a/x . (10.18)
With x = (d-m-i+1)/2 and a = m/2, each summand is at most
m/(d-m-i+1) <= m/(d-m-k+1). Summing over the k summands,
Delta <= (k/2) * m/(d - m - k + 1) . (10.19)
With k = m = 2 floor(d/16) and d >= 64, the denominator d - m - k + 1 is at
least 3d/4, so
Delta <= (k/2) (2k)/(3d/4) = (4/3) k^2 / d <= C k . (10.20)
This is of order d, not d log d. That is what the argument needs.
The prior density f enters Delta only through the label law. Handle this
once and for all by a dyadic decomposition of the distance from S_1 to the
affine subspace S_1 + F_u that both A and A_tilde annihilate.
Fix the tuple U = (S_1,...,S_t) and the actual label Y = A S_1. Write
delta(s') = |P_{F^perp}(s' - S_1)|.
Conditional on the tuple, the observable A_tilde has law gamma^F_{k,d}. The
ball-average version of Theorem 12 at the label A_tilde S_1 gives
E_{A_tilde}[p_{A_tilde}(A_tilde S_1)]
<= (2 pi)^{-k/2} int delta(s')^{-k} p(ds'). (10.23a)
Indeed, on a radius-rho ball of centres the coordinates of A_tilde(s'-S_1)
are centered Gaussian with variance delta(s')^2, so the ball mass under
A_tilde_* p is at most v_k rho^k (2 pi)^{-k/2} delta(s')^{-k}; taking
rho = 1/j and applying Fatou gives the displayed inequality.
The affine subspace S_1 + F_u has dimension m, so the tube estimate gives
p{delta <= rho} <= L C^d rho^{d - 1 - m}, 0 < rho <= 1. (10.23b)
Since k and m are proportional to d/16, the exponent d - 1 - m - k is
bounded below by c d for some absolute c > 0. Fix the integer
J_0 = 1 + ceiling((log_2 L + C_1 d)/(d - 1 - m - k)) (10.23c)
with C_1 large enough that the small-distance tail estimate below holds.
The small-distance part of the integral in (10.23a) is controlled by
(10.23b): the sum
(2 pi)^{-k/2} sum_{j >= J_0} 2^{(j+1) k} L C^d 2^{-j (d - 1 - m)} <= 1 (10.23d)
follows from the cutoff in (10.23c). For the remaining distances, split
delta(s') into dyadic bins (r/2, r] with r in {2, 1, ..., 2^{-J_0+1}}.
Since A annihilates F,
|A s' - Y| <= |A|_op delta(s') (10.23e)
for every s' in a bin. If pbar_A^a(Y) is the average of p_A over the
radius-a ball centered at Y, the bin contributes at most
(2/r)^k p{delta <= r} <= 2^k v_k |A|_op^k pbar_A^{|A|_op r}(Y). (10.23f)
The prefactor 2^k v_k comes from the ratio of ball volumes. Since
v_k <= (2 pi e/k)^{k/2}, summing (10.23f) over the bins gives
E_{A_tilde}[p_{A_tilde}(A_tilde S_1)]
<= 1 + (C |A|_op / sqrt(k))^k sum_r pbar_A^{|A|_op r}(Y). (10.23g)
The 1 is the small-distance contribution (10.23d); the sum is over at most
J_0 + 2 bins.
Divide (10.23g) by p_A(Y) and apply Jensen:
E[log p_{A_tilde}(A_tilde S_1) - log p_A(Y) | A, Y, U]
<= log(1 + (C|A|_op/sqrt(k))^k sum_r pbar_A^{|A|_op r}(Y)/p_A(Y)). (10.23h)
Averaging over Y | A with law p_A(y) dy gives two elementary bounds:
E_{Y|A}[pbar_A^a(Y)/p_A(Y)] <= 1 (10.23i)
for every radius a fixed by A, and
E_{Y|A}[1/p_A(Y)] <= v_k |A|_op^k <= (2 pi e/k)^{k/2} |A|_op^k. (10.23j)
The first is a ball average of a probability density over {p_A > 0}; the
second is the ellipsoid's Lebesgue volume. Jensen again, over Y, bounds
(10.23h) by
k log(C (1 + |A|_op / sqrt(k))) + log(J_0 + 2). (10.23k)
Two estimates complete the bound. A 1/4-net argument on the unit spheres
in R^d and R^k shows E|A|_op <= C sqrt(d), and since the logarithm is
concave, k >= d/32 gives
E[k log(C (1 + |A|_op / sqrt(k)))] <= C k. (10.23l)
The cutoff in (10.23c) with d - 1 - m - k >= c d gives
log(J_0 + 2) <= C log(2 + log L). (10.23m)
Combining (10.23l) and (10.23m) and taking the outer expectation over A:
Delta <= C k + C log(2 + log L). (10.23)
Every step is proved. The uniform-prior bound (10.20) is the special case
L = 1, for which (10.23m) is absorbed into Ck.
Combine (10.12) with (10.23):
K - K' <= C k m + m ( C k + C log(2 + log L) ). (10.24)
Insert into Lemma 9, which says
t I(S;W|B,BS) <= H(W) + K - K':
t I(S;W | B, B S) <= H(W) + C k m + m ( C k + C log(2 + log L) ).
(10.25)
Divide by t = m+1 >= m and absorb constants:
I(S;W | B, B S) <= H(W)/t + C k + C log(2 + log L). (10.26)
THEOREM 17 (the one-block bound). Let 0 <= f <= L < infinity with
int f dsigma_d = 1, let k = 2 floor(d/16), m = k, t = m+1 and ell = 4k.
Draw S ~ f sigma_d, a k x d standard Gaussian A, the exact label Y = A S, a
message W from a kernel of (A,Y) that is conditionally independent of S,
and an ell x d standard Gaussian B independent of everything. Then, for
all d >= 64, (10.26) holds with an absolute constant C.
Three things are being said at once.
The message entropy is divided by t = m+1 ~ d/16. A message with M bits
contributes at most M log 2 / t, which is 16 M log 2 / d.
There is an unavoidable additive cost of order d, one k. That is the
price of the projected replicas being distinguishable at all.
The prior enters only through log(2 + log L). Conditioning on an event
of probability a makes L = 1/a, so the cost is log(2 + log(1/a)): doubly
logarithmic in the rarity. This is exactly what lets the block averaging
over rare states without paying a large penalty.
Now the blocks are put together. From this point on eps and T and M are
functions of d; eps, T, M is written for short, and
beta = log(1/eps), 0 < eps <= 1/10, beta >= 2. (11.1)
The learner is the one fixed at the outset: finite state, at most 2^M values, exact
labels, deterministic horizon T, and uniform-prior success at least 2/3.
Let xi denote the entire collection of the learner's random variables: the
shared seed, and every fresh transition coin and output coin. Given a
realization of xi, the learner's state path, stopping index and output are
deterministic functions of the rows and labels.
Let c(xi) be the conditional success probability given xi, that is, the
probability of angular success computed over the signal and the rows with
xi held fixed. Then c is measurable, 0 <= c <= 1, and 2/3 <= E c, because
the overall success probability is the average of the conditional ones.
A nonnegative function whose average is at least 2/3 attains a value at
least 2/3. Fix such a value xi_0. Hence:
FROM NOW ON THE LEARNER IS DETERMINISTIC, AND IT SUCCEEDS WITH
PROBABILITY AT LEAST 2/3 WHEN THE SIGNAL IS UNIFORM.
Nothing is lost: 2/3 >= 3/5, and 3/5 is the threshold in Corollary 5 and in
Lemma 6. Measure-theoretic details of choosing Borel versions for
per-seed kernels are not needed for the bound; they only matter if one
wants a deterministic learner whose state path is Borel measurable in the
data.
The learner may stop early. Pad it:
Draw all T rows in advance, X_1,...,X_T.
Run the learner. At the stopping index tau, freeze the state and record
the pair (tau, state at tau). Continue drawing and discarding the
remaining rows, keeping the tagged state unchanged.
The padded state at the end has at most
K = (T+2) 2^M values, log K = h_T = M log 2 + log(T+2).
(11.2)
The terminal output is a function of the final padded state together with
the fresh output randomness, which was already fixed in xi_0. So the
output is a function of the padded state alone.
Split the padded stream into blocks of k consecutive rows, with
k = 2 floor(d/16) as in (10.1). Let
n = ceil(T/k) (11.3)
be the number of blocks, and append extra ignored rows if needed so that
the last block is complete. Never let the learner see the extra rows; they
exist only to complete the bookkeeping.
Let V_i be the padded state at the end of block i, and V_0 the initial
padded state. Then V_0 is a constant: it is the initial state together
with the tag "index 0", and both are fixed by xi_0.
If T >= d beta, the theorem is already proved with constant 1, because
beta = log(1/eps). So assume
T <= d beta . (11.4)
On this branch, Lemma 8 applies (its only hypothesis is a fixed positive
success probability, and 2/3 is available). It gives
beta = o(d), T = o(d^2), h_T = o(d^2). (11.5)
Also, by Lemma 6, success at least 3/5 with exact raw observations
requires T > floor(d/2). A memory-limited learner cannot do better than
one that keeps every raw row, so
T > d/2 , hence n = ceil(T/k) >= 4 , (11.6)
for all large d, using k < d/8.
Fix i with 1 <= i <= n. Condition on the padded history V_{i-1} = h, a
value with probability p_h > 0. Under this conditioning:
The signal S still has a density with respect to sigma_d, namely
f_h(s) = P{V_{i-1} = h | S = s} / p_h, by Bayes' formula. This is a
probability density and
f_h <= 1/p_h , so the prior bound is L = 1/p_h. (11.7)
The i-th block consists of k fresh independent Gaussian rows, with
matrix A_i and labels A_i S. They are independent of (S, V_{i-1}).
The new state V_i is a deterministic function of (h, A_i, A_i S).
So it is a message drawn from a kernel of (A_i, A_i S), with an alphabet
of at most K values by (11.2).
Draw a fresh ell x d standard Gaussian matrix B, independent of the whole
learner experiment. It is used only for the analysis.
All the hypotheses of Theorem 17 hold, with k, m = k, t = m+1, ell = 4k,
prior density f_h and message V_i. Therefore
I( S ; V_i | V_{i-1} = h, B, B S )
<= (log K)/t + C k + C log( 2 + log(1/p_h) ). (11.8)
Now average (11.8) over h. Two averages are needed.
The first is immediate: (log K)/t = h_T / t does not depend on h, and Ck
does not either.
The second needs Jensen in the right direction. Put u_h = log(1/p_h).
The identity E[u_H] = H(V_{i-1}) says that the expected surprise of a
finite random variable is its entropy. The function u -> log(2 + u) is
concave and increasing on [0, infinity), so Jensen gives an upper bound:
E_h log( 2 + log(1/p_h) ) = E log(2 + u_H)
<= log( 2 + H(V_{i-1}) )
<= log( 2 + (i-1) log K ). (11.9)
The last inequality is the entropy bound H(V_{i-1}) <= (i-1) log K: each
of the i-1 preceding blocks contributes one state, and one state has
entropy at most log K by (11.2).
So, after averaging,
I( S ; V_i | V_{i-1}, B, B S )
<= h_T / t + C k + C log( 2 + (i-1) h_T ). (11.10)
Chain rule, then data processing. For any 1 <= j <= n,
I(S ; V_j | B, B S)
<= I(S ; V_1,...,V_j | B, B S)
<= sum_{i=1}^{j} I( S ; V_i | V_1,...,V_{i-1}, B, B S )
<= sum_{i=1}^{j} I( S ; V_i | V_{i-1}, B, B S ). (11.11)
The first inequality is data processing (V_j is a function of the tuple),
the second is the chain rule, and the third holds because conditioning on
the whole history V_1,...,V_{i-1} reveals at least V_{i-1}, so it can only
reduce information.
Take j = n and insert (11.10):
I(S ; V_n | B, B S)
<= n [ h_T / t + C k ] + C n log( 2 + n h_T ). (11.12)
Now use the branch facts. By (11.5), h_T = o(d^2) and n <= T/k + 1
= o(d^2)/k, so n h_T = o(d^4)/k, and therefore
log( 2 + n h_T ) <= C log d (11.13)
for all large d. Also t = m+1 >= k >= d/32, so h_T/t = o(d^2)/(d/32)
= o(d) <= C d. Putting these into (11.12),
I(S ; V_n | B, B S) <= C d n . (11.14)
That is the information the final padded state carries about the signal
once the analyst knows B S. The bound is linear in d per block.
The output S-hat is a function of V_n together with randomness already
fixed, so it is a function of V_n. By data processing in the conditional
experiment (condition on B, B S),
I( S ; S-hat | B, B S ) <= I( S ; V_n | B, B S ). (11.15)
For the left side, apply Corollary 5 with the b x d matrix being the
ell x d matrix B, so b = ell. Two hypotheses must be checked.
ell = 4k = 8 floor(d/16) <= d/2,
and the success probability is at least 2/3 >= 3/5. So for all large d,
I( S ; S-hat | B, B S )
>= (1/2)(d - ell - 1) log( 1/(5 eps) ) - log 2
>= c_1 d beta , (11.16)
using d - ell - 1 >= d/2 - 1 and log(1/(5eps)) >= 0.3 beta.
Combine (11.14), (11.15) and (11.16):
c_1 d beta <= I(S ; V_n | B, B S) <= C d n ,
so n >= c_2 beta with c_2 = c_1/C. By (11.3),
T + k >= n k >= c_2 beta k >= c_2 beta d/32 , (11.17)
because k >= d/32. Since beta >= 2 and k <= d/8, (11.17) gives
T >= c_2 beta d/32 - d/8 >= c d beta (11.18)
for an absolute c > 0, once beta >= 2 and d is large. This is the required
lower bound on the branch (11.4).
Both branches now give T >= c d beta, with the same absolute c once it is
taken small enough. That completes the streaming bound.
LEMMA 18 (streaming bound, conditional form). Let 0 < eps <= 1/10 and let
the learner be a finite-state deterministic learner with at most 2^M states,
deterministic horizon T, exact Gaussian rows and labels, and uniform-prior
angular success at least 2/3. Let B be an independent ell x d standard
Gaussian matrix with ell = 8 floor(d/16). Then, for all sufficiently large
d, and with the threshold allowed to depend on the sequence M = M(d),
if M = o(d^2) then T >= c d log(1/eps) (11.19)
with an absolute c > 0.
This is Theorem 1, the sole conclusion of the argument.
THEOREM 19 (memory-precision tradeoff). Let M(d) be a nonnegative
integer-valued sequence with M(d) = o(d^2), meaning M(d)/d^2 -> 0. Let
0 < eps(d) <= 1/10. Consider a learner with all of the following
properties, for every d.
(i) The signal is an unknown unit vector s in S^{d-1}. The rows
X_1, X_2, ... are independent standard Gaussians, and the labels
Y_j = <X_j, s> are exact.
(ii) The learner's persistent state has at most 2^M(d) values. Each
transition, and the stopping decision, may be any measurable
randomized function of the current state and the whole pair
(X_j, Y_j).
(iii) The learner stops by a pre-agreed deterministic horizon T(d) and
then outputs a unit vector s-hat, computed from its final state
and fresh private randomness.
(iv) When s is uniform on the sphere, the probability that
arccos(<s-hat, s>) <= eps(d) is at least 2/3.
Then there is an absolute constant c > 0 such that
T(d) >= c d log( 1/eps(d) ) (12.1)
for all sufficiently large d. The threshold in "sufficiently large" may
depend on the sequence M(d), but c does not depend on d, eps, M, or the
learner.
WHAT "ABSOLUTE" EXCLUDES. The constant c cannot be made to depend on the
memory sequence, on how the learner is built, on the number of rows T, or
on the accuracy. A bound whose constant shrinks as M grows would be
vacuous in exactly the regime that matters.
Apply the padding lemma: fix the learner's randomness once and for all, obtaining a
deterministic learner of the same memory and horizon with uniform-prior
success still at least 2/3. The deterministic learner satisfies every
hypothesis of Lemma 18, whose conclusion is exactly (12.1). That
is the whole proof.
REMARK 1 (why exact labels matter for the statement, not just the proof).
Suppose a learner is promised only noisy labels, Y_j = <X_j,s> + noise with
noise bounded by delta. A learner promised exact labels can first add its
own noise and then run the noisy-label algorithm, so a lower bound for
noisy labels does not imply one for exact labels. Exactness makes the
problem harder for the analyst, not easier: a single real number can carry
arbitrarily many bits in principle, and the theorem says that a
memory-limited stream cannot exploit that.
REMARK 2 (the role of the analyst's projection). The matrix B appears
nowhere in the learner. It is drawn by the analyst and revealed to the
analyst. It converts an unconditional statement about a state into a
conditional one: after B S is known, any residual information about S must
live in the part of S that B does not see, and that part has dimension
d - rank(B) >= d/2. Without the projection the endpoint estimate would be
about the whole sphere, and the replica argument would have nothing to
compare.
REMARK 3 (why 2/3 and not 1/2). Two thresholds are used. The endpoint
needs success at least 3/5, to survive the loss from the event that the
residual radius is small; the raw-data bound needs at least 3/5 for the
same reason. The factor 2/3 leaves room. The bound is not sharp in the
constant; the statement is asymptotic in d.
REMARK 4 (the memory threshold). The hypothesis is M = o(d^2). The proof
uses it twice: to force log(1/eps) = o(d) on the branch (11.4), and to keep
the padded state entropy h_T subquadratic. Nothing established says what happens
when M is a positive fraction of d^2. A matrix of d rows has d^2 entries,
so quadratic memory is the natural scale at which the whole problem
changes, and that regime is not treated.
REMARK 5 (density comparison). The dyadic argument proves it for a
general bounded prior with no quoted estimate. The uniform-prior case
reduces to a difference of log-determinants (10.20); the general case is
controlled by (10.23). Every step is derived from the definitions.
REMARK 6 (the two hand computations). The two key computations are: the entropy formula (10.16), which shows
that for the uniform prior the whole density comparison collapses to a
difference of expected log-determinants; and the normalization (8.7),
which is where the constant (2 pi)^{-km/2} comes from and where the
equal-label identity turns into a probability statement.
A concrete instance: with eps = 10^{-3}, d = 1000, and a state of
10^5 bits (far below d^2/4 = 250000), the theorem requires about d log(1/eps) = 1000 * 6.9 = 6900 rows,
times an absolute constant. A learner keeping all rows would need 1000.
The extra factor is the price of the state being small: information about
the residual sphere has to be paid for one block at a time, and each block
of k ~ d/16 rows can buy at most O(d) nats, so the number of blocks must
be at least the ratio of the total needed information to that per-block
amount, which is of order log(1/eps).
total information needed ~ d log(1/eps)
information per block ~ d
number of blocks >= log(1/eps) / c
rows >= k * blocks ~ d log(1/eps)
That is the whole argument, in four lines.