TY - GEN

T1 - Agnostic learning by refuting

AU - Kothari, Pravesh K.

AU - Livni, Roi

N1 - Publisher Copyright:
© Pravesh K. Kothari and Roi Livni.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - The sample complexity of learning a Boolean-valued 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 example-label 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 co-authors [6, 8, 10] 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 [25] discovered a similar relationship between refutation and PAC-learning in the realizable (i.e. noiseless) case.

AB - The sample complexity of learning a Boolean-valued 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 example-label 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 co-authors [6, 8, 10] 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 [25] discovered a similar relationship between refutation and PAC-learning in the realizable (i.e. noiseless) case.

KW - Computational learning

KW - Learning theory

KW - Rademacher complexity

UR - http://www.scopus.com/inward/record.url?scp=85041640880&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041640880&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2018.55

DO - 10.4230/LIPIcs.ITCS.2018.55

M3 - Conference contribution

AN - SCOPUS:85041640880

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 9th Innovations in Theoretical Computer Science, ITCS 2018

A2 - Karlin, Anna R.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 9th Innovations in Theoretical Computer Science, ITCS 2018

Y2 - 11 January 2018 through 14 January 2018

ER -