Memory–sample lower bounds for noiseless Gaussian regression
From OpenAI Aftermath
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 (github.com/openai/math) claim that memory of order d2 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 Ad2 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 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(d2) forces at least 2−16d log2(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
1581d4c, Subsphere methods for memory–sample lower bounds in noiseless Gaussian regression and Memory and precision in noiseless Gaussian regression. - Formalization, as described by the repository. The scope note 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(d2). It lists eight Comparator challenges, among them
NoiselessRegression,MemoryPrecisionandSubsphereCurrent.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 22 October 2026) |
|---|---|---|---|---|
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit bb5fdb6, 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 | acprk/memory-sample-leading-constant (GitHub, commit 2d87aa4), note The leading constant of the memory–sample tradeoff for noiseless Gaussian regression |
Extension (sharp constant) | Replaces the constant 2−16 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(log2(1/ε) + 2 log2 d) ≤ M = o(d2) the optimal sample count is stated as (2 ln 2 + o(1)) d log2(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 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.
