# How to sketch a learning algorithm

arXiv: https://arxiv.org/abs/2604.07328 · HTML: https://mlsanity.com/paper/2604.07328/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 19 references that are in the map.
- First posted on arXiv 8 Apr 2026.

## Builds on (most cited first, 10 of 10)

- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [TRAK: Attributing Model Behavior at Scale](https://mlsanity.com/paper/2303.14186/) (2023)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [On the Accuracy of Influence Functions for Measuring Group Effects](https://mlsanity.com/paper/1905.13289/) (2019)
- [Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition](https://mlsanity.com/paper/2406.09073/) (2024)
- [Certified Unlearning for Neural Networks](https://mlsanity.com/paper/2506.06985/) (2025)
- [Understanding Influence Functions and Datamodels via Harmonic Analysis](https://mlsanity.com/paper/2210.01072/) (2022)
- [Optimizing ML Training with Metagradient Descent](https://mlsanity.com/paper/2503.13751/) (2025)
- [MAGIC: Near-Optimal Data Attribution for Deep Learning](https://mlsanity.com/paper/2504.16430/) (2025)
- [Spectral norm of a symmetric tensor and its computation](https://mlsanity.com/paper/1808.03864/) (2018)

## Built on by (most cited first, 2 of 2)

- [Data Attribution via Sketched Metadifferentiation](https://mlsanity.com/paper/2609.15044/) (2026)
- [Training Witnesses: Trusting the Training without Trusting the Trainer](https://mlsanity.com/paper/2609.33915/) (2026)

## Abstract (arXiv)

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 tildeO(log(1/δ)/varepsilon2) factors slower than regular training and inference, respectively. The storage requirements are those of tildeO(log(1/δ)/varepsilon2) 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.