Deletion capacity is a formal quantity introduced in Sekhari et al. (2021) that measures the maximum number of training samples that can be unlearned from a model while still maintaining a bounded excess population risk (test loss). It serves as the primary metric for comparing the efficiency of unlearning algorithms.
Formally, for a pair of learning algorithm A and unlearning algorithm A_bar that are (epsilon, delta)-unlearning, the deletion capacity m_{epsilon,delta}^{A,A_bar}(d, n) is defined as:
m_{epsilon,delta}^{A,A_bar}(d, n) := max{ m | E[max_{U subset S, |U| ⇐ m} F(A_bar(U, A(S), T(S)))] - F* ⇐ 0.01 }
where F is the population risk and F* is the optimal population risk. The expectation is over the random draw of dataset S and any randomness in the algorithms. The constant 0.01 is arbitrary and can be replaced by any small gamma > 0.
Deletion capacity depends critically on the problem dimension d, the dataset size n, and the properties of the loss function. The key results from Sekhari et al. establish the following landscape:
Key Details
- Upper bound (Theorem 1): For strongly convex losses, even with access to all remaining samples S\U, the deletion capacity is at most O(cn) for some constant c < 1, demonstrating inherent limits
- DP baseline (Lemma 1): Any differentially private learning algorithm provides deletion capacity of at least Omega(n * epsilon / sqrt(d * log(e^epsilon / delta))), i.e., O(n / sqrt(d))
- Unlearning algorithms (Theorem 2): For convex losses, the Newton-step unlearning algorithm achieves deletion capacity of at least c * n * sqrt(epsilon) / (d * log(1/delta))^{1/4}, i.e., O(n / d^{1/4})
- Separation from DP: The multiplicative gap of Theta(d^{1/4}) between unlearning and DP demonstrates that algorithms aware of which points are being deleted can fundamentally outperform privacy-based approaches
- The deletion capacity concept implicitly captures a three-way trade-off between: number of deletions, generalization performance, and computational/storage costs
- This concept has been referenced in subsequent theoretical work on machine unlearning bounds, including Huang and Canonne (2023)