Search papers, labs, and topics across Lattice.
This paper investigates the sample complexity of replicable realizable PAC learning, establishing a lower bound with a near $(\log|H|)^{3/2}$ dependence on the hypothesis class size. The authors achieve this lower bound by constructing a hard learning problem and analyzing a random walk on a Cayley graph associated with the hypothesis class, leveraging the spectral properties of the graph's adjacency matrix. They also provide an almost matching upper bound for the constructed instance, suggesting the tightness of their lower bound for this specific problem instance.
Replicable PAC learning is harder than we thought: achieving it provably requires a sample complexity scaling as $(\log|H|)^{3/2}$, a significant hurdle for large hypothesis classes.
In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to $(\log|H|)^{3/2}$ dependence on the size of the hypothesis class $H$. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with $H$ and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem.
