The Sample Complexity of Replicable Realizable PAC Learning

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.