Noiseless Gaussian regression: the sample price of finite memory and precision

← All digests

Family 140 · Theoretical computer science
Importance 1/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

An unknown unit vector $s\in\mathbb R^d$ generates exact linear observations. Each observation gives a fresh Gaussian vector $x$ and the noiseless value $y=\langle x,s\rangle$. With unrestricted storage of real numbers, $d$ independent equations determine $s$ almost surely.

What changes if a learner reads the observations once and can retain only finitely many bits between them?

Exact observations contain arbitrarily fine real information, but a finite state cannot preserve an arbitrary collection of real equations. To obtain a more accurate estimate, the learner may need additional fresh observations even though no measurement noise is present.

This family contains six manuscripts developing a common precision lower bound through different geometric and information-theoretic methods. The broad fixed-memory statement is that, for every fixed $A>0$, retaining at most $Ad^2$ bits forces a sample horizon of order at least $d\log(1/\varepsilon)$ to achieve angular error $\varepsilon$. Other manuscripts give subquadratic-memory consequences, explicit constants, and analytic comparisons that support this conclusion.

2. Background and essential definitions

The signal lies on the unit sphere

$$S^{d-1}=\{s\in\mathbb R^d:\|s\|=1\}.$$

At time $t$, the learner receives

$$X_t\sim N(0,I_d),\qquad Y_t=\langle X_t,S\rangle,$$

with independent Gaussian rows and exact labels. The signal is fixed before sampling, or drawn independently from a stated prior. The main average-case prior is uniform on the sphere.

An $M$-bit learner has at most $2^M$ persistent states at each index. It may perform unrestricted computation on the current observation and use fresh randomness, but only its next finite state survives. It cannot choose the Gaussian rows or reread discarded observations.

A data-independent shared seed may select the rules, which can depend on dimension, accuracy, and sample index. The seed and initial state are jointly independent of the signal and rows. This permits very general algorithms without granting hidden data-dependent advice.

The learner stops by a prescribed deterministic horizon $T$. Its unit-vector output $\widehat S$ depends only on the terminal state, stopping index, and fresh randomness. In particular, the final raw observation is not available to an uncharged output computation after it has been discarded.

Angular error is

$$\arccos\langle\widehat S,S\rangle.$$

Success at accuracy $\varepsilon$ means that this angle is at most $\varepsilon$. The main statements cover $0<\varepsilon\le1/10$, uniformly across this range at sufficiently large dimension.

Mutual information measures how much observing a random variable reduces uncertainty about another. A finite state has limited entropy, but this elementary fact alone does not produce the sharp sample bound: exact observations and highly concentrated conditional signal distributions require geometric analysis.

3. Development history and previous partial results

Work on memory-constrained learning established that stored information can be a statistical resource independent of computation time. Steinhardt and Duchi studied minimax rates in sparse noisy regression. Steinhardt, Valiant, and Wager connected memory with communication and statistical queries.

For discrete learning, Raz proved a quadratic-memory versus exponential-sample separation for parity. Finite-width branching programs became an important way to model a learner’s retained state. Exact real observations create different technical issues from finite-alphabet samples, so those results do not directly settle the present regression model.

The closest precision comparison is Sharan, Sidford, and Valiant. Their Gaussian-regression theorem includes a small positive additive noise, memory at most $d^2/4$ bits, and Euclidean accuracy $d^{-r}$ in a specified range. It gives a sample lower bound of order $d\log r$.

The new family claims a stronger precision dependence and exact labels. A lower bound for noisy observations alone cannot establish one for noiseless observations: the latter provide more information. Conversely, a noiseless learner can add synthetic noise, so an exact-observation lower bound can transfer to appropriately matched noisy models.

Dagan, Kur, and Shamir studied related linear-prediction space barriers, including approximate null vectors and empirical residuals on a random-order equation system. Those objectives and joint data distributions differ from recovery of one fixed signal under independent fresh Gaussian rows.

