Timezone: »
We investigate and leverage a connection between Differential Privacy (DP) and the recently proposed notion of Distributional Generalization (DG). Applying this connection, we introduce new conceptual tools for designing deep-learning methods that bypass "pathologies" of standard stochastic gradient descent (SGD). First, we prove that differentially private methods satisfy a "What You See Is What You Get (WYSIWYG)" generalization guarantee: whatever a model does on its train data is almost exactly what it will do at test time. This guarantee is formally captured by distributional generalization. WYSIWYG enables principled algorithm design in deep learning by reducing \emph{generalization} concerns to \emph{optimization} ones: in order to mitigate unwanted behavior at test time, it is provably sufficient to mitigate this behavior on the train data. This is notably false for standard (non-DP) methods, hence this observation has applications even when privacy is not required. For example, importance sampling is known to fail for standard ERM, but we show that it has exactly the intended effect for DP-trained models. We use these insights to construct simple algorithms which match or outperform SOTA in several distributional robustness applications, and to significantly improve the privacy vs. disparate impact tradeoff of DP-SGD. Finally, we also improve on known theoretical bounds relating DP, stability, and distributional generalization.
Author Information
Bogdan Kulynych (EPFL / Harvard)
Yao-Yuan Yang (UCSD)
Yaodong Yu (University of California, Berkeley)
Jarosław Błasiok (Columbia)
Preetum Nakkiran (Harvard)
More from the Same Authors
-
2021 : Distributional Generalization: A New Kind of Generalization (Extended Abstract) »
Preetum Nakkiran · Yamini Bansal -
2022 : Causal Prediction Can Induce Performative Stability »
Bogdan Kulynych -
2022 : Robust Calibration with Multi-domain Temperature Scaling »
Yaodong Yu · Stephen Bates · Yi Ma · Michael Jordan -
2022 : Understanding Rare Spurious Correlations in Neural Networks »
Yao-Yuan Yang · Chi-Ning Chou · Kamalika Chaudhuri -
2023 : Adversarial Robustness for Tabular Data through Cost and Utility Awareness »
Klim Kireev · Bogdan Kulynych · Carmela Troncoso -
2023 : Arbitrary Decisions are a Hidden Cost of Differentially Private Training »
Bogdan Kulynych · Hsiang Hsu · Carmela Troncoso · Flavio Calmon -
2023 : Prediction without Preclusion: Recourse Verification with Reachable Sets »
Avni Kothari · Bogdan Kulynych · Lily Weng · Berk Ustun -
2023 : Prediction without Preclusion Recourse Verification with Reachable Sets »
Avni Kothari · Berk Ustun · Lily Weng · Bogdan Kulynych -
2023 : SCAFF-PD: Communication Efficient Fair and Robust Federated Learning »
Yaodong Yu · Sai Praneeth Karimireddy · Yi Ma · Michael Jordan -
2023 : Federated Conformal Predictors for Distributed Uncertainty Quantification »
Charles Lu · Yaodong Yu · Sai Praneeth Karimireddy · Michael Jordan · Ramesh Raskar -
2023 : Prediction without Preclusion Recourse Verification with Reachable Sets »
Avni Kothari · Bogdan Kulynych · Lily Weng · Berk Ustun -
2023 Poster: Federated Conformal Predictors for Distributed Uncertainty Quantification »
Charles Lu · Yaodong Yu · Sai Praneeth Karimireddy · Michael Jordan · Ramesh Raskar -
2022 Poster: Predicting Out-of-Distribution Error with the Projection Norm »
Yaodong Yu · Zitong Yang · Alexander Wei · Yi Ma · Jacob Steinhardt -
2022 Spotlight: Predicting Out-of-Distribution Error with the Projection Norm »
Yaodong Yu · Zitong Yang · Alexander Wei · Yi Ma · Jacob Steinhardt -
2022 Poster: Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback »
Tianyi Lin · Aldo Pacchiano · Yaodong Yu · Michael Jordan -
2022 Spotlight: Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback »
Tianyi Lin · Aldo Pacchiano · Yaodong Yu · Michael Jordan -
2021 : Distributional Generalization: A New Kind of Generalization (Extended Abstract) »
Preetum Nakkiran · Yamini Bansal -
2021 Poster: Connecting Interpretability and Robustness in Decision Trees through Separation »
Michal Moshkovitz · Yao-Yuan Yang · Kamalika Chaudhuri -
2021 Spotlight: Connecting Interpretability and Robustness in Decision Trees through Separation »
Michal Moshkovitz · Yao-Yuan Yang · Kamalika Chaudhuri -
2020 : Spotlight Talk 2: A Closer Look at Accuracy vs. Robustness »
Yao-Yuan Yang -
2020 Workshop: Participatory Approaches to Machine Learning »
Angela Zhou · David Madras · Deborah Raji · Smitha Milli · Bogdan Kulynych · Richard Zemel -
2020 : Opening remarks »
Deborah Raji · Angela Zhou · David Madras · Smitha Milli · Bogdan Kulynych -
2020 Poster: Rethinking Bias-Variance Trade-off for Generalization of Neural Networks »
Zitong Yang · Yaodong Yu · Chong You · Jacob Steinhardt · Yi Ma