Memory–sample lower bounds for noiseless Gaussian regression

Exact clues still cost more reading for each extra digit of accuracy when memory is limited.

6 papers September 27, 2026 Explained by AI

A learner must find a hidden direction from exact linear clues, read once each. If it could keep every clue, d clues would settle the answer exactly. This paper proves (Lean proof listed) that a learner with a constant times d² bits cannot do that. It needs at least a constant times d times the logarithm of one over the allowed error. So each extra digit of accuracy costs extra clues, even with no noise at all.

First step

2019

Sharan, Sidford and Valiant, the noisy version with d²/4 bits

Significance

Solid

It gives a lower bound for the exact-clue form of a 2019 precision question, for memory up to order d².

Trust

Formal proof listed

Field

Theoretical computer science

6 papers

The explanation

Hide an arrow of length 1 in 100-dimensional space. Each clue is a list of 100 random numbers plus one exact answer. The answer is the sum of each random number times the matching coordinate of the arrow. No clue has any noise. Keep the first 100 clues and you can solve for the arrow exactly. But storing them takes 10,100 real numbers, each with endless digits.

Now suppose you may not store clues. A classic method, the Kaczmarz step, keeps only a running guess. Each clue nudges the guess so that it fits that one clue exactly. The paper computes its average squared error. That error shrinks by a factor of 1 − 1/d per clue, where d is the dimensionSource 1. With d = 100, that factor is 0.99. A typical miss of 0.01 means an average squared miss of 0.0001. Reaching it takes about 917 clues. A typical miss of 0.0001 takes about 1,833. Each extra two digits of accuracy costs another 916 clues or so.

That pattern has a name in the paper: the scale d log(1/ε), where ε is the allowed error. Here log is the natural logarithm, and the error is measured as an angle. For small errors, the angle and the distance nearly agree. But the Kaczmarz guess stores real numbers with endless digits. The paper says it gives no recipe for a learner with a fixed number of bitsSource 2. So the real question is this. Suppose a learner keeps only a fixed number of bits between clues. Must it still pay that price for accuracy?

The paper's model is a finite-state learner. It reads each clue once, in order, and may compute anything with it. Afterwards it keeps only a state, one of at most 2^M possibilities, where M is its memory in bitsSource 3. It may use randomness. Its final guess may depend only on its last state, when it stopped, and fresh randomnessSource 4. A discarded clue can never be read again.

The closest earlier result is a 2019 paper by Vatsal Sharan, Aaron Sidford and Gregory Valiant. They studied the same kind of clues with a tiny amount of added noise. With at most d²/4 bits, they gave a lower bound on clues for very small errors. They also asked whether this cost of precision was optimal under bounded memory. The obstacle is that exact clues tell you more than noisy ones. A lower bound with noise does not by itself cover the exact caseSource 5.

This paper proves a lower bound for the exact case. Fix any number A, and allow A·d² bits of memory. Hide the arrow at a uniformly random direction. Then success with probability at least 2/3 needs at least c·d·log(1/ε) cluesSource 6. Here c is a positive constant that depends on A, and ε may be any error up to 1/10Source 7. For memory that grows more slowly than d², the constant c can be the same for every memory budgetSource 8. For that slower-growing memory, a companion paper makes it explicit. It needs at least 2^−16 times d times log₂(1/ε) clues in large dimensionSource 9.

Exactness is also what makes the proof hard. One exact clue pins the arrow to a thin slice of the sphere of possible directionsSource 10. The usual way to track what the learner believes then breaks down. The paper works backwards from the end instead. It keeps the original random direction fixedSource 11. It asks how tightly the directions on which the learner would still succeed can cluster. Each block of about d clues can loosen that clustering only by a bounded factorSource 12.

Return to d = 100, with 10,000 bits of memory. That budget is about one bit per number in the 100 clues that would settle the arrow. The theorem says the number of clues must grow at least in step with the digits of accuracy. It fixes that growth rate, not the exact count. Still, the theorem only applies above some large dimension that the paper does not state. The explicit constant 2^−16 is also tiny. And it is a lower bound only: it does not show that a finite-memory learner can reach that cost.

