Efficient Optimal PAC Learning
This work addresses computational efficiency in PAC learning for machine learning researchers, but it appears incremental as it builds on existing optimal learners.
The paper tackles the computational cost of optimal PAC learners by proposing an alternative learner that offers a different tradeoff in computational cost tied to empirical risk minimization, without specifying concrete numerical results.
Recent advances in the binary classification setting by Hanneke [2016b] and Larsen [2023] have resulted in optimal PAC learners. These learners leverage, respectively, a clever deterministic subsampling scheme and the classic heuristic of bagging Breiman [1996]. Both optimal PAC learners use, as a subroutine, the natural algorithm of empirical risk minimization. Consequently, the computational cost of these optimal PAC learners is tied to that of the empirical risk minimizer algorithm. In this work, we seek to provide an alternative perspective on the computational cost imposed by the link to the empirical risk minimizer algorithm. To this end, we show the existence of an optimal PAC learner, which offers a different tradeoff in terms of the computational cost induced by the empirical risk minimizer.