Multi-Pass Memory Lower Bounds for Learning Problems

摘要

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 one-pass streaming setting. Assuming that the examples are sampled from {0,1}^d and the optimal hypothesis can be encoded using κ bits, they showed learning algorithms with constant error using a near-minimal number of examples, O(κ), require Ω(dκ) bits of memory. Moreover, for a general number N of examples, their memory lower bound takes the form Ω(dκ·κ/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 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 Ω(dκ·κ/NL) bits of memory. Intuitively, our lower bound shows that a stream of L· 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 problem in the multi-pass streaming setting, a basic problem that may have independent significance. In the problem, one sees a stream of N i.i.d. random bits drawn from either or , and would like to distinguish the two cases. Our results not only extend the previous lower bound on 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.