Timezone: »
We present a transductive learning algorithm that takes as input training examples from a distribution P and arbitrary (unlabeled) test examples, possibly chosen by an adversary. This is unlike prior work that assumes that test examples are small perturbations of P. Our algorithm outputs a selective classifier, which abstains from predicting on some examples. By considering selective transductive learning, we give the first nontrivial guarantees for learning classes of bounded VC dimension with arbitrary train and test distributions—no prior guarantees were known even for simple classes of functions such as intervals on the line. In particular, for any function in a class C of bounded VC dimension, we guarantee a low test error rate and a low rejection rate with respect to P. Our algorithm is efficient given an Empirical Risk Minimizer (ERM) for C. Our guarantees hold even for test examples chosen by an unbounded whitebox adversary. We also give guarantees for generalization, agnostic, and unsupervised settings.
Author Information
Shafi Goldwasser (The Simons Institute for the Theory of Computing)
Shafi Goldwasser is Director of the Simons Institute for the Theory of Computing, and Professor of Electrical Engineering and Computer Science at the University of California Berkeley. Goldwasser is also Professor of Electrical Engineering and Computer Science at MIT and Professor of Computer Science and Applied Mathematics at the Weizmann Institute of Science, Israel. Goldwasser holds a B.S. Applied Mathematics from Carnegie Mellon University (1979), and M.S. and Ph.D. in Computer Science from the University of California Berkeley (1984). Goldwasser's pioneering contributions include the introduction of probabilistic encryption, interactive zero knowledge protocols, elliptic curve primality testings, hardness of approximation proofs for combinatorial problems, and combinatorial property testing. Goldwasser was the recipient of the ACM Turing Award in 2012, the Gödel Prize in 1993 and in 2001, the ACM Grace Murray Hopper Award in 1996, the RSA Award in Mathematics in 1998, the ACM Athena Award for Women in Computer Science in 2008, the Benjamin Franklin Medal in 2010, the IEEE Emanuel R. Piore Award in 2011, the Simons Foundation Investigator Award in 2012, and the BBVA Foundation Frontiers of Knowledge Award in 2018. Goldwasser is a member of the NAS, NAE, AAAS, the Russian Academy of Science, the Israeli Academy of Science, and the London Royal Mathematical Society. Goldwasser holds honorary degrees from Ben Gurion University, Bar Ilan University, Carnegie Mellon University, Haifa University, University of Oxford, and the University of Waterloo, and has received the UC Berkeley Distinguished Alumnus Award and the Barnard College Medal of Distinction.
Adam Tauman Kalai (Microsoft Research)
Yael Kalai (Micr)
Omar Montasser (Toyota Technological Institute at Chicago)
Related Events (a corresponding poster, oral, or spotlight)

2020 Poster: Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples »
Thu. Dec 10th 05:00  07:00 PM Room Poster Session 5 #1444
More from the Same Authors

2022 : A Theory of Unsupervised Translation for Understanding Animal Communication »
Shafi Goldwasser · David Gruber · Adam Tauman Kalai · Orr Paradise 
2022 : Certifiable Robustness Against Patch Attacks Using an ERM Oracle »
Kevin Stangl · Avrim Blum · Omar Montasser · Saba Ahmadi 
2023 : SelfTaught Optimizer (STOP): Recursively SelfImproving Code Generation »
Eric Zelikman · Eliana Lorch · Lester Mackey · Adam Tauman Kalai 
2023 : Do Language Models Know When They're Hallucinating References? »
Ayush Agrawal · Mirac Suzgun · Lester Mackey · Adam Tauman Kalai 
2023 : Testing Language Model Agents Safely in the Wild »
Silen Naihin · David Atkinson · Marc Green · Merwane Hamadi · Craig Swift · Douglas Schonholtz · Adam Tauman Kalai · David Bau 
2023 Poster: Partial Matrix Completion »
Elad Hazan · Adam Tauman Kalai · Varun Kanade · Clara Mohri · Y. Jennifer Sun 
2023 Poster: Strategic Classification under Unknown Personalized Manipulation »
Han Shao · Avrim Blum · Omar Montasser 
2023 Poster: A Theory of Unsupervised Translation Motivated by Understanding Animal Communication »
Shafi Goldwasser · David Gruber · Adam Tauman Kalai · Orr Paradise 
2022 Panel: Panel 1A4: Hardness of NoiseFree… & Adversarially Robust Learning:… »
Aravind Gollakota · Omar Montasser 
2022 Poster: Boosting Barely Robust Learners: A New Perspective on Adversarial Robustness »
Avrim Blum · Omar Montasser · Greg Shakhnarovich · Hongyang Zhang 
2022 Poster: Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization »
Omar Montasser · Steve Hanneke · Nati Srebro 
2022 Poster: A Theory of PAC Learnability under Transformation Invariances »
Han Shao · Omar Montasser · Avrim Blum 
2020 Poster: Reducing Adversarially Robust Learning to NonRobust PAC Learning »
Omar Montasser · Steve Hanneke · Nati Srebro 
2020 Invited Talk: Robustness, Verification, Privacy: Addressing Machine Learning Adversaries »
Shafi Goldwasser 
2018 : Invited talk 2: Machine Learning and Cryptography: Challenges and Opportunities »
Shafi Goldwasser