# A Characterization of List Learnability

Source: [A Characterization of List Learnability](<https://www.sota2.com/research/paper/68fa6ee81e209131cea42ccb>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T01:09:40.360Z

Authors: Moses Charikar, Chirag Pabbaraju

Published: 2022-11-07T21:28:05.000Z

## Abstract

A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz. In this work we consider list PAC learning where the goal is to output a list of $k$ predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to $k$-list learn a hypothesis class? We completely characterize $k$-list learnability in terms of a generalization of DS dimension that we call the $k$-DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is $k$-list learnable if and only if the $k$-DS dimension is finite.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [List Learning on List Learning Agnostic](<https://www.sota2.com/research/sota/list-learning-on-list-learning-agnostic.md>): List Learning; List Learning Agnostic; Sample Complexity: 6.

- [List Learning on List Learning (realizable)](<https://www.sota2.com/research/sota/list-learning-on-list-learning-realizable.md>): List Learning; List Learning (realizable); Sample Complexity: 6.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2211.04956>)

[PDF](<https://arxiv.org/pdf/2211.04956.pdf>)