Efficient Optimal PAC Learning

Mikael Høgsgaard Møller
Proceedings of The 36th International Conference on Algorithmic Learning Theory, PMLR 272:578-580, 2025.

Abstract

Recent advances in the binary classification setting by Hanneke (2016) 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v272-hogsgaard-moller25a, title = {Efficient Optimal PAC Learning}, author = {H{\o}gsgaard M{\o}ller, Mikael}, booktitle = {Proceedings of The 36th International Conference on Algorithmic Learning Theory}, pages = {578--580}, year = {2025}, editor = {Kamath, Gautam and Loh, Po-Ling}, volume = {272}, series = {Proceedings of Machine Learning Research}, month = {24--27 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v272/main/assets/hogsgaard-moller25a/hogsgaard-moller25a.pdf}, url = {https://proceedings.mlr.press/v272/hogsgaard-moller25a.html}, abstract = {Recent advances in the binary classification setting by Hanneke (2016) 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.} }
Endnote
%0 Conference Paper %T Efficient Optimal PAC Learning %A Mikael Høgsgaard Møller %B Proceedings of The 36th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Gautam Kamath %E Po-Ling Loh %F pmlr-v272-hogsgaard-moller25a %I PMLR %P 578--580 %U https://proceedings.mlr.press/v272/hogsgaard-moller25a.html %V 272 %X Recent advances in the binary classification setting by Hanneke (2016) 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.
APA
Høgsgaard Møller, M.. (2025). Efficient Optimal PAC Learning. Proceedings of The 36th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 272:578-580 Available from https://proceedings.mlr.press/v272/hogsgaard-moller25a.html.

Related Material