Online Learning and Disambiguations of Partial Concept Classes

Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami, Kaave Hosseini
3/30/2023
cs.LGcs.CC

No confident code implementation found for this paper.

Abstract

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).

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

A Theory of Optimistically Universal Online Learnability for General Concept Classes

81% match2025

Multiclass Online Learning and Uniform Convergence

79% match2023

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem

78% match2024

Private PAC Learning May be Harder than Online Learning

78% match2024

On Computable Online Learning

77% match2023

A Combinatorial Characterization of Supervised Online Learnability

75% match2023

Cite this paper

@article{cheung2023online,
  title  = {Online Learning and Disambiguations of Partial Concept Classes},
  author = {Tsun-Ming Cheung and Hamed Hatami and Pooya Hatami and Kaave Hosseini},
  year   = {2023},
  eprint = {2303.17578},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2303.17578v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2303.17578.svg)](https://codeofpaper.com/paper/2303.17578)

Discussion