Subquadratic and fixed-quadratic memory–precision lower bounds

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\), let
\(0\le M\le Ad^2\) be an integer, and let \(0<\epsilon\le1/10\).
For any learner in Definition~\ref{h:model}, draw
\(S\sim\sigma_d\) independently of the rows and the learner's
data-independent randomness. If
\[
 \Prob\{\arccos\ip{\widehat s}{S}\le\epsilon\}\ge\frac23,
\]
then its prescribed horizon satisfies
\[
 T\ge c_A\,d\log(1/\epsilon).
\]

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
in Definition~\ref{h:model} 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. The
dimension threshold may depend on the memory sequence.

The conclusions of Theorem~\ref{h:main} and
Corollary~\ref{h:subquadratic} also hold when their average-success
assumption is replaced by
\[
 \Prob\{\arccos\ip{\widehat s}{s}\le\epsilon\}\ge\frac23
 \qquad\text{for every }s\in S^{d-1},
\]
where this probability is over the rows and the learner's randomness.

For all sufficiently large $d$, set
\[
 k=2\lfloor d/16\rfloor,\qquad m=k,\qquad t=m+1,\qquad \ell=4k.
\]
Suppose $p=f\sigma_d$ is a probability with $0\le f\le L<\infty$.
In the block experiment above, let $A$ have $k$ rows and let $B$ have
$\ell$ rows. There is an absolute constant $C$ such that
\begin{equation}
 I(S;W\mid B,BS)
 \le \frac{H(W)}{t}+Cd+C\log(2+\log L).
\end{equation}
The bound is uniform over the prior, the density bound $L$, and the message
kernel. The labels used to produce $W$ are the exact values $AS$.

Let $M(d)=o(d^2)$ be nonnegative integer-valued, and let
$0<\epsilon(d)\le1/10$. Suppose a family of learners in
Definition~\ref{def:streaming-model} satisfies
\[
 \Prob\{\arccos\langle\widehat S,S\rangle\le\epsilon(d)\}\ge\frac23
 \qquad\text{when }S\sim\sigma_d,
\]
where the probability includes the signal, samples, and learner randomness.
Then there is an absolute $c>0$ such that
\[
 T(d)\ge c\,d\log\frac1{\epsilon(d)}
\]
for all sufficiently large $d$. The eventual threshold may depend on the
memory sequence.

There is an absolute constant $c>0$ with the following property.
For any fixed $C_0>0$, consider the experiment above with $t\ge0$
blocks and $N\ge1$ possible message values, and suppose
\begin{equation}
 \bigl(2/m+e^{-ck}\bigr)\log N\le C_0d.
\end{equation}
One can reveal nested dyadic cells
$Q_0\supset Q_1\supset\cdots\supset Q_t$ containing $Z$, where $Q_i$
is a finite-valued measurable function of $Z$, the preceding revelations,
and $W_1,\ldots,W_i$, so that the augmented transcript
\[
 \Pi_t=(W_1,Q_1,\ldots,W_t,Q_t)
\]
satisfies
\begin{equation}
 I(Z;\Pi_t)\le Cdt.
\end{equation}
Here $C$ is a constant depending only on $C_0$. If $J_t$ is the level of $Q_t$, the
construction also gives $\E J_t\le Ct$.

Let $M(d)=o(d^2)$ be a nonnegative integer-valued memory bound, and let
$0<\epsilon(d)\le1/10$.  Suppose a family of learners in the model
above satisfies
\[
 \mathbb P\!\left\{\arccos\langle\widehat s,s\rangle
              \le\epsilon(d)\right\}\ge\frac23
 \qquad\text{for every }s\in S^{d-1}.
\]
There is an absolute $c>0$ such that, for all sufficiently large $d$,
\[
 T(d)\ge c\,d\log_2\frac1{\epsilon(d)}.
\]
The eventual dimension threshold may depend on the memory sequence.

Let \(M(d)=o(d^2)\) be integer-valued and let
\(0<\epsilon(d)\le1/10\).  Every learner of
Section~\ref{l:model} with uniform-sphere angular success probability
at least \(2/3\) must satisfy
\[
 T(d)\ge c\,d\log(1/\epsilon(d))
\]
for all sufficiently large \(d\), with an absolute \(c>0\).
The eventual dimension threshold may depend on the memory sequence.
Success at least \(2/3\) for every fixed signal implies the same
conclusion by averaging.

Let \(M(d)=o(d^2)\) be a sequence of nonnegative integers and let
\(0<\epsilon(d)\le1/10\). There is an absolute \(c>0\) such that, for
all sufficiently large \(d\), every learner in the experiment above whose
uniform-sphere average success satisfies
\[
 \Prob\{\arccos\inner{\widehat S}{S}\le\epsilon(d)\}\ge\frac23
\]
must use
\[
 T(d)\ge c\,d\log\frac1{\epsilon(d)}.
\]
The dimension threshold may depend on the memory sequence. In particular,
the conclusion holds when the same success probability is required
separately for every \(s\in S^{d-1}\).

Let \(d,k,q\) be integers and \(\beta\) a real number with
\(k\ge1\), \(q\ge2\), and
\begin{equation}
 k+q\le d,\qquad 0<\beta\le d,\qquad
 \beta-k-(q-2)\ge1.
