View source for Memory–sample lower bounds for noiseless Gaussian regression

'''Memory–sample lower bounds for noiseless Gaussian regression''' concern a streaming learner that reads exact Gaussian linear equations for an unknown unit vector and may keep only a bounded number of bits between samples. Six manuscripts dated 27 September 2026 in OpenAI's public mathematics collection ([https://github.com/openai/math github.com/openai/math]) claim that memory of order ''d''<sup>2</sup> bits forces order ''d'' log(1/ε) samples. This page summarizes the published claims and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.

== Background ==
* As recounted in the introduction of the manuscript ''Subsphere methods for memory–sample lower bounds in noiseless Gaussian regression'': Steinhardt and Duchi, and Steinhardt, Valiant and Wager, related bounded-memory inference to communication and statistical-query models and asked about exponential-sample separations for parity learning; Raz established such a separation through finite-width branching programs.
* With exact real observations, ''d'' independent equations determine the unknown vector almost surely. The question is how many equations a learner needs when it cannot store them at full precision.

== The original results ==
* '''Claim.''' The collection's summary states that for fixed ''A'' > 0, a one-pass learner with ''Ad''<sup>2</sup> persistent bits needs Ω<sub>''A''</sub>(''d'' log(1/ε)) noiseless Gaussian samples to recover a unit vector to angular error 0 < ε ≤ 1/10 with probability 2/3, uniformly in the accuracy for large ''d''. Computation and randomized updates are unrestricted; the output uses only the terminal state, the stopping index and fresh randomness.
* '''Explicit constant.''' The subsphere manuscript states that memory ''o''(''d''<sup>2</sup>) forces at least 2<sup>−16</sup>''d'' log<sub>2</sub>(1/ε) samples for large ''d'', under the uniform prior on the sphere.
* '''Sources.''' The six manuscripts are listed in the scope note below; for example, at commit <code>1581d4c</code>, [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Subsphere-methods-for-memory-sample-lower-bounds-in-noiseless-Gaussian-regression-September-27-2026 Subsphere methods for memory–sample lower bounds in noiseless Gaussian regression] and [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Memory-and-precision-in-noiseless-Gaussian-regression-September-27-2026 Memory and precision in noiseless Gaussian regression].
* '''Formalization, as described by the repository.''' The scope note [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/docs/140.md lean/docs/140.md] states that the Lean formalization proves the fixed-quadratic-memory bound with a constant depending on ''A'', and a universal constant for memory ''o''(''d''<sup>2</sup>). It lists eight Comparator challenges, among them <code>NoiselessRegression</code>, <code>MemoryPrecision</code> and <code>SubsphereCurrent</code>.

== Public follow-up work ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 22 October 2026)
|-
| 2026-10-08 || [https://github.com/mathvet/mathvet MathVet] (GitHub; review of openai/math, tables at repository commit <code>bb5fdb6</code>, 18 October 2026) || Review (fidelity of the formal statements) || Rates all eight challenges of this family "full" and records sandboxed Comparator passes for each. || MathVet states that it does not claim any theorem false and reports what was machine-checked as stated.
|-
| 2026-10-10 || [https://github.com/acprk/memory-sample-leading-constant/tree/2d87aa4e62003ec550a2bb2dc2ffb53385969823 acprk/memory-sample-leading-constant] (GitHub, commit <code>2d87aa4</code>), note ''The leading constant of the memory–sample tradeoff for noiseless Gaussian regression'' || Extension (sharp constant) || Replaces the constant 2<sup>−16</sup> of the subsphere manuscript by any constant below 2 ln 2 ≈ 1.386, uniformly in 0 < ε ≤ 1/10, and shows that randomized Kaczmarz with fixed-point registers attains it. So in the memory window ''d''(log<sub>2</sub>(1/ε) + 2 log<sub>2</sub> ''d'') ≤ ''M'' = ''o''(''d''<sup>2</sup>) the optimal sample count is stated as (2 ln 2 + ''o''(1)) ''d'' log<sub>2</sub>(1/ε). It also shows that the upstream method with its fixed split cannot exceed about 0.5176. || The README states that the results were found and checked by Claude agents, that there is no human peer review and no Lean formalization, and that they depend on the upstream manuscript being correct.
|-
| 2026-10-10 || cert-machine, openai/math lane K: runs [https://github.com/carlostoledo1891/cert-machine/blob/910dddee72220b30c85da00fc414b6c987f8c954/corpus/openai-math/kernel-runs/38051470892/NoiselessRegression.json 38051470892] for the eight challenges of this family || Verification (two kernels) || Records that Lean's default kernel and the nanoda kernel accept all eight solutions, in 194 s to 681 s each. || Repository.
|}

== Notes ==
* The earlier results are due to the authors named in the Background section, as recounted by the manuscript.
* The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.

[[Category:OpenAI results]]