The Sample Complexity of Replicable Realizable PAC Learning
This addresses the sample complexity of replicable learning, a key issue in machine learning theory, but is incremental as it focuses on a specific instance and bounds.
The paper tackles the problem of replicable realizable PAC learning by constructing a hard learning instance and proving a sample complexity lower bound with a close to (log|H|)^{3/2} dependence on hypothesis class size, with an almost matching upper bound for that instance.
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.