Carolin Heinzler

For certified unlearning of a deletion set $U$ from a model trained on $S$, the relevant noise need not protect the privacy of the retained data $R=S\setminus U$; this creates a conceptual separation from differential privacy. For this purpose we introduce the notion of retain sensitivity given a dataset $R$ and show a reduction in noise necessary for unlearning for multiple problems in ML, statistics and TCS, as well as reduced noise for two well-known unlearning alogrithms.

When models train on their own past guesses, mistakes can echo and mislead learning. We introduce a learning-theoretic setting that models this phenomenon: Online Learning in the Replay Setting. We introduce a combinatorial measure, the Extended Threshold dimension, which characterises learnability in this setting.

We investigate the challenge of establishing stochastic-like guarantees when learning from a stream of i.i.d. data with clean-label adversarial samples. Introducing the notion of a clean-label adversary in the agnostic context, we are the first to give a theoretical analysis of a disagreement-based learner for thresholds.