License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.72
URN: urn:nbn:de:0030-drops-175752
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17575/
Hu, Lunjia ;
Peale, Charlotte
Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
Abstract
In many learning theory problems, a central role is played by a hypothesis class: we might assume that the data is labeled according to a hypothesis in the class (usually referred to as the realizable setting), or we might evaluate the learned model by comparing it with the best hypothesis in the class (the agnostic setting). Taking a step beyond these classic setups that involve only a single hypothesis class, we study a variety of problems that involve two hypothesis classes simultaneously.
We introduce comparative learning as a combination of the realizable and agnostic settings in PAC learning: given two binary hypothesis classes S and B, we assume that the data is labeled according to a hypothesis in the source class S and require the learned model to achieve an accuracy comparable to the best hypothesis in the benchmark class B. Even when both S and B have infinite VC dimensions, comparative learning can still have a small sample complexity. We show that the sample complexity of comparative learning is characterized by the mutual VC dimension VC(S,B) which we define to be the maximum size of a subset shattered by both S and B. We also show a similar result in the online setting, where we give a regret characterization in terms of the analogous mutual Littlestone dimension Ldim(S,B). These results also hold for partial hypotheses.
We additionally show that the insights necessary to characterize the sample complexity of comparative learning can be applied to other tasks involving two hypothesis classes. In particular, we characterize the sample complexity of realizable multiaccuracy and multicalibration using the mutual fat-shattering dimension, an analogue of the mutual VC dimension for real-valued hypotheses. This not only solves an open problem proposed by Hu, Peale, Reingold (2022), but also leads to independently interesting results extending classic ones about regression, boosting, and covering number to our two-hypothesis-class setting.
BibTeX - Entry
@InProceedings{hu_et_al:LIPIcs.ITCS.2023.72,
author = {Hu, Lunjia and Peale, Charlotte},
title = {{Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {72:1--72:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17575},
URN = {urn:nbn:de:0030-drops-175752},
doi = {10.4230/LIPIcs.ITCS.2023.72},
annote = {Keywords: Comparative learning, mutual VC dimension, realizable multiaccuracy and multicalibration, sample complexity}
}
|
Keywords: |
|
Comparative learning, mutual VC dimension, realizable multiaccuracy and multicalibration, sample complexity |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
