Adaptive Learning with Robust Generalization Guarantees
Rachel Cummings 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 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 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 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 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.
中文速览
机器学习中"泛化"的传统定义存在一个隐患：算法在单独使用时能保证训练误差接近真实误差，但一旦多个算法被自适应地组合使用（比如科学家根据已有结果决定下一步分析方向），这个保证就会失效，导致过拟合或虚假发现。为此，这篇论文系统研究了三种比传统泛化更强、且对后处理和自适应组合都具有鲁棒性的泛化概念：最弱的"鲁棒泛化（Robust Generalization）"、居中的差分隐私（Differential Privacy）、以及最强的"完美泛化（Perfect Generalization）"，并厘清了三者之间的严格强弱关系。核心结论是：任何可PAC学习的假设类都可以在鲁棒泛化保证下以几乎相同的样本复杂度被学习，而差分隐私比鲁棒泛化严格更强——存在可以在鲁棒泛化下解决、却无法由差分隐私算法解决的学习任务（如实数轴上的阈值函数学习）；与此同时，完美泛化比差分隐私严格更强，但许多学习任务仍可在完美泛化保证下完成。这项工作为自适应数据分析提供了理论基础，指出压缩方案（compression schemes）是实现鲁棒泛化的第三条路径，填补了该领域的重要空白。
原文 arXiv:1602.07726;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1602.07726v2