Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-017 | 5th February 2017 18:12

Mixing Implies Lower Bounds for Space Bounded Learning


Authors: Michal Moshkovitz, Dana Moshkovitz
Publication: 5th February 2017 19:08
Downloads: 1947


One can learn any hypothesis class $H$ with $O(\log|H|)$ labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires $|X|^{O(\log|H|)}$ memory states, where $X$ is the set of all labeled examples. A question that arises is how many labeled examples are needed in case the memory is bounded. Previous work showed, using techniques such as linear algebra and Fourier analysis, that parities cannot be learned with bounded memory and less than $|H|^{\Omega(1)}$ examples. One might wonder whether a general combinatorial condition exists for unlearnability with bounded memory, as we have with the condition $VCdim(H)=\infty$ for PAC unlearnability.

In this paper we give such a condition. We show that if an hypothesis class $H$, when viewed as a bipartite graph between hypotheses $H$ and labeled examples $X$, is mixing, then learning it requires $|H|^{\Omega(1)}$ examples under a certain bound on the memory. Note that the class of parities is mixing. As an immediate corollary, we get that most hypothesis classes are unlearnable with bounded memory. Our proof technique is combinatorial in nature and very different from previous analyses.

ISSN 1433-8092 | Imprint