Abstract
The sample complexity of learning a Booleanvalued function class is precisely characterized by its Rademacher complexity. This has little bearing, however, on the sample complexity of efficient agnostic learning.
We introduce refutation complexity, a natural computational analog of Rademacher complexity of a Boolean concept class and show that it exactly characterizes the sample complexity of efficient agnostic learning. Informally, refutation complexity of a class C is the minimum number of examplelabel pairs required to efficiently distinguish between the case that the labels correlate with the evaluation of some member of C (structure) and the case where the labels are i.i.d. Rademacher random variables (noise). The easy direction of this relationship was implicitly used in the recent framework for improper PAC learning lower bounds of Daniely and coauthors via connections to the hardness of refuting random constraint satisfaction problems. Our work can be seen as making the relationship between agnostic learning and refutation implicit in their work into an explicit equivalence.
In a recent, independent work, Salil Vadhan discovered a similar relationship between refutation and PAClearning in the realizable (i.e. noiseless) case.
BibTeX  Entry
@InProceedings{kothari_et_al:LIPIcs:2018:8348,
author = {Pravesh K. Kothari and Roi Livni},
title = {{Improper Learning by Refuting}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {55:155:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8348},
URN = {urn:nbn:de:0030drops83488},
doi = {10.4230/LIPIcs.ITCS.2018.55},
annote = {Keywords: learning thoery, computation learning}
}
Keywords: 

learning thoery, computation learning 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018) 
Issue Date: 

2018 
Date of publication: 

05.01.2018 