The Space Complexity of Learning-Unlearning Algorithms

Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman +2

We study the memory complexity of machine unlearning algorithms that provide strong data deletion guarantees to the users. Formally, consider an algorithm for a particular learning…