Posterior replicas and conditional information in Gaussian regression

Proof. For r\le1, rotate z to the north pole. A point in the chordal ball has last coordinate at least 1-r^2/2\ge1/2. As a graph over its first q-1 coordinates, the surface has area element at most twice Lebesgue measure, and its projection lies in the (q-1)-ball of radius r. The whole sphere has area at least twice the volume of the unit (q-1)-ball, by projecting both hemispheres. This proves (2). For r>1, total mass one suffices. Angular distance at most \epsilon implies chordal distance 2\sin(\epsilon/2)\le\epsilon, proving the last assertion.□

Proof. The zero-row case is immediate: conditioning on empty data changes nothing, and the residual radius is one. It does not involve a beta law with a zero shape parameter.

Suppose b\ge1. The matrix is full row rank almost surely in the Gaussian case and by definition in the Haar case. For fixed G, write S=Z/\norm Z with Z standard Gaussian and split Z into the row space of G and its kernel. The squared lengths are independent chi-squares with b and d-b degrees of freedom. Their normalized ratio gives (3); the direction in the kernel is independent and uniform. Given the projection, its row-space component is fixed, so the remaining signal is uniform on the asserted affine sphere. Its radius has

These formulas also hold for the deterministic zero-row radius. Markov’s inequality applied to 1-R^2, whose mean is b/d, proves (4). If b\le d/2, the mean of R^2 is at least 1/2 and its variance is at most 1/(2(d+2)). Chebyshev’s inequality at distance 1/4 from the mean gives the first bound in (5).

For the second bound, still with b\le d/2, let Z_{\ker} be the kernel component of Z. Its squared norm has mean d-b\ge d/2 and variance at most 2d, while \norm Z^2 has mean d and variance 2d. Chebyshev gives

Outside these events R^2\ge1/4. Their union gives 90/d. For b=0 the probability is zero, as already established.□

Proof. Put Z=(G,GS). Compare the true law of (S,V,Z) with P_ZP_{S\mid Z}P_{V\mid Z}, and in both laws generate \widehat S using the same kernel from V. Adding that kernel preserves the divergence, which is I(S;V\mid Z).

Fix side data with residual radius R\ge r_0 and fix an output. If the set of successful points on the fiber is nonempty, choose one such point. Angular success implies Euclidean distance at most \epsilon from the output, so any two successful fiber points are at Euclidean distance at most 2\epsilon. After translating and rescaling the fiber to its unit sphere, the successful set therefore lies in a chordal ball of radius 2\epsilon/R\le2\epsilon/r_0<1 centered on that sphere. By Lemma 2.2, its conditional mass is at most (2\epsilon/r_0)^{d-b-1}. Under the comparison law, the output and signal are conditionally independent given Z, so the event of success and R\ge r_0 has probability at most this quantity. Under the true law it has probability at least \alpha.

For Bernoulli probabilities a,c, relative entropy obeys

this follows by dropping the nonnegative term (1-a)\log(1/(1-c)) and using binary entropy at most \log2. Apply data processing to the event just described. If the comparison probability is zero the conclusion is immediate; otherwise its upper bound and the true lower bound give (6).□

Proof. Use r_0=1/2. In (i), the failure probability is at most 8/(d+2), so the true event has mass at least 1/2 for large d. The angular cap bound is (5\epsilon)^{d-b-1}, which gives the displayed version of the binary entropy calculation. In (ii), Markov’s estimate leaves event mass at least 1/3, and the chordal cap is (4\epsilon)^{d-b-1}. In (iii), the stated 90/d estimate leaves mass at least 1/2. The last assertion follows from d-b-1\ge d/2-1 and

The positive multiple of d\log(1/\epsilon) absorbs \log2 eventually.□

Proof. For each state and index combine the next-state and stopping alternatives into a finite destination set. Choose a Borel version of every coordinate of this finite probability vector. Such versions exist for completed- measurable real functions: approximate by simple functions and replace their countably many level sets by Borel sets modulo null sets. On the Borel null set where the resulting vector is negative in a coordinate or fails to sum to one, replace it by a fixed point mass. The finite union over all states and indices is contained in one Borel \lambda-null set N.

For a nonzero fixed x, the scalar \langle x,S\rangle has a Lebesgue density when S\sim\sigma_d and d\ge2. Rotation and the one-coordinate spherical law show this directly. The event x=0 is Gaussian-null. Consequently each pre-generated sample pair (X_j,\langle X_j,S\rangle) has law absolutely continuous with respect to \lambda, and it avoids N almost surely. This remains true on the event that any particular state is reached, because that event intersected with the pair lying in N is contained in the marginal null event. The finite union over sample indices is still null. Coupling each original finite kernel and its Borel version by the same fresh uniform random variable now makes their state paths and stopping decisions agree by induction. Their output laws agree at the identical terminal pair.□

Proof. The original jointly measurable law gives a measurable conditional success function of the shared seed whose average is the original success. Work on a common full-measure set of seed values where the conditional law is the stated fixed-seed experiment and the conditional initialization remains independent of the signal and rows. The latter property follows from the joint independence of the initial state and shared seed from the signal and all rows. Some seed in this set has conditional success at least p: otherwise the strictly positive difference between p and that conditional success would have a positive integral. Apply Lemma 2.6 to this one fixed-seed experiment. Its uniform-prior success is unchanged. This step does not require a jointly measurable choice of Borel replacements across seeds.

In the resulting fixed-seed Borel experiment, for a finite destination kernel use an independent uniform variable and the cumulative coordinate probabilities to choose the destination. There are only finitely many state/index rules; unused choices can be generated in advance as well. Similarly pre-generate, for each terminal state/index, an output with its prescribed distribution, independently of the data. Together with the conditional initial state, these variables are jointly independent of the signal and samples. Conditional on their realization, the initialization and rules are deterministic and state based. The finite Borel construction is jointly measurable, and averaging its success gives that of the selected fixed-seed experiment. Some realization therefore has success at least p'<p.

At a layer the active state set has at most 2^M values. Each earlier stopping index contributes a disjoint frozen copy of a state set of that size, and there are at most T+1 stopping indices, including zero. The stated count follows. The frozen pair retains exactly the information allowed to determine the postponed output, and ignored fresh samples add no information to it.□

Proof. Bayes’ formula gives the Borel density

Averaging \log L_h gives (11). In particular, H may be one padded state or a history of padded states; these have different entropy costs.□

Proof. First fix a shared seed in the original conditional experiment. There are at most (T+1)2^M terminal state/index pairs. For a fixed pair, write \nu_{j,v} for its prescribed output law and r_{j,v}(s) for the conditional probability of reaching it given S=s. Its contribution to success is

because r_{j,v}\le1 and each angular cap has mass at most \epsilon^{d-1} by Lemma 2.2. Summing gives (12) for its conditional success. The same numerical bound holds for almost every seed, so averaging the original conditional success probabilities gives the stated bound for the jointly measurable mixture.

On T\le d\beta, the inequalities \beta\ge\log10 and T+1\le2d e^\beta imply

Dividing by d proves \beta=o(d) for a subquadratic memory sequence. The branch then gives T=o(d^2), and (10) gives h_T=o(d^2).□

Proof. For d\le2, both numerical bounds exceed one. We may therefore assume d\ge3, when b\le\lfloor d/2\rfloor\le d-2. Condition on all the data. The estimator and the signal are then conditionally independent, and the conditional signal is the residual sphere in Lemma 2.3. On radius at least 1/2, the successful points have relative chordal cap mass at most (4\epsilon)^{d-b-1}, by the argument in Lemma 2.4. Add the corresponding failure probability from (5). The zero-row case uses the deterministic radius one.

If a learner stops by T\le\lfloor d/2\rfloor, grant it all of the first \lfloor d/2\rfloor rows and labels, including unused ones. Its output is a kernel of those data and independent randomness. The displayed bound tends to zero uniformly for \epsilon\le1/10, contradicting success 3/5. This proves the last assertion. The angular-cap version used in the first replica route follows as well by replacing 4\epsilon by the weaker 5\epsilon.□

Proof. Let K_W be the average total correlation conditional on W, computed relative to the product of the conditional one-coordinate marginals. Decomposing the relative entropy of (S_1,\ldots,S_t,W) from p^{\otimes t}\otimes Q_W in the two orders gives

The relative entropy being decomposed is at most K+H(W), so every nonnegative chain-rule term in this display is finite. Define K'_W in the same way after projection, conditionally on (B,W). The corresponding identity after projection is

Coordinatewise data processing gives K'\le K and K'_W\le K_W. Independence of B and the fact that \phi_B(S) is determined by (B,S) also give

Subtracting (17) from (16) therefore gives the exact identity

The conditional tuple-information is at most H(W), and K_W-K'_W\ge0. This proves the inequality. The remaining assertion is nonnegativity of relative entropy.□

