{"id":"openai-math/Subsphere-methods-for-memory-sample-lower-bounds-in-noiseless-Gaussian-regression","pdf":"https://github.com/openai/math/blob/main/preprints/Subsphere-methods-for-memory-sample-lower-bounds-in-noiseless-Gaussian-regression-September-27-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Subsphere-methods-for-memory-sample-lower-bounds-in-noiseless-Gaussian-regression-September-27-2026","tags":["learning-theory","memory-bounds","streaming","gaussian-regression"],"score":0,"title":"Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression","domain":"Theoretical computer science","family":"140","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"Let a finite-state streaming learner estimate a uniformly random unit vector from independent exact Gaussian linear measurements. We prove that $`o(d^2)`$ bits of persistent memory and angular success probability at least 2/3 require at least $`2^{-16}d\\log_2(1/\\epsilon)`$ samples for all sufficiently large d , uniformly for $`0\\lt \\epsilon\\le1/10`$. The proof conditions each batch on its observed projection and controls the resulting random residual subsphere.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{},"formalized":true,"family_title":"Memory–sample lower bounds for noiseless Gaussian regression"}