A time-space lower bound for a large class of learning problems

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

12 Scopus citations

Abstract

We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. As a special case, this gives a new proof for the time-space lower bound for parity learning [R16]. Our result is stated in terms of the norm of the matrix that corresponds to the learning problem. Let X, A be two finite sets. Let M: A X \rightarrow \{-1,1\} be a matrix. The matrix M corresponds to the following learning problem: An unknown element x X was chosen uniformly at random. A learner tries to learn x from a stream of samples, (a-1, b-1), (a-2, b-2)..., where for every i, a-i A is chosen uniformly at random and b-i = M(a-i,x). Let \sigma be the largest singular value of M and note that always \sigma ≤ |A|^{1/2} |X|^{1/2}. We show that if \sigma ≤ |A|^{1/2} |X|^{1/2 - ∈, then any learning algorithm for the corresponding learning problem requires either a memory of size quadratic in ∈ n or number of samples exponential in ∈ n, where n = \log-2 |X|.As a special case, this gives a new proof for the memorysamples lower bound for parity learning [14].

Original languageEnglish (US)
Title of host publicationProceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
PublisherIEEE Computer Society
Pages732-742
Number of pages11
ISBN (Electronic)9781538634646
DOIs
StatePublished - Nov 10 2017
Event58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 - Berkeley, United States
Duration: Oct 15 2017Oct 17 2017

Publication series

NameAnnual Symposium on Foundations of Computer Science - Proceedings
Volume2017-October
ISSN (Print)0272-5428

Other

Other58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
CountryUnited States
CityBerkeley
Period10/15/1710/17/17

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A time-space lower bound for a large class of learning problems'. Together they form a unique fingerprint.

Cite this