Timezone: »
Data deletion algorithms aim to remove the influence of deleted data points from trained models at a cheaper computational cost than fully retraining those models. However, for sequences of deletions, most prior work in the non-convex setting gives valid guarantees only for sequences that are chosen independently of the models that are published. If people choose to delete their data as a function of the published models (because they don’t like what the models reveal about them, for example), then the update sequence is adaptive. In this paper, we give a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences, using differential privacy and its connection to max information. Combined with ideas from prior work which give guarantees for non-adaptive deletion sequences, this leads to extremely flexible algorithms able to handle arbitrary model classes and training methodologies, giving strong provable deletion guarantees for adaptive deletion sequences. We show in theory how prior work for non-convex models fails against adaptive deletion sequences, and use this intuition to design a practical attack against the SISA algorithm of Bourtoule et al. [2021] on CIFAR-10, MNIST, Fashion-MNIST.
Author Information
Varun Gupta (School of Engineering and Applied Science, University of Pennsylvania)
Christopher Jung (University of Pennsylvania)
Seth Neel (University of Pennsylvania)
PhD student in statistics studying fairness and privacy in learning. Advised by Aaron Roth and Michael Kearns.
Aaron Roth (University of Pennsylvania)
Saeed Sharifi-Malvajerdi (University of Pennsylvania)
Chris Waites (Stanford University)
More from the Same Authors
-
2022 : Differentially Private Gradient Boosting on Linear Learners for Tabular Data »
Saeyoung Rho · Shuai Tang · Sergul Aydore · Michael Kearns · Aaron Roth · Yu-Xiang Wang · Steven Wu · Cedric Archambeau -
2022 Poster: Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications »
Daniel Lee · Georgy Noarov · Mallesh Pai · Aaron Roth -
2022 Poster: Practical Adversarial Multivalid Conformal Prediction »
Osbert Bastani · Varun Gupta · Christopher Jung · Georgy Noarov · Ramya Ramalingam · Aaron Roth -
2022 Poster: Private Synthetic Data for Multitask Learning and Marginal Queries »
Giuseppe Vietri · Cedric Archambeau · Sergul Aydore · William Brown · Michael Kearns · Aaron Roth · Ankit Siva · Shuai Tang · Steven Wu -
2021 : Panel »
Oluwaseyi Feyisetan · Helen Nissenbaum · Aaron Roth · Christine Task -
2021 : Invited talk: Aaron Roth (UPenn / Amazon): Machine Unlearning. »
Aaron Roth -
2019 : Aaron Roth, "Average Individual Fairness" »
Aaron Roth -
2019 : Poster Session »
Clement Canonne · Kwang-Sung Jun · Seth Neel · Di Wang · Giuseppe Vietri · Liwei Song · Jonathan Lebensold · Huanyu Zhang · Lovedeep Gondara · Ang Li · FatemehSadat Mireshghallah · Jinshuo Dong · Anand D Sarwate · Antti Koskela · Joonas Jälkö · Matt Kusner · Dingfan Chen · Mi Jung Park · Ashwin Machanavajjhala · Jayashree Kalpathy-Cramer · · Vitaly Feldman · Andrew Tomkins · Hai Phan · Hossein Esfandiari · Mimansa Jaiswal · Mrinank Sharma · Jeff Druce · Casey Meehan · Zhengli Zhao · Hsiang Hsu · Davis Railsback · Abraham Flaxman · · Julius Adebayo · Aleksandra Korolova · Jiaming Xu · Naoise Holohan · Samyadeep Basu · Matthew Joseph · My Thai · Xiaoqian Yang · Ellen Vitercik · Michael Hutchinson · Chenghong Wang · Gregory Yauney · Yuchao Tao · Chao Jin · Si Kai Lee · Audra McMillan · Rauf Izmailov · Jiayi Guo · Siddharth Swaroop · Tribhuvanesh Orekondy · Hadi Esmaeilzadeh · Kevin Procopio · Alkis Polyzotis · Jafar Mohammadi · Nitin Agrawal -
2019 : Poster Session »
Nathalie Baracaldo · Seth Neel · Tuyen Le · Dan Philps · Suheng Tao · Sotirios Chatzis · Toyo Suzumura · Wei Wang · WENHANG BAO · Solon Barocas · Manish Raghavan · Samuel Maina · Reginald Bryant · Kush Varshney · Skyler D. Speakman · Navdeep Gill · Nicholas Schmidt · Kevin Compher · Naveen Sundar Govindarajulu · Vivek Sharma · Praneeth Vepakomma · Tristan Swedish · Jayashree Kalpathy-Cramer · Ramesh Raskar · Shihao Zheng · Mykola Pechenizkiy · Marco Schreyer · Li Ling · Chirag Nagpal · Robert Tillman · Manuela Veloso · Hanjie Chen · Xintong Wang · Michael Wellman · Matthew van Adelsberg · Ben Wood · Hans Buehler · Mahmoud Mahfouz · Antonios Alexos · Megan Shearer · Antigoni Polychroniadou · Lucia Larise Stavarache · Dmitry Efimov · Johnston P Hall · Yukun Zhang · Emily Diana · Sumitra Ganesh · Vineeth Ravi · · Swetasudha Panda · Xavier Renard · Matthew Jagielski · Yonadav Shavit · Joshua Williams · Haoran Wei · Shuang (Sophie) Zhai · Xinyi Li · Hongda Shen · Daiki Matsunaga · Jaesik Choi · Alexis Laignelet · Batuhan Guler · Jacobo Roa Vicens · Ajit Desai · Jonathan Aigrain · Robert Samoilescu -
2019 : Invited talk #3 »
Aaron Roth -
2019 Poster: Average Individual Fairness: Algorithms, Generalization and Experiments »
Saeed Sharifi-Malvajerdi · Michael Kearns · Aaron Roth -
2019 Oral: Average Individual Fairness: Algorithms, Generalization and Experiments »
Saeed Sharifi-Malvajerdi · Michael Kearns · Aaron Roth -
2017 Poster: Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM »
Katrina Ligett · Seth Neel · Aaron Roth · Bo Waggoner · Steven Wu -
2016 Workshop: Adaptive Data Analysis »
Vitaly Feldman · Aaditya Ramdas · Aaron Roth · Adam Smith -
2015 Poster: Generalization in Adaptive Data Analysis and Holdout Reuse »
Cynthia Dwork · Vitaly Feldman · Moritz Hardt · Toni Pitassi · Omer Reingold · Aaron Roth