Optimal Agnostic PAC Learning of Partial Binary Classes by Soft Selection

This manuscript studies agnostic PAC learning of partial binary concept classes, with undefined predictions counted as errors. Under finite-trace measurability and finite partial VC dimension, it presents a deterministic improper learner with a high-probability excess-risk bound of order sqrt((d + log(1/delta))/n), measured against the empirical-limit comparator. The construction uses soft selections of partial traces and existing disambiguation, martingale, and threshold-validation techniques. Dimension zero is treated separately. The result is information-theoretic and does not assert an efficient implementation, comparator-dependent fast rates, or a multiclass extension.