A signal s is a point of the unit sphere S^{d-1} in R^d, fixed before any sampling. At each step j = 1, 2, ..., T a fresh row x_j drawn from the standard Gaussian distribution N(0, I_d) arrives together with its exact inner product y_j = <x_j, s>. The rows are independent across j, and the learner cannot choose, replace, or revisit a row. Between steps the learner keeps a finite message m_j that lies in a set of cardinality at most 2^M; the memory bound M = M(d) is nonnegative and integer. Given m_{j-1} and the pair (x_j, y_j) a transition may use unrestricted computation and fresh private randomness and must produce m_j. A stopping rule chooses whether to keep sampling, and a terminal rule outputs a unit vector s-hat from the final message and fresh randomness. Every quantity below is defined on the standard Borel spaces inherited from R^d and S^{d-1}, so all information-theoretic expressions are measurable and finite or infinite as stated.

The sample horizon T = T(d) is deterministic. Angular accuracy is measured by arccos<s, s-hat> <= epsilon with 0 < epsilon <= 1/10. The main result is that no learner of this kind, with M(d) = o(d^2) bits, succeeds at accuracy epsilon with probability at least 2/3 uniformly over signals using fewer than c d log(1/epsilon) samples; the constant c is absolute and the eventual dimension threshold may depend on the memory sequence. This closes an exact-observation analogue of the memory-sample tradeoffs known for noisy sparse regression and for parity: prior art bounds sample complexity by memory for specific regression and finite-learning problems, whereas the exact Gaussian model removes noise and leaves the geometric cost of localization as the only obstruction.

pdf/steinhardt-duchi-2015.pdf
pdf/steinhardt-valiant-wager-2016.pdf
pdf/raz-2016.pdf
pdf/raz-2017.pdf
pdf/dagan-kur-shamir-2019.pdf
pdf/ssv-2019.pdf

The proof has one organizing idea. Concentration of the posterior is funded either by a geometric quantity whose increase is billed against information, or by a side-projection certificate the learner never sees. Both funds come from the same exact-label projection identity for independent Gaussian rows. The remaining work is bookkeeping: a chain rule that carefully separates what the learner retains from what the analysis retains, and a decoding argument to turn the information bound into a sample bound.

pdf/austin-2020.pdf

All logarithms are natural unless an explicit base 2 is written. For probability measures P << Q on a standard Borel space, D(P||Q) = integral of log(dP/dQ) with respect to P; mutual information I(U; W) = D(P_{U,W} || P_U (x) P_W); conditional versions average the corresponding relative entropies against the conditioning variable. For a discrete variable W, H(W) = -sum_w P(W = w) log P(W = w), with 0 log 0 = 0. The chain rule and data processing on standard Borel spaces in the conditional-relative-entropy formulation of Austin are used without further comment; the cited Lemma 3.6 and Sections 3.3-3.4 of that reference contain the exact statements required. Shannon's founding account of entropy and channel capacity is the historical source of these quantities. Watanabe's early treatment of multivariate total correlation is the direct antecedent of the multi-information bookkeeping used later, with the standard-Borel formulation in Austin.

pdf/shannon-1948.pdf

The proof proceeds in three movements. First the exact equal-label finite-measure identity is recorded: it is the only external ingredient, and every projection and volume estimate to follow rests on it. Second a dyadic-cell refinement charges the cost of concentration. Third, three localization mechanisms (maximum-score refinement, predecessor-span averaging, and finite-entropy regularization) each give a chain-rule drift. The three combine into the sample lower bound. In all cases, the auxiliary variables introduced during the analysis are not visible to the learner.
The one external geometric fact used below is the finite measure carried by tuples of signal points that share a common exact label. Fix integers k >= 1 and m >= 1, write t = m + 1, and require k + m <= d - 2. Two base laws are permitted: uniform probability on S^{d-1}, or standard Gaussian probability on R^d; write P for either. For an ordered tuple u = (u_1, ..., u_t) in (R^d)^t set D_u = [u_2 - u_1, ..., u_t - u_1], the d-by-m matrix assembled from these difference columns, let F_u = col(D_u) be their span, and set J(u) = sqrt(det(D_u^T D_u)). Write Gamma_{k,d} for the law of a k-by-d matrix of independent standard Gaussians, and Gamma_{k,d}^{F_u} for the conditional law of such a matrix whose rows are independent standard Gaussians in F_u^perp = col(D_u)^perp; this law is defined whenever rank D_u = m, which holds except on a null set for both base laws.

