# Certified Approximation for Interpretable Representer Landmarks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 57 references that are in the map.
- First posted on arXiv 30 Sep 2026.

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

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Barlow Twins: Self-Supervised Learning via Redundancy Reduction](https://mlsanity.com/paper/2103.03230/) (2021)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning](https://mlsanity.com/paper/2105.04906/) (2021)
- [Understanding Dimensional Collapse in Contrastive Self-supervised Learning](https://mlsanity.com/paper/2110.09348/) (2021)
- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [TRAK: Attributing Model Behavior at Scale](https://mlsanity.com/paper/2303.14186/) (2023)
- [Influence Functions in Deep Learning Are Fragile](https://mlsanity.com/paper/2006.14651/) (2020)
- [Limitations of the Empirical Fisher Approximation for Natural Gradient Descent](https://mlsanity.com/paper/1905.12558/) (2019)
- [Representer Point Selection for Explaining Deep Neural Networks](https://mlsanity.com/paper/1811.09720/) (2018)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Sketching Curvature for Efficient Out-of-Distribution Detection for Deep Neural Networks](https://mlsanity.com/paper/2102.12567/) (2021)
- [A Fast, Well-Founded Approximation to the Empirical Neural Tangent Kernel](https://mlsanity.com/paper/2206.12543/) (2022)
- [ViViT: Curvature access through the generalized Gauss-Newton's low-rank structure](https://mlsanity.com/paper/2106.02624/) (2021)
- [A Bayesian Approach To Analysing Training Data Attribution In Deep Learning](https://mlsanity.com/paper/2305.19765/) (2023)
- [Efficient Sketches for Training Data Attribution and Studying the Loss Landscape](https://mlsanity.com/paper/2402.03994/) (2024)
- [Distributed Adaptive Sampling for Kernel Matrix Approximation](https://mlsanity.com/paper/1803.10172/) (2018)
- [Block subsampled randomized Hadamard transform for low-rank approximation on distributed architectures](https://mlsanity.com/paper/2210.11295/) (2022)
- [Imperfect Influence, Preserved Rankings: A Theory of TRAK for Data Attribution](https://mlsanity.com/paper/2602.01312/) (2026)
- [oASIS: Adaptive Column Sampling for Kernel Matrix Approximation](https://mlsanity.com/paper/1505.05208/) (2015)
- [Interpretable Self-Supervised Learning via Representer Landmarks and Nystr"om Approximation](https://mlsanity.com/paper/2509.24467/) (2025)
- [A Unified Theory of Random Projection for Influence Functions](https://mlsanity.com/paper/2602.10449/) (2026)

## Abstract (arXiv)

Representer explanations rank the training landmarks that most influence a self-supervised representation. At scale, this ranking rests on up to four stacked approximations of the empirical neural tangent kernel (eNTK). These are random output heads, a parameter sketch, landmark sampling and a coefficient fit. Existing analyses bound each approximation separately, but none certifies the top-K set against their combined error. We introduce CAIRN (Certified Approximation for Interpretable Representer laNdmarks), a framework that carries this error through to the ranking. We derive the exact variance of the sketched multi-head eNTK, which matches measurement within 4% where Johnson-Lindenstrauss bounds err by up to 2.5×. This yields a high-probability top-K certificate for a fixed coefficient fit, alongside exact residual-trace certificates for discarded spectral mass. An exact product-variance identity separates kernel error from fit variability and identifies when a larger kernel budget can still sharpen a ranking. Stochastic Lanczos Quadrature (SLQ) estimates the effective dimension within 0.72% and guides the landmark budget without dense eigendecomposition. We show that residual mass does not control class coverage, and residual-greedy selection cuts the worst coverage excess of k-means++ from 8.5× to 1.55× (4× on the sketched eNTK). Cross-view initializers outperform principal-component initialization in five (AUI) to all six (CSI) settings. Against the KREPES Gauss-Newton solver, CAIRN converges 2.5 to 11.3× faster, trails by at most 0.31 points and gains up to 3.14 points on MNIST. Together, these results make the reliability of representer explanations measurable and show where approximation budgets are best spent.