### Abstract

A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [11, 7, 12, 9, 2, 5]. For example, any algorithm for learning parities of size n requires either a memory of size Ω(n^{2}) or an exponential number of samples [11]. All these works modeled the learner as a one-pass branching program, allowing only one pass over the stream of samples. In this work, we prove the first memory-samples lower bounds (with a super-linear lower bound on the memory size and super-polynomial lower bound on the number of samples) when the learner is allowed two passes over the stream of samples. For example, we prove that any two-pass algorithm for learning parities of size n requires either a memory of size Ω(n^{1.5}) or at least 2^{Ω(}n) samples. More generally, a matrix M : A × X → {−1, 1} corresponds to the following learning problem: An unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a1, b1), (a2, b2) . . ., where for every i, ai ∈ A is chosen uniformly at random and bi = M(ai, x). Assume that k, `, r are such that any submatrix of M of at least 2^{−k} · |A| rows and at least 2^{−`} · |X| columns, has a bias of at most 2^{−r}. We show that any two-pass learning algorithm for the learning problem corresponding to M requires either a memory of size at least Ω k · min{k, `}, or at least 2^{Ω(min{k,`,r})} samples.

Original language | English (US) |
---|---|

Title of host publication | 34th Computational Complexity Conference, CCC 2019 |

Editors | Amir Shpilka |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771160 |

DOIs | |

State | Published - Jul 1 2019 |

Event | 34th Computational Complexity Conference, CCC 2019 - New Brunswick, United States Duration: Jul 18 2019 → Jul 20 2019 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 137 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 34th Computational Complexity Conference, CCC 2019 |
---|---|

Country | United States |

City | New Brunswick |

Period | 7/18/19 → 7/20/19 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Branching program
- Lower bounds
- PAC learning
- Time-space tradeoffs
- Two-pass streaming

## Fingerprint Dive into the research topics of 'Time-space lower bounds for two-pass learning'. Together they form a unique fingerprint.

## Cite this

*34th Computational Complexity Conference, CCC 2019*(Leibniz International Proceedings in Informatics, LIPIcs; Vol. 137). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2019.22