Assumption comparator

These bounds look comparable and are not. Sekhari forbids storing the training set; Regehr grants it. Van Waerebeke's unlearner may only touch the retain set, so SCRUB and every other forget-set method falls outside its algorithm class. Each of those is a single sentence in its own paper. Together they decide whether a rate transfers.

Rows are ordered by year. A cell reading “not stated” means the paper is silent, not that we did not look.

Filter rows

Paper	ConvexityWhat the loss must satisfy for the result to hold.	Applies toWhether assumptions bind per training example or only in aggregate.	Storage allowedWhat the unlearner may retain between training and the deletion request.	Forget-set accessWhether the unlearning algorithm may look at the data being deleted.	Dependence on dHow cost or quality scales with parameter count -- the barrier for a ResNet.	What is boundedThe quantity the result actually controls. These are not interchangeable.	Empirical scope
cao2015forget 2015	None. Requires the algorithm be expressible as statistical queries.	Whole learning pipeline, including feature selection.	The summations; training data may be discarded.	Yes -- the deleted sample is subtracted from the summations.	Not analysed; cost is in the number of summations, not d.	Completeness and timeliness, defined operationally against their systems.	LensKit, Zozzle, an OSN spam filter, PJScan. No deep networks.
ginart2019deletion 2019	None assumed; the case study is k-means.	Distributional -- equality in distribution between unlearned and retrained.	Arbitrary metadata permitted, including partial computations.	Yes -- deletion is by index into the training set.	Not the focus; the lower bound Omega(n/m) is in n and m.	Amortised computation time in an online deletion stream.	Quantized and Divide-and-Conquer k-means. No deep networks.
golatkar2020eternal 2020	Quadratic loss and gradient-flow optimisation for the theory. The implemented method assumes only SGD stability.	Population-level; the forget set is assumed small.	The FIM diagonal.	Yes.	The full Newton step is unaffordable, which is why Section 4 sets h(w)=w and keeps only the noise.	KL between scrubbed and retrained weight distributions, via the Forgetting Lagrangian.	CIFAR-10, Lacuna, All-CNN and ResNet-18 -- the only theory-adjacent paper here that runs deep networks.
guo2020certified 2020	Convex, everywhere differentiable, with lambda-strong regularisation and a unique minimiser.	Per-example bounds on gradient norm and a gamma-Lipschitz second derivative.	The Hessian, formed offline at O(d^2 n).	Yes -- the removed point's gradient drives the Newton step.	O(d^3) at removal time. Theorem 1's bound carries 1/lambda^2.	Max-divergence between the removal mechanism's output and retraining.	Linear models. For deep models the mechanism applies ONLY to a linear head over a frozen or DP-trained feature extractor.
izzo2021approximate 2021	Linear regression; extended to logistic regression via IRLS.	Squared loss, so gradients are scalar multiples of the input.	The hat matrix, precomputed at O(n d^2).	Yes -- the update projects onto the span of the deleted points.	O(k^2 d) for the UPDATE ONLY. Precomputation remains O(n d^2).	Distance to the leave-k-out parameter, optimally among updates in that span.	Linear and logistic regression. No deep networks.
neel2021descent 2021	m-strongly convex and M-smooth for the perfect-unlearning result. The authors state their techniques do not extend without strong convexity.	Per-example L-Lipschitz and m-strongly convex in Lemma 2.12.	Secret state permitted for ordinary unlearning; perfect unlearning may keep none.	Yes -- updates are (datapoint, add/delete) pairs.	Per-update runtime at least logarithmic in the dimension.	(alpha,beta)-accuracy across an UPDATE SEQUENCE, with cost growth in the number of requests.	None in the sections read.
sekhari2021remember 2021	lambda-strongly convex, L-Lipschitz AND M-Hessian-Lipschitz.	Per-example -- all three conditions hold for every z.	T(S) explicitly excludes storing the training set or aggressive checkpointing. \|T(S)\| = O(d^2).	Yes, and centrally so -- hence the title.	O(d^2) storage, O(d^omega) time. Deletion capacity scales as n/d^(1/4).	Excess POPULATION risk, and deletion capacity against it.	None in the sections read.
vanwaerebeke2025whentoforget 2025	Minimax over the strongly convex class; theta* assumed the unique minimiser.	Function-class level, not per-example.	Not the constraint; the algorithm class is defined by the update rule.	NO. Unlearning algorithms may only sample the RETAIN set. SCRUB, NegGrad+, Bad-T and SalUn all fall outside this class.	Upper bound carries sqrt(d); the authors note their lower bound does not match it.	Minimax COMPUTATION TIME to a target excess risk -- not forget quality.	Linear regression, synthetic worst-case objectives, and the Digit dataset.
xu2025infotheoretic 2025	NONE in the sections read. The machinery is mutual information, Fano, data-processing and Pinsker.	Distributional, over model outputs rather than parameters.	Not a constraint; the criterion needs only output samples.	Not framed this way; the criterion is auditable from outputs alone.	The authors describe Theorem 2.1's bound as dimension- and output-space-agnostic.	Mutual information between model outputs and a latent source label, plus a utility budget.	Section 6 reportedly implements on tabular data and image classification. NOT READ.
regehr2026nearoptimal 2026	Smooth strongly convex SCO. Unlike Sekhari, no Lipschitz-Hessian requirement.	Per-example -- Lipschitz, strongly convex and smooth for every z.	FULL storage granted: T(Z) = Z. The opposite of Sekhari's constraint.	Yes -- the unlearner sees the dataset, the deletion set and the learned model.	The gain factor is e^{-2 eps/(d+2)}; it only helps when eps >> d.	Excess population risk under PURE (delta = 0) eps-unlearning, with MATCHING upper and lower bounds.	None. Pure theory.