Time-space lower bounds for two-pass learning

Sumegha Garg, Ran Raz, Avishay Tal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 Ω(n2) 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 Ω(n1.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 languageEnglish (US)
Title of host publication34th Computational Complexity Conference, CCC 2019
EditorsAmir Shpilka
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771160
DOIs
StatePublished - Jul 1 2019
Event34th Computational Complexity Conference, CCC 2019 - New Brunswick, United States
Duration: Jul 18 2019Jul 20 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume137
ISSN (Print)1868-8969

Conference

Conference34th Computational Complexity Conference, CCC 2019
CountryUnited States
CityNew Brunswick
Period7/18/197/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

    Garg, S., Raz, R., & Tal, A. (2019). Time-space lower bounds for two-pass learning. In A. Shpilka (Ed.), 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