2026-07-22T13:39:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18094 2024-03-06T11:01:00Z ddc:004 open_access

Online Learning and Disambiguations of Partial Concept Classes Cheung, Tsun-Ming Hatami, Hamed Hatami, Pooya Hosseini, Kaave Online learning Littlestone dimension VC dimension partial concept class clique vs independent set Alon-Saks-Seymour conjecture Standard Optimal Algorithm PAC learning 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tsun-Ming Cheung and Hamed Hatami and Pooya Hatami and Kaave Hosseini 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.42 urn:nbn:de:0030-drops-180946 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.42 eng https://creativecommons.org/licenses/by/4.0/legalcode