Timezone: »
To assess generalization, machine learning scientists typically either (i) bound the generalization gap and then (after training) plug in the empirical risk to obtain a bound on the true risk; or (ii) validate empirically on holdout data. However, (i) typically yields vacuous guarantees for overparameterized models; and (ii) shrinks the training set and its guarantee erodes with each re-use of the holdout set. In this paper, we leverage unlabeled data to produce generalization bounds. After augmenting our (labeled) training set with randomly labeled data, we train in the standard fashion. Whenever classifiers achieve low error on the clean data but high error on the random data, our bound ensures that the true risk is low. We prove that our bound is valid for 0-1 empirical risk minimization and with linear classifiers trained by gradient descent. Our approach is especially useful in conjunction with deep learning due to the early learning phenomenon whereby networks fit true labels before noisy labels but requires one intuitive assumption. Empirically, on canonical computer vision and NLP tasks, our bound provides non-vacuous generalization guarantees that track actual performance closely. This work enables practitioners to certify generalization even when (labeled) holdout data is unavailable and provides insights into the relationship between random label noise and generalization.
Author Information
Saurabh Garg (Carnegie Mellon University)
Sivaraman Balakrishnan (CMU)
Zico Kolter (Carnegie Mellon University / Bosch Center for AI)
Zachary Lipton (Carnegie Mellon University)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: RATT: Leveraging Unlabeled Data to Guarantee Generalization »
Thu. Jul 22nd 04:00 -- 06:00 AM Room
More from the Same Authors
-
2021 : Empirical robustification of pre-trained classifiers »
Mohammad Sadegh Norouzzadeh · Wan-Yi Lin · Leonid Boytsov · Leslie Rice · Huan Zhang · Filipe Condessa · Zico Kolter -
2021 : Certified robustness against adversarial patch attacks via randomized cropping »
Wan-Yi Lin · Fatemeh Sheikholeslami · jinghao shi · Leslie Rice · Zico Kolter -
2021 : Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification »
Shiqi Wang · Huan Zhang · Kaidi Xu · Xue Lin · Suman Jana · Cho-Jui Hsieh · Zico Kolter -
2021 : Assessing Generalization of SGD via Disagreement Rates »
YiDing Jiang · Vaishnavh Nagarajan · Zico Kolter -
2021 : Do You See What I See? A Comparison of Radiologist Eye Gaze to Computer Vision Saliency Maps for Chest X-ray Classification »
Jesse Kim · Helen Zhou · Zachary Lipton -
2022 : Domain Adaptation under Open Set Label Shift »
Saurabh Garg · Sivaraman Balakrishnan · Zachary Lipton -
2022 : Unsupervised Learning under Latent Label Shift »
Pranav Mani · Manley Roberts · Saurabh Garg · Zachary Lipton -
2022 : Characterizing Datapoints via Second-Split Forgetting »
Pratyush Maini · Saurabh Garg · Zachary Lipton · Zico Kolter -
2022 : Improving adversarial robustness via joint classification and multiple explicit detection classes »
Sina Baharlouei · Fatemeh Sheikholeslami · Meisam Razaviyayn · Zico Kolter -
2022 : Agreement-on-the-Line: Predicting the Performance of Neural Networks under Distribution Shift »
Christina Baek · Yiding Jiang · aditi raghunathan · Zico Kolter -
2022 : Counterfactual Metrics for Auditing Black-Box Recommender Systems for Ethical Concerns »
Nil-Jana Akpinar · Liu Leqi · Dylan Hadfield-Menell · Zachary Lipton -
2022 : RiskyZoo: A Library for Risk-Sensitive Supervised Learning »
William Wong · Audrey Huang · Liu Leqi · Kamyar Azizzadenesheli · Zachary Lipton -
2023 Poster: Can Neural Network Memorization Be Localized? »
Pratyush Maini · Michael Mozer · Hanie Sedghi · Zachary Lipton · Zico Kolter · Chiyuan Zhang -
2023 Poster: Low-Variance Gradient Estimation in Unrolled Computation Graphs with ES-Single »
Paul Vicol · Zico Kolter · Kevin Swersky -
2023 Poster: Mimetic Initialization of Self-Attention Layers »
Asher Trockman · Zico Kolter -
2023 Poster: Domain Adaptation Under Relaxed Label Shift »
Saurabh Garg · Nick Erickson · University of California James Sharpnack · Alex Smola · Sivaraman Balakrishnan · Zachary Lipton -
2023 Poster: Abstracting Imperfect Information Away from Two-Player Zero-Sum Games »
Samuel Sokota · Ryan D'Orazio · Chun Kai Ling · David Wu · Zico Kolter · Noam Brown -
2023 Poster: Neural Network Approximations of PDEs Beyond Linearity: A Representational Perspective »
Tanya Marwah · Zachary Lipton · Jianfeng Lu · Andrej Risteski -
2023 Poster: CHiLS: Zero-Shot Image Classification with Hierarchical Label Sets »
Zachary Novack · Saurabh Garg · Julian McAuley · Zachary Lipton -
2023 Oral: Mimetic Initialization of Self-Attention Layers »
Asher Trockman · Zico Kolter -
2023 Workshop: 2nd Workshop on Formal Verification of Machine Learning »
Mark Müller · Brendon G. Anderson · Leslie Rice · Zhouxing Shi · Shubham Ugare · Huan Zhang · Martin Vechev · Zico Kolter · Somayeh Sojoudi · Cho-Jui Hsieh -
2022 Workshop: Principles of Distribution Shift (PODS) »
Elan Rosenfeld · Saurabh Garg · Shibani Santurkar · Jamie Morgenstern · Hossein Mobahi · Zachary Lipton · Andrej Risteski -
2022 Workshop: Workshop on Formal Verification of Machine Learning »
Huan Zhang · Leslie Rice · Kaidi Xu · aditi raghunathan · Wan-Yi Lin · Cho-Jui Hsieh · Clark Barrett · Martin Vechev · Zico Kolter -
2022 Poster: A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks »
Huan Zhang · Shiqi Wang · Kaidi Xu · Yihan Wang · Suman Jana · Cho-Jui Hsieh · Zico Kolter -
2022 Spotlight: A Branch and Bound Framework for Stronger Adversarial Attacks of ReLU Networks »
Huan Zhang · Shiqi Wang · Kaidi Xu · Yihan Wang · Suman Jana · Cho-Jui Hsieh · Zico Kolter -
2022 Poster: Supervised Learning with General Risk Functionals »
Liu Leqi · Audrey Huang · Zachary Lipton · Kamyar Azizzadenesheli -
2022 Poster: Communicating via Markov Decision Processes »
Samuel Sokota · Christian Schroeder · Maximilian Igl · Luisa Zintgraf · Phil Torr · Martin Strohmeier · Zico Kolter · Shimon Whiteson · Jakob Foerster -
2022 Spotlight: Supervised Learning with General Risk Functionals »
Liu Leqi · Audrey Huang · Zachary Lipton · Kamyar Azizzadenesheli -
2022 Spotlight: Communicating via Markov Decision Processes »
Samuel Sokota · Christian Schroeder · Maximilian Igl · Luisa Zintgraf · Phil Torr · Martin Strohmeier · Zico Kolter · Shimon Whiteson · Jakob Foerster -
2021 Workshop: A Blessing in Disguise: The Prospects and Perils of Adversarial Machine Learning »
Hang Su · Yinpeng Dong · Tianyu Pang · Eric Wong · Zico Kolter · Shuo Feng · Bo Li · Henry Liu · Dan Hendrycks · Francesco Croce · Leslie Rice · Tian Tian -
2021 : RL Explainability & Interpretability Panel »
Ofra Amir · Finale Doshi-Velez · Alan Fern · Zachary Lipton · Omer Gottesman · Niranjani Prasad -
2021 Poster: Correcting Exposure Bias for Link Recommendation »
Shantanu Gupta · Hao Wang · Zachary Lipton · Yuyang Wang -
2021 Spotlight: Correcting Exposure Bias for Link Recommendation »
Shantanu Gupta · Hao Wang · Zachary Lipton · Yuyang Wang -
2021 Poster: DORO: Distributional and Outlier Robust Optimization »
Runtian Zhai · Chen Dan · Zico Kolter · Pradeep Ravikumar -
2021 Spotlight: DORO: Distributional and Outlier Robust Optimization »
Runtian Zhai · Chen Dan · Zico Kolter · Pradeep Ravikumar -
2021 Poster: On Proximal Policy Optimization's Heavy-tailed Gradients »
Saurabh Garg · Joshua Zhanson · Emilio Parisotto · Adarsh Prasad · Zico Kolter · Zachary Lipton · Sivaraman Balakrishnan · Ruslan Salakhutdinov · Pradeep Ravikumar -
2021 Poster: Stabilizing Equilibrium Models by Jacobian Regularization »
Shaojie Bai · Vladlen Koltun · Zico Kolter -
2021 Spotlight: On Proximal Policy Optimization's Heavy-tailed Gradients »
Saurabh Garg · Joshua Zhanson · Emilio Parisotto · Adarsh Prasad · Zico Kolter · Zachary Lipton · Sivaraman Balakrishnan · Ruslan Salakhutdinov · Pradeep Ravikumar -
2021 Spotlight: Stabilizing Equilibrium Models by Jacobian Regularization »
Shaojie Bai · Vladlen Koltun · Zico Kolter -
2020 : Invited Talk: Zico Kolter (Q&A) »
Zico Kolter -
2020 : Invited Talk: Zico Kolter »
Zico Kolter -
2020 : Contributed Talk 3: A Unified View of Label Shift Estimation »
Saurabh Garg -
2020 Poster: Adversarial Robustness Against the Union of Multiple Perturbation Models »
Pratyush Maini · Eric Wong · Zico Kolter -
2020 Poster: Combining Differentiable PDE Solvers and Graph Neural Networks for Fluid Flow Prediction »
Filipe de Avila Belbute-Peres · Thomas Economon · Zico Kolter -
2020 Poster: Certified Robustness to Label-Flipping Attacks via Randomized Smoothing »
Elan Rosenfeld · Ezra Winston · Pradeep Ravikumar · Zico Kolter -
2020 Poster: Uncertainty-Aware Lookahead Factor Models for Quantitative Investing »
Lakshay Chauhan · John Alberg · Zachary Lipton -
2020 Poster: Overfitting in adversarially robust deep learning »
Leslie Rice · Eric Wong · Zico Kolter -
2019 Poster: Domain Adaptation with Asymmetrically-Relaxed Distribution Alignment »
Yifan Wu · Ezra Winston · Divyansh Kaushik · Zachary Lipton -
2019 Poster: What is the Effect of Importance Weighting in Deep Learning? »
Jonathon Byrd · Zachary Lipton -
2019 Oral: Domain Adaptation with Asymmetrically-Relaxed Distribution Alignment »
Yifan Wu · Ezra Winston · Divyansh Kaushik · Zachary Lipton -
2019 Oral: What is the Effect of Importance Weighting in Deep Learning? »
Jonathon Byrd · Zachary Lipton -
2019 Poster: Certified Adversarial Robustness via Randomized Smoothing »
Jeremy Cohen · Elan Rosenfeld · Zico Kolter -
2019 Poster: Wasserstein Adversarial Examples via Projected Sinkhorn Iterations »
Eric Wong · Frank R Schmidt · Zico Kolter -
2019 Oral: Wasserstein Adversarial Examples via Projected Sinkhorn Iterations »
Eric Wong · Frank R Schmidt · Zico Kolter -
2019 Oral: Certified Adversarial Robustness via Randomized Smoothing »
Jeremy Cohen · Elan Rosenfeld · Zico Kolter -
2019 Poster: SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver »
Po-Wei Wang · Priya Donti · Bryan Wilder · Zico Kolter -
2019 Poster: Adversarial camera stickers: A physical camera-based attack on deep learning systems »
Juncheng Li · Frank R Schmidt · Zico Kolter -
2019 Oral: SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver »
Po-Wei Wang · Priya Donti · Bryan Wilder · Zico Kolter -
2019 Oral: Adversarial camera stickers: A physical camera-based attack on deep learning systems »
Juncheng Li · Frank R Schmidt · Zico Kolter -
2018 Poster: Detecting and Correcting for Label Shift with Black Box Predictors »
Zachary Lipton · Yu-Xiang Wang · Alexander Smola -
2018 Poster: Born Again Neural Networks »
Tommaso Furlanello · Zachary Lipton · Michael Tschannen · Laurent Itti · Anima Anandkumar -
2018 Oral: Born Again Neural Networks »
Tommaso Furlanello · Zachary Lipton · Michael Tschannen · Laurent Itti · Anima Anandkumar -
2018 Oral: Detecting and Correcting for Label Shift with Black Box Predictors »
Zachary Lipton · Yu-Xiang Wang · Alexander Smola -
2018 Poster: Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope »
Eric Wong · Zico Kolter -
2018 Oral: Provable Defenses against Adversarial Examples via the Convex Outer Adversarial Polytope »
Eric Wong · Zico Kolter -
2017 Poster: Input Convex Neural Networks »
Brandon Amos · Lei Xu · Zico Kolter -
2017 Poster: OptNet: Differentiable Optimization as a Layer in Neural Networks »
Brandon Amos · Zico Kolter -
2017 Poster: A Semismooth Newton Method for Fast, Generic Convex Programming »
Alnur Ali · Eric Wong · Zico Kolter -
2017 Talk: OptNet: Differentiable Optimization as a Layer in Neural Networks »
Brandon Amos · Zico Kolter -
2017 Talk: Input Convex Neural Networks »
Brandon Amos · Lei Xu · Zico Kolter -
2017 Talk: A Semismooth Newton Method for Fast, Generic Convex Programming »
Alnur Ali · Eric Wong · Zico Kolter