Memory–sample lower bounds for noiseless Gaussian regression

1 · The essentials

How much can a learner discover if it receives perfectly accurate measurements but can remember only a limited amount between them? This family studies a hidden direction chosen uniformly at random in a space with $d$ coordinates. Each measurement gives an exact reading along a fresh, randomly chosen Gaussian direction. The main result says that, for any fixed positive $A$ , a learner retaining at most $A d^{2}$ bits needs at least a constant times $d lo g (1/ ϵ)$ measurements to find the hidden direction within angle $ϵ$ , with success probability at least two thirds. This holds for sufficiently large $d$ and every $0 < ϵ \leq 1/10$ , with a constant that may depend on $A$ . Even unlimited computation and randomized updates do not remove this requirement: the final answer may use only the last stored state, the stopping index, and fresh randomness. The main result has a Lean formalization, while the companion manuscripts examine several ways to establish related memory–measurement limits.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine trying to identify a direction from a stream of perfectly accurate clues while keeping only a small notebook. You may think as hard as you like about each clue, but only what remains in the notebook carries forward; the result quantifies a limitation of that situation for a particular mathematical measurement model.

Why it matters

The result separates limited memory from imperfect data: the measurements here have no noise, yet the memory restriction still imposes a sample requirement that grows with the requested precision. It also isolates memory from computational power, since computation and randomized updates are unrestricted. The companion results connect this limitation to bounds on how much information finite messages can retain from exact measurements.

2 · Going further

The precise problem is one-pass estimation of a uniformly random unit vector on $S^{d - 1}$ from fresh exact Gaussian linear measurements. For every fixed $A > 0$ , the main result gives a lower bound of $Ω_{A} (d lo g (1/ ϵ))$ samples when persistent memory is at most $A d^{2}$ bits and angular success probability is at least $2/3$ . The statement is uniform over $0 < ϵ \leq 1/10$ for sufficiently large $d$ . The hidden constant may depend on $A$ ; the main abstract states that it is absolute for $o (d^{2})$ memory. The repository summary specifies that output depends only on the terminal state, stopping index, and fresh randomness.

The abstracts describe several information-based approaches rather than a single detailed argument for the main theorem. Manuscript 2 bounds conditional information in a finite message $W$ , with an independent projection revealed only to the analyst. For a signal density bounded by $L$ relative to uniform spherical probability and specified row counts proportional to $d$ , its bound is $O (H (W) / d + d + lo g (2 + lo g L))$ . Manuscript 3 shows in the manuscript that messages from $t$ blocks of $Θ (d)$ measurements reveal only $O_{A} (d t)$ information when each message has at most $exp (A d^{2})$ possible values, under its spherical image-of-a-cube signal model. It also gives that bound with supplementary nested cells restoring the required geometric spread.

Other companions develop geometric and replacement methods. Manuscript 4 obtains projection moment estimates for finite measures with controlled mass on Euclidean balls, together with positive domination by countable sums of spherical cap measures; it supplies three routes to the $o (d^{2})$ -memory lower bound, keeping stopping and accuracy costs explicit. Manuscript 5 bounds the increase in remaining conditional information when measurement rows used to select a message are replaced by independent rows: the increase is at most $C d$ under its uniform-sphere, entropy, and row-dimension assumptions. Its learner application uses a deterministic finite horizon and success probability at least $3/5$ .

Manuscript 6 conditions each batch on its observed projection and controls the resulting random residual subsphere. For $o (d^{2})$ persistent bits and success probability at least $2/3$ , it gives the explicit lower bound $2^{- 16} d lo g_{2} (1/ ϵ)$ for sufficiently large $d$ , uniformly over the stated accuracy range. The main manuscript and Manuscripts 2, 4, 5, and 6 are marked Lean-formalized; Manuscript 3 is not.

Useful notions

Vectors, length, and angle
Random measurements and probability of success
Memory measured in bits
Entropy and conditional information
Asymptotic lower-bound notation

What was known before / what is new

Before

The supplied source gives no historical baseline or account of earlier results outside this family. Within the family, several companions establish lower bounds for memory $o (d^{2})$ , with different assumptions on stopping, signal distribution, or success probability. Their order in the list does not establish a historical sequence.

