Memory Requirements of Unlearning

The concept of machine unlearning has emerged as an important paradigm both for AI safety as well as to accommodate data protection laws that aim to give users more control over how their data is used. Briefly, this concept aims to provide an information-theoretic guarantee that post an unlearning request of a data point, the trained ML model behaves as if the deleted data were never used. In this talk, we will study the memory complexity of machine unlearning algorithms. Particularly, we ask how many bits of storage are needed to be able to delete certain training samples at a later time. We will focus on the task of realizability testing, where the goal is to check whether the remaining training samples are realizable within a given hypothesis class (H). We will show that for any hypothesis class H, the amount of information that the learner needs to store, so as to perform unlearning later, is lower bounded by the Eluder dimension of H, a combinatorial notion that can be much larger than the VC dimension.