A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 6 OF 6 · Memory–sample lower bounds for noiseless Gaussian regression
Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression
expertly designed by an internal OpenAI model · released 2026-09-27
· original PDF
IntroductionAn exact linear equation may contain arbitrarily fine real information. Indeed, \(d\) independent Gaussian equations determine a vector in \(\mathbb 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 (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 \[X_t\sim N(0,I_d),\qquad Y_t=\langle X_t,s\rangle,\qquad 1\le t\le T,\] 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 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, the following implication holds. If \(S\) is uniform on \(S^{d-1}\), independently of the Gaussian rows and learner randomness, and \[\mathbb P\{\arccos\langle \widehat s,S\rangle\le\epsilon\}\ge\frac23,\] then \[ T\ge 2^{-16}d\log_2(1/\epsilon). \tag{1}\] Corollary 3 (Guarantees for every signal). Under the memory assumption of Theorem 2, suppose a learner satisfies \[\mathbb P_s\{\arccos\langle \widehat s,s\rangle\le\epsilon\}\ge\frac23 \qquad\text{for every }s\in S^{d-1},\] where \(\mathbb P_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 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 ancestryMemory restrictions affect statistical risk already in sparse noisy regression, as shown by Steinhardt and Duchi (Steinhardt and Duchi 2015, sec. 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 (Steinhardt et al. 2016, sec. 1.1, Conjecture 1). Raz established the qualitative separation through finite-width branching programs (Raz 2016, 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 (Sharan et al. 2019). 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 (Sharan et al. 2019, Theorem 1). Their proof experiment draws the target uniformly on the sphere (Sharan et al. 2019, sec. 2). The exact labels in Definition 1 are more informative than noisy labels, so that noisy lower bound alone does not give Theorem 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 (Dagan et al. 2019). 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 (Sharan et al. 2019, sec. 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 (Frankl and Maehara 1990); all normalized densities, conditional laws, and inequalities used here are proved locally. Exact observations and residual subspheresFor 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 \[ z+rS(H),\qquad z\perp H,\quad r>0,\quad \left\lVert z\right\rVert^2+r^2=1. \tag{2}\] 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 \[z+p+\rho S(K),\qquad \rho^2=r^2-\left\lVert p\right\rVert^2,\] 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 \[F_v(K)=\int g_v(z+p+\rho u)\,d\sigma_K(u).\] If the block can choose among at most \(W\) states, then for every positive integer \(h\), \[\mathbb E_K\max_v F_v(K) \le\left(\sum_v\mathbb E_K F_v(K)^h\right)^{1/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 boundThe 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 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 formulationsThe 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 15: 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 2 comes from the beta-mixture proof. Continuations and exact residual spheresThe 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. Borel rules and counterfactual continuationsLemma 4 (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, 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 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/\left\lVert x\right\rVert\) has a Lebesgue density when \(d\ge2\); this will also follow from (4) below. Scaling by \(\left\lVert x\right\rVert\) shows that the conditional law of \(\langle x,S\rangle\) has a density. The event \(x=0\) is Gaussian-null. Thus each pair \((X_t,\langle X_t,S\rangle)\) 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 \[\mathbb P\{\text{current state}=v,\ (X_t,\langle X_t,S\rangle)\in Z\} \le \mathbb P\{(X_t,\langle X_t,S\rangle)\in Z\}=0.\] 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 \[ G_{\rm in}(s)= \mathbb E_X\sum_v\kappa_v(X,Xs)G_v(s). \tag{3}\] 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. Spherical coordinates and beta fractionsWe use uniform probability, never unnormalized surface area, on each sphere. The following normalized formulas are classical; see Frankl and Maehara (Frankl and Maehara 1990) for the geometric beta-law context. We include their derivation and the conditional information needed here. Lemma 5 (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 \[\left\lVert P_{E_1}U\right\rVert^2\sim\operatorname{Beta}(l/2,(D-l)/2),\] 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 \[ c(D,l)(1-\left\lVert t\right\rVert^2)^{(D-l-2)/2}\mathbf 1_{\{\left\lVert t\right\rVert<1\}}, \qquad c(D,l)=\frac{\Gamma(D/2)} {\pi^{l/2}\Gamma((D-l)/2)}. \tag{4}\] 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/\left\lVert G\right\rVert\) 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 \[\frac{q^{\alpha-1}(1-q)^{\beta-1}}{\mathrm B(\alpha,\beta)} \cdot \frac{v^{\alpha+\beta-1}e^{-v}}{\Gamma(\alpha+\beta)}.\] The fraction and sum are independent, and the fraction is \(\operatorname{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 6 (Beta moments and products). For \(A,B>0\) and \(Z\sim\operatorname{Beta}(A,B)\), a real \(q\ge0\) satisfies \[ \mathbb EZ^{-q} =\frac{\mathrm B(A-q,B)}{\mathrm B(A,B)} =\frac{\Gamma(A-q)\Gamma(A+B)} {\Gamma(A)\Gamma(A+B-q)} \quad\text{if }q<A. \tag{5}\] The moment diverges when \(q\ge A\). If \(h\) is a nonnegative integer with \(h<A\), then \[ \mathbb EZ^{-h}=\prod_{t=1}^h\frac{A+B-t}{A-t}, \tag{6}\] where the product for \(h=0\) is one. Moreover, for \(C>0\), independent \[Z\sim\operatorname{Beta}(A,B),\qquad X\sim\operatorname{Beta}(A+B,C)\] satisfy \[ ZX\sim\operatorname{Beta}(A,B+C). \tag{7}\] 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 \(\operatorname{Beta}(A,B+C)\). ◻ What an exact block leavesUniform orthogonal frames may be generated successively from uniform sphere directions in perpendicular complements; Mezzadri gives an authoritative exposition of this construction (Mezzadri 2007, sec. 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 7 (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 \(\left\lVert z\right\rVert^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 \[ s=z+r\sqrt{1-t}\,e+r\sqrt t\,v, \quad t\sim\operatorname{Beta}((D-b)/2,b/2),\quad e\sim\sigma_{R_X},\quad v\sim\sigma_K, \tag{8}\] where the three draws are independent. The labels are \[Xs=X\bigl(z+r\sqrt{1-t}\,e\bigr).\] 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 5 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 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 8 (Averaging after a block). In the setting of Lemma 7, 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 \[z'=z+r\sqrt{1-t}\,e,\qquad \rho=r\sqrt t,\qquad F_v(K)=\int g_v(z'+\rho u)\,d\sigma_K(u).\] Then \[ \mathbb E_{X,s}\sum_v\kappa_v(X,Xs)g_v(s) \le \mathbb E_{t,e}\mathbb E_{K\mid e}\max_v F_v(K). \tag{9}\] 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 7 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. Caps and directions in a random subspaceThe 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. Caps and terminal outputsLemma 9 (Spherical caps). Let \(e\) be a unit vector in a \(D\)-dimensional Euclidean space. For \(D\ge3\) and every \(\delta>0\), \[ \sigma_{\mathbb R^D}\{u:\left\lVert u-e\right\rVert\le\delta\} \le \frac{c_D}{2}\delta^{D-1} \le \frac{\sqrt D}{2}\delta^{D-1}. \tag{10}\] For \(D\ge2\) and \(0\le\theta\le\pi\), \[ \sigma_{\mathbb R^D}\{u:\angle(u,e)\le\theta\} \le(2\theta)^{D-1}. \tag{11}\] 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 \[ \min\{1,(8\epsilon/R)^{D-1}\}. \tag{12}\] The last assertion also holds after averaging any target-independent output law. Proof. For the chordal cap, \(t=\langle u,e\rangle\) 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. ◻ Directions with a common random subspaceThe joint direction law below is a spherical form of the linear Blaschke–Petkantschin formula; see Rubin (Rubin 2018, Corollary 3.2, equation (3.5)). We derive the normalized conditional density directly. Lemma 10 (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 \[ \frac{c(K,j)}{c(N,j)} \operatorname{dist}(y,V)^{-(N-K)} \le \operatorname{dist}(y,V)^{-(N-K)}. \tag{13}\] 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 \[L=V\oplus L',\qquad L'\text{ uniform of dimension }K-j\text{ in }V^\perp.\] 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 \[\frac{c(K,j)}{c(N,j)} (1-\left\lVert P_Vy\right\rVert^2)^{-(N-K)/2},\] which is (13). The integral normalizing \(c(K,j)\) is at least that normalizing \(c(N,j)\), because \((1-\left\lVert t\right\rVert^2)^{(K-j-2)/2}\ge (1-\left\lVert t\right\rVert^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. ◻ Stopping and the remaining dimension budgetEach 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 11 (Terminal count and padding). For \(d\ge3\), a learner of horizon \(T\) satisfies \[\begin{align*} \mathbb P(\mathrm{success}) &\le (T+1)W(c_d/2)\epsilon^{d-1},\tag{14}\\ \mathbb P(\mathrm{success}) &\le (T+1)W(2\epsilon)^{d-1}. \tag{15}\end{align*}\] The learner can be padded to any prescribed later sample layer, with the same success law and width at most \[ W_*=(T+2)W. \tag{16}\] Proof. Fix a seed realization covered by Lemma 4 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 4 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 \[T+1\ge \frac{4}{3c_d}\,2^{-M}\epsilon^{-(d-1)}.\] 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 12 (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 \[ L=o(d),\qquad T=o(d^2),\qquad \log_2 W_*=o(d^2). \tag{17}\] 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 \[ (d-2)L \le M+\frac32\log_2d+\log_2\frac{c+1}{2\alpha}. \tag{18}\] 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 13 (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 \[ \frac{T}{d(1-r_0^2)} +\min\left\{1,\ \frac{c_D}{2}(2\epsilon/r_0)^{D-1},\ (8\epsilon/r_0)^{D-1}\right\}. \tag{19}\] 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 \[S=p+rU,\qquad r=\sqrt{1-\left\lVert p\right\rVert^2},\qquad U\sim\sigma_{R_X^\perp}.\] Conditional on the data, the residual direction is uniform. At a fixed row span, spherical symmetry gives \(\mathbb E\left\lVert p\right\rVert^2=T/d\). Markov’s inequality yields \(\mathbb P(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 9. 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\), \[\mathbb P(\mathrm{success}) \le\frac13+(c_D/2)0.4^{D-1}=\frac13+o(1)\] uniformly in this range of \(T\). Thus uniform-prior success at least \(1/2\) requires \[ T>d/4 \tag{20}\] 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. A beta-mixture comparison and the explicit constantA 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 10 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 14 (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 \[\alpha=\frac{n-j}{2},\qquad \alpha_*=\frac{D'-j}{2},\qquad \beta_0=\frac j2,\qquad \beta_1=\frac{D'-n+j-1}{2}.\] Let \(\nu_0=\sigma_E\). Let \(\nu_1\) be the law of \[ \sqrt{1-Z}\,e_0+\sqrt Z\,u_0,\qquad Z\sim\operatorname{Beta}(\alpha,\alpha_*-\alpha),\quad e_0\sim\sigma_V,\quad u_0\mid e_0\sim\sigma_{E\cap e_0^\perp}, \tag{21}\] where \(Z\) is independent of the directions. Then, as positive measures on \(S(E)\), \[ \operatorname{Law}(v)\le2^{D'}(\nu_0+\nu_1). \tag{22}\] 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)=\left\lVert P_{V^\perp}y\right\rVert^2\). For the actual direction, the orthogonal decomposition \(N=V\oplus(N\cap V^\perp)\) and Lemma 5 give \[Q(v)\sim\operatorname{Beta}(\alpha,\beta_0).\] For \(\nu_0\), the fraction has law \(\operatorname{Beta}(\alpha_*,\beta_0)\). Under \(\nu_1\), it equals \(ZX\), where \(X=\left\lVert P_{V^\perp}u_0\right\rVert^2\). If \(j>1\), the decomposition \[E\cap e_0^\perp=V^\perp\oplus(V\cap e_0^\perp)\] gives \(X\sim\operatorname{Beta}(\alpha_*,(j-1)/2)\), independently of \(Z\). The beta-product identity (7) gives \(Q\sim\operatorname{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 \[\alpha_*-\alpha=(b-1)/2>0,\qquad \beta_1-\beta_0=(b-2)/2\ge0.\] Let \(f_{A,B}\) denote the normalized beta density. The beta integral decreases when either positive shape parameter increases. For \(q\ge1/2\), \[\frac{f_{\alpha,\beta_0}(q)}{f_{\alpha_*,\beta_0}(q)} =\frac{\mathrm B(\alpha_*,\beta_0)} {\mathrm B(\alpha,\beta_0)} q^{-(\alpha_*-\alpha)} \le2^{\alpha_*-\alpha}\le2^{D'}.\] For \(q<1/2\), \[\frac{f_{\alpha,\beta_0}(q)}{f_{\alpha,\beta_1}(q)} =\frac{\mathrm B(\alpha,\beta_1)} {\mathrm B(\alpha,\beta_0)} (1-q)^{-(\beta_1-\beta_0)} \le2^{\beta_1-\beta_0}\le2^{D'}.\] 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 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 \[ \lambda=\log_2(1/\epsilon),\qquad c_*=2^{-16},\qquad T<c_*d\lambda. \tag{23}\] The short-run reduction.Lemma 12, 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 \[w=(T+2)2^M.\] 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 \[ k=m=\lfloor d/16\rfloor,\qquad p=2\lfloor d/32\rfloor,\qquad \ell=p/2,\qquad J=\lceil T/k\rceil,\qquad G=2^{4d}w^{1/m}. \tag{24}\] 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 11, 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, \[ J\le32c_*\lambda+1=o(d),\qquad J\le d/8,\qquad m,p\ge d/32. \tag{25}\] The first inequality uses \(k\ge d/32\). The suffix bound.Fix a rule seed for which Lemma 4 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 \[ \int h_{i,v}(c+ru)\,d\sigma_H(u) \le G^{J-i}(8\epsilon/r)^p. \tag{26}\] 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 9 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 7 gives \[\rho^2\sim\operatorname{Beta}((D-b)/2,b/2),\qquad c'=c+r\sqrt{1-\rho^2}\,e,\qquad r'=r\rho,\] \[E=H\cap e^\perp,\qquad D'=D-1,\qquad n=D-b.\] Conditional on \(\rho,e\), the residual space \(N\) is uniform of dimension \(n\) in \(E\). By Lemma 8, the left side of (26) is at most \[ \mathbb E_{\rho,e}\mathbb E_N\max_{v'}F_{v'}(N),\qquad F_{v'}(N)=\int h_{i+1,v'}(c'+r'u)\,d\sigma_N(u). \tag{27}\] 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 \[U_0=G^{J-i-1}(8\epsilon/r')^p.\] 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 10 makes \(N\) uniform among the \(n\)-spaces containing \(V\). The parameter bounds imply \[D\ge3d/4,\qquad n\ge11d/16,\qquad m\le d/16<n.\] 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 14. 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 \[\widetilde H=E\cap e_0^\perp,\qquad \widetilde c=c'+r'\sqrt{1-Z}\,e_0,\qquad \widetilde r=r'\sqrt Z.\] Its linear dimension is \(D-2\ge d-2(i+1)\). Also \(\widetilde c\perp\widetilde H\), \(\widetilde r>0\), and \(\left\lVert \widetilde c\right\rVert^2+\widetilde r^2=1\), because \(c'\perp E\) and \(\left\lVert c'\right\rVert^2+(r')^2=1\). The induction hypothesis bounds its mean by \(U_0Z^{-\ell}\). In the notation of Lemma 14, \[n-j\ge10d/16,\qquad \alpha-\ell\ge9d/32\ge d/4,\qquad \alpha_*\le d/2.\] 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: \[ \mathbb EZ^{-\ell} =\prod_{t=1}^{\ell}\frac{\alpha_*-t}{\alpha-t} \le2^\ell\le2^d. \tag{28}\] Since \(D'\le d\), the mixture domination bounds the conditional expected next factor by \[2^dU_0(1+\mathbb EZ^{-\ell})\le2^{3d}U_0.\] 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 \[\mathbb E_NF_{v'}(N)^m\le(2^{3d}U_0)^m.\] Jensen’s inequality and the sum of the at most \(w\) state moments then give \[\mathbb E_N\max_{v'}F_{v'}(N)\le w^{1/m}2^{3d}U_0.\] 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 \[ \mathbb E\rho^{-p} =\prod_{t=1}^{\ell}\frac{D/2-t}{n/2-t} \le2^\ell\le2^d. \tag{29}\] 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=\mathbb 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 4 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 \[\begin{align*} 5d(32c_*\lambda+1)+p(3-\lambda) &\le5d+(160c_*-1/64)d\lambda\\ &\le5d-d\lambda/128\le-3d. \tag{30}\end{align*}\] 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). ◻ The radius-weighted block estimateWe 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 \[ B_n(g)=\sup_{\substack{\dim H=n\\ z\perp H,\ R>0\\ \left\lVert z\right\rVert^2+R^2=1}} R^a\int g(z+R\omega)\,d\sigma_H(\omega). \tag{31}\] In particular \(B_d(g)=\int g\,d\sigma_{\mathbb 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 15 (Radius-weighted block estimate). There are absolute constants \(C\ge1\) and \(d_*\) such that the following holds for every integer \(d\ge d_*\). Put \[k=m=\lfloor d/16\rfloor,\qquad a=d/16.\] Let \(W\ge1\), let \(\mathcal V\) be a nonempty finite set with \(|\mathcal V|\le W\), and let \(\kappa_v:\mathbb R^{k\times d}\times\mathbb 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 \[g_{\rm in}(s)= \mathbb E_X\sum_{v\in\mathcal V}\kappa_v(X,Xs)g_v(s),\] where \(X\) has \(k\) independent \(N(0,I_d)\) rows. For every integer \(n\) with \(d/2\le n\le d\), \[ B_n(g_{\rm in}) \le W^{1/m}C^d\max_{v\in\mathcal V}B_{n-2}(g_v). \tag{32}\] If \(\epsilon>0\), \(\pi\) is any probability measure on \(S^{d-1}\) and \[g_\pi(s)=\int\mathbf 1_{\{\arccos\langle u,s\rangle\le\epsilon\}}\,\pi(du),\] then, in the same range of \(n\), \[ B_n(g_\pi)\le C^d\epsilon^a. \tag{33}\] 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. Caps and subspace momentsThe use of replica moments and successive orthogonalization is related to Sharan, Sidford, and Valiant (Sharan et al. 2019, sec. 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 16 (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\), \[\begin{align*} \int f\,d\sigma_E&\le A_0^d\Lambda,\tag{34}\\ \int_{\left\lVert y-y_0\right\rVert\le\delta}f(y)\,d\sigma_E(y) &\le A_1^d\Lambda\delta^{N-1-a} \quad(y_0\in S(E),\ \delta>0). \tag{35}\end{align*}\] If \[ N-1-a-(h-1)-b\ge1, \tag{36}\] then \[ \mathbb E_L\left(\int f\,d\sigma_L\right)^h \le\left([4\max\{A_0,9A_1\}]^d\Lambda\right)^h. \tag{37}\] For a nonempty family of at most \(W\) functions satisfying the same conditions with numbers \(\Lambda_v\), \[ \mathbb E_L\max_v\int f_v\,d\sigma_L \le W^{1/h}[4\max\{A_0,9A_1\}]^d\max_v\Lambda_v. \tag{38}\] 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 \[ \int_{\operatorname{dist}(y,V)\le\delta}f\,d\sigma_E \le A_1^d3^{\alpha+j}\Lambda\delta^{\alpha-j} \le Q_0^d\Lambda\delta^{\alpha-j}. \tag{39}\] 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}<\operatorname{dist}(y,V)\le2^{-i}\) therefore give \[\begin{align*} \int f(y)\operatorname{dist}(y,V)^{-b}\,d\sigma_E(y) &\le Q_0^d\Lambda\,2^b \sum_{i\ge0}2^{-i(\alpha-j-b)}\\ &\le Q_0^d\Lambda\,2^{b+1} \le (4Q_0)^d\Lambda. \tag{40}\end{align*}\] 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 \(\mathbb E\prod_{i=1}^h f(Y_i)\). Lemma 10 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 \[\mathbb E\max_vF_v(L) \le\mathbb E\left(\sum_vF_v(L)^h\right)^{1/h} \le\left(\sum_v\mathbb EF_v(L)^h\right)^{1/h},\] 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. Proof of the block estimate and its applicationA 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 15. 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 \[p=R P_V\omega,\qquad r=\sqrt{R^2-\left\lVert p\right\rVert^2},\qquad K=H\cap V^\perp,\qquad q=n-k.\] 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 8 bounds the averaged block function by \[ \mathbb E_p\mathbb E_{K\mid p}\max_v \int g_v(z+p+rU)\,d\sigma_K(U). \tag{41}\] 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 7 gives this conditional law. Fix \(p\) and one function \(g=g_v\). On \(S(H')\) set \[f(U)=g(z+p+rU),\qquad \Lambda=r^{-a}B_{n-2}(g).\] For \(w\in S(H')\), condition on the latitude coordinate \(t=\langle U,w\rangle\in(-1,1)\). The target on that latitude is uniform on \[z+p+rtw+r\sqrt{1-t^2}\,S(H'\cap w^\perp).\] 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 \(\left\lVert z\right\rVert^2+\left\lVert p\right\rVert^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 \[\begin{align*} \int f\,d\sigma_{H'}&\le2c_N\Lambda,\tag{42}\\ \int_{\left\lVert U-w\right\rVert\le\eta} f(U)\,d\sigma_{H'}(U) &\le c_N\Lambda\eta^{N-1-a} \qquad(0<\eta\le1). \tag{43}\end{align*}\] 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 16 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\), \[N-1-a-l-(N-q) =n-1-a-l-k \ge n-a-2k \ge5d/16\ge1.\] The moment conclusion is \[ \mathbb E_{K\mid p}\left(\int g(z+p+rU)\,d\sigma_K(U)\right)^m \le\left(C^d r^{-a}B_{n-2}(g)\right)^m. \tag{44}\] 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 \[W^{1/m}C^d r^{-a}\max_v B_{n-2}(g_v).\] It remains to average the residual radius. By Lemma 7, \(t=(r/R)^2\sim\operatorname{Beta}(q/2,k/2)\). The denominator of its beta integral satisfies \[\mathrm B(q/2,k/2) \ge \frac12\,4^{-(q/2-1)_+-(k/2-1)_+} \ge 4^{-d},\] by restriction to \([1/4,3/4]\), where \(x_+=\max\{x,0\}\). After multiplication by \(t^{-a/2}\), the numerator is \[ \int_0^1 t^{(q-a)/2-1}(1-t)^{k/2-1}\,dt\le2. \tag{45}\] 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 \(\mathbb 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 17 (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 \[T\ge c\,d\log_2(1/\epsilon).\] 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 12, 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 11. 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 15 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 \[ d-2i\ge d-2b\ge d/2\qquad(0\le i\le b). \tag{46}\] Iteration of (32), followed by (33), gives \[ \frac12\le [W_*^{1/m}C^d]^b C^d\epsilon^a. \tag{47}\] 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 \[T\ge kL/(2C_1).\] 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. ◻ An affine invariant with explicit constantsThe 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 \[ m=\lfloor d/16\rfloor,\qquad p=\lfloor d/8\rfloor,\qquad a=2\lfloor d/32\rfloor,\qquad n_0=\lceil d/2\rceil,\qquad C_*=1000^{32}. \tag{48}\] Proposition 18 (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. Here \(0<\epsilon\le1/10\), and success means angular error at most \(\epsilon\). Assume \[ n_0+2k\le d,\qquad W^{1/p}\le2^d. \tag{49}\] 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 \[ \int g_v(z+r\xi)\,d\sigma_H(\xi) \le (R_\ell/r)^a,\qquad R_\ell=16C_*^\ell\epsilon. \tag{50}\] 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 9 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 7, 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 \[z'=z+r\sqrt{1-t}\,e,\qquad \rho=r\sqrt t,\qquad f_u(y)=g_u(z'+\rho y),\qquad F_u(L)=\int f_u\,d\sigma_L.\] By Lemma 8, the desired mean is at most \[ \mathbb E_{t,e}\mathbb E_L\max_u F_u(L). \tag{51}\] 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 \[ \int_{\left\lVert y-y_0\right\rVert\le\delta}f_u\,d\sigma_E \le4^d\Lambda\delta^{N-1-a}. \tag{52}\] For \(\delta>1\), total mass proves the same bound. Apply Lemma 16 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\), \[N-1-a-j-(m-1) \ge n-a-p-m \ge d/4+2(\ell+1)\ge1.\] 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 \[\mathbb E_L F_u(L)^p\le(144^d\Lambda)^p,\qquad \mathbb E_L\max_uF_u(L)\le W^{1/p}144^d\Lambda\le288^d\Lambda.\] The remaining radius fraction has \(t\sim\operatorname{Beta}((n-m)/2,m/2)\). Here \(q=a/2=\lfloor d/32\rfloor\) is an integer. Its denominator shapes satisfy \[(n-m)/2-q\ge3d/16>0.\] Since \(n/2\le d/2\), every ratio in the finite product is at most \((d/2)/(3d/16)=8/3<3\). Lemma 6 gives \[ \mathbb Et^{-a/2} =\prod_{j=1}^{q}\frac{n/2-j}{(n-m)/2-j}\le3^d. \tag{53}\] 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 12 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=\mathbb R^d\), average the bound over initialization conditional on the shared seed, and then over that seed. Since \(a\ge1\), \[ \frac23\le(16C_*^k\epsilon)^a,\qquad h\le k\log_2C_*+\log_2 24 \le(T/m+1)\log_2C_*+\log_2 24. \tag{54}\] For \(h\ge2(\log_2C_*+\log_2 24)\), this gives \[T\ge \frac{mh}{2\log_2C_*},\qquad m\ge d/32\] 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. A fixed-length theorem in varying dimensionsThe same conditional direction law gives a different intermediate theorem. Instead of testing one continuation on every affine subsphere in \(\mathbb 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 19 (Dimension-parameterized success bound). There are absolute constants \(C\ge2\) and \(d_*\) such that the following holds for every integer \(d\ge d_*\). Set \[k=p=\lfloor d/32\rfloor,\qquad \gamma=d/32.\] 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 \(\mathbb 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, with \(m\) in place of \(d\). If the target \(s\) is uniform on \(S^{m-1}\), then for every \(\eta>0\), \[ \mathbb P\{\left\lVert \mathrm{output}-s\right\rVert\le\eta\} \le(C^{j+1}\eta)^\gamma. \tag{55}\] 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 4. 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 \[\left\lVert \frac{v}{\left\lVert v\right\rVert}-s\right\rVert \le \left|1-\left\lVert v\right\rVert\right|+\left\lVert v-s\right\rVert\le2\eta.\] 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 \[N_0=R^\perp,\qquad u=P_Rs,\qquad r=\sqrt{1-\left\lVert u\right\rVert^2}.\] 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 \(\mathbb P_{v,s}\) for the law of the continuation from state \(v\) at target \(s\), and \(\widehat s\) for its output. Define on \(S(E)\) \[f_v(z)=\mathbb P_{v,u+rz}\{\left\lVert \widehat s-(u+rz)\right\rVert\le\eta\}.\] 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 7, 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 \[H=E\cap e^\perp,\qquad c=u+rt e,\qquad \rho=r\sqrt{1-t^2}.\] 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',\langle x',z'\rangle)\) 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 \[ x=x'+x'',\qquad y=\langle x'',c\rangle+\rho\langle x',z'\rangle=\langle x,c+\rho z'\rangle. \tag{56}\] This is exactly a fresh standard Gaussian pair in \(\mathbb 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 \[\int f(t e+\sqrt{1-t^2}\,z')\,d\sigma_H(z') \le\left(\frac{C^j\eta}{r\sqrt{1-t^2}}\right)^\gamma.\] 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 \[ \int_{\left\lVert z-e\right\rVert\le\tau}f(z)\,d\sigma_E(z) \le(c_D/2)B^\gamma\tau^{D-1-\gamma} \qquad(\tau>0). \tag{57}\] 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 16 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 \[D-1-\gamma-(p-1)-(k-1) =m-\gamma-2k\ge13d/32+2j\ge1.\] The maximum conclusion of the lemma, over at most \(2^{d^2}\) states, yields \[ \mathbb E\left[\max_v\int f_v\,d\sigma_{N_0}\,\middle|\,u\right] \le2^{d^2/p}144^d(C^j\eta/r)^\gamma. \tag{58}\] 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 7, \(r^2\sim\operatorname{Beta}((m-k)/2,k/2)\). The real-exponent identity (5) gives \[ \mathbb Er^{-\gamma} =\frac{\mathrm B((m-k-\gamma)/2,k/2)} {\mathrm B((m-k)/2,k/2)} \le4^d. \tag{59}\] 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 \[\mathrm B((m-k)/2,k/2) \ge\tfrac12\,4^{-(m/2-2)}\ge4^{-d}.\] 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 \[(2^{64}\cdot576)^d(C^j\eta)^\gamma.\] 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 \[ a_0\le\frac1{8F_0},\qquad a_0\le\frac1{256\log C}. \tag{60}\] 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 12 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 \[(n+1)\log C \le(64a_0F+2)\log C\le F/2.\] Apply Proposition 19 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.
Dagan, Yuval, Gil Kur, and Ohad Shamir. 2019. “Space Lower Bounds for Linear Prediction in the Streaming Model.” Proceedings of the Thirty-Second Conference on Learning Theory, Proceedings of machine learning research, vol. 99: 929–54.
Frankl, Peter, and Hiroshi Maehara. 1990. “Some Geometric Applications of the Beta Distribution.” Annals of the Institute of Statistical Mathematics 42 (3): 463–74. https://doi.org/10.1007/BF00049302.
Mezzadri, Francesco. 2007. “How to Generate Random Matrices from the Classical Compact Groups.” Notices of the American Mathematical Society 54: 592–604.
Raz, Ran. 2016. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning.
Rubin, Boris. 2018. On the Blaschke–Petkantschin Formula and Drury’s Identity.
Sharan, Vatsal, Aaron Sidford, and Gregory Valiant. 2019. “Memory-Sample Tradeoffs for Linear Regression with Small Error.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 890–901. https://doi.org/10.1145/3313276.3316403.
Steinhardt, Jacob, and John Duchi. 2015. “Minimax Rates for Memory-Bounded Sparse Linear Regression.” Proceedings of the 28th Conference on Learning Theory, Proceedings of machine learning research, vol. 40: 1564–87.
Steinhardt, Jacob, Gregory Valiant, and Stefan Wager. 2016. “Memory, Communication, and Statistical Queries.” 29th Annual Conference on Learning Theory, Proceedings of machine learning research, vol. 49: 1490–516.
|
| ||||||||
|