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.

./steinhardt-duchi-2015.pdf
./steinhardt-valiant-wager-2016.pdf
./raz-2016.pdf
./raz-2017.pdf
./dagan-kur-shamir-2019.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.

./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. Watanabe's early information-theoretic treatment of multivariate correlation provides useful context for why a single finite message cannot carry the whole sample history.

./watanabe-1960.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}^{⊗t}(du) dy
    = (2 pi)^{-k m/2} integral J(u)^{-k} mu^{⊗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)^{⊗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}^{⊗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}^{⊗t}(du) equals p_A^0(y)^t (prod_i f(u_i)) P_{A,y}^{⊗t}(du) because the tilted density h_A(y)^t cancels against the t denominators of mu_{A,y}^{⊗t}. Thus inserting prod_i f(u_i) into the test, which the right side does automatically through mu^{⊗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^{⊗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^{⊗p}(du); hence this inverse moment is finite.