CaltechAUTHORS
  A Caltech Library Service

Adaptive Learning with Robust Generalization Guarantees

Cummings, Rachel and Ligett, Katrina and Nissim, Kobbi and Roth, Aaron and Wu, Zhiwei Steven (2016) Adaptive Learning with Robust Generalization Guarantees. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20190627-154059380

[img] PDF - Submitted Version
See Usage Policy.

268Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190627-154059380

Abstract

The traditional notion of generalization---i.e., learning a hypothesis whose empirical error is close to its true error---is surprisingly brittle. As has recently been noted in [DFH+15b], even if several algorithms have this guarantee in isolation, the guarantee need not hold if the algorithms are composed adaptively. In this paper, we study three notions of generalization---increasing in strength---that are robust to postprocessing and amenable to adaptive composition, and examine the relationships between them. We call the weakest such notion Robust Generalization. A second, intermediate, notion is the stability guarantee known as differential privacy. The strongest guarantee we consider we call Perfect Generalization. We prove that every hypothesis class that is PAC learnable is also PAC learnable in a robustly generalizing fashion, with almost the same sample complexity. It was previously known that differentially private algorithms satisfy robust generalization. In this paper, we show that robust generalization is a strictly weaker concept, and that there is a learning task that can be carried out subject to robust generalization guarantees, yet cannot be carried out subject to differential privacy. We also show that perfect generalization is a strictly stronger guarantee than differential privacy, but that, nevertheless, many learning tasks can be carried out subject to the guarantees of perfect generalization.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1602.07726arXivDiscussion Paper
ORCID:
AuthorORCID
Ligett, Katrina0000-0003-2780-6656
Additional Information:Supported in part by NSF grant 1254169, US-Israel Binational Science Foundation grant 2012348, and a Simons Graduate Fellowship. Supported in part by NSF grants 1254169 and 1518941, US-Israel Binational Science Foundation Grant 2012348, the Charles Lee Powell Foundation, a Google Faculty Research Award, an Okawa Foundation Research Grant, a subcontract through the DARPA Brandeis project, a grant from the HUJI Cyber Security Research Center, and a startup grant from Hebrew University’s School of Computer Science. Part of this work was completed during a stay at the Simons Institute for the Theory of Computing at Berkeley. Supported by grants from the Sloan Foundation, a Simons Investigator grant to Salil Vadhan, and NSF grant CNS-1237235. Supported in part by an NSF CAREER award, NSF grant CNS-1513694, a subcontract through the DARPA Brandeis project, and a grant from the Sloan Foundation. We thank Adam Smith and Raef Bassily for helpful comments about adaptive composition of perfectly generalizing mechanisms, and for pointing out an error in an earlier version of this paper. We thank Shay Moran for telling us about variable-length compression schemes and sharing with us his manuscript [DMY16]. We thank our anonymous reviewers for numerous helpful comments.
Funders:
Funding AgencyGrant Number
NSFCNS-1254169
Binational Science Foundation (USA-Israel)2012348
Simons FoundationUNSPECIFIED
NSFCNS-1518941
Charles Lee Powell FoundationUNSPECIFIED
Google Faculty Research AwardUNSPECIFIED
Okawa FoundationUNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Hebrew University of JerusalemUNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
NSFCNS-1237235
NSFCNS-1513694
Record Number:CaltechAUTHORS:20190627-154059380
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20190627-154059380
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96802
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:27 Jun 2019 22:48
Last Modified:27 Jun 2019 22:48

Repository Staff Only: item control page