Refining the Sample Complexity of Comparative Learning

Sajad Ashkezari, Ruth Urner
Proceedings of The 36th International Conference on Algorithmic Learning Theory, PMLR 272:67-88, 2025.

Abstract

Comparative learning, a recently introduced variation of the PAC (Probably Approximately Correct) framework, interpolates between the two standard extreme settings of realizable and agnostic PAC learning. In comparative learning the labeling is assumed to be from one hypothesis class (the source class) while the learner’s performance is to be measured against another hypothesis class (the benchmark class). This setup allows for incorporating more specific prior knowledge into PAC type learning bounds, which are known to be otherwise overly pessimistic. It also naturally represents model distillation tasks, where a predictor with specific requirements (such as being bounded in size or being interpretable) is trained on the labels from another model. A first sample complexity analysis of comparative learning established upper and lower bounds for general comparative learning. In this work, we propose a more fine grained view on this setting, distinguishing between proper learning and general (improper) learning. We derive novel upper and lower sample complexity bounds for both settings. In particular, we identify conditions for each of the regimes, and thereby exhibit how the rate depends on the relatedness of the two classes in perhaps unexpected ways.

Cite this Paper

BibTeX
@InProceedings{pmlr-v272-ashkezari25a, title = {Refining the Sample Complexity of Comparative Learning}, author = {Ashkezari, Sajad and Urner, Ruth}, booktitle = {Proceedings of The 36th International Conference on Algorithmic Learning Theory}, pages = {67--88}, 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/ashkezari25a/ashkezari25a.pdf}, url = {https://proceedings.mlr.press/v272/ashkezari25a.html}, abstract = {Comparative learning, a recently introduced variation of the PAC (Probably Approximately Correct) framework, interpolates between the two standard extreme settings of realizable and agnostic PAC learning. In comparative learning the labeling is assumed to be from one hypothesis class (the source class) while the learner’s performance is to be measured against another hypothesis class (the benchmark class). This setup allows for incorporating more specific prior knowledge into PAC type learning bounds, which are known to be otherwise overly pessimistic. It also naturally represents model distillation tasks, where a predictor with specific requirements (such as being bounded in size or being interpretable) is trained on the labels from another model. A first sample complexity analysis of comparative learning established upper and lower bounds for general comparative learning. In this work, we propose a more fine grained view on this setting, distinguishing between proper learning and general (improper) learning. We derive novel upper and lower sample complexity bounds for both settings. In particular, we identify conditions for each of the regimes, and thereby exhibit how the rate depends on the relatedness of the two classes in perhaps unexpected ways.} }
Endnote
%0 Conference Paper %T Refining the Sample Complexity of Comparative Learning %A Sajad Ashkezari %A Ruth Urner %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-ashkezari25a %I PMLR %P 67--88 %U https://proceedings.mlr.press/v272/ashkezari25a.html %V 272 %X Comparative learning, a recently introduced variation of the PAC (Probably Approximately Correct) framework, interpolates between the two standard extreme settings of realizable and agnostic PAC learning. In comparative learning the labeling is assumed to be from one hypothesis class (the source class) while the learner’s performance is to be measured against another hypothesis class (the benchmark class). This setup allows for incorporating more specific prior knowledge into PAC type learning bounds, which are known to be otherwise overly pessimistic. It also naturally represents model distillation tasks, where a predictor with specific requirements (such as being bounded in size or being interpretable) is trained on the labels from another model. A first sample complexity analysis of comparative learning established upper and lower bounds for general comparative learning. In this work, we propose a more fine grained view on this setting, distinguishing between proper learning and general (improper) learning. We derive novel upper and lower sample complexity bounds for both settings. In particular, we identify conditions for each of the regimes, and thereby exhibit how the rate depends on the relatedness of the two classes in perhaps unexpected ways.
APA
Ashkezari, S. & Urner, R.. (2025). Refining the Sample Complexity of Comparative Learning. Proceedings of The 36th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 272:67-88 Available from https://proceedings.mlr.press/v272/ashkezari25a.html.

Related Material