Adaptive Learning with Robust Generalization Guarantees
Rachel Cummings Thanks: Dept. of Computing and Mathematical Sciences, California Institute of Technology. Supported in part by NSF grant 1254169, US-Israel Binational Science Foundation grant 2012348, and a Simons Graduate Fellowship. Katrina Ligett Thanks: Dept. of Computing and Mathematical Sciences, California Institute of Technology and Benin School of Computer Science and Engineering, Hebrew University of Jerusalem. 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. Kobbi Nissim Thanks: Dept. of Computer Science, Ben-Gurion University and Center for Research in Computation and Society, Harvard University. Supported by grants from the Sloan Foundation, a Simons Investigator grant to Salil Vadhan, and NSF grant CNS-1237235. Aaron Roth Thanks: Dept. of Computer and Information Sciences, University of Pennsylvania. 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. Zhiwei Steven Wu Thanks: Dept. of Computer and Information Sciences, University of Pennsylvania.
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 [9], 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.
原文 arXiv:1602.07726;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1602.07726v2