The Probably Approximately Correct Learning Model in Computational Learning Theory

Rocco A. Servedio · 2025

Read The Probably Approximately Correct Learning Model in Computational Learning Theory by Rocco A. Servedio (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-2511-08791.txt.

Introduction

Rocco Servedio surveys what is known about learning Boolean functions in the Probably Approximately Correct model. Leslie Valiant introduced that framework to define what it means for a machine to learn from examples with high confidence and low error. The survey covers the model itself and its commonly studied variants.

Boolean function classes are the classic testbeds for learning theory. They range from simple conjunctions to rich circuit families. Decades of work have mapped which of them can be learned efficiently and which resist every known algorithm. A survey like this organizes those results, the techniques behind them, and the gaps that remain. It serves researchers and graduate students who need the lay of the land in computational learning theory before pushing on open problems.

Catalog record

CREATORRocco A. Servedio
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-08791

Browse the full library · About the Tower of Babel