In his breakthrough paper, Raz showed that any parity learning algorithm
requires either quadratic memory or an exponential number of samples [FOCS'16,
JACM'19]. A line of work that followed extended this result to a large class of
learning problems. Until recently, all these results considered learning in the
streaming model, where each sample is drawn independently, and the learner is
allowed a single pass over the stream of samples. Garg, Raz, and Tal [CCC'19]
considered a stronger model, allowing multiple passes over the stream. In the
$2$-pass model, they showed that learning parities of size $n$ requires either
a memory of size $n^{1.5}$ or at least $2^{\sqrt{n}}$ samples. (Their result
also generalizes to other learning problems.)
In this work, for any constant $q$, we prove tight memory-sample lower bounds
for any parity learning algorithm that makes $q$ passes over the stream of
samples. We show that such a learner requires either $\Omega(n^{2})$ memory
size or at least $2^{\Omega(n)}$ samples. Beyond establishing a tight lower
bound, this is the first non-trivial lower bound for $q$-pass learning for any
$q\ge 3$. Similar to prior work, our results extend to any learning problem
with many nearly-orthogonal concepts.
We complement the lower bound with an upper bound, showing that parity
learning with $q$ passes can be done efficiently with $O(n^2/\log q)$ memory.

对于每个常数 q，我们证明了在样本流上进行 q 次遍历的任何奇偶性学习算法都需要 Ω(n2) 的内存大小或至少需要 2Ω(n) 个样本数量，并且这是对于任何 q≥3 的第一个非平凡的下界。与先前的工作类似，我们的结果适用于具有许多近似正交概念的任何学习问题。我们还通过上界来补充下界，表明带有 q 次遍历的奇偶性学习可以使用 O (n2/log q) 的内存高效地完成。