Proof. Split a standard Gaussian vector into the row space and kernel of A. Its squared lengths in those spaces are independent chi-squares with k and d-k degrees of freedom. After dividing by the total length, their ratio has the beta density. Polar integration in orthonormal row coordinates gives (21); changing those coordinates to y supplies the determinant factor. The remaining direction is independent and uniform in the kernel. This is the spherical beta projection law, discussed geometrically by Frankl and Maehara [9]. Without normalization, orthogonal Gaussian independence gives the Gaussian assertion. For measurability, generate the kernel component by projecting an extra independent Gaussian with the Borel matrix I-A^\dagger A, and normalize its length in the spherical case. Assign fixed values on rank failures and on the null event of a zero projected Gaussian.

For the inverse moment, first note that an affine j-plane V satisfies

Indeed, cover the part of V within distance one of the unit sphere by at most (C/r)^j balls of radius r. Each nonempty intersection with the sphere is contained in a radius-4r ball centered on the sphere. The spherical ball bound in Lemma 2.2, with the trivial bound one when necessary, proves (23). For a standard Gaussian point, its projection onto the orthogonal complement of the direction space of V has a translated standard Gaussian density. The density is bounded uniformly over the translation, so the analogous estimate is C^d r^{d-j}.

Gram–Schmidt gives

The predecessor affine span has dimension at most i-2. Thus the smallest spherical small-distance exponent in (23) is d-1-(t-2)=d-m>k. Integrating its tail bounds the inverse kth moment of each distance uniformly in the preceding points: for a nonnegative distance X,

Integrate the last point first and repeat. This proves the finite product moment and, since every lower-dimensional affine span has zero base mass, full affine rank almost surely. The Gaussian exponents are larger. Replacing k by k+1 gives the last assertion under k+m\le d-3.□

Proof. We first take \nu=P^0. Let \varphi_\eta be either the uniform density on the radius-\eta k-ball or the density of N(0,\eta^2 I_k). For a continuous compactly supported test G(\mathbf u,A) whose matrix support lies in the open full-row-rank set, integrate

against (P^0)^{\otimes t}(d\mathbf u)\gamma_{k,d}(dA).

Fix A first and disintegrate each point by its projected label. Given the first label y, the other labels approach y under either probability approximate identity. The base density is continuous in the interior of its support, and the conditional fiber law varies weakly continuously there. The spherical boundary has zero projected probability. Thus the integral converges to

To justify the passage, condition first also on u_1. The absolute value of the remaining integral is at most \norm G_\infty(\sup p_A^0)^m. The density suprema are uniformly bounded on the compact matrix support: this follows from (21), whose exponent is nonnegative, and from the Gaussian density formula. The bound is global in all the other labels, including labels near or outside the spherical support, because each \varphi_\eta is a probability density. Dominated convergence applies for both kernels.

In the other order, fix a tuple of full affine rank. Each row of AD_{\mathbf u} is Gaussian with covariance D_{\mathbf u}^{\mathsf T}D_{\mathbf u}. Its joint density has maximum at zero, with value

Conditional on AD_{\mathbf u}=Z, the matrix A is a draw from \gamma_{k,d}^{F_{\mathbf u}} plus Z(D_{\mathbf u}^{\mathsf T}D_{\mathbf u})^{-1}D_{\mathbf u}^{\mathsf T}. This translation tends to zero with Z. The integral in (27), conditioned on the tuple, therefore converges to

For either kernel its absolute value is at most \norm G_\infty w_{k,m}(\mathbf u). Indeed, the joint density of the whole matrix Z=AD_{\mathbf u} is bounded by w_{k,m}, while \prod_{i=2}^t\varphi_\eta(Z_{:,i-1}) has Lebesgue integral one on \R^{k\times m}. This argument does not require the columns of Z to be independent. The bound is integrable by Lemma 3.2. Dominated convergence gives the second integration order and equates these two limits.

For clarity, the left measure is locally finite on the open full-row-rank matrix set before we identify it. If a compact set in that space has matrix projection K_A, its left mass is at most

because \int p_A^0(y)\,dy=1. Thus both sides are locally finite Borel measures on this locally compact second-countable space; the right one is globally finite by (22). Continuous compactly supported tests identify them on that open set. Exhausting it shows that the left total mass there equals the finite right total mass. The right measure gives no mass to remaining matrices: its rows live in a space of dimension d-m\ge k+2. The left measure also has no such mass because \gamma_{k,d} is full rank almost surely. Equality therefore extends to all nonnegative Borel tests. The right measure is supported on full affine rank by Lemma 3.2, so the same holds on the left. In the spherical case its label is in the open ellipsoid, and its fiber radius is positive. Equivalently, a boundary fiber could contain only one unit vector and hence could not contain a full-affine- rank tuple with t\ge2.

Now multiply the base equality by \prod_{i=1}^t f(u_i). The formula (24) converts the fiber side to p_A(y)^t\nu_{A,y}^{\otimes t}; the other side becomes w_{k,m}\nu^{\otimes t}\gamma_{k,d}^{F_{\mathbf u}}. On a fiber with h_A(y)=0, the measure fP^0_{A,y} is zero, so both expressions on the fiber side are zero regardless of the unused conditional probability. This conversion never divides on a zero fiber. Boundedness of f preserves finiteness. Inserting a test H(A,Au_1,\mathbf u) gives (25), since both sides are supported on equal labels. No normalization by \nu(\R^d) has been made. In particular, the two equal-label limit calculations were made only for the base law; no continuity of f or of the reweighted fiber kernel is used in them.

It remains to justify density evaluation on that constraint. For either choice of \varphi, set

The integral and lower limit are jointly measurable. Lebesgue differentiation for the ball and Gaussian approximate identities makes each version agree with (24) at almost every y for each full-rank A. On the left of (25), the common label has a measure with Lebesgue density p_A(y)^t and hence avoids the null sets where the versions disagree or are not finite and positive. Equality of the undivided finite measures transfers this fact to the right. There the weight w_{k,m} is finite and strictly positive at full affine rank. The reference R has finite mass \nu(\R^d)^t and full affine rank almost everywhere, because \nu^{\otimes t}\ll(P^0)^{\otimes t}. Restricting successively to \{1/j\le w_{k,m}\le j\} therefore transfers the same null statement to the unweighted reference (26). The labels where p_A=0 have zero left mass because their weight is p_A^t, so this argument does not divide on them. If \nu=0, both finite measures and R are zero. The only additional limiting assertion for a possibly discontinuous f is the ordinary almost-everywhere differentiation of its projected L^1 density used in this paragraph. This proves the claimed versions before any division by a projection density.□

Proof. Multiply the equal finite measures by p_A(Au_1)^{-m} on their common finite positive set, first with bounded truncations and then by monotone convergence. The exponent t=m+1 on the left becomes one, so that side is exactly the probability experiment defining Q. The right side is the displayed density relative to R. Marginalization gives the last assertion.□

Proof. Write u_A for the uniform-sphere projection density. Since p_A\le Lu_A, (21) bounds the positive logarithm of p_A(Y) by a constant depending on d,k,L plus \tfrac12|\log\det(AA^{\mathsf T})|. Gaussian row Gram–Schmidt expresses that determinant as a product of independent chi-squares with degrees d,d-1,\ldots,d-k+1. Their absolute logarithms are integrable, directly from their densities at zero and infinity. For the negative part, the support of p_A lies in the ball of radius \norm A_{\op} and -z\log z\le1/e for 0<z\le1. The expected volume of that ball is finite because a finite Gaussian matrix has all positive norm moments.

For a simplex height, condition on (A,Y) and let \rho be the fiber radius. Set q=d-k. After translating and rescaling to the unit sphere in \ker A, the posterior has density at most

For a_i=\dist(S_i,\aff(S_1,\ldots,S_{i-1})), the tube estimate (23), also conditional on the predecessors, gives

The exponent is positive. With \log^-x=\max\{0,-\log x\}, tail integration yields

Moreover the bounded density ratio makes its relative entropy finite and

For completeness, the negative part of the density-ratio logarithm is integrable because -z\log z\le1/e against the probability density u_A; the positive part is at most \log L.

Each pair (A,S_i) has the original independent matrix–signal law. For every fixed unit signal, rotational invariance of A makes \rho^2 a beta variable with parameters (d-k)/2,k/2, whose logarithm is integrable. Thus \E[-\log\rho]<\infty. Each unscaled height is at most two, so its positive logarithm is bounded. Summing its two logarithmic parts over the Gram–Schmidt product proves absolute integrability of \log J. We may now integrate the logarithm of (28); this is the finite divergence \KL(Q\Vert R). Forgetting A sends R to p^{\otimes t}, so data processing proves (29).□

Proof. For a fixed full-rank tuple write D=ET, where the columns of E form an orthonormal basis of F and T is invertible. Then G=BE is standard Gaussian and

