1 Introduction
An exact linear equation may contain arbitrarily fine real information. Indeed, d independent Gaussian equations determine a vector in \R^d almost surely, because their coefficient matrix has full rank. A streaming learner with finitely many persistent states cannot retain the equations themselves at arbitrary precision. We study how many fresh equations it needs to estimate a direction when the information passed from one observation to the next is bounded in bits.
Definition 1.1 (Finite-state Gaussian stream). Fix integers d\ge2, M\ge0, and T\ge0, and an accuracy 0<\epsilon\le1/10. For a signal s\in S^{d-1}, the observations are
with the X_t independent. The learner reads these pairs in order. At every sample index its persistent state has at most 2^M possible values. Its transition and stopping rules may depend on the index, d,M,T,\epsilon, the current state, the entire current pair, and fresh randomness. Computation within a transition is unrestricted. All information retained for a later sample must be in the finite state.
The learner stops at an index \tau\in\{0,\ldots,T\} and returns \widehat s\in S^{d-1}. Its output law depends only on the terminal state, \tau, and fresh randomness. Thus the last pair affects the output only through the terminal state.
A shared random seed may choose the rules before the stream starts. The pair consisting of this seed and the initial state is jointly independent of the signal and all sample rows; in particular, conditional on the seed, initialization carries no signal or sample information. Conditional on the seed, fresh transition and output randomness has no additional signal or sample information, and the rules have only the arguments just listed.
The original randomized experiment is required to be jointly measurable in the signal, pre-generated rows, seed, initialization, and fresh transition and output randomness. For almost every fixed seed, pair-input probabilities may be Borel measurable, or measurable in the completion of \gamma_d(dx)\,dy, where \gamma_d=N(0,I_d) and dy is Lebesgue measure. Joint measurability of the original experiment is required also in the latter case; separate measurability assertions for individual seeds do not by themselves define its mixture. The sample bound T is a deterministic finite horizon.
The model charges persistent bits rather than real registers. It permits a different rule at every index and does not limit the work performed on the current sample.
Theorem 1.2 (Explicit noiseless precision bound). Let M:\mathbb N\to\mathbb Z_{\ge0} satisfy M(d)=o(d^2). There is a dimension threshold depending only on this memory sequence such that, for every larger d, every 0<\epsilon\le1/10, and every learner in Definition 1.1, the following implication holds. If S is uniform on S^{d-1}, independently of the Gaussian rows and learner randomness, and
then
Corollary 1.3 (Guarantees for every signal). Under the memory assumption of Theorem 1.2, suppose a learner satisfies
where \Prob_s averages its observations and randomness at the fixed signal s. Then (1) holds at the same dimension threshold.
Proof. Integrate the displayed guarantee over a uniform signal, then apply Theorem 1.2.
The dimension threshold is uniform in the accuracy; no relation between accuracy and memory is assumed. For example, when \epsilon=d^{-r}\le1/10, the conclusion is T\ge2^{-16}r d\log_2 d.
Context and ancestry
Memory restrictions affect statistical risk already in sparse noisy regression, as shown by Steinhardt and Duchi [7, Section 1.1, equation (2)]. Steinhardt, Valiant, and Wager related bounded-memory inference to communication and statistical-query models and posed a quadratic-memory versus exponential-sample question for parity learning [8, Section 1.1, Conjecture 1]. Raz established the qualitative separation through finite-width branching programs [4, Theorem 1]. These works make explicit the distinction between information in a current observation and information that a finite state can carry forward.
The closest continuous-regression comparison among these sources is Sharan, Sidford, and Valiant [6]. Their Theorem 1 uses independent isotropic Gaussian covariates and independent uniform additive noise of half-width 2^{-d/5}. At Euclidean accuracy \epsilon=d^{-r}, for r\le O(d/\log d) in the range specified there, at most d^2/4 bits and success probability at least 2/3 require \Omega(d\log r) samples [6, Theorem 1]. Their proof experiment draws the target uniformly on the sphere [6, Section 2]. The exact labels in Definition 1.1 are more informative than noisy labels, so that noisy lower bound alone does not give Theorem 1.2. The condition-number conjecture in their Section 1.1 concerns a different, ill-conditioned Gaussian experiment at constant accuracy.
Dagan, Kur, and Shamir give related space lower bounds for distinct linear-prediction tasks [1]. Their published Theorem 3 asks for an approximate null vector of independent Gaussian rows. Their Theorem 10 concerns empirical residual error on a finite equation system formed from jointly conditioned rows and one fixed equation. Those targets and observation laws differ from the fixed-signal precision problem considered here.
Our block analysis uses high moments of several directions drawn in one random subspace. The use of independent copies and successive orthogonalization has a close predecessor in the high-moment calculation of Sharan, Sidford, and Valiant [6, Section 7, Lemma 12]. Their calculation concerns a noisy interval projection under a global L^2 density hypothesis. The local argument below instead conditions an exact Gaussian block and controls its residual subsphere. Classical beta laws for random projections are discussed by Frankl and Maehara [2]; all normalized densities, conditional laws, and inequalities used here are proved locally.
Exact observations and residual subspheres
For a Euclidean linear space H, write S(H) for its unit sphere and \sigma_H for uniform probability on that sphere. We test the success probability of a learner on affine subspheres
The dimension of this test means the linear dimension D=\dim H. Fix the shared seed and the learner’s rules. At a block boundary, let g_v(s) be the success probability of the remaining computation started in state v, using fresh samples. This function is defined even when v is unreachable at target s. The proof bounds its average on every test (2) of sufficiently large dimension.
To evaluate one such average, draw the target uniformly on the affine test, independently of fresh block rows. A block of 1\le b<D Gaussian rows identifies the target’s projection p onto their row span in H. Conditional on the full block data, the target is uniform on
where K is the perpendicular complement of that row span in H. When the experiment is instead conditioned on the observed projection p, the space K is uniform among the (D-b)-dimensional subspaces of E=H\cap p^\perp. Thus the block leaves a random residual subsphere, even though the learner may process its exact real data without computational limits. Section 2 proves these conditional laws.
The state chosen after the block may depend on its entire matrix and all its labels. We account for this choice before averaging away the matrix data: the resulting success probability is bounded by the maximum over the possible continuation states. For fixed p,\rho, write
If the block can choose among at most W states, then for every positive integer h,
A bound on the h-th moment therefore charges state selection by W^{1/h}. The moment is an average over h directions drawn independently in the same random space K; those directions are correlated after K is averaged out.
Proof of the precision bound
The central task is to control this correlation without spending a new test dimension for every direction. Conditional on preceding directions with span V, the next direction has more mass near V than a uniform direction in E. The comparison in Section 5 bounds its law by an exponential factor times two simpler probability laws. The first is uniform on S(E). The second chooses one direction in V and then draws a uniform direction on a latitude perpendicular to it. Both laws can be bounded by the same suffix estimate on affine subspheres: the first uses dimension D-1, and the second dimension D-2. Every factor in the moment uses these same tests. Thus a block costs only two test dimensions, although it contains a number of samples proportional to d.
The residual radius and the comparison-latitude radii contribute inverse-radius moments. Their squared radius fractions have beta laws, and finite beta products bound these moments explicitly. Together with a moment order proportional to d, this gives a uniform upper bound on success that can be propagated backward over the blocks. The terminal bound is a spherical cap estimate.
There is still a dimension constraint: this induction is useful only while the test spheres remain large. Section 4 supplies that constraint from the learner model. There are at most (T+1)2^M terminal index-state pairs. Counting their cap probabilities shows that a successful putative run with T=O(d\log(1/\epsilon)) must have \log(1/\epsilon)=o(d) when M=o(d^2). Such a run contains only o(d) blocks, so the induction has sufficient dimensions. A full-data residual estimate handles bounded precision.
The direct proof of Theorem 1.2 therefore proceeds through the continuation and residual laws in Section 2, the cap and common-subspace direction facts in Section 3, the stopping reductions in Section 4, and the beta-mixture comparison in Section 5.
Further analytic formulations
The same geometric setup also gives bounds that apply to arbitrary bounded continuation functions, whether or not they arise from a learner. Section 6 develops a second way to control the correlated directions. A cap estimate bounds mass in a tube around the preceding span, and summing shells controls the singular conditional density. This yields Theorem 6.1: a block selecting among at most W continuations increases their radius-weighted subsphere means by at most W^{1/h}C^d, with h=\lfloor d/16\rfloor, while lowering the test dimension by two. Its terminal bound gives the same precision rate at success probability 1/2, with an unspecified absolute coefficient.
Section 7 gives an explicit version of the suffix estimate simultaneously on all admissible affine subspheres. An even radius exponent lets its inverse-radius moment be evaluated by a finite beta product, retaining explicit constants throughout. Section 8 gives a different extension: its induction compares actual learners in different ambient dimensions and permits arbitrary Euclidean outputs at every positive error tolerance. The key step simulates a latitude target by a smaller Gaussian learner without increasing its state set. These are additional formulations of the method; the numerical coefficient in Theorem 1.2 comes from the beta-mixture proof.
2 Continuations and exact residual spheres
The block estimates test a continuation on many affine subspheres, including subspheres of zero measure for the original uniform prior. We first obtain Borel continuation functions on every such test. We then determine the exact target law left by a Gaussian block.
2.1 Borel rules and counterfactual continuations
Lemma 2.1 (Borel versions under the uniform prior). Fix d\ge2, a finite horizon, and finite state sets. For almost every realization of the shared rule seed in Definition 1.1, there are Borel transition and stopping kernels with the same state sets and terminal output laws whose conditional joint law of the uniform signal, state path, stopping index, and output is unchanged.
Proof. Fix a seed realization for which the conditional model requirements hold. Such realizations have full seed probability. For a fixed state and index, combine continuing and stopping choices into a finite set of tagged destinations. Their probabilities form a finite vector of completed-measurable nonnegative functions summing to one on the pair space. Every completed-measurable real function has a Borel version: approximate it by simple functions and replace their countably many measurable level sets by Borel sets modulo null sets. Choose such a version for each coordinate. On the Borel set where the chosen coordinates are negative or fail to sum to one, replace the vector by a fixed point mass. This set is null. Since there are only finitely many indices and states, a single Borel \gamma_d(dx)\,dy-null set Z contains every pair-input modification.
Let S be uniform on S^{d-1} and pre-generate the independent Gaussian rows. The joint independence in Definition 1.1 ensures that, after fixing this seed, they retain this product law and the initial state carries no information about them. For a fixed x\ne0, the coordinate of S in the direction x/\norm x has a Lebesgue density when d\ge2; this will also follow from (4) below. Scaling by \norm x shows that the conditional law of \ip xS has a density. The event x=0 is Gaussian-null. Thus each pair (X_t,\ip{X_t}{S}) has marginal law absolutely continuous with respect to \gamma_d(dx)\,dy and avoids Z almost surely. This conclusion remains valid along an adaptive state path, because
A finite union over the pre-generated indices is still null. Couple the original and Borel finite kernels using the same fresh uniform random numbers. Their choices agree outside Z, so induction makes their state paths and stopping indices identical almost surely. The terminal output laws have no pair-input argument and can then be coupled identically. This proves the joint-law assertion.
The reduction preserves the averaged experiment; it need not preserve the behavior at every exceptional individual signal. After making the reduction, start the Borel learner at any specified state and index, whether or not that state could have been reached. Its future success probability G_v(s) is a Borel function of s, by finite composition and integration of the Borel kernels over fresh rows and randomness. These are counterfactual continuations, rather than conditional laws given a reached-state event. Every bound below is uniform over the seed realizations covered by the lemma, hence over almost every seed. The original jointly measurable experiment supplies measurable conditional success probabilities. We may therefore average those original probabilities afterward; no jointly measurable choice of Borel versions across seeds is needed.
For a block of k pre-generated rows, the complete transitions from a fixed starting state give Borel destination probabilities \kappa_v(X,y). If a padded program always has a destination, they sum to one. The exact recursion is
All dependence of the block computation on its rows and labels remains in \kappa_v. The continuation uses only its state from the past. Conditional on the shared seed, initialization is independent of the signal and sample rows. It may be averaged at the end, after which the same uniform estimates may be averaged over the seed in the original jointly measurable experiment.
2.2 Spherical coordinates and beta fractions
We use uniform probability, never unnormalized surface area, on each sphere. The following normalized formulas are classical; see Frankl and Maehara [2] for the geometric beta-law context. We include their derivation and the conditional information needed here.
Lemma 2.2 (Coordinates of a uniform direction). Let E=E_1\oplus E_2 be an orthogonal decomposition with \dim E=D, \dim E_1=l, and 1\le l<D. If U\sim\sigma_E, then
and the two component directions are independent uniform directions, independent of this fraction. In coordinates on E_1, the projection P_{E_1}U has density
Conditional on that projection, the complementary direction is uniform on S(E_2). When l=0 or l=D, the squared projection is respectively the point mass at 0 or at 1.
Proof. Write U=G/\norm G for a standard Gaussian G in E. The two Gaussian components are independent. Their squared lengths divided by two are independent unit-scale gamma variables of shapes l/2 and (D-l)/2, and their directions are independent uniform directions. For independent gamma variables A,B of shapes \alpha,\beta>0, the change of variables (A,B)=(qv,(1-q)v) has Jacobian v. Their joint density therefore factors into
The fraction and sum are independent, and the fraction is \Beta(\alpha,\beta). Polar coordinates on E_1 give (4); its normalizing constant follows from the beta integral and the area 2\pi^{l/2}/\Gamma(l/2) of S^{l-1}. The independent component directions give the conditional assertion. This proof includes D-l=1, when S(E_2) has two points and the coordinate-density exponent can be -1/2. The endpoint decompositions l=0,D are deterministic and require no beta law with a zero shape.
For D\ge3, write c_D=c(D,1). The normalizing integrand (1-t^2)^{(D-3)/2} is at least 1/2 on |t|\le D^{-1/2}, so c_D\le\sqrt D. For an exponent at least one this lower bound follows from Bernoulli’s inequality; the remaining nonnegative exponents are immediate. This simple estimate will keep all cap constants exponential in the ambient dimension.
Lemma 2.3 (Beta moments and products). For A,B>0 and Z\sim\Beta(A,B), a real q\ge0 satisfies
The moment diverges when q\ge A. If h is a nonnegative integer with h<A, then
where the product for h=0 is one. Moreover, for C>0, independent
satisfy
Proof. Integrating z^{-q} against the beta density gives the first ratio when the exponent A-q-1 is greater than -1. If it is at most -1, the integral diverges at zero. The identity \mathrm B(x,y)=\Gamma(x)\Gamma(y)/\Gamma(x+y) gives (5), and the gamma recurrence gives (6). For the product, take independent unit-scale gamma variables G_1,G_2,G_3 of shapes A,B,C. The fraction G_1/(G_1+G_2) is independent of G_1+G_2, hence of (G_1+G_2)/(G_1+G_2+G_3). These two fractions have the stated laws, and their product is G_1/(G_1+G_2+G_3), of law \Beta(A,B+C).
2.3 What an exact block leaves
Uniform orthogonal frames may be generated successively from uniform sphere directions in perpendicular complements; Mezzadri gives an authoritative exposition of this construction [3, Section 8, Theorem 4 and Corollary 1]. Here is the short invariance fact we need. A square Gaussian matrix A is invertible almost surely, and Q=A(A^{\mathsf T}A)^{-1/2} is orthogonal. Left and right orthogonal invariance of the Gaussian law show that Q is invariant under both left and right multiplication by any fixed orthogonal matrix. We call this the uniform orthogonal law. Its image of a fixed frame is uniform. To see its conditional frame property, construct an ordered orthonormal frame by choosing the first vector uniformly and each successive vector uniformly in the perpendicular complement of the previous ones. This joint law is left rotation invariant. Uniqueness of invariant probability on any sphere, frame space, or space of flags used below follows by averaging over Q: the average of a fixed object is independent of that object by transitivity and right invariance, while averaging an invariant law leaves it unchanged. Thus the successive construction has the same law as the image under Q, and its definition gives the claimed uniform conditional law of the remaining frame. All subspace averages below are measurable: if K=QK_0 is represented by an orthogonal matrix and a fixed subspace, then \int f(Qu)\,d\sigma_{K_0}(u) is a Borel function of Q for Borel f, by parameter integration, and depends only on K.
Lemma 2.4 (Exact residual law). Let s=z+r\omega with \omega\sim\sigma_H, independently of a matrix X with b independent standard Gaussian rows. Assume z\perp H, r>0, and \norm z^2+r^2=1. Put D=\dim H, and let 1\le b<D. Let R_X be the row span of X restricted to H, and set K=H\cap R_X^\perp. Conditional on X, the joint experiment has the representation
where the three draws are independent. The labels are
Marginally, t is independent of (e,K), e is uniform on S(H), and, conditional on e, K is uniform among the (D-b)-dimensional subspaces of H\cap e^\perp.
Proof. The restriction of X to H has rank b almost surely and its row span is rotation invariant. Conditional on X, Lemma 2.2 applied to H=R_X\oplus K gives (8). In particular the residual direction v is independent of t,e and remains uniform when the full X,t,e are fixed. Since Xv=0, the displayed label identity follows. The restriction of X to R_X is injective, so, given X, the labels determine the projected component r\sqrt{1-t}\,e.
To reverse the order of the other draws, take a uniform orthonormal basis of H, let R_X be the span of its first b vectors, and take its first vector for e. By the invariance just proved, this has the same law as a uniform row span and a uniform direction in it. Conditional on e, the remaining basis is a uniform frame in H\cap e^\perp. Its last D-b vectors span a uniform (D-b)-space there. The beta law of t does not depend on the row span or its directions, which proves the claimed independence. When b=1, the conditional residual space is simply H\cap e^\perp; the statement still applies.
Figure 1: An orthogonal cross-section of the decomposition in Lemma 2.4. The observed row-space component is p=r\sqrt{1-t}\,e; the remaining component has length \rho=r\sqrt t and direction in K. The line meets the displayed circle in two points because this cross-section is two-dimensional. In higher dimension the same intersection is the residual subsphere z+p+\rho S(K).
Figure 1 shows the geometric content of the conditioning. The subspaces in the lemma are analysis variables; the learner is given exactly X,Xs. The next consequence is the point where the full data-dependent state choice is accounted for.
Lemma 2.5 (Averaging after a block). In the setting of Lemma 2.4, let \mathcal V be nonempty and finite, let g_v:S^{d-1}\to[0,1] be Borel, and let Borel weights \kappa_v(X,y)\ge0 satisfy \sum_v\kappa_v\le1. Put
Then
The expectation on the left uses the independent uniform subsphere target and Gaussian block.
Proof. Conditional on X,t,e, the labels are Xz', the weights are fixed, and u is uniform in K. The conditional mean is \sum_v\kappa_v(X,Xz')F_v(K), bounded by \max_vF_v(K). This maximum no longer depends on the remaining matrix data except through K. The reversed-order part of Lemma 2.4 therefore gives the right side of (9).
The maximum is taken before the matrix is replaced by its marginal subspace law. It allows the selected state to depend arbitrarily on the entire matrix and every exact label. No claim that a forward posterior at a reached state is uniform on a subsphere is used.
3 Caps and directions in a random subspace
The residual law reduces a block to averages of continuation functions on a random subspace. We first bound terminal success by spherical caps. We then compute the dependence between several directions drawn in the same random subspace. Both block methods will use this conditional law; their different ways of bounding its moments come later.
3.1 Caps and terminal outputs
Lemma 3.1 (Spherical caps). Let e be a unit vector in a D-dimensional Euclidean space. For D\ge3 and every \delta>0,
For D\ge2 and 0\le\theta\le\pi,
Consequently, on an affine subsphere z+R S(H) as in (2), with radius R and linear dimension D\ge2, the angular success probability of any fixed unit output is at most
The last assertion also holds after averaging any target-independent output law.
Proof. For the chordal cap, t=\ip ue lies in an interval of length at most \delta^2/2 next to 1, and 1-t^2\le\delta^2 on that interval. Integrating (4) with l=1 gives (10). For the angular cap, the polar-angle density is proportional to \sin^{D-2}\phi on [0,\pi]. Its numerator over [0,\theta] is at most \theta^{D-1}/(D-1). Its denominator is at least 2^{-(D-2)}, by integration over [\pi/6,5\pi/6]. This proves (11).
Angular error at most \epsilon between unit vectors implies Euclidean error at most \epsilon. After projection onto H and division by R, the successful directions in (2) lie in a Euclidean ball of radius \epsilon/R. If that set is nonempty, choose one successful direction as a center. Every other successful direction has chordal distance at most 2\epsilon/R from it. For chordal distance \delta\le2, the corresponding angle is at most 2\arcsin(\delta/2)\le(\pi/2)\delta. When 8\epsilon/R<1, (11) therefore gives (8\epsilon/R)^{D-1}; when 8\epsilon/R\ge1, total mass is the asserted bound. Integrating this pointwise statement over an independent output law proves the last claim.
3.2 Directions with a common random subspace
The joint direction law below is a spherical form of the linear Blaschke–Petkantschin formula; see Rubin [5, Corollary 3.2, equation (3.5)]. We derive the normalized conditional density directly.
Lemma 3.2 (Conditional direction law). Let E have dimension N, let L be a uniform K-dimensional subspace, and assume integers 1\le h<K\le N. Conditional on L, draw Y_1,\ldots,Y_h independently with law \sigma_L. Given Y_1,\ldots,Y_j, their span V has dimension j almost surely, and L is uniform among the K-subspaces containing V. For 1\le j<h, the conditional density of Y_{j+1} relative to \sigma_E is
For j=0, the first marginal is \sigma_E. If K=N, the density in (13) is identically one.
Proof. Fix a K-space L_0\subset E. Draw independent \xi_1,\ldots,\xi_h\sim\sigma_{L_0} and an independent uniform orthogonal matrix Q, and put L=QL_0, Y_i=Q\xi_i. This produces the stated experiment. Since h<K, the first j preimages, and hence their images, are linearly independent almost surely.
Condition on the first j preimages and images. Applying Gram–Schmidt to the preimages gives an orthonormal basis of their span, and the images determine its image basis. Conditional on these images, the action of Q on the perpendicular complement is a uniform orthogonal isometry. It follows that
This conditional law depends only on V, so it persists when the preimages are forgotten.
The next preimage is still uniform in L_0. Its projection onto the preceding span has the j-coordinate density (4) in dimension K. Its complementary direction is sent by the uniform remaining isometry to a uniform direction in V^\perp, independently of that projection. The same decomposition of a direction with law \sigma_E uses the coordinate density in dimension N. Taking their ratio gives
which is (13). The integral normalizing c(K,j) is at least that normalizing c(N,j), because (1-\norm t^2)^{(K-j-2)/2}\ge (1-\norm t^2)^{(N-j-2)/2} on the unit ball. Thus the prefactor is at most one. The first marginal is uniform by rotation invariance. When K=N, L=E and the original conditional draws remain independent uniform directions, as the formula also shows.
4 Stopping and the remaining dimension budget
Each block estimate below loses two dimensions. Before iterating it, we must know that enough dimensions remain. Terminal state counting gives this fact on any putative short run. A separate full-data argument covers constant accuracy. Both reductions count individual samples and allow early stopping.
Throughout this section W=2^M, and success is averaged over an independent uniform signal. Logarithms denoted by \log_2 are to base two.
Lemma 4.1 (Terminal count and padding). For d\ge3, a learner of horizon T satisfies
The learner can be padded to any prescribed later sample layer, with the same success law and width at most
Proof. Fix a seed realization covered by Lemma 2.1 and use its Borel version. Its initial-state law is independent of the signal. For each terminal index-state pair (t,v), let q_{t,v}(s) be its probability of being reached at signal s, and let \pi_{t,v} be its target-independent output law. There are at most (T+1)W such pairs. Replacing q_{t,v}(s) by one, then integrating \pi_{t,v} over the uniform signal, bounds that pair’s contribution by a single angular cap mass. Angular success implies chordal error at most \epsilon, so (10) gives (14); (11) gives (15). The same numerical bound holds for almost every fixed seed, so Lemma 2.1 permits averaging the original conditional success probabilities.
To pad, keep every halted state together with its original stopping index as an absorbing state, and ignore later samples. At the final layer use its original output law. At any layer there are at most W active states and (T+1)W halted index-state labels, giving (16). This includes a stop at index zero.
The terminal count also identifies the regime where the output restriction alone is decisive. At success probability at least 2/3, (14) gives
For a fixed \alpha>0, accuracy \epsilon=2^{-\alpha d} therefore requires T\ge2^{(\alpha-o(1))d^2} when M=o(d^2). The block arguments provide an additional obstruction beyond terminal output counting. To apply them, we next extract the remaining dimension budget from the same terminal count.
Lemma 4.2 (Short-run dimension budget). Fix constants c>0 and \alpha>0, and put L=\log_2(1/\epsilon). Suppose M(d)=o(d^2). On any sequence of dimensions where uniform-prior success is at least \alpha and T\le cdL, one has
Consequently, for any block length k\ge c_0d with fixed c_0>0, \lceil T/k\rceil=o(d) on that sequence.
Proof. Since L\ge1, T+1\le(c+1)dL and \log_2 L\le L. Taking logarithms in (14) and using c_d\le\sqrt d gives the estimate
This proves L=o(d), uniformly in the accuracy and the rules on the indicated dimensions. The assumed sample bound gives T=o(d^2); then \log_2 W_*=M+\log_2(T+2)=o(d^2). Dividing T by k\ge c_0d proves the block-count assertion.
The short-run hypothesis is essential: the conclusion L=o(d) applies only on the indicated dimensions.
Lemma 4.3 (Full-data residual bound). Let 0\le T\le d-3. Give an estimator all T Gaussian rows and labels for a uniform signal, and allow any unit output depending on these data and independent randomness. Put D=d-T. For every 0<r_0<1, its angular success probability is at most
Proof. For T\ge1, the row span R_X has dimension T almost surely. Given the full rows and labels, the row-space projection p=P_{R_X}S is known, because the row matrix is injective on its row span. The residual law is
Conditional on the data, the residual direction is uniform. At a fixed row span, spherical symmetry gives \E\norm p^2=T/d. Markov’s inequality yields \Prob(r<r_0)\le T/[d(1-r_0^2)]. On r\ge r_0, successful residual directions lie in a chordal cap of radius 2\epsilon/r_0, by the recentering argument in Lemma 3.1. The sharp and affine terminal cap bounds give the three alternatives in the minimum. The output randomization may be averaged after conditioning on the full data. When T=0, take R_X=\{0\}, p=0, and r=1; the same argument uses the original full sphere.
For T\le d/4, take r_0=1/2 in (19). Since D\ge3d/4 and 2\epsilon/r_0\le0.4,
uniformly in this range of T. Thus uniform-prior success at least 1/2 requires
for all sufficiently large d.
These full-data estimates apply to a learner that stopped earlier, because revealing all pre-generated rows and labels only gives it more information.
5 A beta-mixture comparison and the explicit constant
A block leaves a uniform direction in a random residual subspace. To bound a high moment of its continuation average, we must control the next direction after earlier directions in that same subspace have been exposed. Lemma 3.2 describes this law; the next lemma compares it with two families of tests on which an affine suffix bound can be used directly.
The first test is the whole ambient sphere. The second fixes one direction from the span of the earlier draws and averages on a latitude perpendicular to that direction. If the ambient space has linear dimension D', each such latitude has linear dimension D'-1, regardless of the number of earlier draws. This is the reason that a block will spend only two test dimensions: one for the observed projection direction and one for the comparison latitude. The beta variable in the construction below chooses the latitude radius so that its law controls the next direction near the preceding span.
Lemma 5.1 (Two-component domination). Let E have dimension D', let V\subset E have dimension 1\le j<n<D', and let N be uniform among the n-dimensional subspaces containing V. Conditional on N, let v be uniform on S(N). Set
Let \nu_0=\sigma_E. Let \nu_1 be the law of
where Z is independent of the directions. Then, as positive measures on S(E),
For j=0, the first direction averaged over a uniform N is uniform on S(E). If n=D', then N=E and each new independent direction is uniform even after earlier directions are conditioned on. These cases require no mixture.
Proof. Put Q(y)=\norm{P_{V^\perp}y}^2. For the actual direction, the orthogonal decomposition N=V\oplus(N\cap V^\perp) and Lemma 2.2 give
For \nu_0, the fraction has law \Beta(\alpha_*,\beta_0). Under \nu_1, it equals ZX, where X=\norm{P_{V^\perp}u_0}^2. If j>1, the decomposition
gives X\sim\Beta(\alpha_*,(j-1)/2), independently of Z. The beta-product identity (7) gives Q\sim\Beta(\alpha,\beta_1). If j=1, the second summand is zero and X=1 deterministically. In that case \beta_1=\alpha_*-\alpha, so Q=Z has the same stated law. We do not use a beta law with second shape zero.
The three vector laws are invariant under independent orthogonal transformations of V and V^\perp. Their two component lengths are nonzero almost surely. For completeness, average a bounded Borel function of a vector over an independent uniform element of O(V)\times O(V^\perp). At fixed nonzero component lengths, this average is integration over the product of the two uniform direction laws. Invariance leaves the original expectation unchanged, including after multiplication by any bounded function of Q. Thus each vector law is obtained from its scalar Q law with the same independent uniform component directions. A comparison of the scalar densities therefore lifts to the full vector measures.
Write b=D'+1-n. The nontrivial case has b\ge2, and
Let f_{A,B} denote the normalized beta density. The beta integral decreases when either positive shape parameter increases. For q\ge1/2,
For q<1/2,
This includes equality \beta_1=\beta_0 when b=2. Splitting at 1/2 and using the common direction factors proves (22). For j=0, rotation invariance gives the uniform marginal; for n=D', the subspace is the whole E and the original draws remain independent uniform directions.
Proof of Theorem 1.2. Fix the memory sequence, and suppose that the conclusion fails along an unbounded sequence of dimensions. All logarithms in this proof are to base two. Write
The short-run reduction. Lemma 4.2, with c=c_* and \alpha=2/3, gives \lambda=o(d), T=o(d^2), and \log_2w=o(d^2) for the padded width
These bounds are uniform over the violating accuracies and learner rules: the explicit estimate (18) bounds (d-2)\lambda by a function of d and M(d) alone. If \lambda\le1024, then T<d/64, contradicting the full-data bound (20) at large d. We therefore restrict to \lambda>1024.
Set
The radius exponent p is even, so the inverse-radius moments below have the integer exponent \ell=p/2. Pad early stops to length T using Lemma 4.1, and divide the horizon into J batches of length at most k. A short last batch retains its actual positive length. When T=0, there are no batches. At sufficiently large violating dimensions,
The first inequality uses k\ge d/32.
The suffix bound. Fix a rule seed for which Lemma 2.1 applies, and use its Borel version. The signal remains uniform and independent of the pre-generated rows and initialization. Start a continuation from any specified boundary state, without conditioning on whether that state is reached. All the bounds below are uniform over this fixed choice of rules and state.
For a boundary state v after i batches, let h_{i,v}(s) be its Borel suffix success. We claim that every affine subsphere c+rS(H) with D=\dim H\ge d-2i satisfies
The test dimension in this assertion decreases by two as the boundary index increases. In the backward step from i+1 to i, the available bounds therefore include all affine tests of dimensions D-1 and D-2, whenever the current test has dimension D\ge d-2i.
At i=J, Lemma 3.1 proves the claim. Indeed D\ge d-2J\ge3d/4 gives D-1\ge p; if 8\epsilon/r\ge1, use total mass, and otherwise compare the exponents in (12). This also treats J=0.
One block. Suppose the claim holds at i+1, and let the next batch have length 1\le b\le k. Lemma 2.4 gives
Conditional on \rho,e, the residual space N is uniform of dimension n in E. By Lemma 2.5, the left side of (26) is at most
This step keeps all dependence on the exact batch data until the state maximum has been taken.
We bound this state maximum through an m-th moment. Each conditional factor in that moment will use the same stage-i+1 affine bound; the earlier replica span changes its distribution but not the induction stage.
Fix \rho,e,v' and write
Expand F_{v'}(N)^m using m directions drawn independently conditional on N. Given the first j<m directions, their span V has dimension j almost surely, and Lemma 3.2 makes N uniform among the n-spaces containing V. The parameter bounds imply
For j=0, the next direction is uniform on S(E), and the stage i+1 hypothesis bounds its expected success factor by U_0, since D'=D-1\ge d-2(i+1). If b=1, then n=D' and every next independent direction is uniform in E; the same bound applies. These cases precede any use of a beta mixture.
For j\ge1 and b\ge2, apply Lemma 5.1. The \nu_0 expectation is at most U_0. Under \nu_1, conditional on Z,e_0, the target is uniform on the affine subsphere with
Its linear dimension is D-2\ge d-2(i+1). Also \widetilde c\perp\widetilde H, \widetilde r>0, and \norm{\widetilde c}^2+\widetilde r^2=1, because c'\perp E and \norm{c'}^2+(r')^2=1. The induction hypothesis bounds its mean by U_0Z^{-\ell}.
In the notation of Lemma 5.1,
The other shape \alpha_*-\alpha=(b-1)/2 is positive. The integer \ell=\lfloor d/32\rfloor is strictly below the first shape, and every ratio below is at most two:
Since D'\le d, the mixture domination bounds the conditional expected next factor by
For each preceding replica span, this uses a fresh test in the same dimension D-2. Only the single direction e_0 is removed from E; no dimension decrease is carried from one replica to the next.
Integrating the nonnegative product in reverse conditional order gives
Jensen’s inequality and the sum of the at most w state moments then give
For the residual fraction \rho^2, the first shape satisfies n/2-\ell\ge5d/16\ge d/4, its total shape is D/2\le d/2, and its other shape b/2 is positive even for a one-row batch. The same integer beta identity yields
Averaging r'=r\rho in (27) supplies the factor w^{1/m}2^{4d}=G, completing the backward induction.
The numerical conclusion. At i=0, take the full sphere H=\R^d,c=0,r=1. The bound is uniform in the fixed shared seed and initial state; joint independence permits averaging over initialization, and then Lemma 2.1 permits averaging the original measurable conditional success probabilities over the seed. By \log_2w=o(d^2) and m\ge d/32, we have \log_2G\le5d eventually. The base-two logarithm of the success upper bound is at most
Here 3-\lambda\le-\lambda/2, p\ge d/32, 160c_*=5/2048\le1/128, and \lambda\ge1024. The resulting success is less than 2/3, a contradiction.
Both precision branches exclude an unbounded sequence of violations. All eventual conditions were bounded using (18) and the fixed memory sequence; the full-data cap threshold is absolute. This proves the uniform dimension threshold and (1).
6 The radius-weighted block estimate
We now develop the cap-moment method for arbitrary bounded continuation functions. Weighting the mean on an affine subsphere by a power of its radius makes the same test useful at every scale. The resulting block inequality is independent of a learner and also gives a precision bound at success probability one half.
For a Borel function g:S^{d-1}\to[0,1], an exponent a=d/16, and an integer 1\le n\le d, define
In particular B_d(g)=\int g\,d\sigma_{\R^d}. The radius weight allows small subspheres to carry more mass while keeping the same test at every scale.
The block may choose among arbitrary bounded continuation functions.
Theorem 6.1 (Radius-weighted block estimate). There are absolute constants C\ge1 and d_* such that the following holds for every integer d\ge d_*. Put
Let W\ge1, let \mathcal V be a nonempty finite set with |\mathcal V|\le W, and let \kappa_v:\R^{k\times d}\times\R^k\to[0,1] be Borel functions with \sum_{v\in\mathcal V}\kappa_v\le1. For Borel g_v:S^{d-1}\to[0,1], set
where X has k independent N(0,I_d) rows. For every integer n with d/2\le n\le d,
If \epsilon>0, \pi is any probability measure on S^{d-1} and
then, in the same range of n,
The width factor pays for selecting a continuation after the block. The two-dimensional change instead records the latitude tests used to bound each conditional direction average. We first establish the moment estimate that connects these two features.
6.1 Caps and subspace moments
The use of replica moments and successive orthogonalization is related to Sharan, Sidford, and Valiant [6, Section 7, Lemma 12]. The density becomes large near the preceding span. The next lemma shows that a cap estimate with sufficient dimension slack makes this singularity integrable. Its explicit constant retains a useful quantitative form of the argument.
Lemma 6.2 (Caps and subspace moments). Let E have dimension N\le d, and let L be a uniform K-space in E, with integers 1\le h<K\le N. Put b=N-K. Let f:S(E)\to[0,1] be Borel. Suppose that for some finite \Lambda\ge0, constants A_0,A_1\ge1, and 0\le a<N-1,
If
then
For a nonempty family of at most W functions satisfying the same conditions with numbers \Lambda_v,
In particular, A_0=1,A_1=4 gives the constant 144^d.
Proof. Put \alpha=N-1-a and Q_0=\max\{A_0,9A_1\}. For a j-dimensional subspace V\subset E, 1\le j<h, and 0<\delta<1, every sphere point within distance \delta of V lies within 2\delta of its normalized projection onto S(V). A maximal \delta-separated subset of S(V) has at most (3/\delta)^j points: the open balls of radius \delta/2 about them are disjoint inside the ball of radius 1+\delta/2 in V. Caps of radius 3\delta about these points cover the tube. Hence
The last inequality uses \alpha,j\le d. At \delta=1, the same bound follows from (34). The zero-distance set has sphere measure zero because j<N. The shells 2^{-i-1}<\dist(y,V)\le2^{-i} therefore give
Here \alpha-j-b\ge1 follows from (36), and b+1\le2d. For j=0, the distance of a unit vector from \{0\} is one and the same conclusion follows directly from total mass. Thus this case needs neither a net nor a shell sum.
Conditional on L, draw Y_1,\ldots,Y_h independently from \sigma_L. Expanding the power in (37) gives \E\prod_{i=1}^h f(Y_i). Lemma 3.2 and (40) bound the last conditional factor by (4Q_0)^d\Lambda. Continue in reverse conditional order, using total mass for the first direction. This proves (37). Finally, writing F_v(L)=\int f_v\,d\sigma_L, Jensen’s inequality gives
which proves (38).
The lemma pays for the span of prior replicas through the tube exponent. It does not spend a new induction dimension for each replica: every conditional factor is tested against the same cap hypothesis on S(E). In the applications, one latitude of an affine subsphere supplies that hypothesis.
6.2 Proof of the block estimate and its application
A latitude in the perpendicular ambient sphere has two fewer linear dimensions than the original test. Its radius-weighted mean supplies the cap hypothesis; a final beta integral averages the residual radius.
Proof of Theorem 6.1. We work at sufficiently large d, with the parameters in the theorem. First consider a terminal function g_\pi and a test (z,H,R) of dimension n\ge d/2. If R\ge2\epsilon, the successful directions for any fixed output lie in a chordal cap of radius 2\epsilon/R\le1. By (10), their mass is at most (c_n/2)(2\epsilon/R)^{n-1}. Since n-1\ge a, multiplication by R^a bounds this by (c_n/2)(2\epsilon)^a\le C^d\epsilon^a. If R<2\epsilon, total mass gives R^a\le(2\epsilon)^a. Averaging the output law proves (33).
For the block bound, fix a test (z,H,R) of dimension n. Let V be the span in H of the k projected rows. Put
Almost surely p\ne0 and r>0. Conditional on the matrix and p, the target is z+p+rU with U\sim\sigma_K, and its labels are X(z+p). Lemma 2.5 bounds the averaged block function by
Here K\mid p is uniform among the q-spaces of H'=H\cap p^\perp, whose dimension is N=n-1. Indeed, the length of p fixes the beta fraction, its direction fixes e, and Lemma 2.4 gives this conditional law.
Fix p and one function g=g_v. On S(H') set
For w\in S(H'), condition on the latitude coordinate t=\ip Uw\in(-1,1). The target on that latitude is uniform on
This is an admissible affine subsphere of linear dimension n-2: its center is perpendicular to H'\cap w^\perp, and its squared center norm plus squared radius is \norm z^2+\norm p^2+r^2=1. The definition of B_{n-2} therefore bounds the latitude average of f by \Lambda(1-t^2)^{-a/2}.
The coordinate density in dimension N has remaining exponent (N-3-a)/2\ge0. Integrating it over the whole interval and then over the cap interval gives
For the second line the coordinate interval has length at most \eta^2/2 and 1-t^2\le\eta^2 there. For \eta>1, total mass extends the cap bound with an absolute exponential factor. Since 2c_N\le2\sqrt d\le4^d, these estimates satisfy Lemma 6.2 with absolute A_0,A_1.
Use that lemma with ambient dimension N=n-1, subspace dimension q=n-k, and moment m=k. The singular power is N-q=k-1. The required inequalities hold at large d: 1\le m<q\le N, 0\le a<N-1, and, for 0\le l<m,
The moment conclusion is
Each replica uses the same n-2-dimensional latitude tests. No additional induction dimension is lost while the replicas are integrated.
The maximum inequality (38) now bounds the inner expectation in (41) by
It remains to average the residual radius. By Lemma 2.4, t=(r/R)^2\sim\Beta(q/2,k/2). The denominator of its beta integral satisfies
by restriction to [1/4,3/4], where x_+=\max\{x,0\}. After multiplication by t^{-a/2}, the numerator is
Indeed q-a\ge2 makes the first exponent nonnegative. If k\ge2 the second is also nonnegative; if k=1, its integral is at most \int_0^1(1-t)^{-1/2}\,dt=2. Thus \E(R/r)^a\le C^d. This direct beta-integral argument does not require a/2 to be an integer. Multiplying (41) by R^a, averaging, and taking the supremum over the original test proves (32).
The block theorem now gives a complete lower bound from these norms. This application uses success 1/2, which is enough for the constant-accuracy estimate (20).
Corollary 6.3 (Precision bound from radius weights). There is an absolute c>0 such that, for every M(d)=o(d^2), all sufficiently large d, and all 0<\epsilon\le1/10, a learner with uniform-prior angular success at least 1/2 satisfies
The eventual threshold may depend on the memory sequence.
Proof. Put L=\log_2(1/\epsilon). The dimensions with T\ge dL already satisfy the conclusion. On the remaining dimensions, Lemma 4.2, using (18), gives L=o(d), T=o(d^2), and \log_2 W_*=o(d^2). Pad to b=\lceil T/k\rceil=o(d) blocks of k=\lfloor d/16\rfloor samples with width W_*, as in Lemma 4.1. A short final block is filled with unused fresh rows.
Let G_{i,v} be the Borel suffix success from state v after i blocks. Recursion (3) and Theorem 6.1 apply at each boundary. Use dimension n=d-2i at stage i. For all sufficiently large dimensions under consideration, every needed dimension, including the terminal one, satisfies
Iteration of (32), followed by (33), gives
The same bound holds for each initial state and each fixed independent choice of rules, so averaging them is legitimate.
At large d, m\ge d/32 and \log_2 W_*/m\le d. Taking base-two logarithms in (47), with a=d/16, gives L\le C_1(b+1) for an absolute C_1\ge1. If L\ge4C_1, then b\le T/k+1 implies
Since k\ge d/32 eventually, this is the asserted rate. For L<4C_1, (20) gives the same rate with an absolute smaller constant. This completes every accuracy regime.
7 An affine invariant with explicit constants
The radius-weighted norm packages every test of one dimension into a single number. A closely related formulation propagates an explicit bound on every affine subsphere at once. It uses a different moment order and an even radius exponent, so its inverse-radius calculation is an exact finite beta product. We retain its numerical constants.
In this section m is the block length and k is the number of blocks. Set
Proposition 7.1 (All-affine suffix bound). For all sufficiently large d, consider a Borel learner padded to k blocks of m exact Gaussian samples, of width at most W, and with target-independent unit output laws at the last layer. The randomized experiment, shared seed, initialization, and fresh randomness satisfy the joint measurability, independence, and information restrictions of Definition 1.1. Here 0<\epsilon\le1/10, and success means angular error at most \epsilon. Assume
For each fixed shared seed whose rules satisfy these assumptions, and for a state v at layer (k-\ell)m, let g_v(s) be the success probability of the suffix started in that state. For 0\le\ell\le k, every affine subsphere (2) with \dim H=n\ge n_0+2\ell satisfies
The assertion is uniform in the fixed seed and includes states unreachable from the initial layer.
Proof. At \ell=0, fix a terminal output. If 16\epsilon/r\ge1, total mass proves the bound. Otherwise the successful directions lie in a chordal cap of radius 2\epsilon/r. Its polar angle is at most 4\epsilon/r, so the polar calculation in Lemma 3.1 bounds its mass by (16\epsilon/r)^{n-1}. Since n-1\ge a, this is at most (16\epsilon/r)^a. Average over the output law.
Suppose the assertion holds at \ell. Consider a preceding block on an n-dimensional test with n\ge n_0+2(\ell+1). Lemma 2.4, with b=m, gives a beta fraction t, a direction e, and a uniform residual K=n-m dimensional space L inside E=H\cap e^\perp, of dimension N=n-1. Put
By Lemma 2.5, the desired mean is at most
The maximum is over all next boundary states and has already removed their possible dependence on the rest of the exact block data.
Fix t,e,u and write \Lambda=(R_\ell/\rho)^a. The test z'+\rho S(E) is admissible and has dimension n-1, so the induction hypothesis gives \int f_u\,d\sigma_E\le\Lambda. For a cap about y_0\in S(E), condition a uniform direction on its polar angle \theta. The corresponding target is uniform on the affine subsphere with center z'+\rho\cos\theta\,y_0, radius \rho\sin\theta, and space E\cap y_0^\perp of dimension n-2\ge n_0+2\ell. Its average is at most \Lambda(\sin\theta)^{-a}.
For 0<\delta\le1, the chordal cap has polar angle at most 2\delta. Integrate the latitude bound against the normalized \sin^{N-2}\theta density. The exponent N-2-a is nonnegative, and the original normalizing integral is at least 2^{-(N-2)}. Using \sin\theta\le\theta gives
For \delta>1, total mass proves the same bound.
Apply Lemma 6.2 with A_0=1,A_1=4, moment p, and singular exponent N-K=m-1. We have 1\le p<K\le N, 0\le a<N-1, and, for 0\le j<p,
Indeed n\ge n_0+2(\ell+1)\ge d/2+2(\ell+1), while a\le d/16, p\le d/8, and m\le d/16. The tube coefficient in (39) is 36^d, and (40) gives 144^d\Lambda. Consequently
The remaining radius fraction has t\sim\Beta((n-m)/2,m/2). Here q=a/2=\lfloor d/32\rfloor is an integer. Its denominator shapes satisfy
Since n/2\le d/2, every ratio in the finite product is at most (d/2)/(3d/16)=8/3<3. Lemma 2.3 gives
Substitution into (51) yields 864^d(R_\ell/r)^a. For large d, a\ge d/32, hence C_*^a\ge1000^d\ge864^d. This proves the induction step with R_{\ell+1}=C_*R_\ell.
To apply the proposition, let h=\log_2(1/\epsilon), assume M(d)=o(d^2), and suppose uniform-prior success is at least 2/3. The dimensions with T>dh already have the desired rate. On those with T\le dh, apply Lemma 4.2 with c=1 and \alpha=2/3. It gives h=o(d), T=o(d^2), and padded log-width o(d^2). Pad to k=\lceil T/m\rceil=o(d) blocks with W=(T+2)2^M. Then (49) holds for all sufficiently large such dimensions: n_0+2k\le d, and \log_2 W=o(d^2) with p\ge d/16 eventually gives W^{1/p}\le2^d.
At the initial sphere z=0,r=1,H=\R^d, average the bound over initialization conditional on the shared seed, and then over that seed. Since a\ge1,
For h\ge2(\log_2C_*+\log_2 24), this gives
eventually. For smaller h, (20) gives the same d h rate with an absolute constant. This completes the all-affine proof, including its terminal dimension and bounded-precision cases.
8 A fixed-length theorem in varying dimensions
The same conditional direction law gives a different intermediate theorem. Instead of testing one continuation on every affine subsphere in \R^d, we compare learners in different ambient dimensions. The theorem allows an arbitrary Euclidean output and any positive error tolerance. A latitude is simulated by a smaller Gaussian learner, so the induction remains a statement about actual sample laws.
Proposition 8.1 (Dimension-parameterized success bound). There are absolute constants C\ge2 and d_* such that the following holds for every integer d\ge d_*. Set
Let j\ge0 and m be integers with d/2+2j\le m\le d. Consider a fixed-length learner with jk independent exact Gaussian samples in dimension m, Borel rules, and at most 2^{d^2} states at each layer. Its output may be any vector in \R^m. Its rules may use arbitrary fixed parameters independent of the target. Its randomized experiment, initialization, any shared rule seed, and fresh randomness obey the joint measurability, independence, and information restrictions in Definition 1.1, with m in place of d. If the target s is uniform on S^{m-1}, then for every \eta>0,
Proof. We induct on j, simultaneously over all stated dimensions, learners, fixed parameters, and tolerances. All numerical factors introduced below are absolute and independent of the eventual choice of C. We may condition on the shared seed and start in a fixed state. The joint independence and measurability requirements then permit averaging the original conditional probabilities as in Lemma 2.1.
If j=0, the output is independent of the target. When \eta\ge1, (55) is trivial. When \eta<1, a zero output cannot succeed. For a nonzero output v, success implies
Equation (10) therefore bounds the success probability by K_0^d\eta^\gamma, because m-1\ge\gamma and \eta<1. Choosing C large enough proves the base case, including random output laws.
Suppose j\ge1. Let A be the first k rows, let R be their row span, and put
Almost surely u\ne0 and r>0. Conditional on A,u, the target is u+rz with z\sim\sigma_{N_0}, and the first labels are Au. Thus the first block’s selected state supplies no additional information about z under this conditioning.
For fixed u, let E=u^\perp and D=m-1. Write \Prob_{v,s} for the law of the continuation from state v at target s, and \widehat s for its output. Define on S(E)
These Borel functions use fresh samples and do not depend on the remaining matrix data. Conditional success is at most \max_v\int f_v\,d\sigma_{N_0}. By Lemma 2.4, conditional on u, N_0 is a uniform (m-k)-space in E. Here u=\sqrt{1-t}\,e fixes the beta fraction and direction in that lemma. The state maximum is taken before this marginal subspace law is used.
We obtain a cap bound for f=f_v from the induction hypothesis. Fix e\in S(E), a coordinate t\in(-1,1), and set
The target on this latitude is c+\rho z' with z'\sim\sigma_H, where \dim H=m-2 and c\perp H. Simulate the continuation as a learner for z' in H. From a fresh pair (x',\ip{x'}{z'}) in H, draw a standard Gaussian x'' in H^\perp, independently of the joint tuple consisting of z', x', and all previously used learner randomness. Supply the original continuation with
This is exactly a fresh standard Gaussian pair in \R^m for the latitude target. The extra Gaussian is used within the transition, so the state set does not grow. The parameters H,c,\rho,v are fixed independently of the varying target z'. At the end, project the original output onto H and divide by \rho. Original error at most \eta implies simulated error at most \eta/\rho.
The simulated learner has (j-1)k samples, and m-2\ge d/2+2(j-1). The induction hypothesis therefore gives the latitude average
Put B=C^j\eta/r. Integrating the latitude bound against the coordinate density in dimension D, whose remaining exponent is (D-3-\gamma)/2\ge0, gives
Indeed, the coordinate interval has length at most \tau^2/2, and 1-t^2\le\tau^2 throughout that interval. At \tau=2, the cap is the whole sphere. Since c_D\le\sqrt d and D\le d, both the cap estimate and this total-mass estimate have coefficients at most 4^d.
We can therefore apply Lemma 6.2 to every f_v, with ambient dimension D=m-1, subspace dimension m-k, moment p=k, exponent a=\gamma, and \Lambda=B^\gamma, taking A_0=A_1=4. Its hypotheses hold for all sufficiently large d: 1\le p<m-k\le D\le d, 0\le\gamma<D-1, and
The maximum conclusion of the lemma, over at most 2^{d^2} states, yields
Thus the latitude simulation supplies the cap hypothesis, and the common moment lemma accounts for all dependence between directions in the residual space.
It remains to average the inverse radius. By Lemma 2.4, r^2\sim\Beta((m-k)/2,k/2). The real-exponent identity (5) gives
To see the bound, note that m-k-\gamma\ge7d/16+2j, so both exponents in the numerator’s beta integral are nonnegative for large d, and that integral is at most one. Restricting the denominator to [1/4,3/4] gives
In particular, this argument applies to the real exponent \gamma=d/32.
Finally p\ge d/64 for large d. Averaging (58) and applying (59) bounds success by
Since \gamma=d/32, choose the absolute constant C large enough that C^\gamma absorbs this factor and the base-case factor. This completes the simultaneous induction.
The dimension condition in the proposition is essential to its application. Here is the complete reduction that ensures it. Let F=\log(1/\epsilon) use natural logarithms, put F_0=8\log C, and choose an absolute a_0>0 with
Suppose that along arbitrarily large dimensions, learners with M(d)=o(d^2) and uniform-prior angular success at least 2/3 satisfy T<a_0dF. Apply Lemma 4.2 with L=F/\log2, c=a_0\log2, and \alpha=2/3. It gives F=o(d), T=o(d^2), and padded log-width o(d^2) on this supposed sequence only.
Pad to n=\lceil T/k\rceil=o(d) blocks. The padded width (T+2)2^M is eventually at most 2^{d^2}, and d/2+2n\le d. If F\le F_0, the supposed sample bound and (60) give T<d/8, contradicting (20). If F>F_0, then k\ge d/64 and
Apply Proposition 8.1 with m=d,j=n, and \eta=\epsilon. The original unit-output angular success event implies Euclidean error at most \epsilon, whereas the proposition bounds that Euclidean success by \exp(-\gamma F/2)<2/3 at large d. This contradiction proves the precision lower bound by the fixed-length route, while retaining its stronger arbitrary-vector intermediate statement.
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. Theorem 3 and Theorem 10 locators refer to the published PMLR version. https://proceedings.mlr.press/v99/dagan19b.html.
- [2]Peter Frankl and Hiroshi Maehara. Some Geometric Applications of the Beta Distribution. Annals of the Institute of Statistical Mathematics, 42(3):463–474, 1990. https://doi.org/10.1007/BF00049302. doi:10.1007/BF00049302.
- [3]Francesco Mezzadri. How to Generate Random Matrices from the Classical Compact Groups. Notices of the American Mathematical Society, 54:592–604, 2007. Section 8, Theorem 4 and Corollary 1 locators refer to arXiv:math-ph/0609050v2, 27 February 2007. https://arxiv.org/abs/math-ph/0609050v2.
- [4]Ran Raz. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. 2016. arXiv:1602.05161v1, 16 February 2016. https://arxiv.org/abs/1602.05161v1.
- [5]Boris Rubin. On the Blaschke–Petkantschin Formula and Drury’s Identity. 2018. arXiv:1801.09113v2, 22 November 2018; locators refer to this version. https://arxiv.org/abs/1801.09113v2.
- [6]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 arXiv:1904.08544v2, 10 October 2020; theorem and section locators refer to that version. https://arxiv.org/abs/1904.08544v2. doi:10.1145/3313276.3316403.
- [7]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.
- [8]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.