%ACheung, Tsun-Ming%AHatami, Hamed%AHatami, Pooya%AHosseini, Kaave%AEtessami, Kousha Ed.%AFeige, Uriel Ed.%APuppis, Gabriele Ed.%D2023%ISchloss Dagstuhl – Leibniz-Zentrum für Informatik
%KOnline learning; Littlestone dimension; VC dimension; partial concept class; clique vs independent set; Alon-Saks-Seymour conjecture; Standard Optimal Algorithm; PAC learning; Theory of computation → Online learning theory
%MOSTI ID: 10488557
%PMedium: X
%TOnline Learning and Disambiguations of Partial
Concept Classes
%XIn 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).