ECCC-Report TR17-017https://eccc.weizmann.ac.il/report/2017/017Comments and Revisions published for TR17-017en-usSun, 05 Feb 2017 19:08:06 +0200
Paper TR17-017
| Mixing Implies Lower Bounds for Space Bounded Learning |
Michal Moshkovitz,
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2017/017One 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.Sun, 05 Feb 2017 19:08:06 +0200https://eccc.weizmann.ac.il/report/2017/017