# Online Learning and Disambiguations of Partial Concept Classes

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 14 references that are in the map.
- First posted on arXiv 30 Mar 2023.

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

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)

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

- [List Sample Compression and Uniform Convergence](https://mlsanity.com/paper/2403.10889/) (2024)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Optimal Unambiguous DNFs and Alon-Saks-Seymour](https://mlsanity.com/paper/2608.02533/) (2026)

## Abstract (arXiv)

In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central questions studied in their work is whether the learnability of a partial concept class is always inherited from the learnability of some ``extension'' of it to a total concept class. They showed this is not the case for PAC learning but left the problem open for the stronger notion of online learnability. We resolve this problem by constructing a class of partial concepts that is online learnable, but no extension of it to a class of total concepts is online learnable (or even PAC learnable).