The weight has a plain meaning. When the differences are independent, the points are affinely independent, and the product J(u) is the volume of the m-dimensional simplex that the tuple spans with a fixed base point; a long or thin simplex makes J(u) small, and the forthcoming weight J(u)^{-k} charges exactly that thinning. The classical Blaschke-Petkantschin formula in integral geometry is the antecedent of this bookkeeping, but the argument below computes the relevant Jacobian directly from the Gaussian density and so does not invoke it.

Let mu = f P with f bounded, nonnegative, and Borel, so mu is a finite measure that need not be a probability. For a full-rank matrix A let p_A(y) be the density of A u at the label y in R^k for u ~ P, and let P_{A,y} be the conditional law of u given Au = y; on an unused label the latter may be chosen arbitrarily. Put h_A(y) = integral of f with respect to P_{A,y}, set p_A(y) = p_A^0(y) h_A(y) where p_A^0 is the untilded density for P, and define the tilted fiber mu_{A,y}(du) = (f(u)/h_A(y)) P_{A,y}(du) when h_A(y) > 0. Then for every nonnegative Borel test H(A, y, u),

  integral Gamma_{k,d}(dA) integral_{R^k} p_A(y)^t integral H(A, y, u) mu_{A,y}^{tensor t}(du) dy
    = (2 pi)^{-k m/2} integral J(u)^{-k} mu^{tensor t}(du) integral H(A, A u_1, u) Gamma_{k,d}^{F_u}(dA).

Both sides are finite measures on (A, y, u) before H is inserted, and both are supported on the incidence A u_i = y for all i, on full-column-rank D_u, and on full-row-rank A; the right side places the label at y = A u_1. In the spherical case the shared fiber has a positive radius.

The coarea formula for the map (A, u) -> (A, A u_1), together with the standard disintegration of a density under that map, underlies the statement just displayed.

The proof fixes a bounded continuous test H and first treats P itself. Let phi_eta be a standard approximate identity on R^k, either uniform on the radius-eta ball or the density of N(0, eta^2 I_k). The mollified functional

  I_eta = integral (P)^{tensor t}(du) Gamma_{k,d}(dA) H(A, A u_1, u) prod_{i=2}^{t} phi_eta(A u_i - A u_1)

converges as eta decreases to zero to the left side above. Indeed, p_A(y)^t P_{A,y}^{tensor t}(du) dy is precisely the law of (y, u) under which the t independent signal points are conditioned to share the single label y; the product of the phi_eta differences tests the constraints A u_i = A u_1 in the limit. On the other hand, for a fixed tuple u with rank D_u = m, the image Psi_u(A) = (A u_2 - A u_1, ..., A u_t - A u_1) in (R^k)^m is a centered Gaussian whose per-row covariance is the Gram matrix of the differences, so det(D_u^T D_u) appears with exponent k/2; the density of Psi_u(A) at the origin is exactly (2 pi)^{-k m/2} J(u)^{-k}, and the conditional law of A given Psi_u(A) = 0 is Gamma_{k,d}^{F_u}. The product of the phi_eta is an approximate identity on (R^k)^m at the origin, so I_eta also converges to the right side. Comparing the two limits proves the identity for mu = P. For a general bounded density f, the two t-fold factors change in the same way: p_A(y)^t mu_{A,y}^{tensor t}(du) equals p_A^0(y)^t (prod_i f(u_i)) P_{A,y}^{tensor t}(du) because the tilted density h_A(y)^t cancels against the t denominators of mu_{A,y}^{tensor t}. Thus inserting prod_i f(u_i) into the test, which the right side does automatically through mu^{tensor t}, reduces the claim to the base case. The differentiation and conditional-density versions of p_A agree for Lebesgue-almost every y and at the constrained label for the finite reference measure; taking lower limits of ball averages yields a jointly measurable choice.
The identity pays for itself as a finiteness statement about inverse simplex volumes, and this is the quantitative engine of every block estimate below. Fix integers k >= 1 and p >= 2 with k + p + 1 < d, and draw u_1, ..., u_p independently from P. For almost every tuple the p - 1 difference vectors u_2 - u_1, ..., u_p - u_1 are linearly independent, so J(u) > 0. Then

  integral J(u)^{-(k+1)} P^{tensor p}(du) < infinity.