\end{equation}
Let \(\nu\) be a finite positive Borel measure supported in
\(B(z,R)\), \(R>0\), satisfying \eqref{p:all-ball-mass} for some
\(K\ge0\). Assume that \(P_\#\nu\) is absolutely continuous with
respect to Lebesgue measure for \(\vartheta_{d,k}\)-almost every \(P\).
There is a jointly measurable version \(g(P,u)\) of its density such that
\begin{equation}
 \left(\int_{\mathcal V_{d,k}}\int_{\R^k}g(P,u)^q\,du\,
 d\vartheta_{d,k}(P)\right)^{1/q}
 \le C^d(C\sqrt d)^{k(1-1/q)}
 K R^{\beta-k(1-1/q)}.
\end{equation}
For every \(P\), this version vanishes when \(\norm{u-Pz}>R\).

For sufficiently large \(d\), put
\[
 k=p=\lfloor d/16\rfloor,\qquad \lambda=(d-1)/2.
\]
Let \(X\) be a \(k\)-by-\(d\) standard Gaussian matrix and define
\[
 H=(XX^{\mathsf T})^{1/2},\qquad P=H^{-1}X
\]
on its probability-one full-row-rank event, and set \(P\) to a fixed frame
on the null complement. Let \(m_k\) be uniform
probability on the unit ball of \(\R^k\). Suppose \(\nu\) is a finite
positive Borel measure fixed independently of \(X\), of mass at most one, supported in the unit ball
of \(\R^d\), such that for a fixed \(D>0\),
\[
 \nu(B(b,t))\le D^d t^\lambda
 \qquad(b\in\R^d,\ t>0).
\]
Assume \(P_\#\nu\) is absolutely continuous for almost every \(X\).
There is a jointly measurable nonnegative \(g_X(z)\) such that, for almost
every \(X\), \(P_\#\nu(dz)=g_X(z)\,dz/v_k\). This version vanishes when
\(\norm z>1\) and satisfies
\begin{equation}
 \E_X\int g_X(z)^p\,dm_k(z)\le \exp(C_Ddp).
\end{equation}

Let \(n=d-1\), let \(m,r,q\ge1\) be integers, and put
\(\ell=m+r\).  Suppose
\begin{equation}
 \ell<n,\qquad \ell-m-(q-1)\ge1.
\end{equation}
Let \(\rho\) be a finite nonnegative Borel measure on \(S^{d-1}\).
Suppose that \(B,D>0\) and, for every \(z\in\R^d\) and \(t>0\),
\begin{equation}
 \rho(B(z,t))\le Bt^\ell,\qquad
 \rho(B(z,t))\le Dt^n.
\end{equation}
Let \(X\sim\gamma_m\) and \(Z\sim\gamma_r\) be independent, and set
\(G=(X;Z)\).  For \(\delta>0\), define the cube average
\[
 p_{\rho,\delta}(g,y)
   =(2\delta)^{-\ell}\int
       \ind_{\{\norm{gu-y}_\infty\le\delta\}}\,d\rho(u).
\]
There is an absolute \(C\) such that, for every fixed
\(s\in S^{d-1}\) and every \(\delta>0\),
\begin{equation}
 \left[\E_X
       \left(\E_Z p_{\rho,\delta}((X;Z),(X;Z)s)\right)^q
 \right]^{1/q}
 \le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).
\end{equation}

If in addition \(\rho\ll\sigma\), use the jointly Borel density
\(p_\rho\) in \eqref{eq:r-density-version}.  There is a measurable
set \(E_\rho\subset S^{d-1}\), with \(\rho(E_\rho)=0\), such that
for every \(s\notin E_\rho\) the cube averages converge to
\(p_\rho(G,Gs)\) for \(\gamma_\ell\)-almost every \(G\), and
\begin{equation}
 \left[\E_X
       \left(\E_Zp_\rho((X;Z),(X;Z)s)\right)^q
 \right]^{1/q}
 \le e^{Cd}B\bigl(1+\log^+(D/B)\bigr).
\end{equation}
When \(\rho\ne0\), \(E_\rho\) may also be chosen so that
\(0<p_\rho(G,Gs)<\infty\) for \(\gamma_\ell\)-almost every \(G\)
and every \(s\notin E_\rho\).

In the two experiments of Subsection~\ref{subsec:r-two-experiments},
use the dimensions \eqref{eq:r-critical-parameters}.  Thus
\(S\sim\sigma\), \(A\sim\gamma_m\) is independent of \(S\), and
\(W\) is countable with an arbitrary joint dependence on \((S,A)\).
The aligned law retains \((S,A,W)\) and appends independent
\(r\)-row \(C\), whereas the independent law retains \((S,W)\)
and draws an independent \(\ell\)-row matrix \(G\).
If \(H(W)\le d^2\), then, for an absolute constant \(K\),
\begin{equation}
 I_0(S;W\mid G,GS)\le I_1(S;W\mid G,GS)+Kd.
\end{equation}

Let \(M(d)\) be a nonnegative integer sequence with \(M(d)=o(d^2)\),
and let \(0<\epsilon(d)\le1/10\).  For each \(d\), consider a learner
in Definition~\ref{def:r-streaming-model} with deterministic finite
horizon \(T(d)\).  If its uniform-sphere angular success probability,
including all learner randomness, is at least \(3/5\), then
\[
 T(d)\ge c\,d\log\frac1{\epsilon(d)}
\]
for an absolute \(c>0\) and all sufficiently large \(d\).  The
eventual dimension threshold may depend on the memory sequence.

Let \(M:\mathbb N\to\mathbb Z_{\ge0}\) satisfy \(M(d)=o(d^2)\).
There is a dimension threshold depending only on this memory sequence
such that, for every larger \(d\), every \(0<\epsilon\le1/10\), and
every learner in Definition~\ref{s:model}, the following implication
holds. If \(S\) is uniform on \(S^{d-1}\), independently of the
Gaussian rows and learner randomness, and
\[
 \Prob\{\arccos\ip{\widehat s}{S}\le\epsilon\}\ge\frac23,
\]
then
\begin{equation}
 T\ge 2^{-16}d\log_2(1/\epsilon).
\end{equation}

Under the memory assumption of Theorem~\ref{s:main}, suppose a learner
satisfies
\[
 \Prob_s\{\arccos\ip{\widehat s}{s}\le\epsilon\}\ge\frac23
 \qquad\text{for every }s\in S^{d-1},
\]
where \(\Prob_s\) averages its observations and randomness at the fixed
signal \(s\). Then \eqref{s:main-bound} holds at the same dimension
threshold.