\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\hypersetup{
 pdftitle={Memory and precision in noiseless Gaussian regression},
 bookmarksopen=true,bookmarksnumbered=true,bookmarksopenlevel=1
}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\R}{\mathbb R}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\newcommand{\norm}[1]{\lVert #1\rVert}
\newcommand{\ip}[2]{\langle #1,#2\rangle}
\newcommand{\ind}{\mathbf 1}
\newcommand{\dist}{\operatorname{dist}}
\newcommand{\aff}{\operatorname{aff}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\vol}{\operatorname{vol}}

\title{Memory and precision in noiseless Gaussian regression}
\author{}
\date{}

\begin{document}
\maketitle

\begin{abstract}
For every fixed $A>0$, a learner that keeps at most $Ad^2$ bits between
fresh \emph{exact} Gaussian linear measurements needs
$\Omega_A(d\log(1/\epsilon))$ measurements to estimate a uniformly random
unit vector to angular error at most $\epsilon$, for any
$0<\epsilon\le 1/10$, with probability at least $2/3$. The constant is
absolute when the memory is $o(d^2)$ bits.
\end{abstract}

\tableofcontents

\section{Introduction and main result}

A single exact linear equation $y=\ip{x}{s}$ pins the unknown vector $s$
onto a hyperplane. With independent Gaussian rows $x_t\sim N(0,I_d)$ and
exact labels $y_t=\ip{x_t}{s}$, a handful of equations already carry
arbitrary precision: if all of them could be kept, $d$ rows would
determine $s$ almost surely. The question here is what happens to a
learner that may read each pair only once, keep a bounded number of
bits, and must eventually output an estimate. We show that exact
observations do not rescue finite memory: sharpening $\epsilon$ forces a
logarithmic-in-precision increase in the number of samples.

\subsection{The model}

\begin{definition}[Finite-state Gaussian regression]\label{def:model}
Fix integers $d\ge2$, $M\ge0$, $T\ge0$. A \emph{learner} is specified as
follows. A signal $s\in S^{d-1}$ is fixed before sampling. At index
$t\in\{1,\ldots,T\}$ the learner observes
\[
 x_t\sim N(0,I_d),\qquad y_t=\ip{x_t}{s},
\]
where $x_1,\ldots,x_T$ are independent. The learner reads the pairs once,
in order. Its persistent state always belongs to a prescribed set of at
most $2^M$ elements. A transition may use the entire current pair
$(x_t,y_t)$ and fresh randomness, but only the next finite state is
retained. The learner may stop at any index (including before the first
sample) but must stop by the deterministic horizon $T$. At a stopping
index its output $\widehat s\in S^{d-1}$ is generated from the terminal
state, the stopping index, and fresh randomness only. All transition,
stopping, and output rules may depend on $d$, on the target accuracy
$\epsilon$, and on the index, but never on $s$.
\end{definition}

\noindent
The state bound counts bits, not reals. The horizon $T$ is fixed in
advance. Accuracy means $\arccos\ip{\widehat s}{s}\le\epsilon$, i.e.\ the
angle between the estimate and the truth is at most $\epsilon$.

Write $\sigma=\sigma_d$ for the uniform probability measure on $S^{d-1}$.

\subsection{Main theorem and corollaries}

\begin{theorem}[Memory and precision]\label{thm:main}
For every fixed finite $A>0$ there are constants $c_A>0$ and $d_A$ such
that the following holds. Let $d\ge d_A$, $0\le M\le Ad^2$ an integer,
and $0<\epsilon\le1/10$. Draw $S\sim\sigma$ independently of the rows and
of the learner's data-independent randomness. If a learner as in
Definition~\ref{def:model} has
\[
 \Prob\{\arccos\ip{\widehat s}{S}\le\epsilon\}\ge\tfrac23,
\]
then its horizon satisfies $T\ge c_A\,d\log(1/\epsilon)$.
\end{theorem}

Throughout $\log$ is natural. The constant $c_A$ depends on the fixed
number $A$; the statement makes no uniform claim as $A=A(d)\to\infty$.

\begin{corollary}[Subquadratic memory]\label{cor:sub}
Let $M(d)\ge0$ be integer-valued with $M(d)=o(d^2)$, and let
$0<\epsilon(d)\le1/10$ be any accuracy sequence. A family of learners with
uniform-sphere average success at least $2/3$ satisfies
$T(d)\ge c\,d\log(1/\epsilon(d))$ for all sufficiently large $d$, where
$c>0$ is absolute.
\end{corollary}

\begin{corollary}[A guarantee for every signal]\label{cor:worst}
The conclusions of Theorem~\ref{thm:main} and Corollary~\ref{cor:sub}
hold also when average success is replaced by the requirement that
$\Prob\{\arccos\ip{\widehat s}{s}\le\epsilon\}\ge2/3$ for \emph{every}
$s\in S^{d-1}$, the probability being over the rows and the learner's
randomness.
\end{corollary}

\subsection{Why the scale $d\log(1/\epsilon)$ is natural}

Before proving that memory cannot help, recall why the answer
$d\log(1/\epsilon)$ is the right yardstick even \emph{with} unlimited
memory. The Kaczmarz projection step
\cite{Kaczmarz1937,SV2009} runs
\[
 z_t=z_{t-1}+\frac{y_t-\ip{x_t}{z_{t-1}}}{\norm{x_t}^2}\,x_t
 \qquad(x_t\neq0),
\]
and leaves $z_t=z_{t-1}$ on the Gaussian-null event $x_t=0$. If
$u_t=x_t/\norm{x_t}$, the error is multiplied by $I-u_tu_t^{\mathsf T}$.
Because the fresh direction $u_t$ is uniform on the sphere,
$\E(u_tu_t^{\mathsf T})=I_d/d$, so conditionally
\[
 \E\bigl(\norm{z_t-s}^2\mid z_{t-1}\bigr)
 =(1-1/d)\,\norm{z_{t-1}-s}^2,
\]
and induction gives
$\E\norm{z_t-s}^2=(1-1/d)^t$. Hence
\[
 \E\norm{z_t-s}^2\le e^{-t/d},
\]
so $t\asymp d\log(1/\epsilon)$ samples already bring the error down to
$\epsilon$ with real-valued registers. Theorem~\ref{thm:main} says finite
memory cannot beat this scale either: it does not help to be clever, and
it does not help that the labels are exact.

\subsection{Relation to prior work}

Memory-limited learning has an established lineage. Shamir's
finite-message framework \cite{Shamir2014} and the minimax analysis of
Steinhardt--Duchi \cite{SteinhardtDuchi2015} show that retained
information is itself a statistical resource. For discrete problems,
Steinhardt--Valiant--Wager \cite{SVW2016} isolated a quadratic-memory
versus exponential-sample question, and Raz \cite{Raz2016,Raz2017} proved
qualitative separations via a spectral method. For linear prediction,
Dagan--Kur--Shamir \cite{DKS2019} gave quadratic-space obstructions for a
null-vector task and for a correlated random system.

The closest continuous-regression comparator is
Sharan--Sidford--Valiant \cite{SSV2019}, whose Theorem~1 uses
$N(0,I_d)$ covariates, a fixed unit target, and independent
\emph{uniform noise} of half-width $2^{-d/5}$. With at most $d^2/4$ bits
and Euclidean accuracy $d^{-r}$, it yields an $\Omega(d\log r)$ lower
bound over a stated range of $r$. Its proof draws the target uniformly on
the sphere and averages over it and the samples. Our model follows that
finite-width layered program, with randomized rules and bounded stopping
handled directly; the decisive difference is the observation law. Noise
weakens a negative result---it cannot be used to conclude anything about
the \emph{more informative} exact experiment. Theorem~\ref{thm:main}
settles the exact-observation precision question for isotropic Gaussian
rows, and a short simulation (Section~\ref{sec:assembly}) recovers the
$\Omega_A(d\,r\log d)$ consequence for the noisy ``fine accuracy'' range
of \cite{SSV2019}.

\section{The proof in one page}\label{sec:overview}

The proof never conditions on observed data. Conditioning the uniform
prior on one exact equation almost surely confines the signal to a
hyperplane section of the sphere, a law \emph{singular} against $\sigma$;
bounds would fight zero sets. We keep the original prior fixed instead and
study the probability of \emph{future} success from an arbitrary starting
state.

Fix a state $u$ at index $t$, reachable or not, and let $h(s)$ be the
probability that, starting from $(u,t)$ with signal $s$, the learner
succeeds using fresh future samples. The key object is a quantitative
statement about how concentrated $h$ is. Set
\[
 n=d-1,\qquad a=\frac n2,\qquad q=\left\lfloor\frac n8\right\rfloor.
\]
For $d$ large, $q\ge2$, $q\ge d/16$, and $a\ge d/3$. We say $h:S^{d-1}\to[0,1]$
has \emph{local mass at scale $R$} if
\begin{equation}\label{eq:invariant}
 \int_{B(z,r)}h\,d\sigma\le(Rr)^a
 \qquad\text{for all }z\in S^{d-1},\ r>0.
\end{equation}
The scale $R$ is an upper-bound parameter, not a posterior radius.

The whole argument is three moves.

\begin{enumerate}[label=(\roman*)]
\item \textbf{Terminal.} From a terminal state the output is independent of
the signal. Success is confined to an $\epsilon$-cap \emph{globally} and to
a $r$-cap \emph{locally}; taking the geometric mean gives
\eqref{eq:invariant} at $R=\epsilon$ (Lemma~\ref{lem:terminal}).

\item \textbf{One block.} A block of $m\le q$ rows routes to at most
$N\le(q+2)2^M$ destinations. Two facts combine: the exact joint law of
$(A,As)$ given a local restriction has a joint $L^q$ density whose norm
exceeds the input by a factor of order $\exp(Cd)R^{a}r^{-m(1-1/q)}$
(Theorem~\ref{thm:proj}); and its \emph{common support} is the projected
ellipsoid whose average volume is at most $C_E^d r^m$
(Lemma~\ref{lem:volume}). H\"older then restores the lost radius power and
charges only $N^{1/q}$ for routing. Taking $a$-th roots, one block
multiplies $R$ by at most
$\exp(Cd/a)\,N^{1/(aq)}$ (Lemma~\ref{lem:block}).

\item \textbf{Streaming.} Partition the stream into $B=\lceil T/q\rceil$
blocks. The per-block multiplier is at most $e^{\Lambda}$ with
\[
 \Lambda=C\Bigl(1+\frac{M}{d^2}\Bigr),
\]
because $N^{1/(aq)}$ divides $\log N$ by $q\asymp d$, and $\log N$ carries
the memory budget. Chaining $B$ blocks gives the invariant at scale
$R=\epsilon e^{\Lambda B}$ (Proposition~\ref{prop:stream}). Since the ball
of radius two covers the sphere, total success is at most $(2R)^a$.
\end{enumerate}

The memory enters only through the ratio $M/d^2$: quadratic memory
contributes a constant per block. At constant accuracy the block
inequality is too weak (the logarithm is not yet large), and a separate
symmetry argument supplies $T>d/4$ (Lemma~\ref{lem:reflect}). The two
regimes join in Section~\ref{sec:assembly}.

\section{Terminal states: how concentrated can success be?}\label{sec:terminal}

A terminal estimate is chosen from a law independent of the signal. Its
success as a function of $s$ is concentrated on a cap, and the cap has
small mass. We record both bounds and take their geometric mean.

\begin{lemma}[Cap mass]\label{lem:cap}
For $d\ge2$, $z\in S^{d-1}$, and $0<r\le1/2$,
\begin{equation}\label{eq:cap}
 \sigma_d(B(z,r))\le r^{d-1}.
\end{equation}
\end{lemma}

\begin{proof}
Rotate $z$ to the north pole and write $n=d-1$. For $s\in S^{d-1}\cap B(z,r)$,
the first $n$ coordinates $u=(s_1,\dots,s_n)$ satisfy
$\norm u\le\norm{s-z}\le r$, and the last coordinate is
$s_d=\sqrt{1-\norm u^2}\ge\sqrt{1-r^2}\ge1/2$, since $r\le1/2$. Over the
disk $\norm u\le r$ the graph area element $1/s_d$ is therefore at most two,
so the cap has area at most $2v_nr^n$, where $v_n$ is the volume of the unit
$n$-ball. Each hemisphere projects onto that ball with area element
$1/s_d\ge1$, so the whole sphere has area at least $2v_n$. The ratio is at
most $r^n$.
\end{proof}

\begin{lemma}[Terminal local mass]\label{lem:terminal}
Let $Q$ be a probability law on $S^{d-1}$ independent of the signal and
put
\[
 h(s)=Q\{v:\arccos\ip{v}{s}\le\epsilon\}.
\]
Then $h$ has local mass at scale $R=\epsilon$; that is,
$\int_{B(z,r)}h\,d\sigma_d\le(\epsilon r)^{(d-1)/2}$ for all
$z\in S^{d-1}$, $r>0$.
\end{lemma}

\begin{proof}
Fix a unit output $v$ with $\arccos\ip{v}{s}\le\epsilon$. Then
$\norm{v-s}=2\sin(\theta/2)\le\theta\le\epsilon$, because $\sin t\le t$;
so the globally successful set for a fixed $v$ lies in a cap of chordal
radius $\epsilon$ and has $\sigma$-mass at most $\epsilon^n$. Averaging
against $Q$ gives $\int_{S^{d-1}}h\,d\sigma\le\epsilon^n$, hence
$\int_{B(z,r)}h\,d\sigma\le\epsilon^n$ for every $r$. Now fix $z\in S^{d-1}$
and $r>0$ (throughout the paper $\epsilon\le1/10<1/2$). If $r\le\epsilon$,
then $0\le h\le1$ and Lemma~\ref{lem:cap} give
$\int_{B(z,r)}h\,d\sigma\le\sigma(B(z,r))\le r^n\le(\epsilon r)^{n/2}$.
If $r>\epsilon$, then $\int_{B(z,r)}h\,d\sigma\le\epsilon^n\le(\epsilon r)^{n/2}$.
Either way the bound holds.
\end{proof}

\noindent\textbf{What this says.} Two constraints tug in opposite
directions: for a small ball success cannot exceed the ball's own mass, of
order $r^n$, and globally it cannot exceed the accuracy cap's mass
$\epsilon^n$. The
geometric mean $(\epsilon r)^{n/2}$ has the same exponent in $r$ and
$\epsilon$, exactly the form preserved by one block.

\section{One block of exact equations: the projection theorem}\label{sec:proj}

This is the technical heart. One block of $m$ exact rows turns a localized
part of successful mass into an exact joint law of $(A,As)$; we must
control that law's density and its support. Throughout, $\gamma_m$ is the
law of an $m$-by-$d$ standard Gaussian matrix on $\R^{m\times d}$, and
\[
 \lambda_m(dA,dy)=\gamma_m(dA)\,dy
\]
is the reference measure on $\R^{m\times d}\times\R^m$. For a finite
nonnegative Borel measure $\mu$ on $\R^d$, let $\eta_\mu$ be the image of
$\gamma_m(dA)\,\mu(ds)$ under $(A,s)\mapsto(A,As)$. The matrix is part of
the observed data; $\mu$ is not renormalized. Write $v_m$ for the unit
$m$-ball volume. For a closed support ball $B(z,R)$ set
\begin{equation}\label{eq:support}
 \mathcal E_{z,R}=\{(A,y):y\in Az+AB(0,R)\}.
\end{equation}
This set is Borel (it is the zero set of a continuous function), and the
exact image is carried by it.

\subsection{Affine distance and the Gram determinant}

\begin{lemma}[Tube and inverse-distance bounds]\label{lem:tube}
Let $1\le m\le d$, let $p\ge2$ be an integer, let
$\beta>m+p-2$, $H,R>0$, $z\in\R^d$, and let $\mu$ be a finite nonnegative
Borel measure supported on $B(z,R)$ with
$\mu(B(x,t))\le H t^\beta$ for all $x\in\R^d$, $t>0$. If $L$ is an affine
$j$-plane with $0\le j\le p-2$, then for $0<t\le R$
\begin{align}
 \mu\{s:\dist(s,L)\le t\}&\le 3^j2^\beta H R^j t^{\beta-j},
 \label{eq:tube}\\
 \int\dist(s,L)^{-m}\,d\mu(s)&\le J_j\,H R^{\beta-m},
 \qquad J_j=1+3^j2^\beta\frac{m}{\beta-j-m}.
 \label{eq:inverse}
\end{align}
\end{lemma}

\begin{proof}
The projection of $B(z,R)$ onto $L$ lies in a $j$-dimensional ball of
radius $R$. A maximal $t$-separated set in it is a $t$-net with at most
$(1+2R/t)^j\le(3R/t)^j$ points: disjoint balls of radius $t/2$ fit inside
the ball of radius $R+t/2$. When $j=0$, use its single point. Any point of
$B(z,R)$ within distance $t$ of $L$ is within $2t$ of a net point, so the
ambient ball bound gives
\[
 \mu\{\dist(s,L)\le t\}\le(3R/t)^j\,H(2t)^\beta=3^j2^\beta H R^j t^{\beta-j},
\]
which is \eqref{eq:tube}. Since $\beta>j$, letting $t\downarrow0$ also
gives $\mu(L)=0$.

The total mass is $\mu(\R^d)\le H R^\beta$ (take the ball $B(z,R)$).
Using $\dist(s,L)^{-m}=R^{-m}+m\int_{\dist(s,L)}^{R}t^{-m-1}\,dt$ on the
support (where $\dist\le R$) and Tonelli,
\begin{align*}
 \int\dist(s,L)^{-m}\,d\mu
 &\le R^{-m}\mu(\R^d)+m\int_0^R t^{-m-1}\mu\{\dist(s,L)\le t\}\,dt\\
 &\le H R^{\beta-m}+3^j2^\beta mHR^j\int_0^R t^{\beta-j-m-1}\,dt\\
 &=\Bigl(1+3^j2^\beta\frac{m}{\beta-j-m}\Bigr)HR^{\beta-m}=J_j HR^{\beta-m},
\end{align*}
since $\beta-j-m>0$.
\end{proof}

The exponent $\beta-j-m>0$ is exactly why Theorem~\ref{thm:proj} below
requires $\beta>m+p-2$.

\begin{lemma}[Gram product]\label{lem:gram}
Under the hypotheses of Lemma~\ref{lem:tube}, for the tuple
$(s_1,\ldots,s_p)$ and $V=[s_2-s_1,\ldots,s_p-s_1]$,
\begin{equation}\label{eq:gram}
 \int\det(V^{\mathsf T}V)^{-m/2}\,d\mu^{\otimes p}
 \le H^p R^{\beta p-m(p-1)}\prod_{j=0}^{p-2}J_j,
\end{equation}
the integrand being assigned any fixed value on the
$\mu^{\otimes p}$-null set of rank-deficient tuples.
\end{lemma}

\begin{proof}
Proper affine subspaces of dimension at most $p-2$ have $\mu$-measure zero
(by Lemma~\ref{lem:tube} in the top case $L=\R^d$ if $p-1>d$; otherwise
by slicing). Hence $s_i\notin\aff(s_1,\ldots,s_{i-1})$ for almost every
tuple, so by Gram--Schmidt
\[
 \det(V^{\mathsf T}V)^{-1/2}
 =\prod_{i=2}^p\dist\bigl(s_i,\aff(s_1,\ldots,s_{i-1})\bigr)^{-1}.
\]
Integrate first in $s_p$, then $s_{p-1}$, down to $s_2$. At the $s_i$ step
the preceding span has dimension $i-2$ almost surely, so (2) contributes
$J_{i-2}HR^{\beta-m}$. The final $s_1$ integral contributes at most
$HR^\beta$. All integrands are nonnegative and Tonelli justifies the
order, giving \eqref{eq:gram}.
\end{proof}

\subsection{The Gaussian smoothing identity}

\begin{lemma}[Gaussian difference identity]\label{lem:gauss}
Let $d,m\ge1$, $k\ge2$, $\delta>0$, and $t_1,\ldots,t_k\in\R^d$. Put
$D=[t_2-t_1,\ldots,t_k-t_1]$ and let $\phi_\delta$ be the $N(0,\delta^2I_m)$
density. If $A\sim\gamma_m$ then
\begin{equation}\label{eq:gaussid}
 \E_A\!\int_{\R^m}\prod_{i=1}^k\phi_\delta(y-At_i)\,dy
 =(2\pi)^{-m(k-1)/2}
 \det\!\Bigl(D^{\mathsf T}D+\delta^2(I_{k-1}+\mathbf1\mathbf1^{\mathsf T})\Bigr)^{-m/2}.
\end{equation}
If $D$ has full column rank, the right side is at most
$(2\pi)^{-m(k-1)/2}\det(D^{\mathsf T}D)^{-m/2}$.
\end{lemma}

\begin{proof}
Introduce independent $N(0,\delta^2I_m)$ vectors $\eta_i$. For fixed $A$,
integrating $\prod_i\phi_\delta(y-At_i)$ over the common $y$ gives the
density at zero of the $k-1$ differences
$(At_i+\eta_i)-(At_1+\eta_1)$, $2\le i\le k$; the change of variables from
$k$ vectors to the first plus these differences has determinant one.
Averaging over $A$, each of the $m$ rows of these differences is a centered
Gaussian vector with covariance
$D^{\mathsf T}D+\delta^2(I+\mathbf1\mathbf1^{\mathsf T})$, and the rows are
independent; evaluating the joint density at zero gives \eqref{eq:gaussid}.
If $G=D^{\mathsf T}D$ is positive definite and $Q$ positive semidefinite,
$\det(G+Q)=\det G\,\det(I+G^{-1/2}QG^{-1/2})\ge\det G$. Apply with
$Q=\delta^2(I+\mathbf1\mathbf1^{\mathsf T})$.
\end{proof}

\subsection{The exact projection density}

\begin{theorem}[Exact projection density]\label{thm:proj}
Let $d,m\ge1$ and $p\ge2$ be integers, let $\beta>m+p-2$, $H,R>0$,
$z\in\R^d$, and let $\mu$ be a finite nonnegative Borel measure supported on
$B(z,R)$ with $\mu(B(x,t))\le Ht^\beta$ for all $x,t$. Then $\eta_\mu$ has
a nonnegative jointly Borel density $F$ with respect to $\lambda_m$, which
can be taken to vanish outside $\mathcal E_{z,R}$, and
\begin{equation}\label{eq:projbound}
 \norm{F}_{L^p(\lambda_m)}\le \mathcal B
 :=(2\pi)^{-m(p-1)/(2p)}\,
 H R^{\beta-m(1-1/p)}
 \Bigl(\prod_{j=0}^{p-2}J_j\Bigr)^{1/p},
\end{equation}
with $J_j$ as in Lemma~\ref{lem:tube}.
\end{theorem}

\begin{proof}
\textbf{Step 1 (smoothing moment).} For $\delta>0$ put
$F_\delta(A,y)=\int\phi_\delta(y-As)\,d\mu(s)$. Expanding the $p$-th power
and using Tonelli and Lemma~\ref{lem:gauss} with $k=p$,
\begin{equation}\label{eq:smooth}
 \int F_\delta^p\,d\lambda_m
 =(2\pi)^{-m(p-1)/2}
 \int\det\!\Bigl(V^{\mathsf T}V+\delta^2(I+\mathbf1\mathbf1^{\mathsf T})\Bigr)^{-m/2}\,d\mu^{\otimes p}
 \le\mathcal B^p,
\end{equation}
where we used that adding the positive semidefinite covariance only
increases the determinant, that rank-deficient tuples are null for
$\mu^{\otimes p}$, and Lemma~\ref{lem:gram}. Note the exact
$(2\pi)^{-m(p-1)/2}$ under the root matches the prefactor in
\eqref{eq:projbound}.

\textbf{Step 2 (limit functional).} For real $\psi\in C_c(\R^{md}\times\R^m)$
and independent $Z\sim N(0,I_m)$,
\[
 \int\psi F_\delta\,d\lambda_m
 =\int\E_Z\psi(A,As+\delta Z)\,d\gamma_m(A)\,d\mu(s)
 \longrightarrow\int\psi\,d\eta_\mu
\]
by bounded convergence, since $\mu$ is finite and $\psi$ is bounded
continuous. By H\"older and \eqref{eq:smooth},
$\bigl|\int\psi F_\delta\,d\lambda_m\bigr|
\le\mathcal B\,\norm{\psi}_{L^{p/(p-1)}(\lambda_m)}$.

\textbf{Step 3 (density by duality).} The measure $\lambda_m$ is locally
finite, $\sigma$-finite, Borel; $\eta_\mu$ is finite, nonnegative, Borel.
The bounded functional $\psi\mapsto\int\psi\,d\eta_\mu$ on $C_c$ extends to
$L^{p/(p-1)}(\lambda_m)$ with norm at most $\mathcal B$. Standard $L^p$
duality then gives $f\in L^p(\lambda_m)$ with $\norm{f}_p\le\mathcal B$ and
$\eta_\mu=f\lambda_m$; taking a Borel representative and using
$\eta_\mu=f^+\lambda_m$ (the negative part is a nonnegative measure that
annihilates all nonnegative tests) yields a nonnegative density.

\textbf{Step 4 (support).} The image measure is carried by the Borel set
$\mathcal E_{z,R}$; multiplying the density by $\ind_{\mathcal E_{z,R}}$
preserves the identity and makes $F$ vanish almost everywhere outside it.
\end{proof}

\begin{remark}
Theorem~\ref{thm:proj} is the only place measure-theoretic care is needed.
The analytic content is entirely in Lemma~\ref{lem:tube} and
Lemma~\ref{lem:gram}; the passage from the smoothed bound
\eqref{eq:smooth} to the exact density is a standard Riesz-representation
argument, and we have included it so that the proof uses \emph{exact}
labels, not a smoothed surrogate.
\end{remark}

\section{How much room do the labels take?}\label{sec:volume}

The density bound of Theorem~\ref{thm:proj} loses $m(1-1/p)$ powers of the
support radius; the same powers must be recovered by the average volume of
the common support. The projected ellipsoid does exactly this.

\begin{lemma}[Projected volume]\label{lem:volume}
Let $1\le m\le d$, $z\in\R^d$, $R>0$, and let $\mathcal E_{z,R}$ be as in
\eqref{eq:support}. There is an absolute $C_E\ge1$ with, for a standard
Gaussian $m$-by-$d$ matrix,
\begin{equation}\label{eq:volume}
 \lambda_m(\mathcal E_{z,R})
 =v_mR^m\,\E_A\sqrt{\det(AA^{\mathsf T})}
 \le v_mR^md^{m/2}
 \le R^m\Bigl(\frac{2\pi e\,d}{m}\Bigr)^{m/2}
 \le C_E^d R^m.
\end{equation}
\end{lemma}

\begin{proof}
Almost surely $AA^{\mathsf T}$ is invertible; in singular-value
coordinates $AB(0,R)$ is an ellipsoid with semiaxes $R$ times the singular
values of $A$, so its volume is exactly $v_mR^m\sqrt{\det(AA^{\mathsf T})}$.
Hadamard's inequality bounds $\sqrt{\det(AA^{\mathsf T})}$ by the product of
the row norms, whose expectations are at most $\sqrt d$ each; independence
gives the first inequality. Also
$(2\pi)^{m/2}=\int e^{-\norm y^2/2}\,dy\ge e^{-m/2}v_mm^{m/2}$, whence
$v_m\le(2\pi e/m)^{m/2}$. For $t=m/d\in(0,1]$, since $t\log(1/t)\le1/e$,
\[
 \frac1d\log\Bigl(\bigl(\tfrac{2\pi e d}{m}\bigr)^{m/2}\Bigr)
 =\frac t2\log(2\pi e)+\frac t2\log\tfrac1t
 \le\frac12\log(2\pi e)+\frac1{2e},
\]
an absolute constant, so some $C_E$ works.
\end{proof}

\section{Routing among many destinations}\label{sec:selection}

All later estimates select among boundedly many continuation measures
supported on one common data domain. Selection costs only $N^{1/p}$.

\begin{lemma}[Selection]\label{lem:select}
Let $(E,\mathcal E,\lambda)$ be a measure space, $\mathcal D\in\mathcal E$
of finite measure, $p>1$, $U\ge0$, $N\ge1$. Suppose finite nonnegative
measures $\eta_1,\ldots,\eta_N$ are supported on $\mathcal D$ and satisfy,
for all measurable $0\le g\le1$,
\begin{equation}\label{eq:test}
 \int g\,d\eta_j\le U\Bigl(\int_{\mathcal D}g\,d\lambda\Bigr)^{1-1/p}.
\end{equation}
Then for measurable $g_j\ge0$ with $\sum_jg_j\le1$,
\begin{equation}\label{eq:selection}
 \sum_{j=1}^N\int g_j\,d\eta_j
 \le N^{1/p}U\,\lambda(\mathcal D)^{1-1/p}.
\end{equation}
In particular, if $U\le HLr^{\beta-m(1-1/p)}$ and
$\lambda(\mathcal D)\le Vr^m$, then the right side is at most
$N^{1/p}H V^{1-1/p}L\,r^\beta$.
\end{lemma}

\begin{proof}
Let $b_j=\int_{\mathcal D}g_j\,d\lambda$. Each $g_j\in[0,1]$, so
\eqref{eq:test} gives $\int g_j\,d\eta_j\le Ub_j^{1-1/p}$, and H\"older on
the finite index set gives
$\sum_jUb_j^{1-1/p}\le U N^{1/p}(\sum_jb_j)^{1-1/p}$. Since
$\sum_jg_j\le1$, we have $\sum_jb_j\le\lambda(\mathcal D)$; this proves
\eqref{eq:selection}. The radius substitution multiplies the two powers of
$r$ into $r^\beta$.
\end{proof}

\section{Putting one block together}\label{sec:block}

\begin{lemma}[Backward block bound]\label{lem:block}
Let $1\le m\le q$ and $N\ge1$. Suppose $h_1,\ldots,h_N:S^{d-1}\to[0,1]$
have local mass at a common scale $R>0$ in the sense of
\eqref{eq:invariant}. Let $g_j:\R^{m\times d}\times\R^m\to[0,1]$ be Borel
with $\sum_jg_j\le1$ and define
$h(s)=\sum_jh_j(s)\int g_j(A,As)\,d\gamma_m(A)$. Then for every
$z\in S^{d-1}$ and $r>0$,
\begin{equation}\label{eq:block}
 \int_{B(z,r)}h\,d\sigma\le\exp(Cd)N^{1/q}(Rr)^a.
\end{equation}
Equivalently $h$ has local mass at scale
$R'=R\exp(Cd/a)N^{1/(aq)}$.
\end{lemma}

\begin{proof}
Fix $z\in S^{d-1}$, $r>0$, and $\mu_j=\ind_{B(z,r)}h_j\sigma$, a finite
Borel measure on $B(z,r)$. If an ambient ball $B(x,t)$ has positive
$\mu_j$-mass, choose a point $p$ of its intersection with the sphere; every
other point of the intersection lies within $2t$ of $p$. The local bound
therefore gives
\begin{equation}\label{eq:ambient}
 \mu_j(B(x,t))\le(2Rt)^a\qquad(x\in\R^d,\ t>0).
\end{equation}
Apply Theorem~\ref{thm:proj} with exponent $\beta=a$, moment order $p=q$,
coefficient $H=(2R)^a$, and support radius $r$. The margin
$J_\ell\le\exp(Cd)$ holds for $0\le\ell\le q-2$ by \eqref{eq:invariant}
parameters; absorbing $2^a$, we obtain exact joint densities $f_j$,
supported on $\mathcal E_{z,r}$, with
\[
 \norm{f_j}_{L^q(\lambda_m)}\le\exp(Cd)R^a r^{a-m(1-1/q)}.
\]
These represent unnormalized successful mass, not posteriors.

Put $q'=q/(q-1)$. By the exact image-measure identity, H\"older on
matrix--label space, and H\"older on the finite index set,
\begin{align*}
 \int_{B(z,r)}h\,d\sigma
 &=\sum_j\int_{\mathcal E_{z,r}}f_jg_j\,d\lambda_m\\
 &\le\exp(Cd)R^a r^{a-m(1-1/q)}
   \sum_j\Bigl(\int_{\mathcal E_{z,r}}g_j^{q'}\,d\lambda_m\Bigr)^{1/q'}\\
 &\le\exp(Cd)R^a r^{a-m(1-1/q)}N^{1/q}
   \Bigl(\int_{\mathcal E_{z,r}}\sum_jg_j^{q'}\,d\lambda_m\Bigr)^{1/q'}.
\end{align*}
Since $0\le g_j\le1$ and $\sum_jg_j\le1$, the last integral is at most
$\lambda_m(\mathcal E_{z,r})\le C_E^d r^m$ by Lemma~\ref{lem:volume}. Its
$1-1/q$ power restores the radius exponent:
$r^{a-m(1-1/q)}(r^m)^{1-1/q}=r^a$. Absorbing constants proves
\eqref{eq:block}; the $a$-th root gives the scale update.
\end{proof}

\begin{remark}[Why the two radii cancel]
The localization radius $r$ appears with \emph{opposite} signs in the
density norm ($r^{-m(1-1/q)}$) and the support volume ($r^{+m(1-1/q)}$).
Their product leaves exactly $r^a$, so the block bound pays no price for
localizing. Only the destination count and absolute constants remain.
For a block of length $m\le q$ with $N\le(q+2)2^M$,
\[
 \log\frac{R'}{R}\le\frac{Cd}{a}+\frac{M\log2+\log(q+2)}{aq}
 \le C\Bigl(1+\frac{M}{d^2}\Bigr)=:\Lambda,
\]
since $d/a\le3$ and $1/(aq)\le48/d^2$. Here is where quadratic memory
enters: $q\asymp d$ divides the log of the number of choices.
\end{remark}

\section{Reading a whole stream}\label{sec:stream}

We now split the horizon into blocks of at most $q$ rows and iterate
Lemma~\ref{lem:block}. Two bookkeeping facts are needed: how many
destinations a block can have, and how to pass from completed-measurable
rules to Borel rules without changing the prior experiment.

\subsection{Destinations of a block}

\begin{lemma}[Destinations]\label{lem:dest}
For a fixed-seed Borel learner with state sets $Q_t$ ($|Q_t|\le2^M$), a
sample-free stopping check at each index, and the horizon treated as
terminal, let $0\le t<T$, $u\in Q_t$, and $1\le m\le T-t$. There are an
integer $1\le N\le(m+2)2^M$, Borel routes $g_j\ge0$ with $\sum_jg_j\le1$,
and Borel functions $h_j:S^{d-1}\to[0,1]$ such that, for every $s$,
\begin{equation}\label{eq:category}
 h_{t,u}(s)=\sum_{j=1}^N h_j(s)\int g_j(A,As)\,d\gamma_m(A).
\end{equation}
Each destination is either a terminal state (with output law depending
only on its state and stopping index) or a continuing state at index
$t+m$.
\end{lemma}

\begin{proof}
Pre-generate all $m$ rows of the block. At each $k=t,\ldots,t+m-1$ perform
the sample-free stopping check; if active, process the next pair into
the next state. A terminal tag from the last transition stops at $t+m$;
an active exit is passed to the continuation before the check at $t+m$,
so that check is performed exactly once. A terminal destination records
its local offset $i\in\{0,\ldots,m\}$ and state in $Q_{t+i}$ (with $i=0$
the immediate stop and $i=m$ from the last transition); these outcomes
merge with same-state, same-index sample-free stops. Continuing
destinations form one extra copy of $Q_{t+m}$, distinguished from
terminal ones at that index. Thus
\[
 N\le\sum_{i=0}^m|Q_{t+i}|+|Q_{t+m}|\le(m+2)2^M.
\]
Because only local offsets appear, the count has no factor of $T$. For
arbitrary data $(A,b)$, each $g_j(A,b)$ is a finite sum of products of
Borel coordinate probabilities, hence Borel; conditioning on block data
then on the destination proves \eqref{eq:category} for every signal and
every starting state.
\end{proof}

\subsection{Borel versions}

\begin{lemma}[Borel reduction]\label{lem:borel}
Let $d\ge2$, let $\pi$ be a Borel probability measure on $S^{d-1}$, and
let $X\sim\gamma_1$ be independent of $S\sim\pi$. Suppose
\begin{equation}\label{eq:domination}
 \mathcal L(X,\ip{X}{S})\ll\lambda,\qquad \lambda(dx,dy)=\gamma_1(dx)\,dy.
\end{equation}
Fix a horizon $T\ge0$ and finite state sets. If every coordinate of the
finite transition/stopping vector is measurable in the $\lambda$-completion
of the Borel $\sigma$-field, then there are everywhere-defined Borel
transition and stopping kernels, with the same state sets and terminal
output laws, whose $\pi$-prior joint law of the signal, state path,
stopping index and output is unchanged. The domination
\eqref{eq:domination} holds when $\pi=\sigma$ is uniform, for every
$d\ge2$.
\end{lemma}

\begin{proof}
If $f$ is $\lambda$-completed-measurable, each dyadic superlevel set
agrees with a Borel set off a Borel $\lambda$-null set; replacing these by
their Borel representatives in
$f_n=2^{-n}\sum_{k=1}^{2^n}\ind\{f\ge k2^{-n}\}$ yields Borel $f_n$ with a
Borel limit equal to $f$ off the union of countably many null sets. Do
this simultaneously for all coordinates of all kernels; the (null) set
where a resulting vector fails to be a probability vector is repaired by a
fixed point mass. One Borel $\lambda$-null set $Z$ contains every altered
pair. Pre-generate all $T$ rows; each pair $(X_t,\ip{X_t}{S})$ has
$\lambda$-null $Z$-preimage, and a finite union over $t$ shows no altered
pair is ever visited almost surely. Coupling original and modified finite
choices by shared uniform randomness makes the state paths agree almost
surely; equal terminal state and index give equal output laws.

For the domination: condition on $X=x$, rotate to make $x/\norm{x}$ the
first axis, and write a uniform sphere point as $G/\norm G$ with
$G=(G_1,G_\perp)$. Then $\norm{G_\perp}>0$ almost surely and is independent
of $G_1$, and $g\mapsto g/\sqrt{g^2+R^2}$ ($R=\norm{G_\perp}$) is a smooth
increasing bijection of $\R$ with nonzero derivative. So $\ip{X}{S}$ is
absolutely continuous for every $x\neq0$; Fubini over sections of a
$\lambda$-null set proves \eqref{eq:domination}.
\end{proof}

The reduction averages original conditional success probabilities; it
never exchanges limits with a jointly measurable choice of Borel
replacements.

\subsection{The quantitative success bound}

\begin{proposition}[Success after a finite stream]\label{prop:stream}
There are absolute constants $C,d_0>0$ with the following property. For
$d\ge d_0$, every learner with $M\ge0$ bits and integer horizon $T\ge0$
has, for $S\sim\sigma$ independent of the fresh Gaussian rows,
\begin{equation}\label{eq:streambound}
 \Prob\{\arccos\ip{\widehat s}{S}\le\epsilon\}
 \le\min\Bigl\{1,\ \bigl[2\epsilon\exp\bigl(\Lambda\lceil T/q\rceil\bigr)\bigr]^a\Bigr\},
\end{equation}
where $0<\epsilon\le1/10$, $a=(d-1)/2$, $q=\lfloor(d-1)/8\rfloor$, and
$\Lambda=C(1+M/d^2)$.
\end{proposition}

\begin{proof}
Use the angular score. Fix a prior-preserving Borel replacement
(Lemma~\ref{lem:borel}) with prior $\sigma$. If $T=0$, the output is a
signal-independent mixture of terminal laws, so total success is at most
$(2\epsilon)^a$. Now assume $T\ge1$; increase $d_0$ so $q\ge2$, $q\ge d/16$,
$a\ge d/3$. Partition the $T$ indices into $B=\lceil T/q\rceil$ consecutive
blocks of length at most $q$. At the final boundary every continuation is
terminal and obeys Lemma~\ref{lem:terminal} at scale $\epsilon$.

Suppose at the end of one block all continuing functions obey
\eqref{eq:invariant} at a common scale $R\ge\epsilon$; terminal
destinations do so too by Lemma~\ref{lem:terminal} and monotonicity in the
scale. For a block of length $m\le q$, Lemma~\ref{lem:dest} puts every
preceding continuation in the form required by Lemma~\ref{lem:block} with
$N\le(q+2)2^M$. That lemma multiplies the scale by at most
$\exp(C_0d/a)N^{1/(aq)}$, whose logarithm is at most
\[
 \frac{C_0d}{a}+\frac{M\log2+\log(q+2)}{aq}\le C\Bigl(1+\frac{M}{d^2}\Bigr)=\Lambda,
\]
using $d/a\le3$, $1/(aq)\le48/d^2$, and
$\log(q+2)/(aq)\le48\log(d+2)/d^2$. Backward induction gives
\eqref{eq:invariant} at scale $R=\epsilon e^{\Lambda B}$ for every initial
state; averaging over the independent initial-state law preserves it. The
radius-two ball about any sphere point covers $S^{d-1}$, so total success is
at most $(2R)^a$. By Lemma~\ref{lem:borel} this bounds the original
conditional success for almost every seed; averaging over seeds gives
\eqref{eq:streambound}, and a probability is also at most one.
\end{proof}

\section{Constant accuracy: a symmetry argument}\label{sec:reflect}

For $\epsilon$ not small, the block inequality is too lossy; but a learner
that sees only $T$ rows can never distinguish a signal from its reflection
across the row span. Even with unlimited memory and all data, accuracy
near $1/10$ needs more than $d/4$ rows.

\begin{lemma}[Reflection]\label{lem:reflect}
Let $d\ge1$, $T\ge0$, $S\sim\sigma$. Let a $T$-by-$d$ matrix $A$,
independent of $S$, have row span $U$ with $\dim U\le T$, and let
$\widehat S$ be drawn from a kernel depending only on $(A,AS)$. Put
$u=P_US$, $v=(I-P_U)S$. For any $\widehat S\in\R^d$ and
$0<\epsilon<1$,
\begin{equation}\label{eq:reflect}
 \Prob\{\norm{\widehat S-S}\le\epsilon\}
 \le\frac12+\frac{T}{2d(1-\epsilon^2)}.
\end{equation}
For a unit output, $\E\ip{\widehat S}{v}=0$ and
$\E\ip{\widehat S}{S}\le\sqrt{T/d}$.
\end{lemma}

\begin{proof}
Conditional on $A$, reflection across $U$ sends $S=u+v$ to $u-v$. It
preserves uniform spherical measure and the data $(A,AS)$, because $Av=0$,
so the output kernel is the same at both signals. If $\norm v>\epsilon$,
the two reflected signals are more than $2\epsilon$ apart; a fixed
estimate succeeds for at most one, so averaging the common kernel over the
pair gives success at most $1/2$ on that event. Hence
\[
 \Prob\{\norm{\widehat S-S}\le\epsilon\}
 \le\frac12+\frac12\Prob\{\norm u^2\ge1-\epsilon^2\}.
\]
Spherical isotropy and independence of $A$ give
$\E(\norm u^2\mid A)=\dim U/d\le T/d$; Markov proves \eqref{eq:reflect}.
For unit outputs reflection cancels $\E\ip{\widehat S}{v}$, while
$\ip{\widehat S}{u}\le\norm u$; Cauchy--Schwarz and the same second moment
give the expectation bound.
\end{proof}

\begin{corollary}\label{cor:reflect-d4}
If $T\le d/4$ and $\epsilon\le1/10$, then any learner (even with unlimited
memory and all pre-generated rows) has chordal, hence angular, success
probability less than $2/3$.
\end{corollary}

\begin{proof}
By \eqref{eq:reflect}, success is at most
$\tfrac12+\tfrac{1}{8(1-\epsilon^2)}\le\tfrac12+\tfrac1{7.92}<\tfrac23$.
Angular error $\le\epsilon$ implies $\norm{\widehat S-S}\le\epsilon$ since
$2\sin(\theta/2)\le\theta\le\epsilon$. A learner with a deterministic
horizon uses a kernel of the full data, so the bound applies.
\end{proof}

\section{Proof of the main theorem}\label{sec:assembly}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Fix $A>0$. Let $d$ exceed the absolute threshold of
Proposition~\ref{prop:stream} and satisfy $a\ge d/3$, $q\ge d/16$. Put
\[
 K_A=\exp(C(1+A))>1,\qquad L=\log(1/\epsilon),\qquad B=\lceil T/q\rceil,
\]
with $C$ the absolute constant in $\Lambda$. Since $M\le Ad^2$ we have
$\Lambda\le C(1+A)=\log K_A$. If prior success is at least $2/3$, then by
\eqref{eq:streambound}
\[
 \tfrac23\le(2\epsilon K_A^{B})^a,
\]
so $\epsilon K_A^{B}\ge(1/2)(2/3)^{1/a}\ge1/3$ for large $d$ (since
$a\ge d/3$). Taking logarithms and using $B\le T/q+1$,
\begin{equation}\label{eq:rounding}
 T\ge q\Bigl(\frac{L-\log3}{\log K_A}-1\Bigr).
\end{equation}
Let $H_A=2(\log3+\log K_A)$. If $L\ge H_A$, then
$T\ge qL/(2\log K_A)\ge dL/(32\log K_A)$. If $L<H_A$, Corollary
\ref{cor:reflect-d4} gives $T>d/4>dL/(4H_A)$. Thus with
\[
 c_A=\min\Bigl\{\frac1{32\log K_A},\ \frac1{4H_A}\Bigr\}>0
\]
we have $T\ge c_A\,d\log(1/\epsilon)$ throughout
$0<\epsilon\le1/10$, $M\le Ad^2$.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:sub}]
Since $M(d)=o(d^2)$, there is $d_M$ with $M(d)\le d^2$ for $d\ge d_M$.
Apply Theorem~\ref{thm:main} with $A=1$ for each $d\ge d_M$ and each
accuracy $0<\epsilon(d)\le1/10$; $K_1=e^{2C}$ is absolute and $c_1>0$ is
absolute. The dimension threshold may depend on the memory sequence through
$d_M$. No relation between memory and accuracy is needed.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:worst}]
Average the fixed-signal experiment over $S\sim\sigma$ before selecting
Borel versions; measurability makes the averaged success the integral of
the per-signal successes, so success $\ge2/3$ for every signal gives
uniform success $\ge2/3$. Theorem~\ref{thm:main} and
Corollary~\ref{cor:sub} then apply with unchanged constants and thresholds;
Lemma~\ref{lem:borel} preserves the average even if a version changes
behavior at exceptional individual signals.
\end{proof}

\begin{remark}[The noisy-experiment consequence]
Theorem~\ref{thm:main} yields an $\Omega_A(d\,r\log d)$ lower bound in the
noisy Gaussian experiment of \cite{SSV2019} for fixed $A$, memory
$M\le Ad^2$, and Euclidean accuracy $e=d^{-r}$ in the stated fine-accuracy
range. An exact-observation learner generates the prescribed independent
uniform noise inside each transition and simulates the noisy learner with
the same states and horizon (the per-seed Borel reduction applies first,
since the noisy pair law has a density). On $\norm{V-S}\le e\le1/20$,
normalizing $V$ gives angular error at most $\arcsin e\le2e$; taking
$\epsilon=2e$ gives $T\ge c_A d\log(1/(2e))=\Omega_A(d\,r\log d)$.
\end{remark}

\begin{thebibliography}{99}
\bibitem{Kaczmarz1937} S.~Kaczmarz,
  Angen\"aherte Aufl\"osung von Systemen linearer Gleichungen,
  Bull.\ Int.\ Acad.\ Pol.\ Sci.\ Lett.\ A (1937), 355--357.
\bibitem{SV2009} T.~Strohmer and R.~Vershynin,
  A randomized Kaczmarz algorithm with exponential convergence,
  J.\ Fourier Anal.\ Appl.\ 15 (2009), 262--278.
\bibitem{Shamir2014} O.~Shamir,
  Fundamental limits of online and distributed algorithms for statistical
  learning and estimation, NeurIPS 27 (2014), 163--171.
\bibitem{SteinhardtDuchi2015} J.~Steinhardt and J.~Duchi,
  Minimax rates for memory-bounded sparse linear regression,
  COLT (2015), PMLR 40, 1564--1587.
\bibitem{SVW2016} J.~Steinhardt, G.~Valiant, and S.~Wager,
  Memory, communication, and statistical queries, COLT (2016), PMLR 49,
  1490--1516.
\bibitem{Raz2016} R.~Raz,
  Fast learning requires good memory: a time-space lower bound for parity
  learning, arXiv:1602.05161.
\bibitem{Raz2017} R.~Raz,
  A time-space lower bound for a large class of learning problems,
  FOCS (2017), 732--742.
\bibitem{DKS2019} Y.~Dagan, G.~Kur, and O.~Shamir,
  Space lower bounds for linear prediction in the streaming model, COLT
  (2019), PMLR 99, 929--954.
\bibitem{SSV2019} V.~Sharan, A.~Sidford, and G.~Valiant,
  Memory-sample tradeoffs for linear regression with small error,
  STOC (2019), 890--901; full version arXiv:1904.08544v2.
\end{thebibliography}

\end{document}