Memory–sample lower bounds for noiseless Gaussian regression

What OpenAI claims

For fixed A > 0, a one-pass learner with Ad² persistent bits needs Ω_A(d log(1/ϵ)) noiseless Gaussian samples to recover a unit vector to angular error 0 < ϵ ≤ 1/10 with probability 2/3, uniformly in accuracy for large d. Computation and randomized updates are unrestricted, but output uses only the terminal state, stopping index and fresh randomness. (Lean)

Papers (6)

1. Memory and precision in noiseless Gaussian regression

   27 September 2026 · Preprint, not peer reviewed · PDF

   For every fixed A > 0, a learner that retains at most Ad² bits between fresh exact Gaussian linear measurements needs Ω_A(d log(1/ϵ)) measurements to estimate a uniformly random unit vector to angular error at most ϵ, for any 0 < ϵ ≤ 1/10, with probability at least 2/3. The constant is absolute for o(d²) memory.

2. Posterior replicas and conditional information in Gaussian regression

   27 September 2026 · Preprint, not peer reviewed · PDF

   For a signal with density bounded by L relative to uniform probability on S^d-1, we bound the information in a finite message W formed from exact Gaussian measurements, conditional on an independent projection revealed only to the analyst. For explicit row counts proportional to d, the bound is O(H(W)/d+d+log(2+log L)). Consequently, a finite-state learner with o(d²) persistent bits and a deterministic sample horizon needs Ω(d log(1/ϵ)) fresh noiseless Gaussian measurements for constant-probability angular accuracy 0 < ϵ ≤ 1/10 under the uniform spherical prior.

3. Localization costs and information growth for exact Gaussian observations

   27 September 2026 · Preprint, not peer reviewed · PDF

   For the image of a uniform cube under a spherical coordinate map, we prove that finite messages from t blocks of Θ(d) exact Gaussian measurements reveal only O_A(dt) information when each message has at most exp(Ad²) values, for fixed A. The same bound holds when each message is supplemented with a nested cell that restores the required geometric spread.

4. Projection moments, positive cap domination, and Riesz estimates on the sphere

   27 September 2026 · Preprint, not peer reviewed · PDF

   We prove moment estimates for exact random projections of finite measures whose mass is controlled on Euclidean balls, and derive positive domination by countable sums of spherical cap measures. For learners with M=o(d²) bits of memory, these estimates give three proofs that uniform-sphere average success at least 2/3 at angular accuracy 0 < ϵ ≤ 1/10 requires Ω(d log(1/ϵ)) noiseless Gaussian observations. The three proofs keep their different stopping and accuracy costs explicit.

5. Replacing Gaussian observations in memory-constrained inference

   27 September 2026 · Preprint, not peer reviewed · PDF

   Replacing the Gaussian rows used to select a finite message by independent rows increases the remaining conditional information by at most Cd, for a uniform spherical signal, message entropy at most d2, and the specified row dimensions proportional to d. As an application, we prove that learners with M=o(d²) persistent bits need T=Ω(d log(1/ϵ)) exact observations to attain uniform-sphere angular success at least 3/5, for 0 < ϵ ≤ 1/10 and a deterministic finite horizon.

6. Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression

   27 September 2026 · Preprint, not peer reviewed · PDF

   Let a finite-state streaming learner estimate a uniformly random unit vector from independent exact Gaussian linear measurements. We prove that o(d²) bits of persistent memory and angular success probability at least 2/3 require at least 2^-16d log₂(1/ϵ) samples for all sufficiently large d, uniformly for 0 < ϵ ≤ 1/10. The proof conditions each batch on its observed projection and controls the resulting random residual subsphere.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.