Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2016 | Published + Submitted
Journal Article Open

Adaptive Learning with Robust Generalization Guarantees

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 [Dwork et al. 2015], 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 \emphrobust to postprocessing and amenable to adaptive composition, and examine the relationships between them. We call the weakest such notion \emphRobust Generalization. A second, intermediate, notion is the stability guarantee known as \emphdifferential privacy. The strongest guarantee we consider we call \emphPerfect 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.

Additional Information

© 2016 R. Cummings, K. Ligett, K. Nissim, A. Roth & Z.S. Wu. We thank Adam Smith and Raef Bassily for helpful comments about adaptive composition of perfectly generalizing mechanisms and 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 David et al. (2016). We thank our anonymous reviewers for numerous helpful comments. The first author is supported in part by NSF grant 1254169, US-Israel Binational Science Foundation grant 2012348, and a Simons Graduate Fellowship. The second author is 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 when the second author was visiting the Simons Institute for the Theory of Computing at Berkeley. The third author is supported by grants from the Sloan Foundation, a Simons Investigator grant to Salil Vadhan, and NSF grant CNS-1237235. The fourth author is 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.

Attached Files

Published - cummings16.pdf

Submitted - 1602.07726.pdf

Files

1602.07726.pdf
Files (634.8 kB)
Name Size Download all
md5:46f6cd641506a1556620e2d65c6aa7a6
274.7 kB Preview Download
md5:010bbbb69795e2dd475223f8621896f0
360.1 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 20, 2023