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

CREATORPascale Gourdeau, Tosca Lechner, Ruth Urner
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-06089

Browse the full library · About the Tower of Babel