Multi-Pass Memory Lower Bounds for Learning Problems

Qian Li, Shuo Wang, Jiapeng Zhang
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3671-3699, 2025.

Abstract

Space complexity in learning problems has received a lot of attention in recent years. In this direction, Brown, Bun, and Smith (COLT 2022) studied space complexity lower bounds for several natural learning problems under the \textit{one-pass streaming} setting. Assuming that the examples are sampled from $\{0,1\}^d$ and the optimal hypothesis can be encoded using $\kappa$ bits, they showed learning algorithms with constant error using a near-minimal number of examples, $\Tilde{O}(\kappa)$, require $\Tilde{\Omega}(d\kappa)$ bits of memory. Moreover, for a general number $N$ of examples, their memory lower bound takes the form $\Tilde{\Omega}(d\kappa\cdot \frac{\kappa}{N})$. However, as mentioned by Brown, Bun, and Smith (COLT 2022), the learning process often involves multiple passes over the data. Hence, it is equally important to study the space complexity in the \textit{multi-pass streaming} setting. The authors conjectured that similar lower bounds should apply but left it as an open problem. In this paper, we resolve this open problem by proving that any $L$-pass streaming algorithm using $N$ samples requires $\Tilde{\Omega}(d\kappa\cdot \frac{\kappa}{NL})$ bits of memory. Intuitively, our lower bound shows that a stream of $L\cdot N$ fresh examples is at least as useful as $L$ passes over $N$ examples. A key component of our approach is a lower bound on the information complexity of the \textsf{Bit-Bias$(p,q)$} problem in the multi-pass streaming setting, a basic problem that may have independent significance. In the \textsf{Bit-Bias$(p,q)$} problem, one sees a stream of $N$ i.i.d. random bits drawn from either \textsf{Bernoulli$(p)$} or \textsf{Bernoulli$(q)$}, and would like to distinguish the two cases. Our results not only extend the previous lower bound on \textsf{Bit-Bias$(0,1/2)$} by Brown, Bun, and Smith from the one-pass streaming setting to the more general multi-pass setting, but also cover more general values of $p$ and $q$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-li25d, title = {Multi-Pass Memory Lower Bounds for Learning Problems}, author = {Li, Qian and Wang, Shuo and Zhang, Jiapeng}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {3671--3699}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/li25d/li25d.pdf}, url = {https://proceedings.mlr.press/v291/li25d.html}, abstract = {Space complexity in learning problems has received a lot of attention in recent years. In this direction, Brown, Bun, and Smith (COLT 2022) studied space complexity lower bounds for several natural learning problems under the \textit{one-pass streaming} setting. Assuming that the examples are sampled from $\{0,1\}^d$ and the optimal hypothesis can be encoded using $\kappa$ bits, they showed learning algorithms with constant error using a near-minimal number of examples, $\Tilde{O}(\kappa)$, require $\Tilde{\Omega}(d\kappa)$ bits of memory. Moreover, for a general number $N$ of examples, their memory lower bound takes the form $\Tilde{\Omega}(d\kappa\cdot \frac{\kappa}{N})$. However, as mentioned by Brown, Bun, and Smith (COLT 2022), the learning process often involves multiple passes over the data. Hence, it is equally important to study the space complexity in the \textit{multi-pass streaming} setting. The authors conjectured that similar lower bounds should apply but left it as an open problem. In this paper, we resolve this open problem by proving that any $L$-pass streaming algorithm using $N$ samples requires $\Tilde{\Omega}(d\kappa\cdot \frac{\kappa}{NL})$ bits of memory. Intuitively, our lower bound shows that a stream of $L\cdot N$ fresh examples is at least as useful as $L$ passes over $N$ examples. A key component of our approach is a lower bound on the information complexity of the \textsf{Bit-Bias$(p,q)$} problem in the multi-pass streaming setting, a basic problem that may have independent significance. In the \textsf{Bit-Bias$(p,q)$} problem, one sees a stream of $N$ i.i.d. random bits drawn from either \textsf{Bernoulli$(p)$} or \textsf{Bernoulli$(q)$}, and would like to distinguish the two cases. Our results not only extend the previous lower bound on \textsf{Bit-Bias$(0,1/2)$} by Brown, Bun, and Smith from the one-pass streaming setting to the more general multi-pass setting, but also cover more general values of $p$ and $q$. } }
Endnote
%0 Conference Paper %T Multi-Pass Memory Lower Bounds for Learning Problems %A Qian Li %A Shuo Wang %A Jiapeng Zhang %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-li25d %I PMLR %P 3671--3699 %U https://proceedings.mlr.press/v291/li25d.html %V 291 %X Space complexity in learning problems has received a lot of attention in recent years. In this direction, Brown, Bun, and Smith (COLT 2022) studied space complexity lower bounds for several natural learning problems under the \textit{one-pass streaming} setting. Assuming that the examples are sampled from $\{0,1\}^d$ and the optimal hypothesis can be encoded using $\kappa$ bits, they showed learning algorithms with constant error using a near-minimal number of examples, $\Tilde{O}(\kappa)$, require $\Tilde{\Omega}(d\kappa)$ bits of memory. Moreover, for a general number $N$ of examples, their memory lower bound takes the form $\Tilde{\Omega}(d\kappa\cdot \frac{\kappa}{N})$. However, as mentioned by Brown, Bun, and Smith (COLT 2022), the learning process often involves multiple passes over the data. Hence, it is equally important to study the space complexity in the \textit{multi-pass streaming} setting. The authors conjectured that similar lower bounds should apply but left it as an open problem. In this paper, we resolve this open problem by proving that any $L$-pass streaming algorithm using $N$ samples requires $\Tilde{\Omega}(d\kappa\cdot \frac{\kappa}{NL})$ bits of memory. Intuitively, our lower bound shows that a stream of $L\cdot N$ fresh examples is at least as useful as $L$ passes over $N$ examples. A key component of our approach is a lower bound on the information complexity of the \textsf{Bit-Bias$(p,q)$} problem in the multi-pass streaming setting, a basic problem that may have independent significance. In the \textsf{Bit-Bias$(p,q)$} problem, one sees a stream of $N$ i.i.d. random bits drawn from either \textsf{Bernoulli$(p)$} or \textsf{Bernoulli$(q)$}, and would like to distinguish the two cases. Our results not only extend the previous lower bound on \textsf{Bit-Bias$(0,1/2)$} by Brown, Bun, and Smith from the one-pass streaming setting to the more general multi-pass setting, but also cover more general values of $p$ and $q$.
APA
Li, Q., Wang, S. & Zhang, J.. (2025). Multi-Pass Memory Lower Bounds for Learning Problems. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:3671-3699 Available from https://proceedings.mlr.press/v291/li25d.html.

Related Material