==============================================================================
POSTERIOR REPLICAS AND CONDITIONAL INFORMATION IN GAUSSIAN REGRESSION
a complete proof in plain language
==============================================================================
Read this like a story. Every claim is proved here. Nothing is quoted.
If a line looks technical, the sentence after it says what it means.
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.