  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.
