Certified Approximation for Interpretable Representer Landmarks

Abstract

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\times$. 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\times$ to $1.55\times$ ($4\times$ 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\times$ 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.