Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/Subsphere-methods-for-memory-sample-lower-bounds-in-noiseless-Gaussian-regression
curl -X POST /api/v1/records/openai-math/Subsphere-methods-for-memory-sample-lower-bounds-in-noiseless-Gaussian-regression/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Subsphere-methods-for-memory-sample-lower-bounds-in-noiseless-Gaussian-regression/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'