Retain-Forget Limits and Tradeoffs in Machine Unlearning with Partial Information

Machine unlearning is commonly framed as an approximation to retraining on the retained data. While prior literature typically characterizes unlearning as a tradeoff between computational efficiency and accuracy, this work reframes the task as an optimization problem constrained by partial information about the training set, such as the original model and local Hessian of the training loss, but not the full retained data. We formalize the resulting ambiguity through the set of feasible datasets consistent with the same partial information, and define retain-set excess risk and forget-set unlearning risk, which measure the gap between an unlearned model and the retraining oracle on the retained and forgetting data respectively. For least-squares regression, we decompose both risks into algorithm-dependent fitting terms and algorithm-independent ambiguity floors. We then construct a two-layer ReLU example, showing that both ambiguity floors scale as $\Omega (k)$, where $k$ is the forget-set size, even when the algorithm utilizes the original model, the forget set, and local Hessian. We further show that the retain and forget fitting objectives need not share a minimizer, yielding a Pareto tradeoff between the two goals. Finally, for representative first- and second-order unlearning methods, we derive matching $O(k)$ risk upper bounds under suitable regularity conditions and analyze their tradeoff between retain and forget.