TY - GEN

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

AU - Raz, Ran

PY - 2017/11/10

Y1 - 2017/11/10

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=85041097497&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041097497&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2017.73

DO - 10.1109/FOCS.2017.73

M3 - Conference contribution

AN - SCOPUS:85041097497

T3 - Annual Symposium on Foundations of Computer Science - Proceedings

SP - 732

EP - 742

BT - Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

PB - IEEE Computer Society

T2 - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017

Y2 - 15 October 2017 through 17 October 2017

ER -