How to sketch a learning algorithm

Sam Gunn

cs.LGApr 8, 2026

How to sketch a learning algorithm

Authors: Sam Gunn

Organizations: UC Berkeley

Abstract

How does the choice of training data influence an AI model? This broad question is of central importance to interpretability, privacy, and basic science. At its technical core is the data deletion problem: after a reasonable amount of precomputation, quickly predict how the model would behave in a given situation if a given subset of training data had been excluded from the learning algorithm. We present a data deletion scheme capable of predicting model outputs with vanishing error $\varepsilon$ and failure probability $δ$ in the deep learning setting. Our precomputation and prediction algorithms are only $\tilde{O}(\log(1/δ)/\varepsilon^2)$ factors slower than regular training and inference, respectively. The storage requirements are those of $\tilde{O}(\log(1/δ)/\varepsilon^2)$ models. Our proof is based on an assumption that we call stability. In contrast to the assumptions made by prior work, stability appears to be fully compatible with learning powerful AI models. In support of this, we show that stability is satisfied in a minimal set of experiments with microgpt. Our code is available at https://github.com/SamSpo1/microgpt-sketch. At a technical level, our work is based on a new method for locally sketching an arithmetic circuit by computing higher-order derivatives in random complex directions. Forward-mode automatic differentiation allows cheap computation of these derivatives.

Figures & tables

q_{i}=q_{i,0}+q_{i,1}z+\dots+q_{i,s}z^{s}

Algorithm 2

\mathsf{PREDICT}_{\bm{\Psi},\mathbf{P},m}(D,\phi)

: Counterfactual prediction

Panel of Figure 1 — Figure 1: Estimates of $\log\norm{\bT^{(r)}}_{\mathrm{F}}$ , i.e., the log Frobenius norms of the Taylor coefficients of $f=\phi\circ\mathcal{A}$ . The estimates are obtained as $\log\left(\sqrt{n[r]}\,\absolutevalue{\inner{\bT^{(r)}}{\bpsi^{\otimes r}}}\right)$ for random complex directions $\bm{\uppsi}$ . The learning algorithm $\mathcal{A}$ trains microgpt with Adam for 1000 steps on a dataset of names with a batch size of 1, as in [ 20 ] . Here $\phi$ is the loss of the given model on a random training example (chosen independently for each direction $\bm{\uppsi}$ ).

Panel of Figure 2 — Figure 2: Taylor approximations to $f(z\,\mathbf{1}_{D})$ , where $f=\phi\circ\mathcal{A}$ . As in Figure 1 , the learning algorithm $\mathcal{A}$ trains microgpt for 1000 steps on a dataset of names [ 20 ] . The deleted set $D$ is all names containing the letter “x” (there are 18) and the measurement function $\phi$ is the loss on the name “max.” The black dots are the values $f(z\,\mathbf{1}_{D})$ for $z\in\{0,0.1,\dots,1\}$ , and the colored lines are Taylor approximations to the function $z\mapsto f(z\,\mathbf{1}_{D})$ around $z=0$ .

Panel of Figure 3 — Figure 3: Predicted loss obtained using Algorithms 1 and 2 with the same $\mathcal{A}$ , $\phi$ , and $D$ as in Figure 2 . We use $s\in\{1,2,3\}$ and $k=500$ in $\mathsf{PRECOMPUTE}_{s,k}(\mathcal{A})$ and $m=1$ in $\mathsf{PREDICT}_{\bm{\Psi},\mathbf{P},m}(D,\phi)$ . The lines are the predictions obtained by the data deletion scheme, with 1 standard deviation shaded. In this case the approximation to the degree 3 expansion happens to be more accurate than the degree 3 expansion itself (cf. Figure 2 ), but this is pure chance.

Machine Unlearning

Machine unlearning removes the influence of selected data or concepts from trained models while preserving useful behavior and avoiding full retraining.

See all 351 papers

Jul 7, 2026

Auditing of Unlearning Algorithms

Evaluating whether unlearning algorithms truly remove training data influence remains an open challenge. We propose a practical auditor that computes data-dependent lower bounds on the unlearning parameter

\varepsilon

using membership inference attacks. Evaluating multiple unlearning algorithms, we find a sharp separation: algorithms with rigorous guarantees, such as model clipping and rewind-to-delete, achieve very small

\varepsilon

bounds that do not falsify their unlearning guarantees, whereas empirical methods such as Hessian-based unlearning, interleaved ascent-descent, ascent on the forget set, and fine-tuning on the retain set exhibit large bounds, indicating poor unlearning. Our auditor provides a practical tool for empirically falsifying unlearning claims through a hypothesis-testing framework, and we validate it on CIFAR-100 and Shakespeare text.

Sahasrajit Sarmasarkar, Anastasia Koloskova, Sanmi Koyejo

Stanford University · University of Zurich

Machine Unlearning Machine Unlearning Evaluation

Ask PDF

May 19, 2026

OriginBlame: Record- and Token-Level Data Provenance for AI Training Datasets

When a data contributor requests removal, model trainers face a practical gap: unlearning algorithms require a forget set, yet no tool can locate which training records belong to a given author. Existing provenance systems operate at file or dataset level, forcing catastrophic over-deletion. We present ob, a record- and token-level data provenance system that propagates author identity through data processing pipelines and resolves revocation requests into precise forget sets via deterministic queries. Evaluation on 219,555 Wikipedia pages demonstrates that record-level provenance eliminates dataset-level over-deletion (from 101x to 1.3x), while integration adds 1.3-4.0% throughput overhead (HuggingFace) and 2.1-19.0% (Datatrove) on wiki data. On a 1.7B model, provenance-based forget sets improve unlearning by 42% over random baselines.

Haolin Xue

Data Provenance LLM Unlearning Data Provenance in Language Models

Ask PDF

Oct 7, 2026

Why Forget-Only Unlearning Needs Memorization

Machine unlearning asks for a deletion algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, we study forget-only unlearning, where the deletion algorithm receives only the trained model and the examples to forget, with no retained data or extra training information. We ask whether forget-only unlearning is always possible. We first show that this depends on the learning method: different datasets can produce the same trained model but require very different outputs after the same examples are removed. Using this observation, we derive lower bounds on how accurately unlearning can match retraining and instantiate them for several standard learning algorithms. We then ask what must be true when forget-only unlearning succeeds. To this end, we derive lower bounds on what an algorithm must memorize about the training data to handle arbitrary deletion requests. For simple threshold learners, the required information can be as large as the entire dataset, even though ordinary training keeps only one boundary point. Overall, our results show that information discarded during ordinary learning may be needed later for deletion, so models designed for forget-only unlearning may need to retain more information than standard training does.

Luka Radić, Vikrant Singhal, Amartya Sanyal

Department of Computer Science, University of Copenhagen

Machine Unlearning

Ask PDF

Abstract

Machine Unlearning

Explore similar work

Auditing of Unlearning Algorithms

OriginBlame: Record- and Token-Level Data Provenance for AI Training Datasets

Why Forget-Only Unlearning Needs Memorization