Apply the identity with row count r = k + 1 and tuple size t = p, so m = p - 1 and the dimension condition r + m = k + p <= d - 2 is the hypothesis. Take the test identically one and base density f = 1, so each fiber mu_{A,y} = P_{A,y} is a probability and the left side collapses to

  L = integral Gamma_{k+1,d}(dA) integral_{R^{k+1}} p_A(y)^p dy.

The projected density of a uniform sphere point under a full-rank (k+1)-by-d matrix A is supported on the ellipsoid {y : y^T (A A^T)^{-1} y <= 1} and equals, up to the normalising constant c_{d,k+1} of that projection, the function det(A A^T)^{-1/2} (1 - y^T (A A^T)^{-1} y)^{(d - k - 3)/2}. The exponent is nonnegative because k + 3 <= d; changing to z = (A A^T)^{-1/2} y turns the inner integral into sqrt(det(A A^T)) times a bounded function of z on the unit ball, so it is at most c_{d,k+1}^{p-1} det(A A^T)^{-(p-1)/2} for a finite normalizing constant. Gram-Schmidt writes sqrt(det(A A^T)) as the product of successive perpendicular lengths of the k + 1 independent Gaussian rows; those lengths live in dimensions d, d - 1, ..., d - k, every one of which exceeds p - 1 because k + p + 1 < d. A Gaussian perpendicular length in dimension at least p has a finite inverse moment of order p - 1, so iterating conditional expectation makes the double integral L finite. On the right side of the identity the number L equals (2 pi)^{-(k+1)(p-1)/2} times the total mass of Gamma_{k+1,d}^{F_u}, which is one, times integral J(u)^{-(k+1)} P^{tensor p}(du); hence this inverse moment is finite.

The fibers and their label densities are explicit when P is uniform on the sphere, and this explicit form is the object the displayed identity integrates. Fix an integer 1 <= r <= d - 2 and let X be an r-by-d matrix of full row rank; write Gamma_{r,d} for the law of such matrices with independent standard Gaussian entries. Let rho_{0,r}(X, y) be the density at the label y in R^r of X s for s uniform on S^{d-1}, and let mu_{X,y} be the conditional law of s given X s = y. With X-plus = X^T (X X^T)^{-1}, on the open ellipsoid where ||X-plus y|| < 1 the conditional law is uniform on the sphere centered at X-plus y, of radius sqrt(1 - ||X-plus y||^2), inside the affine space parallel to ker X, and the label density is

  rho_{0,r}(X, y) = C_{d,r} (1 - ||X-plus y||^2)^{(d - r - 2)/2} / sqrt(det(X X^T)),  for ||X-plus y|| < 1,

and zero otherwise, where C_{d,r} = Gamma(d/2) / (pi^{r/2} Gamma((d - r)/2)). This constant is the reciprocal of the mass that the projection assigns to the unit ball, so rho_{0,r} integrates to one.

One line verifies the shape. Write a sphere point in orthogonal row and null coordinates as (u, sqrt(1 - ||u||^2) theta), with u in R^r and theta on the unit sphere of the (d - r)-dimensional kernel. The null-space scaling multiplies the surface element by (1 - ||u||^2)^{(d - r - 1)/2}. The Gram determinant of the derivatives in the r row directions equals (1 - ||u||^2)^{-1/2}, and the row and null tangent directions are orthogonal, so the two factors combine. Changing the row coordinates from u to y = X s introduces the constant Jacobian sqrt(det(X X^T)), and the power simplifies to (d - r - 2)/2. When P is standard Gaussian on R^d instead of the sphere, s has no bounded support and the same sandwich of the label by the row map applies, with the fiber carrying a Gaussian rather than a spherical measure; every estimate in the identity and in the inverse-volume bound treats the two base laws together.

For the replica experiment the likelihood of the tuple has a closed form, because the equal-label identity converts the fiber likelihoods into the constrained Gaussian matrix law. Suppose a full-row-rank X and a signal s are present, the prior law of s has density f_A with respect to P given an analysis variable A, and rho_A is the conditional label density. Define

  rho_A(X, y) = rho_{0,k}(X, y) * int f_A(s) mu_{X,y}(ds)

when rho_{0,k}(X, y) > 0 and the integral is finite, and rho_A(X, y) = 0 on rank failures or on unused fibers where the integral is infinite. The product 0 * infinity never occurs. Let pi_A be the law of (s_1, ..., s_p, X) under the replica construction, and let lambda be the probability measure mu^{⊗ p}(ds) gamma_{k, B_s}(dX), defined arbitrarily on the null set where J = 0. Then pi_A is absolutely continuous with respect to lambda and

  d pi_A / d lambda (s, X) = (2 pi)^{-k (p-1)/2} J(s)^{-k} * prod_{i=1}^p f_A(s_i) / rho_A(X, X s_1)^{p-1}.

