Sketching Learning Algorithms: From Data Deletion to Causal Attribution

How do we know whether a specific image in a training set caused a generative model to produce a particular output? This question sits at the intersection of machine learning interpretability, privacy law, and causal inference. Traditionally, answering it required retraining the model from scratch without the suspect data, a prohibitively expensive operation for modern deep learning systems. In the recent preprint "How to sketch a learning algorithm", Sam Gunn introduces a framework that may change this calculation entirely, offering a method to predict model behavior under counterfactual data deletion with only polynomial overhead in the inverse error.

The Technical Machinery: Stability and Complex Derivatives

Gunn frames the problem as data deletion, a formalization that differs subtly from the related field of machine unlearning. While unlearning focuses on approximately removing the influence of data from a model, data deletion aims to predict, with arbitrary precision ε, what a measurement of the model would have been had a subset of training data never been included. The framework rests on three pillars: an arithmetic circuit representation of the learning algorithm, a stability assumption about the model's sensitivity to training data perturbations, and a novel local sketching technique using higher-order automatic differentiation.

The arithmetic circuit formulation is crucial for rigor. Rather than treating the learning algorithm as a black box, Gunn models it as a composition of arithmetic operations mapping training data downweights to model parameters. This captures standard training procedures like stochastic gradient descent, where the algorithm iteratively updates parameters based on per-example losses. The downweight vector w ∈ R^n encodes which examples are included; setting w_i = 1 effectively deletes example i from training.

The stability assumption quantifies how sensitive a measurement function ϕ (mapping model parameters to a scalar, such as the probability of generating a specific output) is to small changes in the training data. In its weaker form, stability requires that the kth order derivatives of ϕ with respect to the downweights are bounded by k! times a constant factor. This allows for a Taylor expansion around the full training set that converges sufficiently quickly. Unlike previous theoretical approaches that required strong convexity or other constraints incompatible with deep learning, stability appears empirically plausible for actual neural networks.

The technical innovation enabling efficient computation is local sketching via higher-order derivatives in random complex directions. Rather than computing the full tensor of higher-order derivatives, which would be exponentially expensive, Gunn's method uses forward-mode automatic differentiation to compute directional derivatives along random vectors in complex space. This yields a compressed representation, or sketch, of the learning algorithm's behavior in a neighborhood of the training data. The precomputation phase requires only poly(1/ε) times the cost of standard training, and the storage requirement is equivalent to storing poly(1/ε) copies of the model. Prediction for a deletion set of size d requires only d · poly(1/ε) times the cost of a single forward pass.

From Unlearning to Causal Certificates

The immediate application is machine unlearning, but the deeper implications concern causal attribution. Current approaches to determining training data influence, such as influence functions, provide first-order approximations that break down when removing multiple data points or when the loss landscape is highly non-convex. They answer the question "how would the loss change if we slightly downweighted this example?" rather than "what would the model output be if this example never existed?"

Gunn's scheme bridges this gap. After precomputation, one can query the prediction algorithm to obtain ϕ(A(T \ D)), the exact counterfactual measurement, with error bounded by O(ε) for constant deletion set size d, or with error depending on the strength of the stability assumption for arbitrary d. This is not an approximation of unlearning; it is a compression of the counterfactual itself.

Consider the legal implications. Under emerging AI liability frameworks, courts may need to determine whether a specific copyrighted work in a training corpus caused a generative model to infringe. Currently, this requires either statistical correlation analysis, which cannot establish causation, or expensive retraining campaigns. Gunn's framework suggests a third path: a deletion certificate proving that the probability of generating the suspect output would have been within ε of the observed probability even if the copyrighted material had been excluded. Such certificates could be generated in polynomial time rather than requiring weeks of GPU cluster time for retraining.

Limitations and the Path Forward

Despite the theoretical elegance, several caveats temper immediate enthusiasm. The stability assumption, while empirically validated on microgpt (a small transformer model), remains unproven for large-scale production systems like GPT-4 or Claude. Deep learning exhibits phase transitions and emergent capabilities; it is conceivable that certain measurements become unstable when training data crosses critical thresholds, violating the smoothness required for the Taylor expansion.

The storage costs also warrant scrutiny. While poly(1/ε) is polynomial, for high-precision applications where ε = 0.01, storing even 100 model copies may be prohibitive for trillion-parameter systems. The scheme trades computational efficiency for space efficiency in a manner that may not yet be economically viable for the largest models, though it remains vastly superior to naive retraining.

Furthermore, the method assumes white-box access to the learning algorithm and the ability to instrument training with complex arithmetic. This excludes certain proprietary training pipelines or federated learning scenarios where data never concentrates in a single location. The restriction to arithmetic circuits, while general enough to capture SGD and its variants, may not extend to training procedures involving discrete operations or external tool use.

My own view is that this work represents a shift from post-hoc interpretability to pre-computed accountability. Rather than inspecting a finished model and attempting to reverse engineer which data influenced it, Gunn's approach requires foresight during training to construct the sketch. This aligns with a broader trend in AI governance toward auditability by design. The method essentially stores a compressed representation of the training process's higher-order geometry, allowing for efficient counterfactual queries later.

The connection to causal inference is particularly rich. By treating data deletion as an intervention on the training process, the sketch provides a way to compute the effect of do-operators in Pearl's causal hierarchy without rerunning the generative process. The random complex directions method resembles techniques from randomized numerical linear algebra, suggesting potential cross-pollination with sketching algorithms for matrix approximation.

Conclusion

Gunn's data deletion scheme offers the first rigorous, efficient method for predicting model behavior under arbitrary training data exclusions in the deep learning regime. By leveraging the stability assumption and complex directional derivatives, it reduces the computational cost of causal counterfactuals from exponential to polynomial in the precision parameter. The experiments with microgpt provide proof of concept, though scaling to industrial systems remains an open challenge.

Several questions remain for future work. Can the stability assumption be characterized in terms of more familiar quantities like the Hessian condition number or sharpness of the loss landscape? Can the storage requirements be reduced via more aggressive compression of the derivative sketches? And perhaps most urgently, how will legal systems adapt to the possibility of mathematically rigorous deletion certificates?

If these technical hurdles can be cleared, we may be approaching a future where AI systems are not only powerful but provably accountable, where the causal chain from training data to any output can be audited in polynomial time. For a field increasingly concerned with alignment and liability, that would be a welcome development indeed.