==============================================================================
POSTERIOR REPLICAS AND CONDITIONAL INFORMATION IN GAUSSIAN REGRESSION
a complete proof in plain language, with one quoted estimate
==============================================================================
Read this like a story. If a line looks technical, the sentence after it
says what it means.
One estimate is quoted rather than re-derived. It is the density comparison
for a general bounded prior, in Part 10.6. It is flagged where it occurs,
and again in Remark 5 of Part 12. Everything else in these twelve parts is
proved from the beginning.
CONTENTS
Part 0 the question and the answer
Part 1 the learner, written down exactly
Part 2 information: entropy, divergence, and four tools
Part 3 geometry of the sphere: caps, tubes, residual spheres
Part 4 the endpoint: an accurate state must hold many bits
Part 5 the clock: an early stop cannot beat the endpoint
Part 6 replicas: turning one message into many signals
Part 7 exact labels: the equal-label measure
Part 8 the replica likelihood
Part 9 everything is integrable
Part 10 the one-block bound
Part 11 assembling the stream
Part 12 the theorem
NOTATION, ONCE AND FOR ALL
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"
==============================================================================
PART 0. THE QUESTION AND THE ANSWER
==============================================================================
The signal is an unknown unit vector s in R^d. We never see it.
At step j = 1, 2, 3, ... nature draws a fresh random row
X_j ~ N(0, I_d)
and hands us the single exact real number
Y_j = <X_j, s>.
No noise. No rounding. One number per step.
If we could keep all the rows, d steps would be enough: the d rows almost
surely form an invertible matrix, and then s = A^{-1} Y exactly.
But the machine has a state with at most 2^M values, that is M bits. At
each step it may look at its state and at the new pair (X_j, Y_j), think
as long as it likes, and write a new state. It may stop. It must stop by
a pre-agreed step T. Then it outputs a unit vector s-hat, computed from
its final state and from fresh private randomness.
QUESTION. If M is far smaller than d^2, how large must T be so that
s-hat is within angle eps of s with probability at least 2/3, when s is
uniform on the sphere?
ANSWER, proved in Part 12.
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.
WHY THE ANSWER IS PLAUSIBLE. Give a friendly analyst one extra
projection of s, namely B s, where B is an independent random matrix with
about d/2 rows. The machine never gets B. If the machine's final state
still says a lot about s even after the analyst learns B s, then the state
must encode something about s that no d/2 dimensional shadow reveals.
Exact observations make that encoding expensive, and a machine with far
fewer than d^2 bits cannot afford it. This paper is a careful accounting
of that expense.
THE STRATEGY, IN ONE SENTENCE. Prove a bound for one block of fresh
rows, then add the per-block bounds along the stream.
==============================================================================
PART 1. THE LEARNER, WRITTEN DOWN EXACTLY
==============================================================================
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 THAT ARE USED LATER.
(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 is allowed, chosen once and independent of
everything. We condition on the seed and average at the end.
(4) We may replace a randomized rule 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 we 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 for us, at the cost of a few extra states used to
remember where it stopped.
SUCCESS CONDITION. 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.
A NOTE ON WORST CASE VERSUS AVERAGE. 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. We prove the average case, which is stronger.
==============================================================================
PART 2. INFORMATION
==============================================================================
The proof never looks inside the machine. It only counts bits. The
currency is information, measured in nats (natural-log units).
2.1 ENTROPY. 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.
THE PADDED STATE. Suppose the learner stops at some index tau in
{0,1,...,T} and we keep the pair (tau, state at tau). 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)
2.2 RELATIVE ENTROPY. 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.
2.3 MUTUAL INFORMATION. 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
our uncertainty about S.
2.4 FOUR TOOLS.
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.
2.5 A TWO-OUTCOME ESTIMATE. 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.
==============================================================================
PART 3. GEOMETRY OF THE SPHERE
==============================================================================
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.
3.1 CAPS ARE SMALL.
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 we may write the sphere
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.
3.2 TUBES AROUND AFFINE SUBSPACES ARE SMALL.
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.
3.3 CONDITIONING ON A PROJECTION LEAVES A SPHERE.
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), note that 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.
3.4 AN ACCURATE ANSWER INSIDE A FIBER NEEDS MANY BITS.
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 one we live in.
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.
==============================================================================
PART 4. THE ENDPOINT: AN ACCURATE STATE MUST HOLD MANY BITS
==============================================================================
Lemma 4 has a constant alpha, a radius r0 and a dimension b in it. We now
commit to one set of numbers, the ones the proof of the theorem uses, and
write the result 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). Here r = 2 eps/r0 = 4 eps, so 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 we have 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.
==============================================================================
PART 5. THE CLOCK: AN EARLY STOP CANNOT BEAT THE ENDPOINT
==============================================================================
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 "we 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 of Part 10 will apply with room to spare.
==============================================================================
PART 6. REPLICAS
==============================================================================
Everything so far was about one signal. Information bounds need many
signals at once, tied together by the same observations.
THE BLOCK EXPERIMENT. 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. We measure
information about S in W after the analyst has learned B S.
POSTERIOR REPLICAS. 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.)
TWO MEASURES OF DEPENDENCE. 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.
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'. Part 9 shows
that K is finite, so that (6.6) is meaningful; Part 10 bounds the loss of
correlation for the specific dimensions k = 2 floor(d/16), t = k+1,
ell = 4k.
==============================================================================
PART 7. EXACT LABELS: THE EQUAL-LABEL MEASURE
==============================================================================
This is the geometric heart. Exact labels mean that the several replicas
satisfy A S_1 = ... = A S_t exactly. We need the exact law of that event,
with its normalization, because a normalization error of even one power of
d would destroy the whole argument.
We work only with the spherical base. 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 Part 8.
7.1 THE PROJECTION AND THE FIBER.
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 PROJECTED DENSITY. 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| we get |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).
Here 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.
7.2 SIMPLEX HEIGHTS.
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, we have 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.
7.3 THE THEOREM.
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 in 7.1, and D_u, F_u, J as
in 7.2. 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)
Here 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.
READING (7.6). 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 next parts prove it, and Part 8 extracts the probability statement.
7.4 PROOF OF THEOREM 12: THE FIRST INTEGRAL ORDER.
We first prove (7.6) in the base case nu = sigma_d. The general nu = f
sigma_d then follows by multiplying both sides by a nonnegative function,
which is the last step of 7.6.
AN APPROXIMATE IDENTITY. The identity we want 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 we relax it to
"approximately equal" and then pass 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. Our
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.
THE FIRST ORDER. 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 at the end of 7.1: 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.
THE DOMINATION NEEDED FOR (7.8). 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.
7.5 PROOF OF THEOREM 12: THE SECOND INTEGRAL ORDER.
Now compute the same I_eta by fixing the tuple first.
FIX THE TUPLE. 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.
A CHANGE OF VARIABLES. 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.
THE LIMIT. 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.
EQUATING THE TWO LIMITS. The limit of a sequence of numbers does not
depend on how we compute it, 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.
7.6 PROOF OF THEOREM 12: FINITENESS, EXTENSION, AND THE PRIOR DENSITY.
Now that (7.12) is proved for bounded continuous tests, three steps
complete the theorem.
STEP 1: BOTH SIDES 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.)
STEP 2: MULTIPLY BY 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).
A CONVENTION FOR ZERO FIBRES. 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 we still owe). The identity (7.6) is a statement about finite
measures. To get a probability statement we must divide by p_A(y)^m, which
is legitimate only where p_A(y) > 0. Part 8 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.
==============================================================================
PART 8. THE REPLICA LIKELIHOOD
==============================================================================
8.1 DIVIDING BY p_A(y)^m, WITH TRUNCATIONS.
Theorem 12 is an identity of finite measures. To read it as a statement
about probabilities we must divide both sides by p_A(y)^m. That is legal
only where p_A(y) > 0, so we truncate and then let the truncation go.
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.
8.2 THE PROJECTED DENSITY IS POSITIVE AT THE ACTUAL LABEL.
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, we have 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, here is the same identity with every integral written out:
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 we were after: 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 replica law of 6.1. 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.
WHY (8.8) IS THE RIGHT SHAPE. The term -k E log J is the one we know how
to cancel: Part 10 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; Part 10's density comparison 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. We record this properly in Part 9, where all the
logarithms are shown to be integrable.
THE INTERPRETATION. 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.
==============================================================================
PART 9. THE LOGARITHMS ARE INTEGRABLE
==============================================================================
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 before using it we check that both terms behave.
The reason to check this now rather than later: Part 10 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
here, Part 10 can compute expectations freely.
9.1 TWO FACTS ABOUT ENTROPY AND SUPPORT.
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 the same computation as Edelman and Rao,
Section 5.
9.2 log J IS INTEGRABLE.
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)
9.3 log p_A(A Y) IS INTEGRABLE.
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.
9.4 THE WISHART DETERMINANT.
Part 10 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, we get 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.
9.5 SUMMARY.
Put the estimates 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 of Part 6 and the reference law R of Part 8:
(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.
A WORD OF WARNING ABOUT SIGNS. 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 Part 10 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.
==============================================================================
PART 10. THE ONE-BLOCK BOUND
==============================================================================
10.1 THE DIMENSIONS.
For the rest of the proof fix
k = 2 floor(d/16), m = k, t = m + 1, ell = 4k. (10.1)
For d >= 64 we have k >= 8 and k >= d/32. The hypotheses of Parts 6 to 9
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 from Part 6. 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.
THEOTARGET. 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.
10.2 THE OBSERVABLE MATRIX.
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.
10.3 THE TEST.
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.
TWO REWRITINGS. 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 is recorded here, 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.
10.4 THE VARIATIONAL STEP.
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 the logarithms here are integrable by Lemma 14 and by (9.11), (9.12),
so this is a legitimate inequality between real numbers.
10.5 THE EXACT CANCELLATION OF log J.
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 here was exact. Part 10.6 bounds Delta.
10.6 THE DENSITY COMPARISON.
We must bound Delta from (10.13). 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.
DELTA FOR THE UNIFORM BASE. 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)
COMPUTING THE DIFFERENCE. 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.
WHAT THE PRIOR DENSITY f CHANGES. With general 0 <= f <= L, entries of
the entropy acquire two extra terms, both fiber averages of f:
- int p_M log p^0_M gains - ((d-k-2)/2) ( W_M - W^0_M ),
- int p_M log h_M is G_M := E_{S ~ nu} [ - log h_M(M S) ],
with W_M = E_{S ~ nu}[ log |P_{ker M} S|^2 ] and G_M the expected negative
logarithm of the fiber average of f. So
Delta = (1/2)( E log det Sigma_A - E log det Sigma_{A_tilde} )
- ((d-k-2)/2)( W_A - W_{A_tilde} )
+ ( G_A - G_{A_tilde} ). (10.21)
Both extra differences compare the same functional at two matrices with
the same rank k whose kernels differ by containing the tuple plane F_u.
The first difference is O(k^2/d) by the same digamma estimate, because
|P_{ker M}S|^2 is close to (d-k)/d |S|^2 = (d-k)/d for both matrices and
the f-tilt affects both in the same way. The second difference is where
the prior bound L enters, and it enters only logarithmically twice: h_M
is a conditional average of f, so it is at most L, and the inequality
t log(1/t) <= 1/e for 0 < t <= 1 gives
E_{Y ~ p_M} [ - log h_M(Y) ] <= 1/e + log(2 + log L) . (10.22)
HONEST STATUS OF THIS STEP. Equation (10.20) is proved. Equation (10.22)
is proved. Passing between them, that is bounding (W_A - W_{A_tilde}) and
(G_A - G_{A_tilde}) simultaneously for a general bounded f, is the one
estimate in this writeup that we quote rather than re-derive. The original
argument performs it by a dyadic decomposition of the radii of ball
averages of p_A together with a weak maximal estimate. The conclusion,
which is what (10.3) needs, is
Delta <= C k + C log(2 + log L) . (10.23)
A reader who wants only the uniform prior, or any prior with a density
bounded above and below by constants, gets (10.23) with the logarithm
dropped, directly from (10.20). A reader who wants to reconstruct the
missing step should prove: for 0 <= f <= L with int f dsigma_d = 1, the
quantities W_M and G_M of (10.21) differ between two rank-k matrices M, M'
whose kernels both have dimension d-k by at most Ck^2/d + C log(2+log L).
10.7 THE BLOCK BOUND.
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 of Part 6, 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.
READING (10.26). 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 Part 11 average
over rare states without paying a large penalty.
==============================================================================
PART 11. ASSEMBLING THE STREAM
==============================================================================
We now put the blocks together. From this point on eps and T and M are
functions of d; we write eps, T, M for short, and
beta = log(1/eps), 0 < eps <= 1/10, beta >= 2. (11.1)
The learner is the one of Part 1: finite state, at most 2^M values, exact
labels, deterministic horizon T, and uniform-prior success at least 2/3.
11.1 REDUCING TO A DETERMINISTIC LEARNER.
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.
11.2 PADDING THE STREAM.
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.
11.3 THE BRANCH SPLIT.
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 we have 2/3). 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.
11.4 THE BLOCK STEP.
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 here, 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)
11.5 SUMMING OVER THE BLOCKS.
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.
11.6 THE MATCHING LOWER BOUND.
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 our
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)
where we used d - ell - 1 >= d/2 - 1 and log(1/(5eps)) >= 0.3 beta.
11.7 SOLVING FOR T.
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.
==============================================================================
PART 12. THE THEOREM
==============================================================================
12.1 THE STATEMENT.
This is Theorem 1 of the paper, and the only result this writeup sets out
to prove.
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.
12.2 THE PROOF.
Apply Part 11.1: 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 of Part 11, whose conclusion is exactly (12.1). That
is the whole proof.
12.3 WHAT EACH PART DID.
Part 2 set up entropy, relative entropy, mutual information, the
chain rule, data processing, and the variational bound.
Part 3 proved three geometric estimates: spherical caps are small,
tubes around affine subspaces are small, and conditioning on
a random Gaussian projection leaves the signal uniform on an
affine sphere of random radius.
Part 4 deduced the endpoint: a state that identifies S to accuracy
eps while the analyst knows an independent projection B S of
rank b <= d/2 must contain at least ~(1/2)(d-b-1)log(1/eps)
nats about S.
Part 5 showed that stopping early cannot help: a learner that stops
by d log(1/eps) has at most o(d^2) bits and must have
log(1/eps) = o(d).
Part 6 introduced posterior replicas and proved the replica
information inequality: t times the desired information is at
most the message entropy plus the loss of correlation caused
by the projection B.
Part 7 proved the equal-label finite measure identity, which is the
exact exchange rate between drawing labels first and drawing
signals first.
Part 8 divided that identity by p_A(y)^m to get the replica
likelihood, and derived the resulting bound on the total
correlation K.
Part 9 checked that every logarithm in sight has a finite
expectation, so the algebra in Parts 10 and 11 is legitimate.
Part 10 built an observable test from the projected replicas, whose
logarithm contains +k log J. That term cancels the -k log J
in the correlation bound exactly. What survives is bounded by
O(d) per block.
Part 11 divided the stream into blocks of k rows, applied Part 10 to
each block against the conditional prior given the history,
summed, and matched the result against the endpoint of Part 4.
12.4 REMARKS.
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. Nothing here is 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 here 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 this writeup does not address that regime.
REMARK 5 (what is quoted). Part 10.6 proves the density comparison for
the uniform prior, and for priors bounded above and below by constants,
with no quoted estimate: the bound (10.20) is Delta <= Ck. For a general
bounded prior density the same step produces two fiber averages of the
prior, and bounding their difference by Ck + C log(2 + log L) is the one
estimate taken from the original argument rather than re-derived here.
Everything else in these twelve parts is proved from the beginning.
REMARK 6 (what a reader should be able to redo). The two computations
really worth doing by hand 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
identity of Part 7 turns into a probability statement.
12.5 THE SHAPE OF THE ANSWER.
Put numbers in (12.1). To reach accuracy eps = 10^{-3} in dimension
d = 1000 with a state of, say, 10^5 bits, which is 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.
END OF THE PROOF.