The Sharan-Sidford-Valiant precision question: do learners with $o(d^2)$ memory need $\Omega(d\log(1/\epsilon))$ samples for linear regression?

Main theorem: for fixed $A>0$ there are $c_A,d_A$ such that any learner with $M\le Ad^2$ bits, $d\ge d_A$, $0<\epsilon\le1/10$ and uniform-prior success at least $2/3$ in reaching angular error $\epsilon$ needs horizon $T\ge c_A d\log(1/\epsilon)$; for $M=o(d^2)$ the constant is absolute, and the bound also holds under an every-signal guarantee. Transitions may use unbounded computation and randomness; the output uses only the terminal state, stopping index and fresh randomness, with a deterministic horizon. It implies an $\Omega_A(dr\log d)$ bound in the noisy experiment of Sharan-Sidford-Valiant at Euclidean accuracy $d^{-r}$ in their range. No matching finite-memory upper bound is proved, and memory well above $d^2$ is not treated.

Main theorem: for fixed $A>0$ there are $c_A,d_A$ such that any learner with $M\le Ad^2$ bits, $d\ge d_A$, $0<\epsilon\le1/10$ and uniform-prior success at least $2/3$ in reaching angular error $\epsilon$ needs horizon $T\ge c_A d\log(1/\epsilon)$; for $M=o(d^2)$ the constant is absolute, and the bound also holds under an every-signal guarantee. Transitions may use unbounded computation and randomness; the output uses only the terminal state, stopping index and fresh randomness, with a deterministic horizon. It implies an $\Omega_A(dr\log d)$ bound in the noisy experiment of Sharan-Sidford-Valiant at Euclidean accuracy $d^{-r}$ in their range. No matching finite-memory upper bound is proved, and memory well above $d^2$ is not treated.