On Learnability and Disambiguation of Multiclass Partial Concept Classes

Jingyuan Xu; Xin Zou; Xiuwen Gong; Weiwei Liu

ICML 2026poster0 citations

On Learnability and Disambiguation of Multiclass Partial Concept Classes

Jingyuan Xu, Xin Zou, Xiuwen Gong, Weiwei Liu

Abstract

We study the Probably Approximately Correct (PAC) learnability of partial concept classes in the multiclass setting, where the label space can be infinite. While the Natarajan dimension characterizes learnability for finite label spaces, we show it fails when the label space is unbounded. Instead, we prove that the Daniely-Shalev (DS) dimension provides a characterization of learnability for partial concept classes in the general multiclass setting. Furthermore, our analysis reveals a surprising phenomenon we call the ``Disambiguation Paradox'': disambiguation schemes with simple label space can destroy learnability, while richer labeling may preserves it. We further characterize how the number and structure of disambiguation labels control the induced DS dimension, yielding a trade-off between label complexity and sample complexity.

Theory

BibTeX

@inproceedings{
xu2026on,
title={On Learnability and Disambiguation of Multiclass Partial Concept Classes},
author={Jingyuan Xu and Xin Zou and Xiuwen Gong and Weiwei Liu},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=LbYeOvDo3o}
}