  Recent digital rights frameworks give users the right to delete their data
from systems that store and process their personal information (e.g., the
"right to be forgotten" in the GDPR). How should deletion be formalized in
complex systems that interact with many users and store derivative information?
We argue that prior approaches fall short. Definitions of machine unlearning
Cao and Yang [2015] are too narrowly scoped and do not apply to general
interactive settings. The natural approach of deletion-as-confidentiality Garg
et al. [2020] is too restrictive: by requiring secrecy of deleted data, it
rules out social functionalities. We propose a new formalism:
deletion-as-control. It allows users' data to be freely used before deletion,
while also imposing a meaningful requirement after deletion--thereby giving
users more control. Deletion-as-control provides new ways of achieving deletion
in diverse settings. We apply it to social functionalities, and give a new
unified view of various machine unlearning definitions from the literature.
This is done by way of a new adaptive generalization of history independence.
Deletion-as-control also provides a new approach to the goal of machine
unlearning, that is, to maintaining a model while honoring users' deletion
requests. We show that publishing a sequence of updated models that are
differentially private under continual release satisfies deletion-as-control.
The accuracy of such an algorithm does not depend on the number of deleted
points, in contrast to the machine unlearning literature.
