oai-math-revised beta

Browse › Theoretical computer science › 140 Memory–sample lower bounds for noiseless Gaussian regression

Replacing Gaussian observations in memory-constrained inference

OpenAI · September 27, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

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

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Formalization

  • OpenAI, Memory–sample lower bounds for noiseless Gaussian regression: Lean scope notes (oai-math-revised mirror of openai/math, 2026-10). Describes the Lean formalization across the six papers, with eight comparator files (e.g. NoiselessRegression.lean, SubsphereCurrent.lean); for this paper it reports row-replacement comparisons and fiber-block estimates, excluding the separate streaming consequences and several intermediate constructions. [family-level]

Digests and expositions

News and blogs

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Replacing-Gaussian-observations-in-memory-constrained-inference-September-27-2026,
  author = {{OpenAI}},
  title = {{Replacing Gaussian observations in memory-constrained inference}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Replacing-Gaussian-observations-in-memory-constrained-inference-September-27-2026/paper.pdf}{OAI:Replacing-Gaussian-observations-in-memory-constrained-inference-September-27-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/140.md. The Lean statements have not been checked by people against the paper's claims.

Family 140: Memory–sample lower bounds for noiseless Gaussian regression

For fixed A > 0, a one-pass learner with $Ad^2$ persistent bits needs $\Omega_A(d\log(1/\epsilon))$ noiseless Gaussian samples to recover a unit vector to angular error $0\lt \epsilon\le1/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.

Other papers in this family: