### Abstract

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,b_{1}), (a2,b_{2}) . . ., where for every i, a_{i} ∈ A is chosen uniformly at random and b_{i} = 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 learning algorithm for the learning problem corresponding to M requires either a memory of size at least Ω (k · ℓ), or at least 2^{Ω}(r) samples. The result holds even if the learner has an exponentially small success probability (of 2^{−Ω}(r)). In particular, this shows that for a large class of learning problems, any learning algorithm requires either a memory of size at least Ω ((log |X|) · (log |A|)) or an exponential number of samples, achieving a tight Ω ((log |X|) · (log |A|)) lower bound on the size of the memory, rather than a bound of Ω min (log |X|)^{2}, (log |A|)^{2} obtained in previous works by Raz [FOCS’17] and Moshkovitz and Moshkovitz [ITCS’18]. Moreover, our result implies all previous memory-samples lower bounds, as well as a number of new applications. Our proof builds on the work of Raz [FOCS’17] that gave a general technique for proving memory-samples lower bounds.

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

Title of host publication | STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Monika Henzinger, David Kempe, Ilias Diakonikolas |

Publisher | Association for Computing Machinery |

Pages | 297-310 |

Number of pages | 14 |

ISBN (Electronic) | 9781450355599 |

DOIs | |

State | Published - Jun 20 2018 |

Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: Jun 25 2018 → Jun 29 2018 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|

Country | United States |

City | Los Angeles |

Period | 6/25/18 → 6/29/18 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Branching programs
- Extractors
- Learning from samples
- Time-space tradeoff

## Fingerprint Dive into the research topics of 'Extractor-Based time-Space lower bounds for learning'. Together they form a unique fingerprint.

## Cite this

*STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*(pp. 297-310). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188962