On the Computability of Multiclass PAC Learning
Pascale Gourdeau, Tosca Lechner, Ruth Urner · 2025
Read On the Computability of Multiclass PAC Learning by Pascale Gourdeau, Tosca Lechner, Ruth Urner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-06089.txt.
Description
Pascale Gourdeau, Tosca Lechner, and Ruth Urner study when multiclass learning is computable within the PAC framework. In computable PAC learning, both the learner and the functions it outputs must be computable objects. The authors focus on finite label spaces, the case most used in practice.
They propose a computable version of the Natarajan dimension and show it characterizes computable learnability in that setting. A broader meta result follows for a family of dimensions built from distinguishers, embeddings of the label space defined in classic work. Each distinguisher yields a computable dimension that characterizes learnability. The DS dimension, which handles infinite label spaces, proves not expressible as a distinguisher even for finite labels.
Catalog record
| CREATOR | Pascale Gourdeau, Tosca Lechner, Ruth Urner |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-06089