The geometric tools have older roots in projection theory, inverse-distance energies, and affine-volume formulas. The manuscripts combine these ideas with finite-message selection, conditional information, and the need to control increasingly localized signal distributions.

4. What the new manuscripts claim

The common regression conclusion

M1 states that, for every fixed finite $A>0$, there are $c_A>0,d_A$ such that memory $M\le Ad^2$, dimension $d\ge d_A$, and uniform-sphere average success at least $2/3$ imply

$$T\ge c_A d\log(1/\varepsilon).$$

No relation between accuracy and memory is assumed. The constant may depend on $A$; this is not a uniform statement when $A$ grows with dimension. For $M(d)=o(d^2)$, the lower-bound constant can be absolute, with the dimension threshold depending on the memory sequence.

A guarantee of success for every fixed signal implies the average guarantee and therefore the same bound. This does not mean every individual signal is difficult for every learner.

What the six manuscripts contribute

Manuscript	Principal contribution and stated scope
M1	Backward propagation of future-success concentration; the bound for every fixed quadratic-memory coefficient $A$.
M2	Conditional-information inequalities from several posterior replicas and an analyst-only independent projection; a subquadratic-memory streaming consequence.
M3	Localization and information-growth arguments that account for the cost of revealing cells, scales, or other auxiliary information; separate cube-chart and spherical-prior formulations.
M4	Exact projection moments, positive domination by spherical-cap measures, and fixed-offset inverse-distance estimates; several regression proofs and an explicit memory tradeoff.
M5	Comparison of actual observation rows with fresh independent rows after a finite message has been selected; a subquadratic-memory consequence already at average success $3/5$.
M6	Residual-subsphere analysis with the explicit subquadratic-memory bound $T\ge2^{-16}d\log_2(1/\varepsilon)$ at success $2/3$.

M4’s integrated-projection argument also states

$$T\ge\frac{c\,d\log(1/\varepsilon)}{1+M/d^2}$$

for arbitrary nonnegative integer $M$, at an absolute sufficiently large dimension and under its stated success convention.

M3’s cube-based routes begin with the image of uniform cube volume on a spherical patch, not uniform spherical area. Their full-range learner applications use an every-signal guarantee; its spherical routes use uniform-prior average success. The different priors and success thresholds should remain attached to their respective statements.

5. Why the advance matters

Provisional importance: 1/5. This family supplies a focused precision–memory law for a tightly specified streaming-regression model. Its direct application concerns exact isotropic Gaussian measurements, a finite persistent state, one-pass access, and a controlled terminal-output rule.

Within that setting, the conclusion is informative. It explains why the availability of exact equations does not eliminate a precision-dependent sample cost once the learner must compress each observation into finite memory. For $\varepsilon=d^{-r}$, the scale becomes $dr\log d$, making the dependence on requested precision explicit.

The six manuscripts provide several routes to the same central phenomenon and develop useful geometric estimates. Their number does not multiply the scope of the application. The relative score reflects that concentration of subject matter; it is not a judgment about proof difficulty or correctness.

The analytic tools may support broader applications, but the digest attributes only the consequences stated in the sources. General noisy regression, chosen measurements, multiple passes, and arbitrary covariate distributions are separate settings.

6. The main idea

Count the information needed to localize a direction

An angular ball of radius $\varepsilon$ occupies a very small fraction of a high-dimensional sphere, on the scale of $\varepsilon^{d-1}$. Accurately locating a random direction therefore requires information proportional to $d\log(1/\varepsilon)$.

The challenge is to show that a learner with limited memory cannot retain all the useful information in each block of exact equations. Conditioning on exact labels places the signal on lower-dimensional fibers, so the conditional distribution can be singular relative to the original sphere. Treating it as an ordinary bounded density would miss this issue.

Propagate future success backward

M1 fixes a possible state and asks for the probability of eventual success as a function of the signal, using fresh future observations. This continuation function is defined even at states that the actual learner might never reach for that signal.

At termination, successful signals lie near the possible output direction. The argument bounds the mass of success inside every ball and propagates that bound backward through blocks containing order $d$ measurements. Each block can enlarge the concentration parameter by only a controlled factor when $M/d^2$ is bounded.