The action of B on F^\perp is independent of G. Conditional on G and the tuple, C_0 is fixed with orthonormal rows and C_0BE=0. Thus \widetilde A=C_0B has law \gamma_{k,d}^{F}, independently of G given the tuple. Since B is independent of the replica experiment, this remains its law after conditioning also on the original A. The test is observable from (B,U_1,\ldots,U_t): C_0, C_0B, and its evaluated label C_0U_1 are all determined there. The common density versions of Theorem 3.3 make the last factor measurable, finite, and positive almost surely under the independent-tuple reference. The replica tuple is absolutely continuous with respect to that reference’s tuple marginal, so the same assertion holds for replicas.

Under the independent-signal reference law, integrate the factor \det(G^{\mathsf T}G)^{-k/2} first. It contributes Z_{k,m}. The remaining expectation is

by Corollary 3.4. This proves the normalization of (32).

Here are the needed Gaussian determinant bounds. Gram–Schmidt expresses \det(G^{\mathsf T}G) as a product of independent chi-squares with degrees \nu=\ell,\ell-1,\ldots,\ell-m+1; this standard Gaussian reduction is also described by Edelman and Rao [7, Section 5]. The smallest degree is 3k+1>k. Since k is even, direct integration of the chi-square density gives

In particular Z_{k,m}<\infty. The same densities give absolute logarithmic integrability, and Jensen gives \E\log\det(G^{\mathsf T}G)\le m\log\ell. Consequently

Before taking logarithms of the test, we control the positive logarithm of its projection density. For a fixed tuple put

The ball-average density version in Theorem 3.3 holds at \widetilde A S_1 under the independent-tuple reference and hence under the replica law. The coordinates of \widetilde A(s'-S_1) are independent centered Gaussians with variance \delta(s')^2. A ball has probability at most its volume times the maximum Gaussian density. Apply this bound to the ball averages and then use Fatou’s lemma:

Here and below such conditional estimates hold for almost every tuple. The affine space S_1+F has dimension m, so (23) gives

Since d-1-m>k, tail integration bounds the inverse moment uniformly over tuples for fixed d,L. Thus \log^+p_{\widetilde A}(\widetilde A S_1) is integrable.

The projected law has divergence K'\le K<\infty from the independent-signal reference. Normalization of the test and (19) imply that (\log\Lambda)^+ is integrable. Its defining identity is

The negative part of this expression is bounded by a constant and the positive logarithms of J, the Gaussian determinant, and the last density. Those are integrable by Lemma 3.6, the chi-square calculation, and (35). Thus \log\Lambda is absolutely integrable. Solving (36) for the last logarithm proves its absolute integrability as well.

We may now apply the entropy test (18) to obtain K'\ge\E\log\Lambda. Subtract this bound from (31). Equation (36) displays the exact cancellation of -k\E\log J, and (34) bounds the remaining determinant terms by Ckm. This gives (33).□

Proof. Fix the tuple and its actual (A,Y), and again write \delta(s')=\norm{P_{F^\perp}(s'-S_1)}. Conditional on these data, \widetilde A has law \gamma_{k,d}^{F}. We refine the inverse-moment bound (35) by using A. Choose the deterministic integer

with a sufficiently large absolute C_1. The denominator is bounded below by a positive absolute multiple of d. The contribution of \delta\le2^{-J_0} to the inverse moment, including the Gaussian constant, is at most

For the remaining distances use the bins \delta\in(r/2,r], where r=2,1,\ldots,2^{-J_0+1}. These cover the remaining values because \delta(s')\le\norm{s'-S_1}\le2. Since A annihilates F,

Let v_k be the unit k-ball volume, and let \overline p_A^{\,a}(y) be the average of p_A over the radius-a ball centered at y. The contribution of one bin is at most

Integrating e^{-\norm z^2/2} on the radius-\sqrt{k} ball gives v_k\le(2\pi e/k)^{k/2}. Hence

The right side depends on the tuple only through (A,Y).

Divide by the finite positive density p_A(Y) and apply Jensen first to \widetilde A; all logarithms are integrable by Lemma 4.1. Only after obtaining (39) do we average over Y given A. Its law is then the original p_A(y)\,dy, and for every radius fixed by A,

The first inequality integrates an averaged probability density over \{p_A>0\}, and the second is the volume of that set, contained in the radius-\norm A_{\op} ball. A second application of Jensen thus bounds the expected log ratio by

This order of averaging is essential: before the tuple has disappeared, its conditional label need not have density p_A under further conditioning.

For completeness, choose 1/4-nets of the unit spheres in \R^d and \R^k, with at most 9^d and 9^k points. The operator norm is at most twice the maximum absolute Gaussian bilinear form on these nets. The expected maximum of N absolute standard normals is at most \sqrt{2\log(2N)}, by the exponential-moment bound; their independence is not required. Thus \E\norm A_{\op}\le C\sqrt d. Since k is a fixed positive fraction of d, Jensen bounds the first term of (40) by Ck. The cutoff (38) gives \log(J_0+2)\le C\log(2+\log L), proving the lemma.□

Proof of Theorem 1.1. Generate W conditionally on (A,Y) independently of the replicas. Each pair (S_i,W) has the original pair law, and the side matrix B is independent of the whole construction. Lemma 3.1, followed by Lemmas 4.1 and 4.2, gives

Here the representative signal is coupled independently with B, exactly as in the original block experiment. Since t=m+1 and k is proportional to d, division by t proves (1).□

Proof. We first record a uniform-sphere distance estimate. Let U be uniform on S^{n-1} with n\le d, and let E be a linear subspace of dimension j whose codimension h=n-j is at least d/2. Write a normalized Gaussian representation with independent components X\in\R^h and Z\in\R^j. For t\ge\log2,

The Gaussian density bound and the unit-ball volume estimate give \Prob\{\norm X\le a\}\le(Ca/\sqrt h)^h. Also

Since j\le d\le2h, these inequalities yield \E\norm Z^h\le(C\sqrt h)^h. Hence

If the law of U is reweighted by a density at most e^a, the right side is multiplied by e^a and capped by one. Integrating the logarithmic tail gives

The case j=0 is immediate and also satisfies this bound.

Condition now on (A,Y,S_1,\ldots,S_{i-1}). Let r and s_0 be the radius and center of the posterior fiber, and write u_j=(S_j-s_0)/r. The vectors lie on the unit sphere in \ker A, of ambient dimension n=d-k, and the next vector has density at most e^{b_{A,Y}} there. Moreover

The latter span has dimension at most i-1 and codimension at least d-k-q+1\ge d/2. Apply (45) and then (43). The additional contribution \E[-\log r] is bounded by an absolute constant: for each fixed signal, rotational invariance of the independent row space of A makes r a uniform-vector distance to a k-dimensional linear space, so (45) applies with a=0. This proves the negative-log bound. A zero height would make that expectation infinite, so heights are positive almost surely. The bound \rho_i\le2 follows because all signals are on the unit sphere.□

Proof of Theorem 5.1. Generate W from the shared data independently of the replicas conditional on (A,Y). Each replica has the original signal–message pair law, and B is independent of this coupling. The finite correlation bound (47) therefore permits Lemma 3.1 with t=q:

Subtract (57) from (47). The measurement entropy and all height logarithms cancel. Since k\le d/16, division by q gives (42). Section 6 applies this bound while conditioning only on the current state and retaining its separate late elimination of the clock cost.□

Proof. Use the first step of Lemma 2.7 to choose a fixed shared-seed conditional experiment with success at least 3/5 and then take its Borel replacement. Its initialization is independent of the signal and all rows; fresh transition and output randomness remains in the kernels. This selection uses the original jointly measurable experiment and does not require a jointly measurable family of Borel replacements.

Put \beta=\log(1/\epsilon). If T>d\beta, the conclusion is immediate. On the remaining branch, Lemmas 2.7 and 2.9 give padded states of entropy at most

Let

Append ignored fresh samples so that the padded stream has n complete blocks. Let V_i be the padded state at the end of block i, with V_0 the data-independent initial padded state. The latter includes a possible stopping decision at index zero. Draw a single standard Gaussian \ell\times d matrix B independently of the entire selected learner experiment and all appended rows, and put Z=BS.

Consider a positive-probability value V_i=v, and put p_v=\Prob\{V_i=v\}. By Lemma 2.8, its conditional signal law has a Borel density f_v satisfying

The next block matrix is independent of the pair (S,V_i): the state uses only the signal, completed rows, and learner randomness, and the new rows are fresh. Given v, the next state is a finite kernel of the new matrix A and its exact label AS. The side matrix B remains independent of this entire conditional signal, block, and message experiment. Therefore Theorem 1.1 applies with L=L_v and with message V_{i+1}.

Apply that numerical bound at each v before averaging. Concavity of x\mapsto\log(2+x) and the entropy bound give

All conditional uses have bounded priors and finite conditional replica correlation, as established in the block theorem. Since t\asymp d and h_T=o(d^2), the last line is at most C_1d for all sufficiently large d, with one absolute C_1.

Write \mathcal I(V)=I(S;V\mid B,Z). The chain rule and data processing give

Here \mathcal I(V_0)=0 by the independence of initialization and the index-zero decision from (S,B,Z). Iterating (59) yields

