1 Exact observations and finite memory
An exact linear equation carries arbitrarily fine information. Indeed, d independent Gaussian equations determine an unknown vector in \R^d almost surely if all the equations can be retained. A learner that reads the equations once and remembers only a finite state faces a different problem. Increasing the required accuracy can force it to read more equations even when every equation is noiseless.
Definition 1.1 (Finite-state Gaussian regression). Fix integers d\ge2, M\ge0, and T\ge0. A data-independent shared seed may choose the learner’s rules; the descriptions of its transitions and output below are conditional on that seed. A signal s\in S^{d-1} is chosen before sampling. At sample index t\in\{1,\ldots,T\}, the observation is
where the rows x_1,\ldots,x_T are independent. A learner reads the pairs once, in order. After each number of samples its persistent state belongs to a prescribed set of at most 2^M elements. The initial state and shared seed are jointly independent of the signal and all rows, but may depend on each other. Conditional on the seed and state, a transition may use the entire current pair and fresh randomness, with unrestricted computation, but only the next finite state is retained.
The learner may stop, including before the first sample, but must stop by the prescribed deterministic finite horizon T. At a stopping index its unit output \widehat s\in S^{d-1} is generated from the terminal state, the stopping index, and fresh randomness only. In particular, a discarded observation cannot be read again by the output rule. The transitions and stopping rules may depend on d, the requested accuracy \epsilon, and the index, but not on s.
The experiment must be jointly measurable in the signal, the complete pre-generated rows, the shared seed, the initial state, and all fresh transition and output randomness. Conditional on the seed, each fixed state/index transition and stopping probability must be Borel in (x,y), or measurable in the completion of \lambda_1(dx,dy)=\gamma_1(dx)\,dy, where \gamma_1 is standard Gaussian probability on \R^d. Fresh randomness supplies no information about the signal or samples beyond the permitted rule arguments. Accuracy means
The state bound measures bits, not real registers. The rules can be nonuniform in the dimension and sample index, and randomization is allowed both in choosing the rules and during the run. The model fixes the rows in advance through their independent Gaussian law: it does not allow a learner to choose a row or revisit an earlier one.
Write \sigma_d for uniform probability on S^{d-1}. Our main statement assumes success only after averaging over this prior.
Theorem 1.2 (Memory and precision). For every fixed finite A>0, there are constants c_A>0 and d_A such that the following holds. Let d\ge d_A, let 0\le M\le Ad^2 be an integer, and let 0<\epsilon\le1/10. For any learner in Definition 1.1, draw S\sim\sigma_d independently of the rows and the learner’s data-independent randomness. If
then its prescribed horizon satisfies
Here and throughout the paper logarithms are natural unless a base is shown. The constants in Theorem 1.2 may depend on the fixed number A. The statement makes no uniform claim when A=A(d) tends to infinity. No relation between \epsilon and M is assumed.
Corollary 1.3 (Subquadratic memory). Let M(d)\ge0 be integer-valued with M(d)=o(d^2), and let 0<\epsilon(d)\le1/10 be any accuracy sequence. A family of learners in Definition 1.1 with uniform-sphere average success at least 2/3 satisfies
for all sufficiently large d, where c>0 is absolute. The dimension threshold may depend on the memory sequence.
Corollary 1.4 (A guarantee for every signal). The conclusions of Theorem 1.2 and Corollary 1.3 also hold when their average-success assumption is replaced by
where this probability is over the rows and the learner’s randomness.
The every-signal consequence follows by averaging the same learner over \sigma_d; it does not say that every individual signal is hard for every learner. We prove Theorem 1.2 and both corollaries after completing the backward argument in Section 6.
The original experiment and measurable versions. All success probabilities refer to the original jointly measurable experiment. Joint independence of the initial state and seed from the signal and rows permits conditioning on the seed without changing the prior or supplying information through initialization. Section 5 replaces completed-measurable rules by Borel versions separately for almost every seed, preserving the corresponding prior success probabilities. Their average is taken in the original experiment; no jointly measurable choice of all these versions is assumed.
1.1 The precision problem and its predecessors
Memory constraints in statistical learning were studied before this precision question. Shamir’s finite-message framework included bounded-memory online processing as a special case [11, Section 2, Definition 1]. In its general form a protocol may retain an entire transcript, so its per-message budget is not a bound on total persistent memory. Steinhardt and Duchi proved memory-dependent minimax risk bounds for sparse noisy regression [14, Section 1.1, Equation (2)]. Their hard family uses positive noise and a different covariate distribution. These works established that information retained from earlier samples can be a statistical resource in its own right.
Steinhardt, Valiant, and Wager connected memory, communication, and statistical queries, and formulated a quadratic-memory versus exponential-sample question for parity learning [15, Section 1.1, Conjecture 1]. Raz proved the qualitative separation for parity [9, Theorem 1 and Remark 1.1] and developed a spectral method for a wider class of learning problems [10]. The qualifier qualitative matters: Raz’s theorem and the published conjecture have different numerical memory coefficients. These discrete results explain the usefulness of finite-width computation models, but they do not supply an estimate for exact real-valued observations.
Among the sources discussed here, the closest continuous-regression comparison is due to Sharan, Sidford, and Valiant [12]. Their Theorem 1 uses independent N(0,I_d) covariates, a fixed unit target, and independent uniform additive noise of half-width 2^{-d/5}. With at most d^2/4 bits and Euclidean accuracy \epsilon=d^{-r}, it gives an \Omega(d\log r) sample lower bound for r from a sufficiently large absolute constant up to order d/\log d, in the range stated there. Their proof experiment draws the target uniformly on the sphere and averages over it and the samples [12, Section 2]. Their nonuniform finite-width layered program is a predecessor of the model above; the measurable randomized rules and bounded stopping used here are handled directly in Section 5.
The observation law is the important difference. A lower bound with additive noise does not by itself bound the more informative exact experiment. Theorem 1.2 treats the exact-observation precision question for isotropic Gaussian rows. Section 1.1 of [12] asks whether the first-order sample dependence on precision is optimal under bounded memory. This is distinct from its separate condition-number conjecture for ill-conditioned Gaussian laws and constant Euclidean accuracy in [12, Section 1.1].
Dagan, Kur, and Shamir obtained related quadratic-space obstructions for two other linear-prediction tasks [1]. Their published Theorem 3 asks for a unit approximate null vector of independent Gaussian rows. Their Theorem 10 asks for small empirical residual on a finite random-order system built from jointly conditioned sphere rows and one fixed equation. These are different targets and observation laws from the fixed-signal stream considered here.
A consequence for the noisy experiment. Theorem 1.2 implies an \Omega_A(d r\log d) sample lower bound in the noisy Gaussian experiment of Sharan, Sidford, and Valiant [12], for every fixed finite A>0, memory M\le Ad^2, and Euclidean accuracy e=d^{-r} in their fine-accuracy range described above, for sufficiently large d. Here success is at least 2/3 averaged over the uniform-sphere target, and learners retain the state, deterministic-horizon, randomness, and joint and per-seed measurability conventions of Definition 1.1, with a terminal estimate V\in\R^d depending only on the terminal state, stopping index, and fresh randomness. An exact-observation learner generates the prescribed independent uniform noise inside each current-pair transition and simulates the noisy learner with the same states and horizon. For completed rules, the noisy pair law has a density with respect to \lambda_1, so the Borel-version and seed-conditioning argument of Section 5 applies before this simulation. On \|V-S\|\le e\le1/20, normalizing V gives angular error at most \arcsin e\le2e; assign any unit output when V=0. Theorem 1.2 at accuracy 2e therefore gives T\ge c_A d\log(1/(2e))=\Omega_A(d r\log d).
1.2 Why the precision scale is natural
With real registers, the classical Kaczmarz projection step [7], in the form stated by Strohmer and Vershynin [16, Algorithm 1], gives a simple benchmark. Starting with z_0=0, use
and set z_t=z_{t-1} on the Gaussian-null event x_t=0. For u_t=x_t/\|x_t\|, the error is multiplied by I-u_tu_t^{\mathsf T}. The direction u_t is fresh and uniform on the sphere, so \E(u_tu_t^{\mathsf T})=I_d/d. Conditional on the previous error,
Induction gives
This calculation explains the scale d\log(1/\epsilon) for fresh isotropic observations. Strohmer and Vershynin’s theorem concerns norm-weighted sampling from a fixed finite matrix; the equality above is the separate symmetry calculation for this stream. The displayed update stores real scalars and supplies no finite-bit upper bound.
1.3 A backward proof under the original prior
Conditioning the uniform prior on one raw exact observation almost surely confines the signal to a hyperplane section of the sphere. That conditional law is singular relative to the original spherical measure. We instead keep the original prior fixed and study the probability of future success from a prescribed state.
Start the learner at a chosen state and index, whether or not the state was reached in an actual run. Let h(s) be its success probability with signal s, using fresh future samples. For a closed Euclidean ball B(z,r), our invariant is
The number R bounds the concentration of successful signals; it is not a radius supporting a posterior. A terminal output rule has R=\epsilon. Moving backward across a block of order d observations multiplies R by at most a constant for fixed M/d^2. Constant average success requires R bounded below, so reaching it from \epsilon takes order \log(1/\epsilon) blocks.
The bound at every radius makes this iteration close. Restrict h\,d\sigma_d to a ball B(z,r), without conditioning on reaching a state or dividing by the restricted mass. This finite measure has an ambient ball bound H t^\beta, with \beta=(d-1)/2 and H controlled by R^\beta. The general projection estimate in Section 3 gives the joint law of a Gaussian matrix and its exact labels an L^q density whose norm is bounded by
for a block of m\le q rows, where q is proportional to d. The density loses a radius power. The volume of the common projected ellipsoid is at most e^{Cd}r^m, and its power 1-1/q restores exactly that loss in Hölder’s inequality.
The geometric step controls inverse distances to affine spans, hence an inverse Gram determinant. Local growth and inverse-distance averaging belong to the classical projection methods represented by Mattila [8, Lemma 5.1 and Theorem 5.4]; the independent-copy expansion and successive orthogonalization have a closer regression predecessor in [12, Section 7, Lemma 12]. We derive the exact multirow density and its quantitative bounds here. Its finite-measure formulation does not require a density relative to spherical area.
Section 4 combines the projection and volume bounds with a second application of Hölder on the N possible destinations. Selection costs N^{1/q}, so taking the (d-1)/2-th root in (3) gives the memory contribution \exp(O(\log N/d^2)). Section 5 constructs fresh continuation functions, counts only stopping indices within one block, and passes from Borel rules to the full randomized model. Reflection across the span of the observed rows gives the independent constant-accuracy endpoint in Section 6, completing the theorem.
The general projection estimate also applies to a lower-dimensional cube prior on the sphere. That application has its own distributional precision bound; the conclusion throughout the stated accuracy range uses an every-signal guarantee and the separate uniform-sphere endpoint. The appendices give distinct exact-label interfaces, compare coefficient normalizations through one backward bound, and retain a sharper full-data residual estimate.
2 Local mass of terminal success
At a terminal state, the output law is independent of the unknown signal. A small spherical ball has small uniform mass, and the same is true of the set of signals close to a fixed output. Combining these two facts initializes the bound that will be propagated backward.
Write \sigma=\sigma_d, and let B(z,r) denote a closed Euclidean ball in the ambient space of its center. Vector norms are Euclidean, and \|A\|_{\op} is the Euclidean operator norm. Constants denoted by C are positive and absolute and may increase between displays. For the main proof set
We work in sufficiently large dimension that q\ge2, q\ge d/16, and a\ge d/3. These are absolute dimension requirements. The real number a is a local-mass exponent, whereas the integer q is a projection-moment order.
For R>0, say that a measurable h:S^{d-1}\to[0,1] has local mass at scale R if
The scale is an upper-bound parameter; it is not a support radius.
Lemma 2.1 (Spherical balls and terminal outputs). For d\ge2, z\in S^{d-1}, and r>0,
Consequently, if Q is any probability law on S^{d-1} independent of the signal and
then h has local mass at scale R=\epsilon:
Proof. For 0<r\le1, rotate z to the north pole and write n=d-1. A point of S^{d-1}\cap B(z,r) has last coordinate at least 1-r^2/2\ge1/2. On the upper hemisphere the surface-area element as a graph over the first n coordinates is the reciprocal of that last coordinate, hence at most two on this cap. Its projection is contained in the n-ball of radius r. The full sphere has area at least twice the volume of the unit n-ball, since both hemispheres project onto that ball with area element at least one. The ratio is at most r^n. For r>1, the total mass one gives the same inequality.
If the angular distance from a fixed unit output v is at most \epsilon, its chordal distance is 2\sin(\theta/2)\le\theta\le\epsilon. Thus the global successful mass for v is at most \epsilon^n. Integrating this inequality against Q gives the same global bound for h. Independently, 0\le h\le1 and (6) give local mass at most r^n. Therefore
where the last inequality follows by considering r\le\epsilon and r\ge\epsilon.
The two bounds play different roles: r^{d-1} controls concentration in a small region, and \epsilon^{d-1} controls the total successful mass. Their geometric mean has the same exponent in r and \epsilon, which is the form preserved by one block.
3 Exact Gaussian projection
A block of exact equations acts on a localized part of each continuation’s successful mass. We prove its projection bound for an arbitrary finite measure with controlled mass in every ambient ball. Keeping the coefficient and support radius visible will expose the cancellation in the block estimate. The same theorem will later apply to a prior supported on a lower-dimensional part of the sphere.
For a positive integer m, let \gamma_m be the law of an m-by-d matrix with independent standard Gaussian entries, and set
For a finite nonnegative Borel measure \mu, let \eta_\mu be the image of \gamma_m(dA)\mu(ds) under (A,s)\mapsto(A,As). The matrix remains part of the observed data; no normalization of \mu is made. The integer m counts rows, while p below is a density moment order. Write v_m for the unit m-ball volume. For a closed support ball B(z,R), define
The exact image is carried by \mathcal E_{z,R}. This set is Borel: it is the zero set of the continuous function (A,y)\mapsto\min_{\|v\|\le R}\|y-Az-Av\|. Changing (A,y) changes this minimum by at most \|y-y'\|+\|A-A'\|_{\mathrm{op}}(\|z\|+R).
In this section H is a local-mass coefficient and R is the geometric radius of a supporting ball. This use of R is separate from the propagated scale in (5).
Theorem 3.1 (Exact projection density from an ambient ball bound). Let d,m\ge1 and p\ge2 be integers, and let \beta>m+p-2, H,R>0, and z\in\mathbb R^d. Suppose that \mu is a finite nonnegative Borel measure supported on B(z,R) and satisfying
For 0\le j\le p-2, put
and define
Then \eta_\mu has a nonnegative jointly Borel density F with respect to \lambda_m, which can be chosen to vanish outside \mathcal E_{z,R}, and
Projection loses m(1-1/p) powers of the support radius. The volume of the projected ball will restore exactly this power. We prove the theorem by controlling inverse affine distances, expanding a smoothed density moment, and then removing the smoothing on matrix–label space. The independent-copy moment and successive orthogonalization have a close predecessor in the noisy regression analysis of [12, Section 7, Lemma 12]. That result treats a one-row noisy interval under a global L^2 density condition; here the input is local growth, and the output concerns several rows and exact labels.
3.1 Affine distances and the Gram determinant
Proposition 3.2 (Affine-distance and Gram bounds). Under the assumptions of Theorem 3.1, use the factors J_j defined there. If L is an affine j-plane with 0\le j\le p-2, then, for 0<t\le R,
For a tuple (s_1,\ldots,s_p), let V=[s_2-s_1,\ldots,s_p-s_1]. The matrix V has full column rank for \mu^{\otimes p}-almost every tuple, and
The integrand in (14) may be assigned any value on the null set of rank-deficient tuples.
Proof. The local growth hypothesis is of Frostman type, and inverse-distance averaging is a classical projection method; compare [8, Lemmas 3.5 and 5.1, pp. 230–231 and 236]. Here we retain the coefficient and radius throughout the calculation.
The orthogonal projection of B(z,R) onto L lies in a j-dimensional ball of radius R. A maximal t-separated set in that ball is a t-net and has at most (1+2R/t)^j\le(3R/t)^j points, by comparing disjoint balls of radius t/2 with the ball of radius R+t/2. When j=0, use its single point. Every point of B(z,R) at distance at most t from L is within 2t of a net point. Applying (9) to these ambient balls proves (12). Since \beta-j>0, letting t\downarrow0 also gives \mu(L)=0.
The total mass is at most HR^\beta. Integrating the elementary identity for an inverse power up to radius R, and using Tonelli’s theorem, gives
The denominator is positive by the stated hypothesis on \beta. This proves (13).
If p-1>d, then d\le p-2; applying the tube estimate to L=\mathbb R^d and letting t\downarrow0 shows that \mu=0. The Gram conclusion is then immediate. Otherwise, the nullity of affine planes of dimensions at most p-2 shows by successive integration that s_i lies outside \operatorname{aff}(s_1,\ldots,s_{i-1}) for almost every tuple and every 2\le i\le p. Hence V has full column rank almost everywhere. Gram–Schmidt orthogonalization gives, on this set,
The product of the corresponding positive heights is (p-1)! times the (p-1)-simplex volume. Related simplex-volume factors occur in Drury’s affine-plane Jacobian [2, Lemma 1, pp. 497–498]; its normalization and exponent differ from this Gaussian calculation.
Integrate first in s_p, then in s_{p-1}, and continue down to s_2. At the s_i step the preceding affine span has dimension i-2 almost everywhere, so (13) contributes J_{i-2}HR^{\beta-m}. The final s_1 integral contributes at most HR^\beta. All integrands are nonnegative, and Tonelli’s theorem therefore justifies this order and proves (14).
3.2 Smoothing and exact labels
Let \phi_\delta be the N(0,\delta^2I_m) density on \mathbb R^m. We first record the Gaussian identity for all tuples, including rank-deficient ones.
Lemma 3.3 (Gaussian difference identity). Let d,m\ge1 and k\ge2 be integers, let \delta>0, and let t_1,\ldots,t_k\in\R^d. Put D=[t_2-t_1,\ldots,t_k-t_1]. If A has law \gamma_m, then
If D has full column rank, the right side is at most (2\pi)^{-m(k-1)/2}\det(D^{\mathsf T}D)^{-m/2}.
Proof. Let \eta_1,\ldots,\eta_k be independent N(0,\delta^2I_m) vectors. For fixed A, integrating the product over the common location y gives the density at zero of the k-1 differences
Indeed, the linear change from k vectors to the first vector and these differences has determinant one. After averaging over A, each of the m rows is a centered Gaussian difference vector with covariance
The m row vectors are independent. Evaluating their joint density at zero gives (15). For fixed \delta>0, the conditional difference densities are continuous and bounded uniformly in A, so their averaged value at zero equals the value of the averaged density. The covariance is positive definite even when D is rank deficient.
If G=D^{\mathsf T}D is positive definite and B is positive semidefinite, then \det(G+B)=\det G\,\det(I+G^{-1/2}BG^{-1/2})\ge\det G. Apply this with B=\delta^2(I+\mathbf1\mathbf1^{\mathsf T}).
Lemma 3.4 (Gaussian smoothing with the full mass factor). Under the assumptions of Theorem 3.1, use the scale \mathcal B from (10). Let \phi_\delta be the N(0,\delta^2I_m) density and put
Then F_\delta is jointly Borel, and, with V=[s_2-s_1,\ldots,s_p-s_1],
Proof. The defining integrand is nonnegative and Borel, so its parameter integral is Borel. Expand the pth power and use Tonelli’s theorem. The general Gaussian difference identity (15), with k=p, m rows, and the tuple s_1,\ldots,s_p, gives the displayed equality. In particular the common first noise contributes \delta^2\mathbf1\mathbf1^{\mathsf T}, and the prefactor is (2\pi)^{-m(p-1)/2}.
On the full-rank tuples of Proposition 3.2, adding the positive definite noise covariance can only increase the determinant. Indeed, for positive definite G and positive semidefinite Q, \det(G+Q)=\det(G)\det(I+G^{-1/2}QG^{-1/2})\ge\det(G). The rank-deficient tuples have product measure zero. The bound now follows from (14) and the definition of \mathcal B.
To pass from the uniform moment bound to exact observations, we use the following compact-test form of L^p duality.
Lemma 3.5 (A density from compactly supported tests). Let E be a Euclidean space, let \lambda be a locally finite, sigma-finite Borel measure on E, and let \eta be a finite nonnegative Borel measure on E. Suppose p>1, U\ge0, and
Then \eta=f\lambda for a nonnegative f\in L^p(\lambda) with \|f\|_p\le U.
Proof. The locally finite Borel measures here have Radon extensions [13, Corollary 2.11]; on Euclidean space these are the completions of the Borel measures. On the completion of \lambda, the space C_c(E) is dense in L^{p/(p-1)}(\lambda) [4, Proposition 416I]. The assumed functional extends by continuity to that space. Real L^p duality [3, Theorem 244K] gives a representing f\in L^p(\lambda) of norm at most U.
Choose a Borel representative of f [3, Section 241B(k)]. Hölder makes f^+\lambda and f^-\lambda finite on compact sets. Their Radon extensions obey
Radon measures are determined by these tests [4, Proposition 416E(b)]. The two measures therefore agree. Evaluating on the Borel set where f<0 gives f^-\lambda=0, and then \eta=f\lambda.
Proof of Theorem 3.1. For a real \psi\in C_c(\mathbb R^{md}\times\mathbb R^m), let Z\sim N(0,I_m) be independent. Then
by bounded convergence, since \mu is finite. Hölder’s inequality and Lemma 3.4 bound the limiting functional by \mathcal B\|\psi\|_{L^{p/(p-1)}(\lambda_m)}. The measure \lambda_m is locally finite and \sigma-finite Borel, and \eta_\mu is finite nonnegative Borel. Applying Lemma 3.5 with U=\mathcal B gives (11). Choose a Borel representative and multiply it by the indicator of \mathcal E_{z,R}. The image measure is supported on the Borel set \mathcal E_{z,R}, so its nonnegative density vanishes almost everywhere outside that set.
Corollary 3.6 (Normalized exact projection). Use the parameters in (4), and let 1\le m\le q. Let \nu be a finite nonnegative Borel measure of mass at most one, supported on the unit ball in \mathbb R^d, such that
The image of \gamma_m(dA)\nu(dt) under (A,t)\mapsto(A,At) has a nonnegative jointly Borel density f_\nu relative to \lambda_m, and
The constant is independent of \nu and m.
Proof. The zero measure is immediate. Any ambient ball of radius \rho with positive mass contains a support point, and is contained in the ball of radius 2\rho about that point. Hence its mass is at most (2\rho)^a. Apply Theorem 3.1 with \beta=a, p=q, H=2^a, and support radius R=1. For 0\le j\le q-2, the parameters in (4) give
Thus J_j\le\exp(Cd), and the stated norm bound follows.
3.3 The common projected support
A density bound alone cannot control a bounded routing function over all label space. We also need a common support of controlled average volume. The exact image ellipsoid supplies it.
Lemma 3.7 (Exact projected volume, including short blocks). Let 1\le m\le d, z\in\mathbb R^d, and R>0. Use the Borel set \mathcal E_{z,R} from (8). There is an absolute C_{\mathrm E}\ge1 such that, for a standard Gaussian m-by-d matrix,
Every density of the exact image of a measure supported on B(z,R) vanishes almost everywhere outside \mathcal E_{z,R}.
Proof. The image measure is carried by \mathcal E_{z,R}, which proves the support assertion.
Almost surely A has full row rank. In singular-value coordinates, A B(0,R) is an ellipsoid whose semiaxes are R times the m singular values of A. Its volume is therefore exactly v_mR^m\sqrt{\det(AA^{\mathsf T})}. Hadamard’s inequality bounds the square root by the product of the row norms: Gram–Schmidt replaces each row norm by the length of its component perpendicular to the preceding rows, which can only decrease it. Those rows are independent and each has expected norm at most \sqrt{\mathbb E\|a_i\|^2}=\sqrt d, giving the first inequality. Also
which proves v_m\le(2\pi e/m)^{m/2}.
To see uniformity for short blocks, put t=m/d\in(0,1]. Since t\log(1/t)\le1/e,
This supplies an absolute C_{\mathrm E} in (20). For any full-block choice m=p with d/16\le p\le d, one can instead use d/p\le16 directly to obtain
4 One block of arbitrary computation
Fix an incoming state and a block of m Gaussian rows. Its complete exact data are (A,As). Suppose the block routes to one of N destinations and destination j has future success function h_j(s). We allow the route to use the whole real-valued block and fresh randomness. This is at least as much within-block access as the streaming learner has.
Lemma 4.1 (Backward block bound). Let 1\le m\le q and N\ge1. Suppose the measurable functions h_1,\ldots,h_N:S^{d-1}\to[0,1] have local mass at a common scale R>0, as in (5). Let g_j:\R^{m\times d}\times\R^m\to[0,1] be Borel routing probabilities with \sum_{j=1}^N g_j\le1, and define
Then, for every z\in S^{d-1} and r>0,
Equivalently, h has local mass at scale
Proof. Fix z\in S^{d-1} and r>0, and let \mu_j=\ind_{B(z,r)}h_j\sigma. This is a finite Borel measure supported on B(z,r). If an ambient ball B(x,t) has positive \mu_j-mass, choose a point of its intersection with the sphere. The intersection is contained in a sphere-centered ball of radius 2t. The local bound therefore gives
Apply Theorem 3.1 with exponent \beta=a, moment order p=q, coefficient H=(2R)^a, and support radius r. The margin (19) shows that every J_\ell\le\exp(Cd) for 0\le\ell\le q-2. Absorbing 2^a, we obtain exact joint densities f_j, all supported on \mathcal E_{z,r}, with
These represent unnormalized successful mass, not posteriors conditioned on a reached state.
Put q'=q/(q-1). The exact image-measure identity and two applications of Hölder give
The first inequality acts on matrix–label space; the second acts on the finite set of destinations. Since 0\le g_j\le1 and \sum_jg_j\le1, the last integral is at most
by Lemma 3.7. Multiplication by its 1/q'=1-1/q power restores the radius exponent:
Absorbing the absolute exponential factor proves (22), and taking the a-th root gives (23).
The localization radius does not change the scale: its loss in the density bound cancels its gain in the projected volume. Only the absolute density and volume constants, and the finite choice of destinations, contribute to the update. Figure 1 displays this cancellation.
Figure 1: The backward block estimate separates the exact projection density from its common support volume. Hölder combines their radius powers to recover r^a, while the routing constraint charges N^{1/q} for the number of destinations. Absolute constants C may change between bounds.
In particular, if \log N\le d^2, then (23) gives R'\le KR for an absolute K: the bounds a\ge d/3 and q\ge d/16 make both terms in Cd/a+(\log N)/(aq) absolute. This form applies to the local alphabet whenever \log((q+2)2^M)\le d^2.
For the local count N\le(m+2)2^M that will be proved in the next section, (23) gives
This is where quadratic memory enters: q\asymp d divides the logarithm of the number of choices, and a\asymp d converts mass growth into scale growth.
5 From one block to a finite stream
The block estimate applies to the success function obtained by starting the learner from a specified state. We first construct these fresh continuations and show that a block has only a bounded number of possible destinations. This count will let us propagate the local bound (5) backward through the stream.
For now fix the shared rule seed and suppose that all finite transition and stopping kernels are Borel and defined at every input pair. Future rows and fresh random choices are independent of the past. We take the action at the horizon to be terminal from every state. Section 5.2 justifies these conventions for the full randomized, completed-measurable model of Definition 1.1, without changing its prior expected terminal score.
5.1 Fresh continuations and local destinations
Write Q_t for the set of persistent states at sample index t, with |Q_t|\le2^M. For each terminal state w\in Q_k, write \mathsf Q_{k,w} for its output probability law on S^{d-1}; with the seed fixed, this law depends only on k,w. Fix a Borel terminal score \ell:S^{d-1}\times S^{d-1}\to[0,1]. Starting from a specified state u\in Q_t before its sample-free stopping check, define h_{t,u}(s) to be the expected terminal score \mathbb E[\ell(s,\widehat s)] with signal s and fresh future samples and randomness. This definition also applies to states the original run never reaches.
A block from index t to index t+m includes the stopping check at its entrance. An active exit is cut before the check at t+m, which the continuation performs. A terminal tag produced by the last transition has already stopped at t+m. These phase conventions use only the state and the index.
Lemma 5.1 (The destinations of a block). For a fixed-seed Borel learner with the state sets, output laws, and phase convention just specified, and the Borel terminal score \ell, let 0\le t<T, u\in Q_t, and 1\le m\le T-t. There are an integer
Borel routing functions g_j:\mathbb R^{m\times d}\times\mathbb R^m\to[0,1] with \sum_jg_j\le1, and Borel functions h_j:S^{d-1}\to[0,1] such that, for every s\in S^{d-1},
Here \gamma_m is the law of an m-by-d standard Gaussian matrix. Each destination is either a terminal state w\in Q_k at an index k\in\{t,\ldots,t+m\}, with score function
or a continuing state w\in Q_{t+m} before its stopping check, with score function h_{t+m,w}(s). The terminal output law \mathsf Q_{k,w} depends only on its state and index. The value g_j(A,b) is the probability of destination j when the block data are (A,b).
Proof. The everywhere-defined kernels and the forced terminal action at T give a finite scored experiment from every specified state. Its score function is Borel in the signal. Indeed, the map (s,x)\mapsto(x,\langle x,s\rangle) is continuous, and each path probability is a finite product of Borel coordinate probabilities. Summing over the finitely many paths and integrating against the fixed laws of future rows preserves Borel measurability. The same argument applied to \ell(s,v) and each fixed output law shows that h^{\mathrm{out}}_{k,w} is Borel. The integration fact follows first for indicators of rectangles and then for nonnegative Borel functions by the monotone class theorem and monotone convergence; see also the composition of kernels in [5, Section 2.3].
Pre-generate all m rows of the block, including those after an early stop. At each k=t,\ldots,t+m-1, perform the sample-free stopping check and, if still active, process the next pair through the transition to k+1. A terminal tag from that transition stops at k+1. An active exit from the final transition is passed to the continuation before the stopping check at t+m, so that check is performed exactly once. If t+m=T, the continuation performs the forced terminal action.
A terminal destination records its local stopping offset i\in\{0,\ldots,m\} and its terminal state in Q_{t+i}. The offset i=0 includes an immediate stop, and i=m can arise from the last transition. A transition tag and a sample-free stop at the same state and index have the same output law, so their outcomes can be merged. Continuing destinations form one additional copy of Q_{t+m}, distinguished from the terminal destinations at that index. Consequently the number of destinations is at most
The block’s entrance index is fixed, so local offsets determine all absolute stopping indices; the count has no factor depending on T.
For arbitrary data (A,b), each destination probability g_j(A,b) is a finite sum over paths of products of Borel coordinate probabilities. It is therefore Borel. The probabilities are nonnegative and sum to one when all destinations are included. A path that stops early is simply independent of the unused rows. After a continuing destination is fixed, independent future rows and fresh choices give its prescribed continuation score. After a terminal destination is fixed, the prescribed output law gives its terminal score. Conditioning first on the block data and then on its destination proves (25). Because the kernels are defined everywhere, this equality holds for every signal and every starting state, rather than only at states reached by the original run.
The angular and chordal success scores are, respectively,
Both are Borel. The backward induction below uses the angular score.
5.2 Borel versions and the original randomized experiment
The fresh continuations require kernels defined even at inputs and states absent from the original run. The model permits transition coordinates measurable in a completed sigma field. Under a dominated fresh-pair law, these coordinates admit everywhere-defined Borel versions that preserve the prior experiment. The following statement keeps the prior general for the later cube application.
Lemma 5.2 (Borel versions under a dominated sample law). Let d\ge2, let \pi be a Borel probability measure on S^{d-1}, and let X\sim\gamma_1=N(0,I_d) be independent of S\sim\pi. Suppose that
on \mathbb R^d\times\mathbb R. Fix an integer horizon T\ge0 and finite state sets at every sample index. For each state and index, suppose every coordinate of the finite vector of transition and stopping probabilities is measurable in the \lambda-completion of the Borel sigma field. A terminal output law is a Borel probability measure on S^{d-1} indexed only by its terminal state and stopping index. Decisions made without a new sample also depend only on the state and index.
There are everywhere-defined Borel transition and stopping kernels, with the same state sets and terminal output laws, whose \pi-prior joint law of the signal, state path, stopping index and output is the same as for the original rules. The domination (26) holds when \pi=\sigma is uniform spherical probability, for every d\ge2.
Proof. We first construct versions for a fixed set of rules. If f:\mathbb R^d\times\mathbb R\to[0,1] is measurable in the \lambda-completion, each dyadic superlevel set \{f\ge k2^{-n}\}, 1\le k\le2^n, agrees with a Borel set outside a Borel \lambda-null set, by the description of completion in Tao [17, Exercise 1.4.26]. Replace these superlevel sets by their Borel representatives in
The resulting Borel functions have a Borel \limsup equal to f outside the union of the countably many null sets, since f_n\to f. Thus each coordinate of each finite kernel has a Borel version. For one state and index, choose all of its coordinate versions simultaneously. The Borel set on which the resulting vector is not nonnegative with sum one is null; on this set replace the vector by a fixed point mass. The result is a Borel probability vector at every sample pair. There are finitely many coordinates, states and indices, so one Borel \lambda-null set Z contains every pair where any coordinate was changed. Sample-free decisions and terminal output laws require no such modification.
Pre-generate all T input rows, including rows after an early stop. Every pair (X_t,\langle X_t,S\rangle) has the marginal law in (26), so
For a state u chosen from earlier observations, the event that the learner is in u before sample t and this pair lies in Z is a subset of the displayed null event. We do not need a density for a sample conditioned on a particular state. A finite union over t shows that no changed pair is visited almost surely. Couple the original and modified finite choices by the same uniform random numbers. Starting from the same initial state, induction makes their states and stopping decisions equal almost surely. At an equal terminal state and index the output laws are identical, so use their diagonal coupling. This proves the asserted joint-law equality. When T=0 there is no sample pair to modify and the same conclusion is immediate.
It remains to check the spherical prior. Conditional on a nonzero X=x, rotate coordinates so that x/\|x\| is the first coordinate vector. Write a uniform sphere point as G/\|G\| for a standard Gaussian vector G=(G_1,G_\perp). When d\ge2, R=\|G_\perp\|>0 almost surely and is independent of G_1. For each fixed R>0, the map
is a smooth strictly increasing bijection from \mathbb R to (-1,1) with nonzero derivative. The image of the Gaussian law of G_1 therefore has a Lebesgue density. Mixing over R and then multiplying by \|x\| shows that \langle x,S\rangle is absolutely continuous for every x\ne0. The point x=0 has \gamma_1-measure zero. Fubini’s theorem applied to the sections of a \lambda-null Borel set now proves (26).
The equality in Lemma 5.2 concerns the experiment under the chosen prior. It need not preserve behavior at every exceptional individual signal. In particular, an every-signal success premise will be averaged over the prior before versions are chosen.
We now return to the model’s original jointly measurable randomized experiment. Fix any Borel prior \pi satisfying (26), and draw the signal from \pi independently of the rows and the model’s data-independent randomness. The preceding lemma supplies the domination condition for the uniform-sphere prior. Write W for the shared rule seed, taking W constant when no seed is used, and I for its initial state. The observable signal, rows, state path, stopping index, and output take values in standard Borel spaces. For a Borel terminal score \ell, its original conditional expectation is a measurable function of W and integrates to the mixed expected score. Since (I,W) is jointly independent of the signal and all pre-generated rows, conditional on almost every W=w those inputs retain their joint law and I is independent of them. The dependence allowed between I and W does not affect this conclusion.
Fix such a seed value for which the model’s per-seed kernel hypotheses also hold. Lemma 5.2 replaces its completed transition and stopping coordinates by everywhere-defined Borel kernels while preserving the original conditional \pi-prior law. Keep its terminal output laws. At index T, force the sample-free action to stop at every state, retaining each prescribed state/index output law. Assign a fixed unit output only where no law was specified, a case absent from original terminating paths. This does not change the original conditional experiment, which already stops by T. It makes the horizon convention in the continuation construction valid even at states absent from that experiment.
The preceding continuation lemma now applies to this fixed-seed Borel learner with any Borel terminal score \ell. A numerical score bound uniform over its initial states can be averaged against the conditional law of I. If the bound is also uniform in the fixed seed, the final seed average uses the original conditional expected scores. Borel versions may be chosen separately for each seed; no jointly measurable choice of these replacements is required.
5.3 The quantitative success bound
We apply the block bound to the fresh continuations just constructed. At every step, all terminal destinations have the original terminal local bound, and all continuing destinations have the inductive bound at that boundary. The following statement records the resulting finite-horizon estimate before we extract the sample lower bound.
Proposition 5.3 (Success after a bounded number of samples). There are absolute constants C,d_0>0 with the following property. For d\ge d_0, every learner in the stated finite-state model with M\ge0 bits and an integer deterministic horizon T\ge0 has, for S\sim\sigma independent of its fresh Gaussian rows,
where 0<\epsilon\le1/10 and a=(d-1)/2, q=\lfloor(d-1)/8\rfloor as in (4). The probability includes data-independent initialization, the shared seed, and fresh random choices.
Proof. Use the angular score in Lemma 5.1. Fix a seed and a prior-preserving Borel replacement as in Section 5.2, with prior \sigma. If T=0, its output is a signal-independent mixture of terminal laws. Lemma 2.1 gives local mass at scale \epsilon. The radius-two ball about a sphere point covers S^{d-1}, so total success is at most (2\epsilon)^a, as required when \lceil T/q\rceil=0. We may now suppose T\ge1.
Increase the absolute threshold d_0 so that q\ge2, q\ge d/16, and a\ge d/3. Partition the T sample indices into B=\lceil T/q\rceil consecutive nonempty blocks, each of length at most q. At the final boundary every continuation is a terminal output function and obeys (5) at scale \epsilon. Suppose that at the end of one block, all continuing functions obey that bound at a common scale R\ge\epsilon. Its terminal destinations also obey the bound at scale R, by Lemma 2.1 and monotonicity in the scale.
For a block of length m\le q, Lemma 5.1 places every preceding continuation in the form required by Lemma 4.1, with N\le(m+2)2^M\le(q+2)2^M. That block lemma multiplies the scale by at most
for an absolute C_0. Its logarithm is at most
where d/a\le3, 1/(aq)\le48/d^2, and \log(q+2)/(aq)\le48\log(d+2)/d^2 allow an absolute C. Backward induction gives (5) at scale R=\epsilon e^{\Lambda B} for every initial state. Averaging over the conditional initial-state law preserves this bound, because that law is independent of the signal and rows. Taking the radius-two ball gives total success at most (2\epsilon e^{\Lambda B})^a, and a probability is also at most one.
By the reduction in Section 5.2, this is a uniform bound on the original conditional success probabilities for almost every seed. Averaging them proves (27); no joint choice of the Borel replacements is used.
6 Constant accuracy and the main lower bound
Rounding the horizon up to a whole number of blocks loses less than one block. At fine accuracy this loss is negligible. For the remaining accuracies, even an estimator retaining all the data needs a linear number of equations. Reflection across their row span proves this without identifying the full conditional law of the signal.
Lemma 6.1 (Reflection with full data). Let d\ge1 be an integer and T\ge0. Let S be uniform on S^{d-1}. Let a matrix A with d columns, independent of S, have row span U of dimension at most T. Suppose an output \widehat S is drawn from a probability kernel depending only on (A,AS). Put u=P_US and v=(I-P_U)S. For an arbitrary output in \mathbb R^d and 0<\epsilon<1,
More generally, for 0<b_0<1 and 0\le\epsilon<\sqrt{1-b_0},
For a unit output one also has
Proof. The projection P_U is a Borel function of A, since P_U=\lim_{\eta\downarrow0}A^{\mathsf T}(AA^{\mathsf T}+\eta I)^{-1}A; for a matrix with no rows it is zero. Conditional on A, reflection across U sends S=u+v to u-v. It preserves uniform spherical measure and the data (A,AS), because Av=0, so the output kernel is the same at both signals. If \|v\|>\epsilon, the reflected signals have distance greater than 2\epsilon; a fixed estimate can succeed for at most one of them. Averaging the common output kernel over the reflected pair gives success at most one half on this event. On its complement use the bound one. Therefore
Spherical isotropy and independence of A give
Markov’s inequality proves (29). The same pairing on the event \|u\|^2<b_0, where \|v\|>\sqrt{1-b_0}>\epsilon, proves (30). For unit outputs, reflection cancels \mathbb E\langle\widehat S,v\rangle, whereas \langle\widehat S,u\rangle\le\|u\|. Cauchy–Schwarz and the same second-moment identity prove (31).
For almost every fixed shared seed, use the prior-preserving Borel rules justified in Section 5. Pre-generate all T Gaussian rows and grant the learner the full matrix and labels. After averaging its signal-independent initial state and fresh choices, its stopped output law is a Borel kernel of those data. Angular error at most \epsilon implies Euclidean error at most \epsilon. If T\le d/4 and \epsilon\le1/10, then (29) gives success probability at most
This uniform bound also holds for the original conditional success probabilities and hence for their average over the seed. Thus any learner with the stipulated average success must satisfy
Proof of Theorem 1.2. Fix the finite constant A>0 in the theorem. Take d above the absolute threshold in Proposition 5.3, and large enough that a\ge1 and q\ge d/16. Put
where C is the absolute constant in that proposition. Since M\le Ad^2 and prior success is at least 2/3,
Taking the ath root gives \epsilon K_A^B\ge1/3. Since B\le T/q+1,
Let H_A=2(\log3+\log K_A). If L\ge H_A, this gives
If L<H_A, (32) instead gives T>d/4>dL/(4H_A). Thus the same choice
works uniformly over 0<\epsilon\le1/10 and M\le Ad^2 for this fixed A. No positive constant uniform as A tends to infinity is asserted.
Proof of Corollary 1.3. Since M(d)=o(d^2), there is a dimension d_M after which M(d)\le d^2. Apply Theorem 1.2 with the numerical choice A=1 at every d\ge d_M, so K_1=e^{2C} in the preceding proof. Its constant c_1 is absolute, and the eventual dimension threshold may depend on the memory sequence through d_M. The argument applies separately at every accuracy 0<\epsilon(d)\le1/10, so it requires neither monotonicity of that sequence nor a relation between memory and accuracy.
Proof of Corollary 1.4. Average the original fixed-signal experiment over S\sim\sigma before choosing Borel versions. Its measurability makes the resulting success probability the integral of the fixed-signal success probabilities. A success probability at least 2/3 for every signal therefore gives uniform-prior success at least 2/3. Theorem 1.2 and Corollary 1.3 give the corresponding conclusions with their unchanged constants and dimension thresholds. Lemma 5.2 preserves the average used in those arguments even if a version changes behavior at exceptional individual signals.
7 Selection on a common data domain
The two applications use the same analytic selection step: several continuation measures are supported on one data domain, and a measurable route chooses among them. The strong density estimate of Theorem 3.1 is sufficient, but a bound for measurable tests already gives the required N^{1/p} cost.
We state this common step before applying the projection theorem to a lower-dimensional cube prior in Section 8. The later sections examine additional exact-label interfaces and alternative coefficient normalizations; they do not assert a stronger main theorem.
Lemma 7.1 (Selection on a common data domain). Let (E,\mathcal E,\lambda) be a measure space, let \mathcal D\in\mathcal E have finite measure, let p>1, let U\ge0, and let N\ge1 be an integer. Suppose finite nonnegative measures \eta_1,\ldots,\eta_N are supported on \mathcal D, and that for every measurable 0\le g\le1,
For measurable routes g_j\ge0 with \sum_jg_j\le1,
A sufficient condition for (34) is \eta_j=f_j\lambda, where f_j\ge0 vanishes outside \mathcal D and \|f_j\|_{L^p(\lambda)}\le U.
In particular, if r>0, m,\beta\in\R, and positive constants H,V,L satisfy
then the right side of (35) is at most
Proof. Each g_j lies in [0,1]. Put b_j=\int_{\mathcal D}g_j\,d\lambda. Equation (34) and Hölder on the finite index set give
Since \sum_jg_j\le1, we have \sum_jb_j\le\lambda(\mathcal D), proving (35). Under the density condition, Hölder gives
because 0\le g\le1. Finally the powers of r in the two assumed bounds add to \beta, giving (36).
The test formulation accommodates a direct open-set limit even when one chooses not to infer a strong L^p density from that limit. The density formulation applies to the other passages. In both cases, the reference measure and the common support must be the ones specified by the corresponding projection estimate.
8 A paired-coordinate cube application
The exact-density theorem for finite measures also applies to a prior supported on a lower-dimensional subset of the sphere. We illustrate this with a cube embedded by coordinate pairs. Its first coordinates transfer the local mass bound to ambient Euclidean balls, and its Lipschitz bound supplies a common support for the projected labels. These are the hypotheses needed by the general projection and selection estimates.
The resulting success bound concerns the cube prior. It gives a sample lower bound at fine accuracy from cube-average success alone. To cover the remaining accuracies for a learner that succeeds at every unit signal, we use the uniform-sphere endpoint from the main proof.
8.1 The prior and its terminal mass
Let d\ge16 be an integer, set n=\lfloor d/2\rfloor, and give
Lebesgue probability measure du. The cube has volume one. Define
with d-2n zero coordinates. Each coordinate pair contributes 1/n to the squared norm, so \iota(Q)\subset S^{d-1}. The signal prior is \iota_\#du.
Write \operatorname{pr}:\mathbb R^d\to\mathbb R^n for projection onto the first n coordinates. Then \operatorname{pr}\iota(u)=u/\sqrt n. On [-1/2,1/2], the derivative of a\mapsto\sqrt{1-a^2} has absolute value at most 1/\sqrt3. The mean value theorem therefore gives
Set
For z\in\mathbb R^n and r>0, abbreviate
where B_j(x,t) is the closed Euclidean ball in \mathbb R^j. The local bound for a function f:Q\to[0,1] will be
We will propagate the coefficient L backward through the stream.
Fix a terminal state and stopping index, after fixing the independent rule seed. Its output law is independent of the signal. Let f_{\rm term}(u) be the probability that this output has angular error at most \epsilon at \iota(u). For a fixed unit output \widehat s, angular error at most \epsilon implies chordal error at most \epsilon. Projection onto the first coordinates then gives
Let \omega_j be the volume of the unit ball in \mathbb R^j. The Gaussian integral gives \omega_j j^{j/2}\le(2\pi e)^{j/2}: integrate e^{-\|x\|^2/2} over the ball of radius \sqrt j and compare with its integral over \mathbb R^j. The successful part of \mathcal B(z,r) lies in two parameter balls, so its volume is at most the smaller of their volumes. With C_0=\sqrt{2\pi e}, the terminal success function consequently satisfies
The last inequality uses \alpha+\beta=n; the same estimate for a random output follows by integration against its signal-independent law.
8.2 Transferring local mass to the embedded measure
Let \gamma_k be the law of a k-by-d matrix with independent standard Gaussian entries, and put
The following specialization supplies both the exact density and its common support. A parameter function measurable in the Lebesgue completion can first be replaced by a Borel version under du, without changing any local integral.
Lemma 8.1 (Exact density and a common projected ellipsoid). Let k be an integer with 1\le k\le p, and let a Borel function f:Q\to[0,1] satisfy (40) with L\ge0. For z\in\mathbb R^n and r>0, define the finite joint measure
for Borel E\subseteq\mathbb R^{k\times d}\times\mathbb R^k. There is a universal C_2\ge1 such that \eta_{f,z,r}=h_{f,z,r}\lambda_k for a nonnegative density with
If \mathcal B(z,r)\ne\varnothing, fix any u_*\in\mathcal B(z,r) and set
Every such density, for this same z,r,u_*, vanishes almost everywhere outside \mathcal E_{u_*,r}, and
Proof. An empty \mathcal B(z,r) gives the zero measure. Otherwise fix u_*\in\mathcal B(z,r), and let
For any x\in\mathbb R^d and t>0, projection onto the first coordinates gives
For u\in\mathcal B(z,r), the distance from u to u_* is at most 2\sqrt n\,r. Thus (38) puts \mu inside B_d(\iota(u_*),4r).
If L=0, (40) applied to a ball containing Q gives f=0 almost everywhere, and the zero density suffices. Suppose now that L>0. Apply the general finite-measure result Theorem 3.1 with
For its factors J_j, the required margin and their uniform bounds are
In particular \beta>k+p-2. We use the general parameter range of that theorem, not the specialization to exponents near half the ambient dimension. Its exact norm bound is
The first factor is at most one, each J_j\le C^n, and 0<\beta-k(1-1/p)\le\beta. Absorbing 4^{\beta-k(1-1/p)}\le4^\beta into C_2^n proves (43). This is the density of the exact joint measure (42); no density relative to spherical area is assumed.
The set \mathcal E_{u_*,r} is the exact projected image of the enclosing ball B_d(\iota(u_*),4r). Lemma 3.7 makes this set Borel and gives the asserted common support. The same lemma gives
after one universal increase of C_2, since d\le2n+1 and k\le n/4. This calculation also covers the zero-density case.
8.3 The block bound and the streaming consequence
The power of r lost in the density norm is restored by the common support volume. Selection then costs only the pth root of the number of continuations.
Corollary 8.2 (A block on the paired-coordinate prior). Let k,N be integers with 1\le k\le p and N\ge1, and let Borel f_1,\ldots,f_N:Q\to[0,1] satisfy (40) with the same L\ge0. Suppose Borel functions g_v:\mathbb R^{k\times d}\times\mathbb R^k\to[0,\infty) obey \sum_{v=1}^N g_v(A,y)\le1. Then
satisfies (40) with C_3^nN^{1/p}L in place of L, for a universal C_3\ge1.
Proof. Fix z,r. An empty \mathcal B(z,r) is immediate. Otherwise choose the same u_*\in\mathcal B(z,r) for all v. The exact joint densities from Lemma 8.1 share its region \mathcal E_{u_*,r}. Apply Lemma 7.1 with density norm at most C_2^nLr^{\beta-k(1-1/p)} and domain measure at most C_2^nr^k. The image-measure identity and that lemma give
The radius powers cancel, and the same C_3 works for every 1\le k\le p.
To apply this bound to the model’s completed-measurable rules, first observe that f=1 satisfies
Take k=1 in Lemma 8.1 and a parameter ball containing Q. The fresh pair (X,\langle X,\iota(u)\rangle), for u\sim du, is therefore absolutely continuous relative to \gamma_1(dx)\,dy. We may consequently use the seedwise Borel reduction and fresh-state continuations of Section 5.2 under this cube prior. As there, the conditional numerical estimates are averaged using the original measurable experiment; no jointly chosen family of Borel replacements is required.
Proposition 8.3 (Precision bound for the cube prior). There are universal constants D\ge e, d_0\ge16, and c>0 with the following property. Let d\ge d_0, M\ge0, and T\ge0 be integers, with M\le d^2 and 0<\epsilon\le1/10. Every learner in Definition 1.1 with these memory and sample bounds has angular success probability under s=\iota(u), u\sim du, at most
The probability averages over u, the fresh Gaussian samples, and the learner’s randomness. If that same learner has angular success probability at least 2/3 for every s\in S^{d-1}, then
Proof. Use the seedwise convention just established, and first start from any prescribed initial state. For T>0, partition the stream into m=\lceil T/p\rceil consecutive blocks, each of length at most p=k_0. Lemma 5.1, with angular terminal score and signal \iota(u), represents the preceding success function by the exact block formula in Corollary 8.2. For a block of length k, its Borel routes have at most
destinations. The stopping offsets are local to this block, including an immediate stop; its continuing functions use fresh future samples. These are the same phase and terminal-state conventions as in that lemma.
For n\ge8, p\ge n/8, d\le2n+1, and M\le d^2,
with a universal C_4. Choose a universal D\ge e so that D\ge C_0 and C_3^nN^{1/p}\le D^n. The terminal coefficient is C_0^n\epsilon^{n/4} by (41). Backward induction, applying the block bound and retaining the terminal estimate at earlier stops, gives coefficient
for every initial state. The ball \mathcal B(0,1) contains Q, so this coefficient bounds total cube-average success. For T=0, the terminal bound gives the same statement with m=0. All constants are uniform over the seedwise Borel rules and prescribed states. The independent conditional initialization and the averaging of original conditional success probabilities from Section 5.2 therefore prove (49) for the original learner, including every short last block.
Suppose now only that the cube-average success is at least 2/3. Taking natural logarithms in (49) and using m\le T/k_0+1 gives
If \log(1/\epsilon)\ge24\log D, its right side is at least \log(1/\epsilon)/(8\log D). Since k_0\ge n/8 and n\ge d/3, this already gives T\ge d\log(1/\epsilon)/(192\log D) in that accuracy range.
For the all-accuracy conclusion (50), assume the stated every-signal guarantee. It gives the cube-average premise just used. It also gives uniform-sphere average success at least 2/3 for the same original learner. The reflection consequence (32) therefore forces T>d/4. For \log(1/\epsilon)<24\log D, this implies
Combining the two ranges proves (50), for example with c=1/(192\log D), after increasing the universal dimension threshold as needed. The memory condition M\le d^2 in particular holds eventually for every sequence M(d)=o(d^2).
8.4 An affine-distance interpretation
The application is complete. The embedding also gives a direct interpretation of the Gram moment behind its projection bound. This alternative calculation isolates what the first coordinates guarantee about affine spans. For u,u_1,\ldots,u_j\in Q, j\ge1,
Indeed, for \sum_i c_i=1, projection of \iota(u)-\sum_i c_i\iota(u_i) is (u-\sum_i c_i u_i)/\sqrt n. Projection cannot increase norm, and taking the infimum proves the claim, including dependent points.
Lemma 8.4 (Affine inverse moments). Let f:Q\to[0,1] be Borel and satisfy (40) with L\ge0. Let k be an integer with 1\le k\le p, and let V\subseteq\mathbb R^n be a nonempty affine subspace of dimension j\le p-2. There is a universal C_1\ge1 such that, for every z\in\mathbb R^n, r>0, and 0<t\le1,
The second integrand is nonnegative and extended-valued on V.
Proof. The cases L=0 and an empty parameter ball are immediate as above. Apply Proposition 3.2 in parameter dimension n to \mathbf1_{\mathcal B(z,r)}f(u)\,du, with
The growth hypothesis follows because a parameter ball of radius a>0 is \mathcal B(x,a/\sqrt n) after intersection with Q. Its tube bound, evaluated at \sqrt n\,tr, is
Its inverse-distance bound is J_jLn^{-k/2}r^{\beta-k}. Multiplication by n^{k/2} gives the normalization in (55). The bounds (47) absorb both constants into a universal C_1^n.
For example, let G be the Gram matrix of the p-1 differences \iota(u_i)-\iota(u_1), 2\le i\le p. Almost every parameter tuple is affinely independent, since proper affine subspaces of \mathbb R^n have zero Lebesgue measure. Writing V_{i-1}=\operatorname{aff}(u_1,\ldots,u_{i-1}), Gram–Schmidt and (53) give
Integrating in the order u_p,\ldots,u_2, followed by u_1, therefore yields
Thus one can also obtain the projection bound by inserting this Gram estimate into the Gaussian difference identity and compact-test passage of Section 3. The main application instead uses the general finite-measure theorem through the ambient ball bound (46).
An enclosing-ball alternative. The common ellipsoid may instead be enclosed in the larger label ball
Thus every density in Lemma 8.1, with the same z,r,u_*, also vanishes almost everywhere outside \{(A,y):y\in\mathcal R_A\}. Its volume has the bound
after a universal increase of C_2, where |\mathcal R_A| is k-dimensional Lebesgue volume. This estimate follows independently from the Gaussian net bound in Lemma B.3, not from the smaller ellipsoid’s volume. It gives the same block bound, although the direct proof above uses the exact projected ellipsoid and does not require this enlargement.
A Other exact-label interfaces
Theorem 3.1 supplies the strong joint L^p density used in both applications. We now separate three additional conclusions that need not be built into that theorem. A direct difference-kernel argument proves the measurable-test estimate needed for selection without using compact-test duality. For spherical restrictions, joint L^1 convergence identifies the limiting density; a specified pointwise version works for every full-row-rank matrix, rather than only almost every matrix.
We retain the notation \eta_\mu,\lambda_m,\mathcal E_{z,R} of Section 3 and the exact norm scale \mathcal B in (10). The coefficient H controls mass in all ambient balls, while R is the radius of a supporting ball; neither measure is normalized to a posterior.
A.1 A direct bound for measurable tests
Proposition A.1 (A direct inequality for measurable tests). Under the assumptions of Proposition 3.2, the exact image measure satisfies
for every Borel set E of finite \lambda_m-measure. In particular \eta_\mu\ll\lambda_m, and the same inequality holds on the \lambda_m-completion after extending \eta_\mu to that completion. For every \lambda_m-completed-measurable 0\le\varphi\le1,
An infinite integral on the right is allowed.
Proof. Let \rho_\delta=(v_m\delta^m)^{-1} \mathbf1_{B(0,\delta)} be the uniform probability density of the radius-\delta ball in \mathbb R^m, and set U_\delta(A,y)=\int\rho_\delta(y-As)\,d\mu(s). After translating the common label variable by As_1, the tuple kernel in its pth moment becomes
It is nonnegative, and Tonelli’s theorem gives the exact normalization
In particular the kernel depends on A only through the differences; no independence of As_1 from those differences is used.
For a full-rank V, the rows of AV are independent centered Gaussian vectors with covariance V^{\mathsf T}V. Their joint density has supremum (2\pi)^{-m(p-1)/2}\det(V^{\mathsf T}V)^{-m/2}. Multiplying this density by the unit-mass kernel (61) bounds the expected tuple kernel by that supremum. Expand \int U_\delta^p\,d\lambda_m, discard only the product-null rank exceptions, and apply (14). This gives
The measure \lambda_m is Borel and finite on compact sets in a Euclidean space. The Radon extension theorem [13, Corollary 2.11] applies and gives outer regularity on Borel sets. If O is open, then for each (A,As)\in O, all sufficiently small label perturbations remain in O. Fatou’s lemma followed by Hölder’s inequality gives
For a Borel E with finite \lambda_m(E), take open supersets whose \lambda_m-measures decrease to \lambda_m(E). The last inequality proves (59). Applied to null sets, it gives \eta_\mu\ll\lambda_m. Extending \eta_\mu by zero on \lambda_m-null sets gives the asserted version on the \lambda_m-completion.
The measure \eta_\mu is supported on the Borel set \mathcal E_{z,R}. If \int_{\mathcal E_{z,R}}\varphi\,d\lambda_m<\infty, apply (59) to \{\varphi>t\}\cap\mathcal E_{z,R} for t>0. Layer cake and concavity of x^{1-1/p} yield
which is (60). The case of an infinite right side is immediate. This proof supplies the measurable-test estimate directly; it does not infer a strong L^p bound from the set inequality alone.
A.2 Spherical absolute continuity and compatible fibers
The remaining constructions use an additional hypothesis: \mu\ll\sigma_d and m<d. It provides absolute continuity for each full-row-rank matrix separately. This hypothesis is not needed by the general finite-measure theorem or the preceding direct-test bound.
Lemma A.2 (Absolute continuity of spherical projections). Let d\ge2 and 1\le m<d. If A:\mathbb R^d\to\mathbb R^m has full row rank, then A_\#\sigma_d is absolutely continuous with respect to Lebesgue measure. The same holds for A_\#\mu whenever \mu is a finite Borel measure with \mu\ll\sigma_d.
Proof. Rotate the row space of A to the first m coordinates. The restriction of A to that row space is an invertible map onto \mathbb R^m, so it suffices to consider the orthogonal projection onto those coordinates. Write a uniform sphere point as
where Z and W are independent standard Gaussian vectors in \mathbb R^m and \mathbb R^{d-m}. Almost surely c=\|W\|>0. Conditional on c, the projection is the image of Z under
This is a smooth diffeomorphism from \mathbb R^m onto the open unit ball; its inverse is u\mapsto cu/\sqrt{1-\|u\|^2}. Thus the conditional projection law has a Lebesgue density, and integrating in c preserves absolute continuity. Applying the invertible row-space map proves the assertion for A_\#\sigma_d. Absolute continuity of A_\#\mu follows from \mu\ll\sigma_d.
A second proof by hemisphere graphs. The two open hemispheres of S^{d-1} are the graphs
Their surface-area element is (1-\|x\|^2)^{-1/2}dx, and the omitted equator has surface measure zero. Projection of \sigma_d onto the first d-1 coordinates therefore has a Lebesgue density. Integrating that density in the last d-1-m coordinates proves the same for projection onto the first m coordinates. Rotation, the invertible row-space map, and \mu\ll\sigma_d finish the argument as in the first proof.
Lemma A.3 (A joint density and its fibers). Let d\ge2, 1\le m<d, and let \mu be a finite nonnegative Borel measure with \mu\ll\sigma_d. Then \eta_\mu has a nonnegative jointly Borel density F(A,y) with respect to \lambda_m. For \gamma_m-almost every A, F(A,\cdot) is a density of A_\#\mu.
If \mu is supported on B(z,R), the density can be chosen to vanish outside the Borel set \mathcal E_{z,R}\subseteq\mathcal S_{z,R} defined in (8).
Proof. For a Borel set E in the matrix–label space, put E_A=\{y:(A,y)\in E\}. If \lambda_m(E)=0, Fubini’s theorem gives |E_A|=0 for \gamma_m-almost every A. Such a matrix has full row rank almost surely, and Lemma A.2 therefore gives (A_\#\mu)(E_A)=0. A second application of Fubini shows that \eta_\mu(E)=0. Thus the finite measure \eta_\mu is absolutely continuous with respect to the \sigma-finite measure \lambda_m. The ordinary Radon–Nikodym theorem [6, Theorem 6.27], applied on the product Borel \sigma-algebra, gives a nonnegative jointly Borel density F.
We verify that one common full-measure set of matrices has the asserted fiber property. Let \mathcal C be the countable \pi-system of half-open boxes with rational endpoints, the empty set, and \mathbb R^m itself. It generates the Borel sets of \mathbb R^m. For C\in\mathcal C and every Borel matrix set D, the density identity applied to D\times C gives
Both integrands are measurable functions of A. Since this equality holds for every D, they agree almost everywhere. Remove the union of these exceptional sets over the countable class \mathcal C. For every remaining A, the two finite measures agree on \mathcal C, and hence on every Borel set by the uniqueness theorem for measures. This proves the fiber assertion.
When \mu is supported on B(z,R), its image is carried by the Borel set \mathcal E_{z,R}. Multiplying F by the indicator of that set preserves the density identity.
A.3 Convergence and an everywhere-full-rank version
The next result asserts actual convergence in the joint L^1 space. The final proposition specifies a single Borel version whose fiber is a density for every full-row-rank matrix, with a separate Lebesgue-null exceptional set of labels allowed for each matrix.
Proposition A.4 (Joint L^1 convergence). In addition to the assumptions of Proposition 3.2, suppose that d\ge2, 1\le m<d, and \mu\ll\sigma_d. Let F be the joint density from Lemma A.3, and let F_\delta be the Gaussian regularization in Lemma 3.4. Then
Proof. For almost every A, the function F_A=F(A,\cdot) is a nonnegative L^1 density of A_\#\mu, of mass \mu(\mathbb R^d), and F_\delta(A,\cdot)=F_A*\phi_\delta. Tao’s continuity theorem for translations in L^1(\mathbb R^m) [17, Proposition 1.6.13] gives
For completeness, fix a small translation radius on which the translation norm is small. The integral inside that radius is then small, and the remaining part is at most 2\|F_A\|_1 times the Gaussian mass outside that radius, which tends to zero. This proves the displayed limit.
The fiber difference norm is at most 2\mu(\mathbb R^d). Because F and F_\delta are jointly measurable, these norms are measurable functions of A. Dominated convergence in \gamma_m therefore proves the joint L^1 limit. Choose a sequence \delta_i\downarrow0 for which \sum_i\|F_{\delta_i}-F\|_{L^1(\lambda_m)}<\infty. Tonelli’s theorem implies F_{\delta_i}\to F almost everywhere. Fatou’s lemma and (16) then give \int F^p\,d\lambda_m\le\mathcal B^p. The density identity from Lemma A.3 now applies to arbitrary bounded \lambda_m-completed-measurable functions of the exact matrix–label pair.
Proposition A.5 (A pointwise joint density version). Assume the same hypotheses as in Proposition A.4. For the Gaussian density \phi_\delta, define
where e_1 is a unit coordinate vector. This is a probability density on (0,\infty), and \phi_\delta is the corresponding mixture of uniform ball densities. Define
Then F^\sharp is jointly Borel. For every full-row-rank A, F^\sharp(A,\cdot) is a density of A_\#\mu up to a Lebesgue null set, and it is a density of \eta_\mu with respect to \lambda_m. Moreover
Proof. The negative radial derivative of the Gaussian is -\frac{d}{dr}\phi_\delta(re_1) =(r/\delta^2)\phi_\delta(re_1). Hence
This is precisely the claimed ball mixture. Integrating it in y and using Tonelli proves \int_0^\infty w_\delta(r)\,dr=1. Also w_\delta(r)=\delta^{-1}w_1(r/\delta); its probability mass therefore concentrates at radius zero as \delta\downarrow0.
Fix a full-row-rank A. Lemma A.2 gives a nonnegative L^1 density f_A of A_\#\mu. At a Lebesgue point y of f_A, its ball averages
tend to f_A(y) as r\downarrow0, by the Lebesgue differentiation theorem [17, Theorem 1.6.19]. The mixture formula gives
Given an error tolerance, choose r_0>0 such that a_r(y) is within that tolerance of f_A(y) for 0<r<r_0. For r\ge r_0, the averages are bounded by \mu(\mathbb R^d)/(v_mr_0^m). The part of the mixture on [r_0,\infty) thus tends to zero after subtracting f_A(y), while the part on (0,r_0) has the chosen error bound. It follows that F_\delta(A,y)\to f_A(y) at every Lebesgue point.
Each F_{1/i} is jointly Borel. The set where its sequence has a finite limit is Borel, so (65) is jointly Borel as well. The preceding fixed-A argument shows that its fiber is a density for every full-row-rank A, outside a null set of labels. Full row rank holds \gamma_m-almost surely, and Fubini therefore identifies F^\sharp with a joint density of \eta_\mu. Finally (F^\sharp)^p\le\liminf_i F_{1/i}^p everywhere by its definition. Fatou’s lemma and (16) prove (66).
The direct-test argument applies to the arbitrary finite measure in Proposition 3.2. The joint L^1 and pointwise constructions use the additional spherical absolute continuity, which holds for every restriction \mu=\mathbf1_{B(z,R)}h\,\sigma_d with 0\le h\le1. In each case the resulting test or density identity is for exact observations.
B Coefficient recurrences and support alternatives
The main block estimate propagated a scale inside a fixed radius power. An equivalent formulation propagates the coefficient of that power. Keeping the exponent variable makes the different terminal accuracy powers visible, while one recurrence handles all of them. The density and exact ellipsoid estimates have already been proved. We first record their spherical specialization and two optional calculations, then give the common coefficient recurrence.
Write \sigma=\sigma_d and n=d-1. For unit vectors u,v, put \operatorname{angle}(u,v)=\arccos\langle u,v\rangle. The following specialization keeps the local exponent variable while fixing a common moment order.
Corollary B.1 (The dimension-scale parameter regime). Under the hypotheses of Proposition 3.2, suppose that
Then, for every 0\le j\le p-2,
where C\ge1 is an absolute constant. Thus the right side of (14) is at most C^{d(p-1)}H^pR^{\beta p-m(p-1)}, uniformly also for short blocks m<p.
Proof. Under (67), p\le d/8 gives the displayed margin. Also m/(\beta-j-m)\le1/2, while 3^j2^\beta\le3^{d/8}2^{d/2}. Enlarging one absolute C gives J_j\le C^d, and multiplying over the p-1 values of j proves the specialization.
Here p\ge d/16 is the moment order and maximum block length, whereas m is the current number of rows. The constants below are absolute unless a dependence is stated.
B.1 Spherical restrictions and a second moment calculation
Lemma B.2 (Exact projection density from an ambient ball bound). Assume (67), and let H,R>0 and z\in\mathbb R^d. Let f:S^{d-1}\to[0,1] be Borel measurable, let \nu=f\sigma, and suppose \nu(B(x,r))\le H r^\beta for every x\in\mathbb R^d and r>0. For \mu=\mathbf 1_{B(z,R)}\nu, the pushforward A_\#\mu has, for almost every A, a Lebesgue density F(A,\cdot). There is an absolute C_{\mathrm D}\ge1 for which a jointly measurable nonnegative choice of these densities satisfies
The density represents the exact labels As.
Proof. The restriction \mu is supported on B(z,R) and inherits the all-radius bound. Theorem 3.1, together with (68), gives its strong joint L^p density and (69). The fiber identification in Lemma A.3 gives the asserted common almost-everywhere choice of projection densities.
The same bound can be obtained from ball averages with a less sharp explicit prefactor. This calculation is independent of the choice of terminal coefficient or support domain.
For \delta>0, set
These functions are jointly measurable. For almost every A they are the ball averages of the exact density F(A,\cdot); hence Lebesgue differentiation and Fubini give F^{\mathrm{ball}}_\delta\to F for \lambda_m-almost every (A,y) along \delta=1/k. In particular this limit, set to zero where it does not exist finitely, is a jointly measurable density version. Expand the pth moment and apply Tonelli’s theorem. The intersection of the p balls of radius \delta about As_1,\ldots,As_p has volume at most v_m\delta^m, and is empty unless \|A(s_i-s_1)\|\le2\delta for every i\ge2. Therefore
For a full-column-rank V=[s_2-s_1,\ldots,s_p-s_1], the rows of AV are independent centered Gaussian vectors with covariance V^{\mathsf T}V. Their joint density is bounded above by
In the difference variables AV, the event in (70) lies in the product of p-1 radius-2\delta balls in \mathbb R^m, whose m(p-1)-dimensional volume is (v_m(2\delta)^m)^{p-1}. The exceptional rank-deficient tuples are null by (14). It follows that
All factors v_m\delta^m have canceled. Combining (71) with (14), absorbing 2^{m(p-1)} into an absolute constant to the power d(p-1), and using Fatou’s lemma proves (69).
For the full-block choice \beta=(d-1)/2 and m=p=\lfloor d/8\rfloor, (71) retains the factor 2^{p(p-1)}. The margin in (68) is in particular at least d/8. Taking the pth root gives the form
For Gaussian averages no new identity is needed: (15) with k=p and (16) give the exact covariance V^{\mathsf T}V+\delta^2(I_{p-1}+\mathbf1\mathbf1^{\mathsf T}) and prefactor (2\pi)^{-m(p-1)/2}. The compact-test, joint-L^1, and pointwise passages all give the same moment estimate under their respective hypotheses. In particular, setting \beta=d/2 in (69) gives, for every 1\le m\le p,
B.2 Enclosing balls as an alternative support
The exact image domain \mathcal E_{z,R} has the volume in Lemma 3.7. The larger operator-norm ball \mathcal S_{z,R} from (8) also suffices; the following proof records its uniformity for short blocks.
Lemma B.3 (Projected support volume). For a standard Gaussian m-by-d matrix A, where 1\le m\le d,
Proof. Choose 1/4-nets of the unit spheres in \R^d and \R^m with at most 9^d and 9^m points. Approximating both arguments in the bilinear supremum loses at most \|A\|_{\op}/2, so
over the net pairs. Each scalar is standard Gaussian. For such a scalar Z, \E|Z|^m\le(C\sqrt m)^m: use |z|^m e^{-z^2/4}\le(2m/e)^{m/2} and \E e^{Z^2/4}=\sqrt2. Bounding the maximum’s m-th power by the sum gives
The unit m-ball volume v_m obeys v_m\le(2\pi e/m)^{m/2}: integrate e^{-\|y\|^2/2} over the ball of radius \sqrt m and compare with its full Gaussian integral. Multiplication cancels m^{m/2}, proving (74) uniformly even for a short block.
Since \lambda_m(\mathcal S_{z,R}) =v_mR^m\mathbb E\|A\|_{\mathrm{op}}^m, this proves
There is a second net calculation with a different explicit factor. Maximal 1/2-separated subsets of the unit spheres in \mathbb R^d and \mathbb R^m are 1/2-nets of sizes at most 5^d and 5^m. Approximating the supremum of a linear form in each argument in turn gives \|A\|_{\mathrm{op}}\le4\max|v^{\mathsf T}Au| over the net pairs. Each scalar in this maximum is a standard Gaussian Z, and
because |t|^me^{-t^2/4}\le(2m/e)^{m/2} and \mathbb E e^{Z^2/4}=\sqrt2. Bounding the maximum’s mth power by the sum therefore gives
Again multiplying by v_mR^m proves (75), with a possibly larger absolute constant. This calculation retains the 1/2-net factor 4.
B.3 Terminal coefficients
The geometric exponent \beta may be chosen before either of the following terminal estimates. The hemisphere proof keeps the explicit coefficient 4^n; the polar proof records two useful denominator bounds.
Lemma B.4 (An ambient ball bound from a hemisphere). Let d\ge2, n=d-1, and let \sigma_d be uniform probability on S^{d-1}. Then
Let \epsilon>0, let \kappa be any probability law on S^{d-1}, independent of the target, and put h(s)=\int\mathbf 1_{\{\|s-u\|\le\epsilon\}}\,\kappa(du). For 0<\beta<n, every z\in\mathbb R^d, and every r>0,
The same upper bound holds for the angular-success function, since angular distance at most \epsilon implies chordal distance at most \epsilon.
Proof. Suppose first that 0<r\le1/4 and that B(z,r) meets the sphere. Choose a point a of the intersection and rotate it to a coordinate axis. Every other point of the intersection is within chordal distance 2r of a, lies in the corresponding open hemisphere, and projects into the radius-2r ball in \mathbb R^n. On that projected ball the graph area element is at most 2, because 2r\le1/2. Thus the area of the patch is at most 2v_n(2r)^n, where v_n is the volume of the unit n-ball. The two hemisphere graphs together have area at least 2v_n. The resulting probability is at most (2r)^n, and hence at most (4r)^n. An empty intersection is harmless. For r>1/4, the bound \sigma_d(B(z,r))\le1<(4r)^n proves (77).
For fixed u, the successful part of B(z,r) is contained both in B(z,r) and in B(u,\epsilon). Apply (77) to each ball, take the smaller bound, and integrate in \kappa. Finally \min\{r^n,\epsilon^n\}\le\epsilon^{n-\beta}r^\beta, by considering r\le\epsilon and r\ge\epsilon separately.
Lemma B.5 (Polar cap estimates). Let d\ge2, n=d-1, and let \sigma be uniform on S^{d-1}. There is an absolute C_0\ge1 such that \sigma(B(z,R))\le C_0^dR^n for every ambient center z and every R>0. Let \epsilon>0. If a unit output is drawn from a law independent of the signal, its success function h(s), for either angular error at most \epsilon or chordal error at most \epsilon, satisfies
Proof. In spherical polar coordinates, the area element at polar angle t is \sin^{d-2}t\,dt times the area element on S^{d-2}. Dividing the cap area by the total area therefore shows that a cap of angular radius 0\le\theta\le\pi has mass
The numerator is at most \theta^n/n, since \sin t\le t. Restricting the denominator to two different intervals gives
Either estimate gives an upper bound C^d\theta^n for the cap.
If B(z,R) meets the sphere, choose s_0 in the intersection. Every other point in it has chordal distance at most 2R from s_0. The angle between two unit vectors is at most \pi/2 times their chordal distance. Thus their angle is at most \pi R when R\le1; for R\le1/4 the bound 2\arcsin R\le4R is also available. The cap estimate and the trivial mass bound one for R\ge1 give the asserted ambient-ball bound after enlarging C_0.
For a fixed unit output, angular error at most \epsilon implies chordal error at most \epsilon, because 2\sin(\theta/2)\le\theta. The global success mass is therefore at most C_0^d\epsilon^n, while its mass in B(z,R) is at most the ambient-ball bound C_0^dR^n. Averaging these bounds over the output law proves the minimum in (79). If R\le\epsilon, then R^n\le\epsilon^{n-\beta}R^\beta; if R\ge\epsilon, then \epsilon^n\le\epsilon^{n-\beta}R^\beta.
Lemma B.4 gives the alternative coefficient
For \beta=n/2, the looser coefficient L_0=4^d\epsilon^\beta follows immediately from (81). For \beta=d/2, (79) gives
B.4 One coefficient recurrence
Proposition B.6 (Backward coefficient step). Assume (67). Let H>0 and let N\ge1 be an integer. Let h_1,\ldots,h_N:S^{d-1}\to[0,1] be Borel functions satisfying
Let g_w(A,y)\ge0 be Borel functions with \sum_wg_w\le1, and define
There is an absolute C_{\mathrm{step}}\ge1 such that
Proof. For the fixed ball B(z,R), take \mu_w=\mathbf1_{B(z,R)}h_w\sigma in Lemma B.2. Its exact density F_w is supported on the common domain \mathcal E_{z,R} of Lemma 3.7. The image identity gives
The density condition of Lemma 7.1 applies on this domain with its norm parameter equal to
Its conclusion and Lemma 3.7 give
The maximum-density proof of the same estimate observes pointwise that \sum_wg_wF_w\le\max_wF_w and (\max_wF_w)^p\le\sum_wF_w^p, then applies Hölder on \mathcal E_{z,R}. It gives \lambda_m(\mathcal E_{z,R})^{1-1/p} (\sum_w\int F_w^p\,d\lambda_m)^{1/p}, bounded by the same expression. The radius exponents are m(1-1/p)+\beta-m(1-1/p)=\beta. The densities in this calculation represent exact observations, so the measurable routing functions are evaluated at the exact labels.
The exact density can be replaced in this step by Proposition A.1 and the test form of Lemma 7.1. For spherical restrictions, Propositions A.4 and A.5 give the same norm. Likewise, either enclosing-ball calculation can replace the exact ellipsoid volume. These choices change only the absolute constant, not the coefficient or radius powers.
Proposition B.7 (A common finite success bound). Assume d\ge16, set n=d-1, p=\lfloor d/8\rfloor, and let n/2\le\beta\le d/2. Let M,T\ge0 be integers, 0<\epsilon\le1/10, and consider a learner in Definition 1.1. Under the uniform-sphere signal prior, write P_{\mathrm{succ}} for its success probability with either angular or chordal error at most \epsilon, and put b=\lceil T/p\rceil. Then
The same assertion holds with the initial factor 4^n replaced by the polar-cap constant C_0^d.
Proof. Use the seedwise conditional experiment and Borel replacement from Section 5.2. Conditional on almost every shared seed, the initial state remains independent of the signal and rows. Lemma 5.1 supplies, from every specified boundary state, including an unreachable one, Borel routes to fresh continuations. In a block of m rows their number is at most (m+2)2^M: continuing states and terminal states tagged with one of the m+1 local stopping indices. The lemma applies to either Borel terminal score.
The terminal bound (78) starts the all-radius coefficient at H_0=4^n\epsilon^{n-\beta}. With N=(p+2)2^M, Proposition B.6 gives one recurrence for all actual block lengths 1\le m\le p:
Each multiplier is at least one, so terminal options, whose coefficient is H_0, satisfy every later bound. The ball B(0,1) contains the whole sphere; hence the initial coefficient bounds total success. Average first over the independent conditional initialization and then over the original seed experiment. As in Section 5.2, this averages original conditional probabilities and requires no jointly measurable choice of the seedwise replacements. The trivial probability bound gives the minimum with one. For T=0 this is the terminal estimate. Starting instead from (79) proves the polar version.
One may instead pad the last block of actual length m<p with independent Gaussian rows and extend each route by ignoring them. Its matrix–label marginal on the first m rows is unchanged. Thus full padded blocks give exactly the same estimate and count.
The two endpoint exponents recover the following bounds.
Corollary B.8 (Finite success bounds for the two coefficients). Assume d\ge16 and p=\lfloor d/8\rfloor. Let M,T\ge0 be integers, let 0<\epsilon\le1/10, and consider a learner in Definition 1.1 with these parameters. Draw S\sim\sigma independently of its Gaussian rows x_1,\ldots,x_T and its data-independent randomness, and set the exact labels y_t=\langle x_t,S\rangle. Write \Pr_\sigma for the resulting joint law and put b=\lceil T/p\rceil. With an absolute C_{\mathrm{step}}\ge1, the uniform-prior angular success probability satisfies
The uniform-prior chordal success probability satisfies
The second event contains the angular success event.
Proof. In Proposition B.7, set \beta=n/2 and use 4^n\le4^d for the first formula. For the second, set \beta=d/2, use the polar terminal coefficient, and enlarge the category bound to N=(2p+4)2^M. The same recurrence then reads
The final ball B(0,1) gives the second formula. Angular success implies chordal success.
C Normalizations and quantitative consequences
The common recurrence separates choices that need not be coupled: the local exponent, the exact-label passage, the common support, and the use of actual or padded blocks. This section records their substitutions and extracts the sample bounds once. Throughout, d\ge16, n=d-1, p=\lfloor d/8\rfloor, and b=\lceil T/p\rceil. The nearby integer p need not equal the moment order q used in the main proof. All success probabilities average the uniform signal, Gaussian rows, and learner randomness. A success guarantee for every signal implies these premises by averaging.
C.1 The density interfaces in the same recurrence
For n/2\le\beta\le d/2, a restricted continuation measure \mu_w=\mathbf1_{B(z,R)}h_w\sigma_d with ambient coefficient H has an exact joint density satisfying
This is Lemma B.2; the joint-L^1 or pointwise construction gives the same bound. Either \lambda_m(\mathcal E_{z,R})\le C_{\mathrm E}^dR^m or \lambda_m(\mathcal S_{z,R})\le C_{\mathrm V}^dR^m restores R^\beta in Lemma 7.1. Thus no normalization to a posterior and no repeated backward induction is needed.
Direct measurable tests. At \beta=d/2,m=p, the inverse-distance bound for an affine j-plane, 0\le j\le p-2, has the explicit form
Proposition A.1 therefore supplies the test scale C^dHR^{d/2-p(1-1/p)}, without using a strong density conclusion. The full-block volume (21) and the test form of Lemma 7.1 give the same coefficient step. The hemisphere terminal coefficient and count (p+2)2^M give (84) at this exponent, and hence the base-two bounds below for either success event.
Joint L^1 convergence. At \beta=n/2, Proposition A.4 applies for every actual row count 1\le m\le p, since \mu_w\ll\sigma_d and m<d. With the polar terminal coefficient, either support estimate and the common recurrence give
for an absolute C_{\mathrm{L1}}. Neither the quarter-net proof nor a particular polar denominator interval is required for this density passage.
Factored accuracy. Writing H=D\epsilon^{n-\beta} moves the fixed accuracy factor outside (85); the recurrence simply multiplies D by C^dN^{1/p}. For example, at \beta=n/2,m=p, the specified pointwise density of Proposition A.5 satisfies
This follows by substituting H=D\epsilon^{n/2} in (66). The corresponding inverse-distance bound is C_3^dD\epsilon^{n/2}R^{n/2-p}, with margin at least d/4. Either net volume or the ellipsoid volume cancels the negative radius power. The valid looser category count \mathcal N=2(p+1)2^M\ge(p+2)2^M consequently gives
This enlargement has no connection to the pointwise fiber quantifier; all category counts concern only local stopping offsets, not T.
C.2 One logarithmic extraction
Suppose an upper bound obtained above has the form
If P_{\mathrm{succ}}\ge2/3, taking natural logarithms and using b\le T/p+1 gives
All the exponents above satisfy \kappa=n-\beta\ge d/3. The negative constant in this inequality is the rounded-block loss. The full-data reflection estimate handles the remaining bounded logarithms; the following elementary consequences retain several useful numerical endpoints.
For a learner with a deterministic sample limit T, use the fixed-seed Borel experiment of Section 5.2. Pre-generate all T Gaussian rows and grant it the full data; its stopped output law is then a kernel of those rows and labels. Apply Lemma 6.1 conditionally and average the original conditional probabilities and expectations, as in the main endpoint argument. If its angular success probability is at least 2/3 and \epsilon\le1/10, then
Together with (31) this proves
For chordal success, T\le d/8 and b_0=3/4 in (30) give
Equivalently, Markov’s inequality bounds \Pr\{\|u\|^2\ge3/4\} by 1/6; on its complement the reflected points have distance greater than one, and at most half of that mass can succeed. The choices b_0=1/2 and T\le d/8 give 5/8. Formula (29) also shows that T\le d/5 is incompatible with success 2/3 when \epsilon\le1/10.
C.3 Explicit constants and thresholds
All statements here assume 0<\epsilon\le1/10 and success at least 2/3, with angular success sufficient whenever the displayed upper bound uses chordal success. Constants may be enlarged to cover any of the preceding density or support calculations.
Half the spherical dimension. For M\le d^2, the count satisfies
since p+2\le2^p and M/p+1\le16d+1\le32d. Choose D\ge\max\{4,e\} so that the per-block factor in (86) is at most D^d. Then
Set L=\log(1/\epsilon) and c_0=(3\log D)^{-1}. Substitution of K=D^d,\Lambda=\log D,\kappa=n/2 into (92) gives b\ge c_0L-2 and T\ge p(c_0L-3). Hence
For L<6/c_0, (93) gives T>(c_0/96)dL.
Equivalently, absorb the initial and block factors into e^{C_*d}, C_*\ge\max\{1,\log4\}. The substitution K=e^{C_*d},\Lambda=C_*,\kappa=n/2 gives
This also applies to (90) when M=o(d^2): its logarithmic category cost is o(d), so an absolute C_* works after a dimension threshold depending on that memory sequence. The direct residual estimate rules out T\le d/5 for the bounded complementary range.
Half the ambient dimension. For M=o(d^2), \log((2p+4)2^M)/p=o(d). Thus an absolute A\ge e, after an eventual dimension threshold depending on the memory sequence, gives
With a_0=(3\log A)^{-1}, substitute K=A^d,\Lambda=\log A,\kappa=d/2-1 in (92) to obtain
and therefore
For L<6/a_0, (94) forces T>d/8>(a_0/48)dL.
For the base-two form, use instead the hemisphere coefficient 4^{d-1}\epsilon^{d/2-1} and the count (p+2)2^M. When M\le d^2, an absolute C_1\ge1 bounds the block factor by 2^{C_1d}. With L_2=\log_2(1/\epsilon), the same logarithmic extraction, using 2(d-1)-\log_2(2/3)\le3d, gives
In particular,
Here L_2/3-3-C_1\ge L_2/6 and p\ge d/16. In the complementary range, the antipodal choice b_0=1/2 gives 5/8<2/3 when T\le d/8. These formulas also apply to the direct-test route above.
The accuracy-factored form. For M=o(d^2), the count in the factored recurrence obeys \mathcal N^{1/p}\le e^d eventually. For absolute constants C_4,C_5 it follows that
The second inequality is (92), with n/2\ge d/3 and the fixed \log(3/2) absorbed into C_5. Reflection gives T>d/8, and p\ge d/16 then gives T/p+2<32T/d. Consequently T\ge d\log(1/\epsilon)/(32C_5) over the entire accuracy range, without a relation between precision and memory.
For each fixed A_0>0, replacing the memory condition by M\le A_0d^2 changes only the constants and bounded-logarithm thresholds, which may depend on A_0. These arguments do not give a uniform positive constant for unbounded A_0=A_0(d).
D A sharper full-data residual bound
The reflection estimate suffices for the main theorem. The following bound gives a sharper success probability by identifying the full conditional residual sphere. It allows arbitrary data-based Euclidean outputs, including randomized ones.
Lemma D.1 (A memory-independent constant-accuracy bound). For all sufficiently large d, let 0\le T\le d/4 be an integer. Let S be uniform on S^{d-1}, let X be an independent T-by-d standard Gaussian matrix, and put Y=XS. For every 0<\epsilon\le1/10, any possibly randomized estimator W\in\mathbb R^d based on the entire pair (X,Y) satisfies
Consequently, a learner with uniform-sphere angular success at least 2/3 at accuracy \epsilon\le1/10 must have T>d/4, even with unlimited memory and access to all pre-generated samples.
Proof. Let U be the row span of X, write r=\dim U\le T, and put k=d-r. The labels determine u=P_US: the restriction of X to U=(\ker X)^\perp is injective. More explicitly, when T>0, diagonalizing XX^{\mathsf T} shows that the consistent label Y determines
This also shows that u is a measurable function of the data. The analogous limit
shows that the projection is measurable in X. For the empty horizon T=0, X has no rows and U=\{0\}, u=0. The same values hold whenever the row span is zero, including an all-zero matrix. In all these cases the residual radius \rho=\sqrt{1-\|u\|^2} equals one.
Standard Borel disintegration supplies a conditional probability kernel for the actual joint law and the Borel data map (X,S)\mapsto(X,XS) [5, Theorem 2.3]. To identify it almost everywhere, condition first on any fixed matrix X with r<d, and generate S as G/\|G\| from an independent standard Gaussian vector. Its orthogonal components G_U and G_{U^\perp} are independent. In polar coordinates on U^\perp, the Gaussian volume element factors as a constant times e^{-\varrho^2/2}\varrho^{k-1}\,d\varrho\,d\omega for \varrho>0, where d\omega is spherical area. Hence
is uniform on the unit sphere of U^\perp and is independent of (G_U,\|G_{U^\perp}\|). Here \|G_{U^\perp}\|>0 almost surely because k=d-r\ge d-T>0. The decomposition
shows that V is independent of (u,\rho) conditional on X. Since u and \rho are determined by (X,Y), the conditional law of the residual signal given the data is uniform on the sphere of radius \rho in U^\perp, for almost every data pair. When U=\{0\} this is the whole unit sphere and \rho=1. This argument uses the Gaussian direction directly, including that zero-rank case.
Independence of X and S, together with \mathbb E SS^{\mathsf T}=I_d/d, gives
Markov’s inequality therefore yields
On data with \rho\ge1/2, fix any proposed estimate w\in\mathbb R^d. If \|w-S\|\le\epsilon, orthogonal projection onto U^\perp and division by \rho imply
If this ball meets the unit sphere of U^\perp, choose a point of the intersection. The entire intersection lies in the ball of radius 2/5 about that sphere point. Lemma 2.1, applied in ambient dimension k\ge d-T\ge3d/4, bounds its conditional spherical probability by
An empty intersection has probability zero. This bound holds for each w, so it also holds after averaging any output probability kernel based on the data. Combining it with (105) proves (104) for large d. Finally, for unit vectors angular error at most \epsilon implies Euclidean error at most \epsilon, since 2\sin(\theta/2)\le\theta. Granting all pre-generated rows lets a full-data estimator simulate any earlier stopping rule, which proves the stated consequence.
References
- [1]Yuval Dagan, Gil Kur, and Ohad Shamir. Space Lower Bounds for Linear Prediction in the Streaming Model. In Proceedings of the Thirty-Second Conference on Learning Theory, pages 929–954, 2019. https://proceedings.mlr.press/v99/dagan19b.html; Theorems 3 and 10 refer to the published PMLR version.
- [2]S. W. Drury. Generalizations of Riesz Potentials and L^p Estimates for Certain k-Plane Transforms. Illinois Journal of Mathematics, 28(3):495–512, 1984.
- [3]D. H. Fremlin. Measure Theory, Chapter 24: Function Spaces. University of Essex, author-hosted online development extract. Chapter version November 15, 2013; Section 241/244 locators refer to https://www1.essex.ac.uk/maths/people/fremlin/chap24.pdf; accessed September 27, 2026.
- [4]D. H. Fremlin. Measure Theory, Chapter 41: Topologies and Measures I. University of Essex, author-hosted online development extract. Section 416 version December 28, 2017 / July 3, 2020; https://www1.essex.ac.uk/maths/people/fremlin/chap41.pdf; accessed September 27, 2026.
- [5]Nicolas Gagné and Prakash Panangaden. A Categorical Characterization of Relative Entropy on Standard Borel Spaces. Logical Methods in Computer Science, 19(4):10:1–10:18, 2023. Theorem 2.3 and Section 2.3 refer to https://arxiv.org/abs/1703.08853v6, November 8, 2023. doi:10.46298/LMCS-19(4:10)2023.
- [6]John K. Hunter. Measure Theory. Department of Mathematics, University of California at Davis, lecture notes, 2011. Theorem 6.27, pp. 75–77, refers to https://www.math.ucdavis.edu/~hunter/measure_theory/measure_notes.pdf; accessed September 27, 2026.
- [7]Stefan Kaczmarz. Angenäherte Auflösung von Systemen linearer Gleichungen. Bulletin International de l’Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, pages 355–357, 1937.
- [8]Pertti Mattila. Hausdorff Dimension, Orthogonal Projections and Intersections with Planes. Annales Academiae Scientiarum Fennicae, Series A I, Mathematica, 1(2):227–244, 1975. https://geodesic.mathdoc.fr/articles/10.5186/aasfm.1975.0110/. doi:10.5186/aasfm.1975.0110.
- [9]Ran Raz. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. 2016. https://arxiv.org/abs/1602.05161v1, version 1, 16 February 2016.
- [10]Ran Raz. A Time-Space Lower Bound for a Large Class of Learning Problems. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, pages 732–742, 2017. https://eccc.weizmann.ac.il/report/2017/020/. doi:10.1109/FOCS.2017.73.
- [11]Ohad Shamir. Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation. In Advances in Neural Information Processing Systems, pages 163–171, 2014. https://proceedings.neurips.cc/paper_files/paper/2014/hash/cc427d934a7f6c0663e5923f49eba531-Abstract.html.
- [12]Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Memory-Sample Tradeoffs for Linear Regression with Small Error. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 890–901, 2019. Full version https://arxiv.org/abs/1904.08544v2, 10 October 2020; theorem and section locators refer to that version. doi:10.1145/3313276.3316403.
- [13]Stanford Mathematics Department. Borel Regular and Radon Measures. Math 205A Lecture Supplement 4. Undated institutional course supplement; https://web.stanford.edu/class/math205a/radon-13.pdf; accessed September 27, 2026.
- [14]Jacob Steinhardt and John Duchi. Minimax Rates for Memory-Bounded Sparse Linear Regression. In Proceedings of the 28th Conference on Learning Theory, pages 1564–1587, 2015. https://proceedings.mlr.press/v40/Steinhardt15.html.
- [15]Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, Communication, and Statistical Queries. In 29th Annual Conference on Learning Theory, pages 1490–1516, 2016. https://proceedings.mlr.press/v49/steinhardt16.html.
- [16]Thomas Strohmer and Roman Vershynin. A Randomized Kaczmarz Algorithm with Exponential Convergence. Journal of Fourier Analysis and Applications, 15:262–278, 2009. Algorithm 1 and Theorem 2 refer to https://arxiv.org/abs/math/0702226v1, 8 February 2007. doi:10.1007/s00041-008-9030-4.
- [17]Terence Tao. An Introduction to Measure Theory. Graduate Studies in Mathematics 126, American Mathematical Society, 2011. Theorem and page locators refer to the author’s AMS-permitted preliminary version, https://terrytao.wordpress.com/wp-content/uploads/2012/12/gsm-126-tao5-measure-book.pdf; accessed September 27, 2026.