From learnable objects to learnable random objects

Aaron Anderson University of Pennsylvania, Michael Benedikt University of Oxford · 2025

Read From learnable objects to learnable random objects by Aaron Anderson University of Pennsylvania, Michael Benedikt University of Oxford (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-2504-00847.txt.

Description

Aaron Anderson and Michael Benedikt studied in 2025 how learning a base family of functions relates to learning averages of those functions over random data. For example, if a family indexed by one input can be learned, can the family of its expected values also be learned? They look at two settings: random examples and examples chosen by an opponent.

For the case where labels may be noisy, they give sharper bounds on how many examples are needed, stated through size measures of the base family. Links to a model theory trick for adding randomness are drawn. Counterexamples are also given for the clean-label case, in both settings, showing where the transfer fails.

Catalog record

CREATORAaron Anderson University of Pennsylvania, Michael Benedikt University of Oxford
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE161 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-00847

Browse the full library · About the Tower of Babel