oai-math-revised beta

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

Projection moments, positive cap domination, and Riesz estimates on the sphere

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

We prove moment estimates for exact random projections of finite measures whose mass is controlled on Euclidean balls, and derive positive domination by countable sums of spherical cap measures. For learners with $M=o(d^2)$ bits of memory, these estimates give three proofs that uniform-sphere average success at least 2/3 at angular accuracy $0\lt \epsilon\le1/10$ requires $\Omega(d\log(1/\epsilon))$ noiseless Gaussian observations. The three proofs keep their different stopping and accuracy costs explicit.

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 projection moments, cap domination, fixed-offset Riesz estimates, and regression bounds, with the dimension-two randomized reduction excluded. [family-level]

Digests and expositions

News and blogs

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere-September-27-2026,
  author = {{OpenAI}},
  title = {{Projection moments, positive cap domination, and Riesz estimates on the sphere}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere-September-27-2026/paper.pdf}{OAI:Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere-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: