Descent-to-Delete: Gradient-Based Methods for Machine Unlearning

Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:931-962, 2021.

Abstract

We study the data deletion problem for convex models. By leveraging techniques from convex optimization and reservoir sampling, we give the first data deletion algorithms that are able to handle an arbitrarily long sequence of adversarial updates while promising both per-deletion run-time and steady-state error that do not grow with the length of the update sequence. We also introduce several new conceptual distinctions: for example, we can ask that after a deletion, the entire state maintained by the optimization algorithm is statistically indistinguishable from the state that would have resulted had we retrained, or we can ask for the weaker condition that only the observable output is statistically indistinguishable from the observable output that would have resulted from retraining. We are able to give more efficient deletion algorithms under this weaker deletion criterion.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-neel21a, title = {Descent-to-Delete: Gradient-Based Methods for Machine Unlearning}, author = {Neel, Seth and Roth, Aaron and Sharifi-Malvajerdi, Saeed}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {931--962}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/neel21a/neel21a.pdf}, url = {https://proceedings.mlr.press/v132/neel21a.html}, abstract = {We study the data deletion problem for convex models. By leveraging techniques from convex optimization and reservoir sampling, we give the first data deletion algorithms that are able to handle an arbitrarily long sequence of adversarial updates while promising both per-deletion run-time and steady-state error that do not grow with the length of the update sequence. We also introduce several new conceptual distinctions: for example, we can ask that after a deletion, the entire state maintained by the optimization algorithm is statistically indistinguishable from the state that would have resulted had we retrained, or we can ask for the weaker condition that only the observable output is statistically indistinguishable from the observable output that would have resulted from retraining. We are able to give more efficient deletion algorithms under this weaker deletion criterion.} }
Endnote
%0 Conference Paper %T Descent-to-Delete: Gradient-Based Methods for Machine Unlearning %A Seth Neel %A Aaron Roth %A Saeed Sharifi-Malvajerdi %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-neel21a %I PMLR %P 931--962 %U https://proceedings.mlr.press/v132/neel21a.html %V 132 %X We study the data deletion problem for convex models. By leveraging techniques from convex optimization and reservoir sampling, we give the first data deletion algorithms that are able to handle an arbitrarily long sequence of adversarial updates while promising both per-deletion run-time and steady-state error that do not grow with the length of the update sequence. We also introduce several new conceptual distinctions: for example, we can ask that after a deletion, the entire state maintained by the optimization algorithm is statistically indistinguishable from the state that would have resulted had we retrained, or we can ask for the weaker condition that only the observable output is statistically indistinguishable from the observable output that would have resulted from retraining. We are able to give more efficient deletion algorithms under this weaker deletion criterion.
APA
Neel, S., Roth, A. & Sharifi-Malvajerdi, S.. (2021). Descent-to-Delete: Gradient-Based Methods for Machine Unlearning. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:931-962 Available from https://proceedings.mlr.press/v132/neel21a.html.

Related Material