How sure is this? The Lean scope note says a computer proof checker, Lean, has a formal proof of the main statement. It also covers the memory below d² case, the every-direction version for that case, and the 2^−16 bound. A stronger variant with success 3/5 is outside that scope, and so is an auxiliary two-dimensional case. No specialist review has been published.

What it doesn't show. This does not give a limited-memory learner that reaches this number of clues; it is only a lower bound.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Solid if the proofs hold. Lean covers the main lower bound. But the constant is unstated or tiny, and the dimension must be large. No specialist review is published.

Words used

Noiseless Gaussian regression: Finding a hidden vector from exact answers to random questions with bell-curve entries.
Finite-state learner: A procedure that keeps only one of a fixed number of states between clues.
Bit: One yes-or-no unit of memory; M bits allow 2^M different states.
Angular error: The angle between the guessed direction and the true one.
Kaczmarz step: An update that moves a guess the shortest distance needed to fit one new equation exactly.
Lower bound: A proven minimum cost that no method can beat.
Lean: A computer program that checks each step of a formal mathematical proof.

The original papers (6)

Memory and precision in noiseless Gaussian regression (PDF, opens in a new tab)
September 27, 2026 Formal proof listed
Posterior replicas and conditional information in Gaussian regression (PDF, opens in a new tab)
September 27, 2026 Formal proof listed
Localization costs and information growth for exact Gaussian observations (PDF, opens in a new tab)
September 27, 2026
Projection moments, positive cap domination, and Riesz estimates on the sphere (PDF, opens in a new tab)
September 27, 2026 Formal proof listed
Replacing Gaussian observations in memory-constrained inference (PDF, opens in a new tab)
September 27, 2026 Formal proof listed
Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression (PDF, opens in a new tab)
September 27, 2026 Formal proof listed

Lean notes

All quoted lines (12)

This calculation explains the scale $d\log(1/\epsilon)$ for fresh isotropic observations. Strohmer and Vershynin's theorem concerns norm-weighted sampling from a fixed finite matrix; the equality above is the separate symmetry calculation for this stream.
Memory and precision in noiseless Gaussian regression Back to text
The displayed update stores real scalars and supplies no finite-bit upper bound.
Memory and precision in noiseless Gaussian regression Back to text
A learner reads the pairs once, in order. After each number of samples its persistent state belongs to a prescribed set of at most $2^M$ elements.
Memory and precision in noiseless Gaussian regression Back to text
At a stopping index its unit output $\widehat s\in S^{d-1}$ is generated from the terminal state, the stopping index, and fresh randomness only. In particular, a discarded observation cannot be read again by the output rule.
Memory and precision in noiseless Gaussian regression Back to text
A lower bound with additive noise does not by itself bound the more informative exact experiment.
Memory and precision in noiseless Gaussian regression Back to text
For every fixed finite $A>0$ , there are constants $c_A>0$ and $d_A$ such that the following holds. Let $d\ge d_A$ , let $0\le M\le Ad^2$ be an integer, and let $0<\epsilon\le1/10$ .
Memory and precision in noiseless Gaussian regression Back to text
The statement makes no uniform claim when $A=A(d)$ tends to infinity.
Memory and precision in noiseless Gaussian regression Back to text
The constant is absolute for $o(d^2)$ memory.
Memory and precision in noiseless Gaussian regression Back to text
We prove that $o(d^2)$ bits of persistent memory and angular success probability at least $2/3$ require at least $2^{-16}d\log_2(1/\epsilon)$ samples for all sufficiently large $d$ , uniformly for $0<\epsilon\le1/10$ .
Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression Back to text
Conditioning the uniform prior on one raw exact observation almost surely confines the signal to a hyperplane section of the sphere.
Memory and precision in noiseless Gaussian regression Back to text
We instead keep the original prior fixed and study the probability of future success from a prescribed state.
Memory and precision in noiseless Gaussian regression Back to text
Moving backward across a block of order $d$ observations multiplies $R$ by at most a constant for fixed $M/d^2$ .
Memory and precision in noiseless Gaussian regression Back to text