The multiplier is zero unless J > 0 and the denominator is finite and positive.

The proof inserts the bounded truncation of the multiplier prod_i f_A(s_i) / rho_A(X, y)^{p-1} into the equal-label identity with r = k, applies monotone convergence, and reads the left side as the actual label law rho_A(X, y) dy followed by p normalized posterior draws. The right side becomes the displayed ratio relative to lambda. No bounded-posterior property of f_A is used; the only geometric input is the identity for the base law P.

Logarithmic integrability is checked before any entropy difference is taken. Because s_i has density f_A given A,

  int f_A (log f_A)_- dP <= 1/e,

and this with finiteness of the conditional relative entropy gives averaged absolute integrability of log f_A(s_i). For almost every (A, X), the positive part of log(g(y) / rho_A(X, y)) against rho_A(X, y) dy is at most 1/e for standard Gaussian density g on R^r, and the negative part of log rho_A(X, Y) is integrable because -log g(Y) = (r/2) log(2 pi) + ||Y||^2 / 2 with E||Y||^2 = r. Setting Z = (2 pi)^{-k(p-1)/2} int J^{-k} d mu^{⊗ p}, which is finite and positive, and defining Q by density (2 pi)^{-k(p-1)/2} J^{-k} / Z relative to lambda, gives pi_A << Q with the same null sets. The log likelihood log Z + sum_i log f_A(s_i) - (p-1) log rho_A(X, Y) then has an integrable positive part and a negative part of integral at most 1/e, so full integrability of log rho_A(X, Y) follows without using log J. The extra-moment bound allows exponential tilting in (log J)_-, and Hadamard's ineuality gives (log J)_+ <= (p-1) log 2 because every chord has length at most two.

The likelihood formula yields the information that one uniformly selected posterior draw carries. For i >= 2 put delta_i = dist(s_i, aff(s_1, ..., s_{i-1})), the distance from s_i to the affine span of its predecessors, and Delta_i = max(0, log(r_A / delta_i)); set Delta_1 = 0. Gram-Schmidt gives J = prod_{i=2}^p delta_i. The likelihood formula makes the tuple marginal absolutely continuous with respect to mu^{⊗ p}, so every delta_i is positive almost surely, and delta_i <= 2. Taking logarithms of the likelihood, discarding X by data processing, and conditioning on the block destination w adds at most log W, where W bounds the destination alphabet. The product-reference chain rule for a p-fold product gives

  E D(L(s | A, w) || mu^{⊗ p}) <= log W + p D(A) + (p-1) E[-log rho_A(X, Y)] - (k(p-1)/2) log(2 pi) - k E log J,

which is finite by the likelihood integrability. The label entropy is bounded by the cross entropy with the Gaussian density of N(X c_A, r_A^2 I_k), because the conditional signal law is supported in B(c_A, r_A) and freshness gives E(||Y - X c_A||^2 / r_A^2 | A) <= k. Hence

  E[-log rho_A(X, Y)] <= (k/2) log(2 pi) + k E log r_A + k/2.

Substituting this and log J = sum_i log delta_i, and using log(r_A / delta_i) <= Delta_i so that k E log r_A - k E log delta_i <= k E Delta_i, gives

  E D(L(s | A, w) || mu^{⊗ p}) <= log W + p D(A) + (k(p-1)/2) + k E sum_i Delta_i.

Now draw I uniform on {1, ..., p}, independent of everything, use s_I as the signal for the next block, and set A_* = (A, w, I, s_1, ..., s_{I-1}). The triple (s_I, A, w) has the original (S, A, w) law, because each draw has that marginal and I is independent. This finite relative entropy also makes each conditional coordinate law, given its predecessors, absolutely continuous with respect to mu. The product-reference chain rule and uniformity of I give the exact identity D(A_*) = (1/p) E D(L(s | A, w) || mu^{⊗ p}). Dividing the last display by p and using (p-1)/p <= 1,

  D(A_*) <= D(A) + (log W)/p + k/2 + k E Delta_I.

The bound holds for the selected draw, not for every fixed draw, and the conditional law of s_I given A_* is absolutely continuous with respect to P.