The side row count satisfies \ell=8\lfloor d/16\rfloor\le d/2. The postponed output is a kernel of V_n with fresh randomness, so (7) gives

for large d. Lemma 2.10 also gives T>\lfloor d/2\rfloor. In particular T>0, and for d\ge32 the inequality k\ge d/16 gives the explicit clock comparison

Combining this with (60) and (61) proves the proposition.□

Proof. Apply Lemma 2.7 with p=2/3 and p'=3/5. It first fixes a shared seed using the original jointly measurable experiment, then chooses Borel versions in that conditional experiment and fixes its independent initialization and remaining fresh randomness. We obtain deterministic Borel state-based rules and an output with uniform-prior success at least 3/5. Pad stopping and postpone this output. The final output is a function of the final tagged state.

For this route keep the convenient clock bound

Indeed, the exact count in Lemma 2.7 is (T+2)2^M, so the entropy of every padded state is at most h_T\le\mathfrak m_T. Use

and append ignored fresh rows through the last block. Let V_0,\ldots,V_n be the block-end states, starting with the data-independent tagged initial state. Independently of the entire deterministic learner experiment and all rows, draw one p\times d standard Gaussian matrix B. It is used only for analysis. Put Z=BS and \mathcal D(V)=I(S;V\mid B,Z).

For a block from V to W, condition on a value v with probability p_v>0. By Lemma 2.8, the conditional signal density is bounded by \exp(b_v), where b_v=\log(1/p_v). The next standard Gaussian matrix A is independent of (S,V), the ending state is a function of (v,A,AS), and B remains independent of the entire conditional experiment. Apply Theorem 5.1 at this fixed v and then average. Since \sum_vp_vb_v=H(V),

The last inequality uses q\ge d/16 for large d. In this calculation the prior cost b_v/d is averaged linearly; no entire state history is retained. The chain rule gives \mathcal D(W)-\mathcal D(V)\le I(S;W\mid V,B,Z), and \mathcal D(V_0)=0. Consequently

For the exact side row count p=\lfloor d/2\rfloor, the independent residual-sphere endpoint (9) gives

for sufficiently large d. This is the direct 90/d radius estimate and the event of mass at least 1/2 used in the distance-bin route. The corresponding raw-data bound in Lemma 2.10 also yields T>\lfloor d/2\rfloor, equivalently T>d/2 for integer T. The zero-row experiment in that lemma has residual radius one.

If T\ge d\beta, the asserted lower bound is immediate. Otherwise \mathcal D(V_n)\le H(V_n)\le\mathfrak m_T and (65) give the route’s clock inequality

Since d\beta+3\le(d+3)(\beta+1) and \log(1+\beta)\le\beta, this implies, for large d,

Thus T<d\beta=o(d^2) and \mathfrak m_T=o(d^2). The right side of (64) is consequently at most C_3nd. For d\ge32, k\ge d/32, and T>d/2 gives

Comparing the resulting upper bound \mathcal D(V_n)\le C_4T with (65) proves the proposition.□

Proof of Theorem 1.2. Its uniform-prior success 2/3 is at least the 3/5 required by Proposition 6.1, which proves the theorem. Proposition 6.2 gives a second proof using the linear entropy cost. The later sections give three further proofs: the Haar current-state argument in Proposition 7.7, and the synthetic and incidence full-history arguments in Proposition 8.4 and Theorem 9.9. Each uses the same learner model, while retaining its own side law, conditional experiment, and clock estimate.□

Proof. We first take P=\sigma. Fix s_0,\ldots,s_{i-1} with \dim D_{i-1}=i-1, and put H=D_{i-1}^\perp, so \dim H=n_i=d-i+1. For a bounded continuous function \varphi(A,s), consider

We compute its limit as t\downarrow0 in both orders of integration.

Fix A first. Disintegration of \sigma under s\mapsto As rewrites the inner integral as the average over the ball of radius t about As_0 of

This function is continuous in the open unit ball. Indeed, use the fiber representation following (72) with a common uniform direction and apply bounded convergence. Because d>k+2, the factor p^0 tends to zero at the boundary, so the product extends continuously by zero to \mathbb R^k. The average therefore tends to

Its absolute value, and that of every preceding average, is at most \lVert\varphi\rVert_\infty\alpha_{d,k}. Dominated convergence thus permits the frame integration as well.

For the other order, fix s and put \delta=\lVert\operatorname{proj}_H(s-s_0)\rVert. When \delta>0, the vector A(s-s_0) under \mathrm dA_{D_{i-1}} has density

This is (70) in the current ambient space H, not in the original d-dimensional space. Since n_i>k+2, the density is bounded by its value \alpha_{n_i,k}\delta^{-k} at zero.

The conditional frame law also has a concrete limit. Put e=\operatorname{proj}_H(s-s_0)/\delta and w=z/\delta. If C is a Haar k-frame in H\cap e^\perp, then the conditional law of A given A(s-s_0)=z, for \lVert w\rVert<1, is the law of

Its rows are orthonormal and Ae=w. Invariance under rotations fixing e identifies the remaining factor as Haar; conversely the displayed formula describes every such frame. The formula is continuous at w=0. At zero the frame law is \mathrm dA_{D_i}, since H\cap e^\perp=D_i^\perp. It follows that the frame integral in (74) tends, for this s, to

The bound \lVert\varphi\rVert_\infty\alpha_{n_i,k}\delta^{-k} dominates the frame averages for every t. It is integrable in s. Choose a (k+1)-dimensional subspace L\subset(D_{i-1}+\operatorname{span}\{s_0\})^\perp; the available dimension is at least d-i\ge d-r>k+1. Then \delta\ge\lVert\operatorname{proj}_L s\rVert. The latter vector has a bounded density by (70), because d>k+3. In k+1 dimensions its inverse kth power is integrable at zero: the radial integral is a constant times \int_0^1 u^k u^{-k}\,\mathrm du<\infty. This also shows that \delta>0 for \sigma-almost every s. Dominated convergence proves the second limit after integration in s.

Equating the two integrated limits in (75) and (78) gives the insertion identity. Bounded continuous functions determine finite Borel measures on the compact frame–sphere space, so the identity also holds for bounded Borel tests. The frame and fiber constructions above make the kernels measurable in the preceding tuple, allowing successive integration.

Start with \sigma(\mathrm ds_0)\mathrm dA and insert, for i=1,\ldots,r, the kernels p^0(As_0)U_{A,As_0}(\mathrm ds_i). Each insertion changes the frame law from \mathrm dA_{D_{i-1}} to \mathrm dA_{D_i} and contributes \alpha_{d-i+1,k}\delta_i^{-k}. On the original side, disintegration of s_0 contributes one more factor p^0(y), so its total power is r+1=m. These measures are finite at every step because p^0\le\alpha_{d,k}; in particular their final mass is \int p^0(y)^m\,\mathrm dy\le\alpha_{d,k}^{m-1}. The preceding almost-sure positivity of every inserted height gives the full-rank support. This proves (73) for \sigma.

Finally multiply this equality of measures by the bounded Borel function \prod_{i=0}^r g(s_i). Formula (72) changes the left side into the stated measure for P, while the right side becomes the product of P measures in (73). The bounded tilt preserves finiteness. No continuity of g or of p_A was used.□

Proof. The positive part of \log p_A under p_A is bounded uniformly in A by \log^+(K\alpha_{d,k}). Its negative part is also integrable uniformly: the density is supported in a ball of finite volume, and -x\log x\le1/e for 0<x\le1. Comparison with uniform probability on the unit ball now gives

To control a height, condition on (A,Y,S_0,\ldots,S_{i-1}). Put h=\sqrt{1-\lVert Y\rVert^2} and n=d-k. Almost surely h>0. The conditional residual direction of S_i in \ker A has density at most

relative to uniform probability on S^{n-1}. Choose a unit vector e\in\ker A perpendicular to the preceding residual directions, including that of S_0. There are at most i\le r<n such directions; a fixed Gram–Schmidt rule makes the choice measurable. Then e\perp D_{i-1}. If U_i is the new unit residual direction, then

The one-coordinate case of (70) and (71) yield

