Tight Time-Space Lower Bounds for Constant-Pass Learning
This provides foundational theoretical limits for multi-pass learning algorithms, impacting the design of efficient machine learning systems.
The paper tackles the problem of establishing memory-sample lower bounds for parity learning with multiple passes over a stream of samples, showing that for any constant number of passes q, a learner requires either Ω(n²) memory or at least 2^{Ω(n)} samples, and complements this with an upper bound of O(n²/log q) memory for efficient learning.
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 $Ω(n^{2})$ memory size or at least $2^{Ω(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.