A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity

Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of testable learning, where the goal is to replace hard-to-verify distributional assumptions (such as Gaussianity) with efficiently testable ones and to require that the learner succeed whenever the unknown distribution passes the corresponding test. In this model, they gave an efficient algorithm for learning halfspaces under testable assumptions that are provably satisfied by Gaussians. In this paper we give a powerful new approach for developing algorithms for testable learning using tools from moment matching and metric distances in probability. We obtain efficient testable learners for any concept class that admits low-degree sandwiching polynomials, capturing most important examples for which we have ordinary agnostic learners. We recover the results of Rubinfeld and Vasilyan as a corollary of our techniques while achieving improved, near-optimal sample complexity bounds for a broad range of concept classes and distributions. Surprisingly, we show that the information-theoretic sample complexity of testable learning is tightly characterized by the Rademacher complexity of the concept class, one of the most well-studied measures in statistical learning theory. In particular, uniform convergence is necessary and sufficient for testable learning. This leads to a fundamental separation from (ordinary) distribution-specific agnostic learning, where uniform convergence is sufficient but not necessary.

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages1657-1670
Number of pages14
ISBN (Electronic)9781450399135
DOIs
StatePublished - Jun 2 2023
Externally publishedYes
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period6/20/236/23/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • generalization
  • moment matching
  • PAC learning
  • Rademacher complexity
  • sandwiching polynomials

Fingerprint

Dive into the research topics of 'A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity'. Together they form a unique fingerprint.

Cite this