# A Characterization of List Regression

arXiv: https://arxiv.org/abs/2409.19218 · HTML: https://mlsanity.com/paper/2409.19218/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 28 Sep 2024.

## Builds on (most cited first, 15 of 15)

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions](https://mlsanity.com/paper/2304.11059/) (2023)
- [Multiclass Boosting: Simple and Intuitive Weak Learning Criteria](https://mlsanity.com/paper/2307.00642/) (2023)
- [On statistical learning via the lens of compression](https://mlsanity.com/paper/1610.03592/) (2016)
- [List Sample Compression and Uniform Convergence](https://mlsanity.com/paper/2403.10889/) (2024)
- [Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension](https://mlsanity.com/paper/1412.6265/) (2014)
- [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024)

## Built on by (most cited first, 6 of 6)

- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [A Characterization of List Language Identification in the Limit](https://mlsanity.com/paper/2511.04103/) (2025)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)
- [PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting](https://mlsanity.com/paper/2605.25678/) (2026)

## Abstract (arXiv)

There has been a recent interest in understanding and characterizing the sample complexity of list learning tasks, where the learning algorithm is allowed to make a short list of k predictions, and we simply require one of the predictions to be correct. This includes recent works characterizing the PAC sample complexity of standard list classification and online list classification. Adding to this theme, in this work, we provide a complete characterization of list PAC regression. We propose two combinatorial dimensions, namely the k-OIG dimension and the k-fat-shattering dimension, and show that they characterize realizable and agnostic k-list regression respectively. These quantities generalize known dimensions for standard regression. Our work thus extends existing list learning characterizations from classification to regression.