Integrating this tail with t=e^{-u} shows that the conditional expectation of \log(1/|\langle e,U_i\rangle|) is at most 1+\log(CK'\sqrt d).

For fixed A, the expected density tilt is

The divergence is finite: p_A/p^0\le K controls its positive part, and -x\log x\le1/e controls its negative part under p^0. Also the individual marginal (A,S_0) consists of an independent Haar frame and a unit vector. Thus \lVert AS_0\rVert^2 has beta parameters k/2,(d-k)/2 for every fixed target, with both parameters positive. The beta integral gives

Combining these estimates gives \mathbb E\log(1/\delta_i)\le C+\log K+C\log d. The negative part is bounded because \delta_i\le2. Both signs of every height logarithm are therefore integrable.

We may now take the expected logarithm of (79). It is exactly the finite relative entropy D_{\mathrm{KL}}(Q\Vert\Lambda)=U. Forgetting A by data processing yields J_S\le U. Adding the independent B and then projecting coordinatewise yields J_Z\le J_S. Finally (71), (83), and the height bound give (82).□

Proof. For every \lambda>0,

To prove this, take a compact subset of the displayed superlevel set. Open and closed balls have the same f-mass, since their boundaries have Lebesgue measure zero. At each point choose an open ball centered there whose f-mass exceeds \lambda times its volume. The strict inequality persists under a sufficiently small enlargement, so these balls give an open cover. Take a finite subcover and greedily keep disjoint balls in decreasing order of radius. Every discarded ball meets a retained ball of at least its radius, and is contained in that ball’s threefold dilation. Hence the compact set has volume at most 3^k times the sum of the retained volumes. The retained balls are disjoint and have total f-mass at most one, so their volumes sum to less than 1/\lambda. Inner regularity proves (86).

Set b=3^k and L_f=K\alpha_{d,k}. Since \mathcal M f\le L_f, layer integration over the unit ball gives

On the support of f, a radius-two ball contains the whole unit ball, so \mathcal M f\ge(v_k2^k)^{-1} there. Its logarithm is bounded on that support, while f\log f is integrable by the bounded-density argument in Lemma 7.2. Jensen’s inequality under the probability density f now yields

Use (71) and d/k\le32 to obtain (85).□

Proof. Given (B,Z_0,\ldots,Z_{i-1}), define for z\in\mathbb R^\ell

Let F_i(t)=P\{s:R_i(Bs)\le t\} be its distribution function under an independent s\sim P. The distance, and hence this conditional distribution function, is measurable in the projected history: the distance is the infimum of the corresponding norms over rational coefficient vectors. Let \rho_i=R_i(Z_i) be the actual replica distance.

If a random variable R has distribution function F, then

This includes distributions with atoms. In fact, the set of real x with F(x)\le u is an initial interval, whose probability is the supremum of F on that interval and is at most u. Tail integration of (88) gives, for 0<a<1,

In particular F(R)>0 almost surely under its own law.

Apply the relative-entropy variational inequality to the test z\mapsto F_i(R_i(z))^{-a} under the conditional one-vector reference law P_B. For an unbounded test, use its minimum with a finite constant and pass monotonically to the limit; (89) bounds its reference expectation. The chain rule for J_Z has one term for each conditional law of Z_i given (B,Z_0,\ldots,Z_{i-1}), and its i=0 term is zero. It follows that

The logarithmic expectations are finite: the variational bound after averaging controls their nonnegative parts by the finite correlation J_Z\le J_S from Lemma 7.2.

We next estimate F_i(\delta_i) while holding the entire replica outcome (A,S_0,\ldots,S_r) fixed. Put D=D_{i-1} and E=\operatorname{row}(B). The isometry B^{\mathsf T}:\mathbb R^\ell \to E gives the exact identity

Indeed, the orthogonal complement within E of \operatorname{proj}_E D is precisely E\cap D^\perp. The projection of the fixed (i-1)-space D into a Haar \ell-space E has full rank almost surely: generate E with independent standard Gaussians and restrict them to an orthonormal basis of D, obtaining an \ell\times(i-1) Gaussian matrix of full column rank. Thus \dim(E\cap D^\perp)=q_i=\ell-i+1. Rotations preserving D show that this intersection is a uniform q_i-space in the n_i-space D^\perp.

For fixed u, let v=\operatorname{proj}_{D^\perp}u. Spherical projection in that n_i-space, followed by (71), gives

with value one if v=0. The constant C_0 is absolute because n_i/q_i\le16/3; the density formula is applicable because n_i-q_i=d-\ell>2. In the replica experiment A annihilates D. Therefore for u=s-S_0, \lVert v\rVert\ge\lVert A(s-S_0)\rVert. Also \rho_i\le\delta_i, since B is a contraction and the distance minimization permits all vectors in D.

Set u_0=AS_0 and q=q_i. The identity

also holds at x=0. Integrating (92) against s\sim P and using Tonelli’s theorem yields

The integral converges because q_i>k, and the last step uses the exact bound q_i/(q_i-k)\le3/2. One absolute choice of C_1 works for every k\ge1.

Now F_i(\rho_i)\le F_i(\delta_i). Jensen’s inequality for -\log and (93), first for each fixed replica outcome, give

Here the last expectation uses the individual marginal (A,S_0). The right side is finite by Lemmas 7.2 and 7.3; Jensen may also be read in the extended sense before averaging. Substitution into (90) proves (87).□

Proof. Fix a state value v with probability p_v>0. Its conditional signal law has the bounded density

relative to \sigma. The new Gaussian design matrix is independent of (S,V). Its row Gram–Schmidt factorization is RA with an invertible triangular R and a Haar k-frame A, almost surely. The exact labels are R(AS), so, conditional on the design, observing them is equivalent to observing Y=AS. Because the whole design is independent of S conditional on V=v, its coefficients R add no information about S once (A,Y) is specified.

Generate the replicas conditionally independently from this posterior, and independently of W given v and the complete block data. A single replica then has the same joint law with the block data and W as the original signal: both use the posterior given the block, and W has no further dependence on the signal once those data and v are fixed. In particular each pair (S_i,W) has the same conditional law as (S,W), the auxiliary B is independent of the entire tuple and W, and the original pair used on the left is also coupled independently with B. The common map (B,s)\mapsto Bs is continuous, and the unprojected total correlation is finite by Lemma 7.2. These are precisely the application hypotheses of Lemma 3.1. Applied in the conditional experiment V=v, it gives

No conditional independence of the replicas given W is asserted or needed.

Insert (96) with K=K_v and average over v. The identity

accounts exactly for rare state values. Jensen’s inequality bounds the average of \log(1+Cd+\log K_v) by \log(1+Cd+H(V)). This proves (97). Under the width hypothesis, H(W\mid V)/m=o(d), the last term is o(1), and the logarithmic term is O(\log d) for all sufficiently large d. The stated Cd bound follows.□

Proof. Apply Lemma 2.4 with G=B, V=V_f, b=\ell, and r_0=1/2. Its hypotheses hold because B is independent of (S,V_f,\widehat S). Explicitly, the Markov bound for the residual radius h is \mathbb P\{h<1/2\}\le4\ell/(3d)\le1/3. Success together with h\ge1/2 therefore has probability at least 1/3, while the conditional prior cap probability is at most (4\epsilon)^{d-\ell-1}. These are exactly the constants in (98).□

Proof. Apply the fixed-shared-seed part of Lemma 2.7 to the learner in Definition 2.1. The resulting Borel experiment has data-independent initialization and uniform-prior success at least 2/3, with fresh transition and output randomness retained. This is the success threshold in Lemma 7.6.

First, success forces T=\Omega(d) without any memory restriction. Suppose T\le d/8, and grant an estimator all T raw pairs, filling in ignored samples after any early stopping. Lemma 2.3 with b=T gives a uniform residual sphere in kernel dimension d-T; (4) bounds its probability of radius below 1/2 by 4T/(3d). At T=0 the radius is one deterministically. On radius at least 1/2, the cap argument of Lemma 2.10 bounds conditional success by (4\epsilon)^{d-T-1}. Thus

The output has no further dependence on S conditional on all the raw data, so the bound also covers randomized estimators. Its right side is at most 1/6+(0.4)^{7d/8-1}<2/3 for all sufficiently large d. Hence T>d/8 on those dimensions.

Put L=\log(1/\epsilon)\ge\log10. If T\ge dL, the conclusion already holds. On the remaining branch T<dL, apply the output-capacity bound of Lemma 2.9 to this uniform-prior experiment with p_0=2/3. It gives

For large d, \log(T+1)\le\log(dL+1)\le dL/2: here dL\ge d\log10 and \log(x+1)\le x/2 for x\ge3. Thus (100) implies

For example, after subtracting dL/2, the left side is (d/2-1)L\ge dL/4 for d\ge4. The second and third conclusions follow from M=o(d^2) and T<dL.

Use Lemma 2.7 to retain the stopping index, postpone the fresh randomized output, and append ignored rows through the last block. Its state count gives every padded state entropy at most

This count restricts the branch where the block argument is needed; it does not replace that argument in the representable-precision regime.

Use a single independent Haar \ell-frame B for the entire analysis, put Z=BS, and divide the padded stream into N=\lceil T/k\rceil blocks. For consecutive states V,W, the chain rule and data processing give

The initial state is independent of (S,B,Z). Proposition 7.5 and (102) therefore imply

The terminal lower bound (98) is at least c dL for all sufficiently large d: indeed d-\ell-1\ge d/2 and

while the subtractive \log2 is absorbed because dL\to\infty. Finally k\ge d/32 and the already proved T>d/8 give

Comparison with (103) proves the proposition.□

Proof. At the fixed tuple, the restriction of B to L has rank u almost surely. Choose an orthonormal m\times q matrix N whose columns span (BL)^\perp, using only BD_{\mathbf x}. Gram–Schmidt with a fixed ordering gives a measurable choice on the full-rank set. With an independent standard Gaussian k\times q matrix H, the required conditional law of F is realized by

The choice of N uses only B|_L. The Gaussian restriction B|_{L^\perp} is independent of B|_L. Write s-x=v+w with v\in L and w\in L^\perp. Then N^{\mathsf T}Bv=0, while, conditionally on B|_L, the vector N^{\mathsf T}Bw has law N(0,\norm w^2I_q). Therefore, conditionally on H and B|_L,

This conditional calculation accounts for the dependence of F on B.

For \eta>0, Tonelli’s theorem and (120) give

The integrand on the right increases as \eta\downarrow0. The tube bound (23) gives \delta(s)>0 for P-almost every s; it also gives a finite inverse kth moment, since d-1-u>k. The matrix H has full row rank almost surely. Monotone convergence on the right and Fatou’s lemma on the left, along \eta=1/j, prove the first inequality in (113).

For completeness, successive orthogonal residuals of the rows of H have independent squared lengths

Indeed, conditionally on the preceding rows, the new row is standard Gaussian on a complement of dimension q-i+1; this conditional law is constant, which also proves independence of the residual lengths. This is the elementary Gaussian orthogonal reduction described in Edelman and Rao [7, Section 5]; the rectangular product used here follows from the displayed conditioning. Direct integration of the chi-squared density gives \E V^{-1}=1/(p-2) for V\sim\chi_p^2, p>2. Cauchy–Schwarz hence gives

We next use the actual observations. If Ax=b and L\subset\ker A, then, for v=P_L(s-x),

Let \alpha=d-1-u. The tube bound, now applied to x+L, gives

Layer-cake integration therefore yields, for 0<r\le1,

Since \alpha-k=d-2k\ge3d/4, an absolute choice of C_0 makes this quantity at most one at r=r_*. On \{\delta>r_*\}, (121) gives both \delta^{-k}\le r_*^{-k} and \delta^{-k}\le a^k\norm{As-b}^{-k}. The pushforward of P under A has density g_A, and both As and b have norm at most a. Integration of these two bounds gives (116) with the two support cutoffs in (115).

The remaining singularity has the critical exponent k in dimension k. Radial integration gives the exact mass

The ball of radius ar_* contributes V_k, and the annulus contributes kV_k\int_{ar_*}^{2a}dt/t. Dropping the outer cutoff in (115) only for its convolution term, and using \int g_A=1, proves (117).

We record the scale in this bound before taking its logarithm. Integrating the standard Gaussian density over the ball of radius \sqrt k gives (2\pi)^{-k/2}V_k\le(e/k)^{k/2}. Also \E\norm A_{\op}\le C\sqrt d: choose 1/4-nets on the two unit spheres of cardinalities at most 9^k and 9^d, bound the operator norm by twice the maximum of the scalar bilinear forms on the nets, and integrate the union bound for their standard Gaussian tails. Jensen’s inequality gives

The cutoff (114) and (105) give

These estimates prove (118). Finally, \log\norm A_{\op} is integrable below because the norm dominates the absolute value of one standard Gaussian entry. Retaining the first term of U_A bounds its total mass below by (2\pi)^{-k/2}V_k\norm A_{\op}^k. Together with (117), these observations prove the two remaining integrability assertions.□

Proof. At a fixed full-affine-rank \mathbf X, write D_{\mathbf X}=UR, where U has orthonormal columns. Since B is independent, BU is a standard Gaussian m\times u matrix. Consequently

The logarithm of \Delta(\mathbf X) is integrable by Lemma 3.6. Gaussian column residuals factor \det(G^{\mathsf T}G) into independent chi-squared variables of degrees m,m-1,\ldots,m-u+1. Their absolute logarithms are integrable from their densities at zero and infinity. This proves (123) and the asserted integrability of \log w(\mathbf Y). Jensen applied to each factor gives (124).

The actual equal-label experiment has L_{\mathbf X}\subset\ker A. Conditionally on (A,b,\mathbf X), the matrix B remains independent, and the conditional law of F is \gamma_{k,m}^{B L_{\mathbf X}}. Lemma 8.2 therefore gives

It follows that \E\log(1+\Xi)<\infty. Here are the details needed for the possible small values of g_A(b). Conditional Jensen reduces the claim to integrability of \log(1+U_A(b)). On the actual finite positive set for g_A,

The first term is integrable by Lemma 3.6. For the second, average over b with density g_A and apply Jensen to obtain at most \log(1+\int U_A). Lemma 8.2 makes its average finite. Thus (\log\Xi)^+ is integrable.

Let the product reference first draw B and then draw \ell independent points from P^B. The divergence of the actual joint law from this reference is \mathcal C_Y<\infty, and R_B integrates to one under this reference. Equation (19) gives

Conditionally on B,\mathbf Y, Equation (111) has a finite positive right side, so \E_F\Xi^{-u}<\infty. Hence \E_F(\log\Xi)^-<\infty on almost every such fiber; also \E_F(\log\Xi)^+<\infty there by the preceding joint bound. Conditional Jensen is now legitimate and gives

Rearranging this inequality,

Its right side has finite expectation, proving joint integrability of (\log\Xi)^-. The same Jensen lower bound gives

so the negative comparison logarithm is integrable as well. Finally use the normalized test R_B in (18). All logarithms are now integrable, and that test together with the conditional Jensen bound proves (125).□

Proof of Proposition 8.1. The preceding lemma permits subtraction of all likelihood and correlation terms. Conditional Jensen in (126) gives

The last logarithm is integrable under the actual label law: U_A(b) is bounded below there by (2\pi)^{-k/2}, and its positive logarithm was controlled in the proof of Lemma 8.3. At fixed A, Jensen with b\sim g_A gives

Together with (113) and (118), this yields

Combine (110), (123), (124), (125), and (128). The result is

The first term is O(k u) by (105). Thus the scale from the projected Gaussian determinant cancels the inverse-determinant scale in the synthetic likelihood. The critical kernel was integrated before taking a logarithm, leaving only \log(1+\log\Lambda).

Apply Lemma 3.1 with t=\ell, the representative S=X_1, message W=z, and map \phi_B(x)=Bx. Every replica has the required signal–message pair law, B is independent of the whole tuple and message, and \mathcal C_X<\infty. Its conclusion and H(z)\le\log K give

The joint law of (B,X_1,z) is the product of the B-law and the original (X,z)-law. Substitution of (129) therefore proves (106).□

Proof. Apply Lemma 2.7 with p=2/3 and p'=s_0=16/25=0.64 to the learner in Definition 2.1. This gives deterministic Borel state-based rules and data-independent initialization, with uniform-prior success at least s_0; all remaining randomness is fixed. Pre-generate all T rows, including rows after an early stop.

Put L_\epsilon=\log(1/\epsilon). It suffices to consider dimensions for which T\le dL_\epsilon. At other dimensions the claimed lower bound already holds. Lemma 2.9, applied with p_0=s_0, gives

Pad first to time T and then to the least multiple of k at least T, using the stopping-index tags and ignored fresh pairs of Lemma 2.7. Its exact per-index state count gives

Since s_0>3/5, Lemma 2.10 gives T>\lfloor d/2\rfloor for all sufficiently large d. We use the weaker consequence

Let p=\lceil T/k\rceil. Write H_i for the tuple of states at the ends of the first i blocks, with H_0 constant. Use one independent B\sim\gamma_{m,d} and Y=BX throughout. If a history h has probability p_h>0, Lemma 2.8 gives its conditional signal density

The next block matrix is independent of (X,H_{i-1}). Given h, the initial state is fixed, and the next state is a measurable K-valued function of the new block and its exact labels. The side matrix remains independent of this conditional experiment. Proposition 8.1 therefore applies with \Lambda=1/p_h. Averaging it over histories gives

The last line uses concavity of t\mapsto\log(1+t) and H(H_{i-1})\le(i-1)\log K. In particular it applies the bounded-prior block theorem before averaging its density cost. Since p=o(d), \ell\ge d/16, and \log K=o(d^2), the right side is at most Cd, with one absolute C, for all sufficiently large d. The chain rule then gives

The postponed deterministic output is a function of the final tagged state, and therefore of H_p.

To obtain the matching endpoint, use Lemma 2.4 with S=X, V=H_p, G=B, and r_0=1/4. The output is a function of H_p, and B is independent of the entire signal–history experiment. Moreover, 2\epsilon<1/4 and m\le d/2\le d-2. For the residual radius \rho_B=\norm{P_{\ker B}X}, (4) gives

Thus the lemma applies with success minus radius-failure probability at least s_0-8/15=8/75, and yields

for all sufficiently large d, with an absolute c_1>0. Indeed,

and d-m-1\ge d/2-1.

By (132), T+d<5T. Combining (134) and (135) therefore gives T\ge c_2dL_\epsilon with an absolute c_2>0. The constants are absolute; the eventual threshold comes only from M(d)=o(d^2). All replicas and auxiliary projections have served solely to bound information. The learner’s observations remain the prescribed fresh Gaussian rows and exact labels.□

Proof. Retain B,C temporarily and put t=Ds_1. Conditional on (B,C,t), the signals are independent with law \mu_{D,t}. Disintegrating this law further according to z=Bs gives \mu_{B,z}: the earlier equation Ds=t is just Cz=t, already determined by z. Formally, disintegrate the law of z=Bs according to Cz, and compose its conditional kernel with \mu_{B,z}; the resulting kernel is a conditional law given Ds=t. These identities hold at the needed values because each individual signal has marginal law \mu given (B,C). Conditioning the independent signals on their separate Z_i’s therefore yields the product in (141). That product does not depend on C,t, so discarding them leaves it unchanged. The independent uniform J and the later kernel for A do not change the marginal under consideration.

Data processing and the conditional chain rule give

This is valid as an extended inequality; absolute continuity will be established below. Relative entropy to a product is at least the sum of the relative entropies of the marginals. For each such summand, convexity of relative entropy permits us, after averaging, to discard the other Z_j’s from its first conditional law. The result is at least

by (139). Sum over i.□

Proof. The tangent space at s is s^\perp. The Gram matrix of the differential L:s^\perp\to\mathbb R^q is L(I-ss^{\mathsf T})L^{\mathsf T}, proving the formula for its normal Jacobian. With P_L=L^{\mathsf T}(LL^{\mathsf T})^{-1}L, the determinant lemma also gives

The differential is onto except when s belongs to the row space of L; that sphere has zero (d-1)-dimensional surface measure. Applying change of variables on coordinate patches of its complement, and then exhausting the complement, gives

To identify these measures with the versions already used, put s_0=L^{\mathsf T}(LL^{\mathsf T})^{-1}t and r=\sqrt{1-\|s_0\|^2}. An interior fiber is s_0+r\mathbb S(\ker L), where \mathbb S(\ker L) is the unit sphere of \ker L, and j_L is constant there. Its induced volume is |\mathbb S^{d-q-1}|r^{d-q-1}. Dividing this volume by |\mathbb S^{d-1}|j_L gives precisely the uniform projection density p_L^0(t) in (21). Consequently, as finite measures on every interior fiber,

Taking mass and then normalizing gives (138) pointwise on its positive set. A uniform direction in \ker L can be generated by projecting a standard Gaussian vector onto that subspace and normalizing. The projection matrix is a measurable function of full-rank L; integrating the bounded Borel function f(s_0+r\theta) against this kernel therefore gives measurable \lambda_{L,t}, p_L(t), and \mu_{L,t}, with the fixed convention on unused fibers from (138).

For orthonormal rows and f=1, the displayed fiber formula gives a density proportional to (1-\|t\|^2)^{(d-q-2)/2} on the unit ball. Its normalizing integral is at least \tfrac12v_qd^{-q/2}: restrict to the ball of radius d^{-1/2} and use (1-1/d)^{(d-q-2)/2}\ge1/2. The maximum of the density times v_q is consequently at most 2d^{q/2}\le d^d. The bound f\le F multiplies this estimate by at most F. Finally, an invertible change from orthonormal row coordinates to L divides the density by \det(LL^{\mathsf T})^{1/2} and multiplies the ellipsoid volume by the same factor. This proves (144); in particular our chosen p_L is finite everywhere.□

Proof. Near a point of \Omega, choose coordinates x=(x',x''), z=(z',z'') so that x'' and z'' each have a coordinates and both G_{x''} and G_{z''} are invertible. Let u_X(x)\,dx, u_Z(z)\,dz be the volume forms in these coordinates. Changing variables from (x',x'') to (x',G) shows that the induced x-fiber volume divided by J_xG is

Indeed, the tangent-volume factor and the normal-volume factor of this change of variables are respectively the induced fiber volume and the reciprocal normal Jacobian. Thus the left integral has local density u_Xu_Z/|\det G_{x''}| in (x',z',z''); the right integral has density u_Xu_Z/|\det G_{z''}| in (x',z',x''). At fixed (x',z'), implicit differentiation gives

The two local integrals agree. Split \Omega into measurable pieces subordinate to a countable coordinate cover and sum using Tonelli’s theorem. This also proves the assertion for infinite integrals.□

Proof. We first establish the identities without dividing by any projection density. In \mathsf M_A, integrating the tuple variables gives the exact (s_1,A)-marginal

For fixed full-rank A, this weight is finite by (144). Where it is positive, \lambda_{A,As_1}^{\otimes\ell} =p_A(As_1)^\ell\mu_{A,As_1}^{\otimes\ell}. The rank argument for the Q experiment therefore shows that \operatorname{rank}U=\ell outside an \mathsf M_A-null set. At zero weight the fiber product has zero mass. The same reasoning in \mathsf M_C gives the exact (s_1,B,C)-marginal

and the rank argument for R removes the loci where U or BU has rank less than \ell. Multiplication by the finite weight in (153) preserves these native null sets.

On either incidence set, the spherical partial differentials are regular on the remaining locus. Indeed, if some s_i belonged to the row space of A, then its row-space projection would have norm one. The equations As_j=As_i would give every s_j that same row-space projection, and their unit norms would force s_j=s_i for all j, contradicting \operatorname{rank}U=\ell. The same argument applies to D. The Gaussian rank assertions above also remove row-rank failures. Thus removing the complements of the full-rank regular loci changes neither \mathsf M_A,\mathsf M_C nor the corresponding \mathsf H_A,\mathsf H_C.

Fix s_1 and apply Lemma 9.4 to

For fixed A, the target has \ell independent n-coordinate blocks, so the partial normal Jacobian is \prod_{i=2}^k j_A(s_i). These are precisely the denominators in \prod_{i=2}^k\lambda_{A,As_1}(ds_i). For fixed tuple, the differential is \Delta A\mapsto\Delta A\,U. It consists of n row maps with Gram matrix U^{\mathsf T}U; its normal Jacobian is \det(U^{\mathsf T}U)^{n/2}. The A-fiber has rows in U^\perp. Restricting the ambient standard Gaussian density to this subspace and then expressing it relative to the normalized Gaussian \gamma_U contributes (2\pi)^{-n\ell/2}. This proves (148) on the regular locus, and hence exactly after the null loci just proved are removed. In particular, integrating over a restricted regular tuple fiber gives at most p_A(As_1)^\ell, and gives equality for native almost every (s_1,A).

For the second identity, fix (s_1,B) and use G(x,C)=CBU. Put W=BU. The tuple partial normal Jacobian is \prod_{i=2}^k j_D(s_i). At CW=0,

Variations whose rows belong to \operatorname{col}W lie in this tangent space, since C W=0. They form the orthogonal complement of the tangent space to the constrained frame fiber. On this normal space the differential is \Delta\mapsto\Delta W, with normal Jacobian \det(W^{\mathsf T}W)^{n/2}. There is no additional metric factor in these normal directions. The constrained fiber, with its induced metric, is isometric to \mathcal V_{n,p-\ell}. Replacing its unnormalized volume by \upsilon_W leaves the volume ratio \kappa. Lemma 9.4 now proves (149), again exactly after removal of native rank-null sets. The corresponding restricted tuple mass is at most p_D(Ds_1)^\ell and equals it for native almost every (s_1,B,C).

We next transfer the density exceptions using these undivided measures. For a full-rank n\times d matrix L, define

and let \mathcal E(L,s) be the condition that either p_L(Ls)\notin(0,\infty), or the limit of b_j(L,Ls) does not exist, or that limit differs from p_L(Ls). This is a measurable condition. Set

For every fixed full-rank L, Lebesgue differentiation and the density formula imply \mu\{s:\mathcal E(L,s)\}=0. The exact native marginals (152) and (153), whose density weights are finite for each fixed native projection, therefore give

On the right sides of (148) and (149), the multiplying Gram weights are strictly positive and finite almost surely. If h denotes either weight, then on \{1/m\le h\le m\} the equality \int_{\mathcal E}h\,d\mathsf H_\bullet=0 gives \mathsf H_\bullet(\mathcal E\cap\{1/m\le h\le m\})=0. Letting m\to\infty proves that \mathcal E_A is \mathsf H_A-null and \mathcal E_D is \mathsf H_C-null. This argument is valid even if an undivided measure has infinite total mass. Adding the unused probability kernels gives both assertions under \mathsf H.

Only now replace each unnormalized fiber measure by its normalized conditional law. The Q experiment divides (148) by p_A(As_1)^\ell, then attaches the same kernels for B,C and the message density w\phi_J(A,As_1) relative to uniform J. This gives (150). The R experiment divides (149) by p_D(Ds_1)^\ell and attaches the unchanged \gamma_U kernel for A and uniform J, giving (151). The divisions are legitimate on the full-measure set just proved. Since r_*>0 and is finite there, Q\ll R.□

Proof. For n=1, the frame manifold is \mathbb S^{h-1}, giving the base case of (154). For n\ge2, the map from \mathcal V_{n,h} to its first row in \mathbb S^{h-1} has constant normal Jacobian 2^{-(n-1)/2}. To compute it, move the frame by an orthogonal transformation to the first n coordinate rows. Tangent matrices then consist of a skew-symmetric block in the first n columns and an arbitrary remaining block. Each of the n-1 skew coordinates affecting the first row appears twice in the squared matrix norm, so the corresponding singular value of the first-row map is 2^{-1/2}. The other first-row coordinates have singular value one. The fiber is isometric to \mathcal V_{n-1,h-1}. Slicing thus gives

Iteration proves (154). The metric factor depends only on n, so it cancels in the ratio defining \kappa. The sphere-area formula |\mathbb S^{h-1}|=2\pi^{h/2}/\Gamma(h/2) gives the product in (155).

For a>0 and \ell/2\ge1, a gamma random variable X of shape a and scale one satisfies \Gamma(a+\ell/2)/\Gamma(a)=\mathbb E X^{\ell/2} \ge(\mathbb E X)^{\ell/2}=a^{\ell/2} by Jensen’s inequality. Apply this with a=(p-j+1-\ell)/2 and then use a\ge(p-n+1-\ell)/2.□

Proof. For fixed z, (140) makes the coordinates of D(z-s_1) independent centered Gaussians with variance \operatorname{dist}(z-s_1,\operatorname{col}U)^2. Hence

The right side is interpreted as +\infty when the distance is zero. Integrate in z using Tonelli’s theorem and then apply conditional Fatou along \rho=2^{-j}. Lemma 9.5 and Q\ll\mathsf H identify the almost-sure limit of the ball averages with p_D(Ds_1). This proves (157) without evaluating an arbitrary density version at a dependent point.

Let H(t) be the \mu-probability that the distance in K is at most t. Since AU=0,

The projection law has a Lebesgue density, so projection-ball boundaries have zero mass. The definition of p_A^* therefore gives H(t)\le K_0t^n. All these distances are at most two; taking t\downarrow2 from above also gives K_0\ge2^{-n}.

A second estimate uses the projection onto U^\perp, of dimension d-\ell\le d-2. Applying Lemma 9.3 to a matrix with orthonormal rows for this projection bounds its density by Fd^d/v_{d-\ell}. A ball of radius t centered at the projection of s_1 consequently has probability at most Fd^dt^{d-\ell}. Thus

The exponent d-\ell uses the bounded projection density and the condition \ell\ge2.

The layer-cake formula, including the possibility of an initially infinite integral, is

Here d-\ell-n>0 and \tau\le1. Use the second estimate in (158) up to \tau and the first thereafter:

The last inequality uses Fd^d\tau^{d-\ell-n}=2^{-n}\le K_0. Finally,

The dimension ratios in (136) give L_F\le C(1+d\log d+\log F). Taking its logarithm gives the stated bound and finiteness of the inverse-distance integral K.□

Proof. Lebesgue differentiation gives p_A^*(t)\ge p_A(t) for A_\#\mu-almost every label. We prove the particular centered maximal inequality we need. Its one-dimensional ancestry is the maximal-function theory of Hardy and Littlewood [10, Section III]; for the dimension cost of customary covering arguments, see Stein and Strömberg [17, p. 259].

For a>0, a compact subset of \{t:p_A^*(t)>a\} has a finite cover by balls centered in that set, each of projection mass greater than a times its volume. Select disjoint balls in decreasing order of radius. Every discarded ball is contained in the triple of a selected ball, since it meets a selected ball of at least its radius. The selected masses sum to at most one, so the compact set has volume at most 3^n/a. Inner regularity gives

The function is measurable: the supremum may be restricted to positive rational radii, because a density gives zero mass to ball boundaries.

Let E_A be the projection ellipsoid and V_A=|E_A|. Since p_A^*\le\|p_A\|_\infty, integration of level sets, using the bound V_A up to level 1/V_A and (160) above that level, gives

Jensen’s inequality with respect to the probability density p_A then yields

Values on \{p_A=0\} do not enter the integral. The preceding estimate and n\asymp d prove (159).□

Proof of Proposition 9.1. On the full-measure set in Lemma 9.5, the log likelihood ratio is the sum of the message term \log(w\phi_J(A,As_1)), the term

and \ell\log(p_D(Ds_1)/p_A(As_1)). The message term is at most \log w.

Under Q, B is independent of U. Conditional on U, put V=U(U^{\mathsf T}U)^{-1/2}. Then G=BV is a standard Gaussian p\times\ell matrix and

The lower bound in (155) and the determinant–trace inequality bound (161) above by

Its positive part has expectation O(n\ell). Indeed, \mathbb E\operatorname{tr}(G^{\mathsf T}G)=p\ell, the ratio p/(p-n+1-\ell) is bounded, and \mathbb E\log^+X\le\log(1+\mathbb E X) for X\ge0.

For the remaining ratio, use \log^+u\le\log(1+u), conditional Jensen, and (157) and (156). Since p_A^*(As_1)/p_A(As_1)\ge1 almost surely, this gives

The Gaussian operator term has expectation O(n). Here are the elementary estimates. A 1/4-net of the unit sphere in \mathbb R^h has size at most 9^h, by packing disjoint radius 1/8 balls. Nets in the two dimensions bound \|A\|_{\mathrm{op}} by twice the maximum of at most 9^{n+d} absolute standard Gaussian bilinear forms. A Gaussian tail bound gives \mathbb E\|A\|_{\mathrm{op}}\le C\sqrt d. Also, integrating the Gaussian density over the ball of radius \sqrt n gives v_n\le(2\pi e/n)^{n/2}. Therefore

whose expectation is O(n) by Jensen and n\asymp d.

The (A,s_1)-marginal under Q is the original independent Gaussian/prior draw. Averaging (162) and using Lemmas 9.7 and 9.8 consequently gives

All positive parts in the log likelihood ratio are now integrable. Since Q\ll R, its negative part is integrable as well: with h=dQ/dR, \int_{\{h<1\}}-h\log h\,dR\le1/e. Thus no undefined subtraction occurs, and

Combine this with (142) and divide by k.□

Proof. The padding count in Lemma 2.7, including stopping at index zero, gives (165). Its stopped records remain fixed while fresh unused observations are generated. The output-capacity bound in Lemma 2.9, with success at least 2/3 and (T+1)2^M\le w, gives

Because L_\epsilon\ge\log10 and T<dL_\epsilon, \log(T+2)\le\log d+\log L_\epsilon+C. Using \log L_\epsilon\le L_\epsilon yields

This proves L_\epsilon=O(1+M/d)=o(d). The remaining assertions follow from T<dL_\epsilon and M=o(d^2).□

Proof. For a positive-probability history V_{i-1}=v, Lemma 2.8 gives the Bayes density

relative to \sigma. A Borel version is available from the Borel learner. The history fixes the previous padded state. Its update over the next fresh block is a kernel of (A,AS) to at most w next states. For the first block, independent initialization can be integrated into the same kernel. The matrix B is absent from the learner and independent of its entire experiment; it remains independent of the entire conditional signal, fresh-block, and message experiment after conditioning on v. Proposition 9.1 therefore applies at each such history.

The finite history has entropy H(V_{i-1})\le b\log w. Hence Jensen’s inequality gives

The last bound uses b=O(d) and \log w=O(d^2) eventually, from (166) and n\asymp d. The same bounds give \log w/k=o(d). Averaging the one-block estimate thus bounds each increment I(S;V_i\mid V_{i-1},B,BS) by Cd eventually. The conditional chain rule, with the same independent B throughout, proves (167).□

Proof. Apply Lemma 2.4 with V=\widehat S, the identity output kernel, b=p, and r_0=1/2. For the residual radius R=\|P_{\ker B}S\|, Lemma 2.3 gives

Success at least 2/3 therefore leaves event mass at least 1/3, and (6) gives the first inequality in (168). The second follows from

because d-p-1 is an absolute positive fraction of d; the subtractive \log2 is absorbed for large d.

For the final assertion, grant the learner all pre-generated observations through its horizon, including ignored rows after stopping. Its output is a kernel of those data and independent randomness. Lemma 2.10 shows that success at least 3/5, and hence at least 2/3, already requires T>\lfloor d/2\rfloor for large d. In particular, T>d/4. That lemma includes the deterministic zero-row residual sphere, so the assertion covers T=0 as well.□

Proof of Theorem 9.9. If T\ge dL_\epsilon, the desired bound is immediate. Otherwise apply Lemmas 9.10 and 9.11. The terminal output is a kernel of the final padded state, hence of V_b; conditional data processing and Lemma 9.12 give

Thus b\ge c_0L_\epsilon for an absolute c_0>0. If L_\epsilon\ge2/c_0, then

after adjusting an absolute constant. If L_\epsilon<2/c_0, the separate conclusion T>d/4 of Lemma 9.12 gives the same order after another absolute adjustment. This proves (164) uniformly over the allowed \epsilon.□