Timezone: »
Poster
Remember What You Want to Forget: Algorithms for Machine Unlearning
Ayush Sekhari · Jayadev Acharya · Gautam Kamath · Ananda Theertha Suresh
We study the problem of unlearning datapoints from a learnt model. The learner first receives a dataset $S$ drawn i.i.d. from an unknown distribution, and outputs a model $\widehat{w}$ that performs well on unseen samples from the same distribution. However, at some point in the future, any training datapoint $z \in S$ can request to be unlearned, thus prompting the learner to modify its output model while still ensuring the same accuracy guarantees. We initiate a rigorous study of generalization in machine unlearning, where the goal is to perform well on previously unseen datapoints. Our focus is on both computational and storage complexity. For the setting of convex losses, we provide an unlearning algorithm that can unlearn up to $O(n/d^{1/4})$ samples, where $d$ is the problem dimension. In comparison, in general, differentially private learning (which implies unlearning) only guarantees deletion of $O(n/d^{1/2})$ samples. This demonstrates a novel separation between differential privacy and machine unlearning.
Author Information
Ayush Sekhari (Cornell University)
Jayadev Acharya (Cornell University)
Gautam Kamath (University of Waterloo)
Ananda Theertha Suresh (Google)
More from the Same Authors
-
2021 Spotlight: Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations »
Ayush Sekhari · Christoph Dann · Mehryar Mohri · Yishay Mansour · Karthik Sridharan -
2021 : FedJAX: Federated learning simulation with JAX »
Jae Hun Ro · Ananda Theertha Suresh · Ke Wu -
2022 : Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distance »
Xin Gu · Gautam Kamath · Steven Wu -
2022 : Hidden Poison: Machine Unlearning Enables Camouflaged Poisoning Attacks »
Jimmy Di · Jack Douglas · Jayadev Acharya · Gautam Kamath · Ayush Sekhari -
2022 : Indiscriminate Data Poisoning Attacks on Neural Networks »
Yiwei Lu · Gautam Kamath · Yaoliang Yu -
2022 : Indiscriminate Data Poisoning Attacks on Neural Networks »
Yiwei Lu · Gautam Kamath · Yaoliang Yu -
2022 : Hidden Poison: Machine unlearning enables camouflaged poisoning attacks »
Jimmy Di · Jack Douglas · Jayadev Acharya · Gautam Kamath · Ayush Sekhari -
2022 Spotlight: Lightning Talks 6A-2 »
Yichuan Mo · Botao Yu · Gang Li · Zezhong Xu · Haoran Wei · Arsene Fansi Tchango · Raef Bassily · Haoyu Lu · Qi Zhang · Songming Liu · Mingyu Ding · Peiling Lu · Yifei Wang · Xiang Li · Dongxian Wu · Ping Guo · Wen Zhang · Hao Zhongkai · Mehryar Mohri · Rishab Goel · Yisen Wang · Yifei Wang · Yangguang Zhu · Zhi Wen · Ananda Theertha Suresh · Chengyang Ying · Yujie Wang · Peng Ye · Rui Wang · Nanyi Fei · Hui Chen · Yiwen Guo · Wei Hu · Chenglong Liu · Julien Martel · Yuqi Huo · Wu Yichao · Hang Su · Yisen Wang · Peng Wang · Huajun Chen · Xu Tan · Jun Zhu · Ding Liang · Zhiwu Lu · Joumana Ghosn · Shanshan Zhang · Wei Ye · Ze Cheng · Shikun Zhang · Tao Qin · Tie-Yan Liu -
2022 Spotlight: Differentially Private Learning with Margin Guarantees »
Raef Bassily · Mehryar Mohri · Ananda Theertha Suresh -
2022 : Private GANs, Revisited »
Alex Bie · Gautam Kamath · Guojun Zhang -
2022 Poster: New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma »
Gautam Kamath · Argyris Mouzakis · Vikrant Singhal -
2022 Poster: Differentially Private Learning with Margin Guarantees »
Raef Bassily · Mehryar Mohri · Ananda Theertha Suresh -
2022 Poster: Private Estimation with Public Data »
Alex Bie · Gautam Kamath · Vikrant Singhal -
2021 Poster: SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs »
Ayush Sekhari · Karthik Sridharan · Satyen Kale -
2021 Poster: Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition »
Jayadev Acharya · Clement Canonne · Yuhan Liu · Ziteng Sun · Himanshu Tyagi -
2021 Poster: Information-constrained optimization: can adaptive processing of gradients help? »
Jayadev Acharya · Clement Canonne · Prathamesh Mayekar · Himanshu Tyagi -
2021 Poster: Learning with User-Level Privacy »
Daniel Levy · Ziteng Sun · Kareem Amin · Satyen Kale · Alex Kulesza · Mehryar Mohri · Ananda Theertha Suresh -
2021 Poster: Boosting with Multiple Sources »
Corinna Cortes · Mehryar Mohri · Dmitry Storcheus · Ananda Theertha Suresh -
2021 Poster: Breaking the centralized barrier for cross-device federated learning »
Sai Praneeth Karimireddy · Martin Jaggi · Satyen Kale · Mehryar Mohri · Sashank Reddi · Sebastian Stich · Ananda Theertha Suresh -
2021 Poster: Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorization »
Pranav Subramani · Nicholas Vadivelu · Gautam Kamath -
2021 Poster: Neural Active Learning with Performance Guarantees »
Zhilei Wang · Pranjal Awasthi · Christoph Dann · Ayush Sekhari · Claudio Gentile -
2021 Poster: Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations »
Ayush Sekhari · Christoph Dann · Mehryar Mohri · Yishay Mansour · Karthik Sridharan -
2021 Poster: Optimal Rates for Nonparametric Density Estimation under Communication Constraints »
Jayadev Acharya · Clement Canonne · Aditya Vikram Singh · Himanshu Tyagi -
2020 Poster: The Discrete Gaussian for Differential Privacy »
Clément L Canonne · Gautam Kamath · Thomas Steinke -
2020 Social: Data Privacy: Academia, Industry, Policy, and Society »
Gautam Kamath -
2020 Poster: CoinPress: Practical Private Mean and Covariance Estimation »
Sourav Biswas · Yihe Dong · Gautam Kamath · Jonathan Ullman -
2020 Poster: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2020 Poster: Reinforcement Learning with Feedback Graphs »
Christoph Dann · Yishay Mansour · Mehryar Mohri · Ayush Sekhari · Karthik Sridharan -
2020 Poster: Learning discrete distributions: user vs item-level privacy »
Yuhan Liu · Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Michael D Riley -
2020 Spotlight: Private Identity Testing for High-Dimensional Distributions »
Clément L Canonne · Gautam Kamath · Audra McMillan · Jonathan Ullman · Lydia Zakynthinou -
2019 Poster: Private Hypothesis Selection »
Mark Bun · Gautam Kamath · Thomas Steinke · Steven Wu -
2019 Poster: Estimating Entropy of Distributions in Constant Space »
Jayadev Acharya · Sourbh Bhadane · Piotr Indyk · Ziteng Sun -
2019 Poster: Sampled Softmax with Random Fourier Features »
Ankit Singh Rawat · Jiecao Chen · Felix Xinnan Yu · Ananda Theertha Suresh · Sanjiv Kumar -
2019 Poster: Differentially Private Algorithms for Learning Mixtures of Separated Gaussians »
Gautam Kamath · Or Sheffet · Vikrant Singhal · Jonathan Ullman -
2019 Poster: Differentially Private Anonymized Histograms »
Ananda Theertha Suresh -
2018 Poster: Learning and Testing Causal Models with Interventions »
Jayadev Acharya · Arnab Bhattacharyya · Constantinos Daskalakis · Saravanan Kandasamy -
2018 Poster: Uniform Convergence of Gradients for Non-Convex Learning and Optimization »
Dylan Foster · Ayush Sekhari · Karthik Sridharan -
2018 Poster: Data Amplification: A Unified and Competitive Approach to Property Estimation »
Yi Hao · Alon Orlitsky · Ananda Theertha Suresh · Yihong Wu -
2018 Poster: Differentially Private Testing of Identity and Closeness of Discrete Distributions »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang -
2018 Poster: cpSGD: Communication-efficient and differentially-private distributed SGD »
Naman Agarwal · Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2018 Spotlight: cpSGD: Communication-efficient and differentially-private distributed SGD »
Naman Agarwal · Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2018 Spotlight: Differentially Private Testing of Identity and Closeness of Discrete Distributions »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang -
2017 Poster: Multiscale Quantization for Fast Similarity Search »
Xiang Wu · Ruiqi Guo · Ananda Theertha Suresh · Sanjiv Kumar · Daniel Holtmann-Rice · David Simcha · Felix Yu -
2017 Poster: Concentration of Multilinear Functions of the Ising Model with Applications to Network Data »
Constantinos Daskalakis · Nishanth Dikkala · Gautam Kamath -
2017 Poster: Model-Powered Conditional Independence Test »
Rajat Sen · Ananda Theertha Suresh · Karthikeyan Shanmugam · Alex Dimakis · Sanjay Shakkottai -
2015 Poster: Optimal Testing for Properties of Distributions »
Jayadev Acharya · Constantinos Daskalakis · Gautam Kamath -
2015 Spotlight: Optimal Testing for Properties of Distributions »
Jayadev Acharya · Constantinos Daskalakis · Gautam Kamath