Learning Partial Concept Classes and Universal Rates Under Massart Noise

Ariel Avital, Klim Efremenko, Steve Hanneke
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:4385-4414, 2026.

Abstract

The Massart noise condition is a central model in Probably Approximately Correct (PAC) learning theory. Its importance lies in it being an interpolation condition between realizable and the agnostic settings, under which one can attain faster rates than in the latter, and, under strict conditions, recover the rates of the former. Despite its importance, the Massart condition has not yet been fully explored in emerging extensions of statistical learning theory beyond the classical PAC framework. In this work, we present two such extensions. First, we revisit the transductive empirical risk minimization (TERM) algorithm of (Hanneke & Moran, 2026), and derive sharper excess error bounds under Massart noise using offset Rademacher techniques and local metric entropy introduced by (Zhivotovskiy & Hanneke, 2018). We then leverage this analysis to obtain new sample complexity bounds for PAC learning with partial concept classes and complete the characterization of universal rates under Massart noise.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-avital26a, title = {Learning Partial Concept Classes and Universal Rates Under Massart Noise}, author = {Avital, Ariel and Efremenko, Klim and Hanneke, Steve}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {4385--4414}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/avital26a/avital26a.pdf}, url = {https://proceedings.mlr.press/v306/avital26a.html}, abstract = {The Massart noise condition is a central model in Probably Approximately Correct (PAC) learning theory. Its importance lies in it being an interpolation condition between realizable and the agnostic settings, under which one can attain faster rates than in the latter, and, under strict conditions, recover the rates of the former. Despite its importance, the Massart condition has not yet been fully explored in emerging extensions of statistical learning theory beyond the classical PAC framework. In this work, we present two such extensions. First, we revisit the transductive empirical risk minimization (TERM) algorithm of (Hanneke & Moran, 2026), and derive sharper excess error bounds under Massart noise using offset Rademacher techniques and local metric entropy introduced by (Zhivotovskiy & Hanneke, 2018). We then leverage this analysis to obtain new sample complexity bounds for PAC learning with partial concept classes and complete the characterization of universal rates under Massart noise.} }
Endnote
%0 Conference Paper %T Learning Partial Concept Classes and Universal Rates Under Massart Noise %A Ariel Avital %A Klim Efremenko %A Steve Hanneke %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-avital26a %I PMLR %P 4385--4414 %U https://proceedings.mlr.press/v306/avital26a.html %V 306 %X The Massart noise condition is a central model in Probably Approximately Correct (PAC) learning theory. Its importance lies in it being an interpolation condition between realizable and the agnostic settings, under which one can attain faster rates than in the latter, and, under strict conditions, recover the rates of the former. Despite its importance, the Massart condition has not yet been fully explored in emerging extensions of statistical learning theory beyond the classical PAC framework. In this work, we present two such extensions. First, we revisit the transductive empirical risk minimization (TERM) algorithm of (Hanneke & Moran, 2026), and derive sharper excess error bounds under Massart noise using offset Rademacher techniques and local metric entropy introduced by (Zhivotovskiy & Hanneke, 2018). We then leverage this analysis to obtain new sample complexity bounds for PAC learning with partial concept classes and complete the characterization of universal rates under Massart noise.
APA
Avital, A., Efremenko, K. & Hanneke, S.. (2026). Learning Partial Concept Classes and Universal Rates Under Massart Noise. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:4385-4414 Available from https://proceedings.mlr.press/v306/avital26a.html.

Related Material