Efficient Optimal PAC Learning

blaba Mikael Møller Høgsgaard Aarhus University [email protected] · 2025

Read Efficient Optimal PAC Learning by blaba Mikael Møller Høgsgaard Aarhus University [email protected] (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-03620.txt.

Introduction

Mikael Møller Høgsgaard wrote this 2025 theory paper on PAC learning, a frame for asking how well a program can learn a rule from examples. Recent work by Hanneke and by Larsen produced learners with the best known sample use. Both, though, lean on a step that picks the rule with the least error on the training data, and their cost tracks the cost of that step.

Høgsgaard asks whether that link to the error-picking step can be loosened. He shows that an optimal learner exists which trades the cost off in a different way. Readers in machine learning theory get a fresh angle on what makes such learners costly to run, and on where gains in speed might come from.

Catalog record

CREATORblaba Mikael Møller Høgsgaard Aarhus University [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE190 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel