Family 140Theoretical computer scienceLeanNot yet digested

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.

Manuscripts in this family · 6

Memory and precision in noiseless Gaussian regression

Sep 27, 2026·paper.pdfLean

For every fixed A > 0, a learner that retains at most

Ad^2

bits between fresh exact Gaussian linear measurements needs

\Omega_A(d\log(1/\epsilon))

measurements to estimate a uniformly random unit vector to angular error at most ϵ, for any

0\lt \epsilon\le 1/10

, with probability at least 2/3. The constant is absolute for

o(d^2)

memory.

Full abstract

PDF on GitHub LaTeX source

Posterior replicas and conditional information in Gaussian regression

Sep 27, 2026·paper.pdfLean

For a signal with density bounded by L relative to uniform probability on

S^{d-1}

, we bound the information in a finite message W formed from exact Gaussian measurements, conditional on an independent projection revealed only to the analyst. For explicit row counts proportional to d, the bound is

O(H(W)/d+d+\log(2+\log L))

. Consequently, a finite-state learner with

o(d^2)

persistent bits and a deterministic sample horizon needs

\Omega(d\log(1/\epsilon))

fresh noiseless Gaussian measurements for constant-probability angular accuracy

0\lt \epsilon\le1/10

under the uniform spherical prior.

Full abstract

PDF on GitHub LaTeX source

Localization costs and information growth for exact Gaussian observations

Sep 27, 2026·paper.pdf

For the image of a uniform cube under a spherical coordinate map, we prove that finite messages from t blocks of

\Theta(d)

exact Gaussian measurements reveal only

O_A(dt)

information when each message has at most

\exp(Ad^2)

values, for fixed A. The same bound holds when each message is supplemented with a nested cell that restores the required geometric spread.

Full abstract

PDF on GitHub LaTeX source

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

Sep 27, 2026·paper.pdfLean

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.

Full abstract

PDF on GitHub LaTeX source

Replacing Gaussian observations in memory-constrained inference

Sep 27, 2026·paper.pdfLean

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 d

^{2}

, 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.

Full abstract

PDF on GitHub LaTeX source

Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression

Sep 27, 2026·paper.pdfLean

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.

Full abstract

PDF on GitHub LaTeX source