New

The main result covers every fixed memory allowance $A d^{2}$ , with a sample lower bound uniform in the stated accuracy range for large dimension. The family also supplies conditional-information bounds, localization estimates, projection methods, and an observation-replacement bound. One companion gives an explicit sample-bound constant for the $o (d^{2})$ -memory setting.

Limits and assumptions

The main statement concerns fresh noiseless Gaussian linear measurements of a uniformly random unit vector, not arbitrary measurement distributions or arbitrary signals. It assumes one-pass access, at most $A d^{2}$ persistent bits for fixed $A > 0$ , angular error $0 < ϵ \leq 1/10$ , success probability at least $2/3$ , and sufficiently large dimension; output is restricted to the terminal state, stopping index, and fresh randomness. Companion statements have their own restrictions, including deterministic horizons in Manuscripts 2 and 5, specified row dimensions, density or geometric conditions, and sometimes $o (d^{2})$ rather than fixed-multiple quadratic memory. The main result has a Lean formalization, and Manuscripts 2, 4, 5, and 6 are also marked Lean-formalized, but the source does not specify claim-by-claim formalization coverage; Manuscript 3 is not marked formalized. The source identifies no particular remaining open problem and does not state a matching upper bound.

Mini glossary

Persistent memory: The bits a learner retains between successive measurements.
Angular error: The angle between the estimated direction and the hidden unit vector.
Uniform spherical prior: A distribution that chooses the hidden unit vector uniformly from the sphere $S^{d - 1}$ .
Entropy: The quantity $H (W)$ measuring uncertainty in the finite message $W$ .
Conditional information: Information measured after accounting for specified additional knowledge, such as a revealed projection.
$o (d^{2})$ memory: A memory allowance whose ratio to $d^{2}$ tends to zero as the dimension grows.

Keywords : Gaussian regression · Memory–sample lower bounds · Conditional information

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

For fixed A > 0, a one-pass learner with $A d^{2}$ persistent bits needs $Ω_{A} (d lo g (1/ ϵ))$ noiseless Gaussian samples to recover a unit vector to angular error $0 < ϵ \leq 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.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/140.md

Manuscripts in this family

★

Memory and precision in noiseless Gaussian regression

27/09/2026

Verified by Lean

For every fixed A > 0, a learner that retains at most $A d^{2}$ bits between fresh exact Gaussian linear measurements needs $Ω_{A} (d lo g (1/ ϵ))$ measurements to estimate a uniformly random unit vector to angular error at most ϵ, for any $0 < ϵ \leq 1/10$ , with probability at least 2/3. The constant is absolute for $o (d^{2})$ memory.

PDF GitHub folder Lean formalization

Posterior replicas and conditional information in Gaussian regression

27/09/2026

Verified by Lean

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 + lo g (2 + lo g L))$ . Consequently, a finite-state learner with $o (d^{2})$ persistent bits and a deterministic sample horizon needs $Ω (d lo g (1/ ϵ))$ fresh noiseless Gaussian measurements for constant-probability angular accuracy $0 < ϵ \leq 1/10$ under the uniform spherical prior.

PDF GitHub folder Lean formalization

Localization costs and information growth for exact Gaussian observations

27/09/2026

To be verified

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} (d t)$ information when each message has at most $exp (A d^{2})$ values, for fixed A. The same bound holds when each message is supplemented with a nested cell that restores the required geometric spread.

PDF GitHub folder

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

27/09/2026

Verified by Lean

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^{2})$ bits of memory, these estimates give three proofs that uniform-sphere average success at least 2/3 at angular accuracy $0 < ϵ \leq 1/10$ requires $Ω (d lo g (1/ ϵ))$ noiseless Gaussian observations. The three proofs keep their different stopping and accuracy costs explicit.

PDF GitHub folder Lean formalization

Replacing Gaussian observations in memory-constrained inference

27/09/2026

Verified by Lean

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

PDF GitHub folder Lean formalization

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

27/09/2026

Verified by Lean

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

PDF GitHub folder Lean formalization