Learning Partial Concept Classes and Universal Rates Under Massart Noise

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.

Machine learning theory studies when and how a learning algorithm can make accurate predictions from data. Classical learning theory often analyzes two extreme cases. In the first, called the realizable setting, the data are assumed to follow some perfect rule contained in the learner's hypothesis class. In the second, called the agnostic setting, no such assumption is made, and the data may be noisy in an arbitrary way. This paper studies an important intermediate case, known as Massart noise, where the labels may be noisy but the noise is bounded: at every input point, the correct label is still more likely than the incorrect one. We investigate Massart noise in two modern extensions of classical learning theory. The first is the study of partial concept classes, where a hypothesis may be undefined on some inputs. This framework is useful for modeling situations in which a rule is meaningful only on part of the domain, or where structural assumptions depend on the data itself. The second is universal learning, which asks for the best possible learning rate under each fixed data distribution, rather than only the worst-case rate over all distributions. Our main contribution is to show that a transductive learning method, which makes predictions using both labeled training examples and unlabeled test points, can be analyzed more sharply under Massart noise. Using this analysis, we obtain improved sample-complexity bounds for learning partial concept classes. We also complete the classification of possible universal learning rates under Massart noise, showing which rates can occur depending on the combinatorial structure of the hypothesis class. Overall, the paper improves our theoretical understanding of learning under structured label noise. It helps clarify when fast learning is possible, how partial information affects learnability, and how the behavior of Massart-noise learning relates to the better-understood realizable and agnostic settings.