Exact Gaussian projection estimates control the effect of a block. High moments introduce several possible signals sharing labels; inverse affine volumes measure how concentrated those collisions can be. Local ball bounds control the singular factors. Choosing among many next states adds a cost softened by the high moment order, producing the relevant quadratic-memory scale.

Keep the cost of auxiliary information visible

M2 draws multiple signals independently from the posterior given the same observations. Each replica has the correct signal–message relationship, but the replicas remain correlated through their shared data. An independent projection, revealed only to the analyst, retains some of that correlation.

The argument bounds the loss of correlation after projection, rather than discarding all the dependence. This yields a conditional-information estimate with the message entropy divided by a quantity proportional to dimension, plus controlled geometric terms.

M3 addresses a related difficulty: earlier messages can concentrate the posterior in a small region. It reveals a cell or scale to restore a useful spread condition, then charges for the information in that revelation. Nested-cell entropy and confinement gains balance one another. Some routes track the full history; others use a corrected information potential for the current state. These auxiliary revelations belong to the analysis and do not give the learner extra memory.

M5 handles selection bias in the observation rows. After conditioning on a state chosen from data, the actual rows are no longer interchangeable with fresh independent rows. Its comparison quantifies the information difference and charges the bias, using exact projection-density estimates and finite fiber measures.

Use caps or residual spheres to control geometry

M4 develops three related analytic descriptions. Integrated projection moments bound density concentration across label space. Positive sums of cap measures dominate selected signal distributions. Fixed-offset estimates control densities at particular affine labels through inverse-distance potentials. Each route retains its own stopping and accuracy costs.

M6 conditions a block on its observed projection. The unresolved signal lies on a random residual subsphere. High moments account for choosing among continuation states, while comparisons of directions in a common random subspace control their dependence. The construction loses only a small amount of test dimension per block, and explicit beta-distribution calculations retain the stated numerical constant.

Across these approaches, roughly $\log(1/\varepsilon)$ blocks of order $d$ observations are needed to reach constant success. The common conclusion comes from controlling both local geometry and the information retained across blocks.

7. Scope, limitations, and open questions

Memory is measured in bits, not exact real registers. Storing $d$ equations at unlimited precision would evade the finite-state model and allow direct recovery. A real-valued iterative projection method also supplies no finite-bit upper bound merely by using only a few vector registers.

The rows are independent isotropic Gaussians fixed by the observation law. Active measurement selection, rereading past samples, additional passes, or data-dependent initialization changes the model. The terminal output cannot recover discarded raw observations through an uncharged final step.

The horizon is deterministic even though stopping may occur earlier. The sources explicitly account for the information carried by the stopping index. Replacing this with an arbitrary expected-sample convention would require another argument.

The family gives lower bounds and related analytic estimates; it does not by itself establish a matching finite-bit algorithm throughout every memory and precision regime. Optimal tradeoffs beyond quadratic memory and extensions to other distributions remain separate questions. The six proof routes are reported as stated without independent verification.

8. Sources and further reading

Raz provides the finite-memory learning background, and Sharan–Sidford–Valiant gives the closest earlier precision tradeoff with noisy Gaussian labels. The six manuscripts below develop the exact-observation geometric and information-theoretic arguments. Their distinct priors, success thresholds, and memory ranges are retained in the comparison above.

Source manuscripts

• M1. OpenAI, Memory and precision in noiseless Gaussian regression (2026).
• M2. OpenAI, Posterior replicas and conditional information in Gaussian regression (2026).
• M3. OpenAI, Localization costs and information growth for exact Gaussian observations (2026).
• M4. OpenAI, Projection moments, positive cap domination, and Riesz estimates on the sphere (2026).
• M5. OpenAI, Replacing Gaussian observations in memory-constrained inference (2026).
• M6. OpenAI, Subsphere methods for memory–sample lower bounds in noiseless Gaussian regression (2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.