Certified Approximation for Interpretable Representer Landmarks

Jayanta Mukherjee; Shourya Verma; Mengbo Wang; Jasorsi Ghosh; Ananth Grama

cs.LGSep 30, 2026

Certified Approximation for Interpretable Representer Landmarks

Authors: Jayanta Mukherjee, Shourya Verma, Mengbo Wang, Jasorsi Ghosh, Ananth Grama

Organizations: Department of Computer Science Purdue University West Lafayette, IN 47907, USA

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.

Figures & tables

Panel of Figure 1 — Figure 1: CAIRN pipeline. Stage 1 sketches the eNTK and selects landmarks by residual-greedy pivoted Cholesky under a $d_{\rm eff}(\lambda)$ budget. Stage 2 fits the coefficients from one of four initializers, and Stage 3 ranks landmarks by $I_{\ell t}$ . Stage 4 certifies the top- $K$ set, flags fit-limited rankings and audits scores by deletion.

Figure 2: Error model and certificates. (a) Measured over predicted SRHT variance ( $P=256$ , $s=32$ ). (b) Finite-population correction. (c) Score spectrum at one query. (d) Plug-in Chebyshev thresholds; the fit floor is $28\times$ the top- $5$ gap.

Dataset	Objective	CAIRN	KREPES	$\Delta$	CAIRN	KREPES	Speedup	CAIRN / KREPES
		Accuracy (%)			Time to converge (s)			Identifiability
Adult	Barlow Twins	84.10 $\pm$ 0.01	84.01	+0.09	0.994	10.5	10.5 $\times$	83 / 73
Adult	SimCLR	84.08	84.35	-0.27	2.04	7.76	3.8 $\times$	97 / 93
Adult	VICReg	84.02	84.33	-0.31	1.57	17.9	11.3 $\times$	83 / 57
MNIST	Barlow Twins	96.30	96.31	-0.01	1.39	7.90	5.7 $\times$	100 / 100
MNIST	SimCLR	96.10 $\pm$ 0.03	94.49	+1.61	6.10	20.4	3.3 $\times$	100 / 100

Table 1: CAIRN vs. KREPES from the same initialization. Accuracy is

k

-NN ( CAIRN : mean

\pm

s.d., three seeds). Identifiability is the best of three ranking percentiles against

30

random deletions.

Figure 3: Coverage and budget. (a,b) $\kappa_{C}$ against Nyström residual; the dotted line is the optimum $\kappa_{C}=C$ . (c) $d_{\rm eff}(\lambda)$ with power-law fits. (d) Residual on nested $k$ -means++ prefixes; stars mark $m=d_{\rm eff}(\lambda)$ .

Table 5

Figure 4: Accuracy and deletion. (a) Test accuracy across selectors (PCI-Lanczos fixed) and initializers ( $k$ -means++ fixed). (b) $k$ -NN confidence drop after deleting the top- $10$ landmarks by $\omega_{\ell}$ , Latent-Space Reselection, or $20$ random sets (bar: mean; tick: maximum).

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Definition
Network, empirical NTK and the sketched kernel
$f_{\theta}$	Frozen backbone network with parameters $\theta$ ; the eNTK is taken at this network and it is never retrained
$x,\,x^{\prime}$	Generic inputs
$d$	Number of network outputs
$P$	Number of network parameters, zero-padded to a power of two for the SRHT (the unpadded count is written out, e.g. $1864$ )
$J_{x}\in\mathbb{R}^{d\times P}$	Jacobian of the network output with respect to the parameters at $x$ , zero-padded

Appendix

Table 4: Notation: network, empirical NTK and the sketched kernel.

Symbol	Definition
Influence scores and ranking certificates
$\mathcal{Z}$ , $m$	Landmark set and its size
$x_{\ell}$	$\ell$ -th landmark, $\ell=1,\dots,m$
$x_{t}$	Query (test) point whose landmark ranking is explained
$\tilde{A},\ \tilde{A}_{0}$	Fitted Nyström coefficient matrix and its initialization; row $\ell$ is $\tilde{A}_{\ell,:}$
$\Delta\tilde{A}$	Coefficient displacement $\tilde{A}-\tilde{A}_{0}$

Appendix

Table 5: Notation: influence scores and the two ranking certificates.

Symbol	Definition
Landmark selection, residual and budget
$\mathcal{X}$ , $n$	Unlabeled data set and the number of candidate points
$M$	Landmark pool size ( $2000$ on Adult, $512$ on MNIST)
$G\in\mathbb{R}^{n\times q}$ , $q$	Selection feature matrix and its feature dimension
$\widetilde{K}=GG^{\top}$	Gram matrix of the selection features
$\psi_{h,s}(x)$	$h$ -head sketched feature map $h^{-1/2}[(SJ_{x}^{\top}w_{1})^{\top},\dots,(SJ_{x}^{\top}w_{h})^{\top}]^{\top}\in\mathbb{R}^{hs}$ , so $q=hs$

Appendix

Table 6: Notation: landmark selection, Nyström residual and landmark budget.

Symbol	Definition
Coefficient initialization
$k$	Output (latent) dimension of the coefficient fit ( $k=256$ ); also the number of retained eigenpairs
$U_{k},\ \Lambda_{k}$	Leading $k$ eigenvectors and eigenvalues of the decomposed matrix
$\epsilon$	Eigenvalue jitter; relative, $10^{-6}\max_{i}\|\lambda_{i}\|$ (KREPES’s own PCI uses absolute $10^{-6}$ )
PCI	Principal-component initialization $\tilde{A}_{0}=U_{k}(\Lambda_{k}+\epsilon I)^{-1/2}$ of the centered $K_{mm}$ (dense or Lanczos eigensolver)
$(\hat{\lambda}_{i},\hat{u}_{i})$	Approximate (Ritz) eigenpair of a symmetric matrix $A$ ( Proposition 3.9 )

Appendix

Table 7: Notation: coefficient initialization.

Symbol	Definition
Training, evaluation and identifiability
$z,\ z_{A},\ z_{B}$	Latent $K\tilde{A}+b$ ; its two-view versions $K_{A}\tilde{A}+b$ and $K_{B}\tilde{A}+b$
$b,\ b_{0}$	Bias of the kernel encoder (initialized to $0.1\cdot\mathbf{1}$ ) and its initial value; $z_{0}$ is the latent at $(\tilde{A}_{0},b_{0})$
$\ell,\ \mathcal{L}$ (Alg. 3 )	Self-supervised loss (BT, SimCLR, VICReg, BYOL) and its batch value
$\iota,\ T,\ p$	Initializer, number of epochs and early-stopping patience (Alg. 3 )
$\gamma,\ \gamma_{0}$ (Alg. 1 )	KREPES bias and its initial value

Appendix

Table 8: Notation: training, evaluation and identifiability.

Figure 5: Equation 9 on all $12$ landmarks of one test point , $64$ realizations. (a) Measured against predicted variance. The median ratio is $0.978$ ; landmarks range from $0.88$ to $1.14$ , within the sampling error of a variance from $64$ draws. (b) Shares of the predicted variance: kernel term $83$ to $89\%$ , weight term $8$ to $14\%$ , cross-term a median $2.7\%$ . The cross-term is present under exact independence and is small because $\omega$ has a small coefficient of variation.

Setting	Value
Output dimension $k$	$256$
Epochs / patience	$20$ / $7$
Batch size	$512$
Learning rate / weight decay	$1.25\times 10^{-2}$ / $3.0\times 10^{-5}$
BT off-diagonal weight	$35$
VICReg $(\lambda,\mu,\nu)$	$(1.85,\,1.61,\,0.161)$

Appendix

Table 9: Stage 2 settings.

Dataset	Objective	CAIRN	KREPES	CAIRN	KREPES	CAIRN	KREPES	stability
		$\lVert A-A_{0}\rVert$		Contribution		Leave-one-out		CAIRN seed
Adult	Barlow Twins	7	23	83	70	63	73	1.00
Adult	SimCLR	97	70	83	87	90	93	1.00
Adult	VICReg	0	57	83	57	67	33	1.00
MNIST	Barlow Twins	100	100	100	100	93	87	0.97
MNIST	SimCLR	100	100	100	0	100	0	1.00

Appendix

Table 10: Landmark identifiability for every ranking. Each cell is the percentile of the ranking’s top-landmark deletion effect (drop in

k

-NN confidence) among 30 random deletions of the same size, median over seeds; bold : at least 95%, i.e. one-sided

p<0.05

. Seed stability: median Jaccard overlap of CAIRN’s top landmarks (

\lVert A-A_{0}\rVert

ranking) across seeds; KREPES is deterministic.

Figure 6:

k

-NN test accuracy against optimization wall-clock time for CAIRN (blue; one line per seed, three seeds) and KREPES (red; one marker per CG iterate) on Adult (top) and MNIST (bottom). Both methods optimize the same objective from the same initialization, on the same GPU in float32. Dashed grey line: initialization accuracy. Dotted black line: CAIRN’s final accuracy. CAIRN settles within about

2.6

s on Adult and

7

s on MNIST. KREPES first incurs a setup cost (gradient pass and preconditioner) before its first iterate, then oscillates on Adult and degrades well below the initialization on MNIST SimCLR and VICReg.

Figure 7: Relative residual of KREPES’s preconditioned conjugate-gradient solve against CG iteration, on a log scale, for Adult (left) and MNIST (right). No objective converges to a tight tolerance within

150

iterations. Adult Barlow Twins plateaus near

0.2

. SimCLR reaches about

10^{-2}

but oscillates by up to an order of magnitude between iterations. MNIST VICReg stops after

20

iterations at about

0.04

. The inexact solves account for the non-monotone KREPES trajectories in Figure 6 .

	Random	$k$ -means++	DPP	$k$ -center	PC-NTK	PC
MNIST	0.526	0.514	0.511	0.665	0.691	0.648
Adult	2.012	1.981	1.988	3.327	4.168	2.065

Appendix

Table 11: Relative Nyström residual

\tr(R)/\tr(K)

(%) by selector.

Dataset	Loss	Acc (%)	$\kappa_{C}$	Classes seen
Adult	BT	81.59	9	2/2
	SimCLR	81.98	2	2/2
	VICReg	81.43	21	2/2
MNIST	BT	90.64	91	10/10
	SimCLR	93.30	73	10/10
	VICReg	93.23	41	10/10

Appendix

Table 12: Test accuracy and

\kappa_{C}

, Kaiming initialization,

k

-means++ landmarks.

\kappa_{C}

is not comparable across class counts. ∗ Collapsed: top two classes take

\geq 75\%

of predictions.

Figure 8: Proposition 3.2 on a real eNTK block ( $r_{\rm tr}(\bar{M})=7.9$ , $p=1864$ unpadded parameters, $d=8$ , $96$ draws per cell, $19$ $(h,s)$ cells). (a) Measured relative variance with 95% CI against a prediction that uses an $h$ -independent JL surrogate for the parameter axis (dashed). Dotted lines mark the output term $2/(h\,r_{\rm tr})$ . (b) Measured over predicted. The unsketched cells ( $s=\infty$ ) give $1.03$ , $1.07$ and $0.99$ . The sketched cells run from $1.27$ at $h=1$ to $0.24$ at $h=16$ , because the surrogate lacks the $1/h$ term of Eq. 4 .

Explore similar work

Probabilistic Linear Explanations
Sep 16, 2026Frederic Koriche, Jean-Marie Lagniez, Chi TranExplainability Explainable AI Methods
Computer science Research Institute of Lens (CRIL), UMR CNRS 8188, University of Artois, Rue Jean Souvraz SP 18, Lens, F-62307, France
Beyond Correlation: Learning Supervised, Sample-Distinct, and Eigenimage-Interpretable Representations
Jul 22, 2025Mojtaba MoattariDimensionality Reduction Face Recognition Model
Independent Researcher
ICON Decomposition: Auditing deep neural networks for shortcuts by decomposing layer-wise representations using concepts
Aug 26, 2026Roshan Prakash Rane, Marco Simnacher, Manuel Pfeuffer +7Explainability Shortcut Learning
Hertie Institute for AI in Brain Health, University of Tübingen, Tübingen, Germany. · Department of Psychiatry and Neurosciences, Charité - Universitätsmedizin Berlin, Berlin, Germany. · Department of Psychology, Humboldt-Universität zu Berlin, Berlin, Germany. +5

Sep 16, 2026, cs.LGJ/K move · Enter open · S save

Probabilistic Linear Explanations

Frederic Koriche, Jean-Marie Lagniez, Chi Tran

Computer science Research Institute of Lens (CRIL), UMR CNRS 8188, University of Artois, Rue Jean Souvraz SP 18, Lens, F-62307, France

Explainability Explainable AI Methods Sparsity

Open paper AskPDF arXiv

Formal explainability provides mathematically grounded justifications for individual predictions. However, abductive explanations often exceed human cognitive limits by involving too many features, while probabilistic relaxations have remained largely limited to categorical classification. We present a unified framework for probabilistic explainability based on sparse, anchored linear models, applicable to both binary classification and continuous regression. By mapping instances to the Boolean hypercube, our linear explanations strictly generalize subset-based approaches: they capture both the magnitude and direction of feature contributions while enforcing a prescribed sparsity budget

k

. We show that minimizing the relevance error for such explanations is \ClassNPPP-hard when the underlying model is a neural network, and we relate this intractable objective to a tractable surrogate---the fidelity error. For a parameterized family of local distributions, the relevance error of any

k

-sparse explanation is bounded by its fidelity error up to a multiplicative factor that remains small locally. We address the resulting empirical problem using two complementary approaches: a Mixed Integer Programming (MIP) formulation that yields provably optimal empirical solutions while maintaining polynomial sample complexity, and a polynomial-time Iterative Hard Thresholding (IHT) algorithm with provable approximation guarantees. Empirical evaluations show that, unlike state-of-the-art baselines such as LIME and MAPLE, our explanations satisfy both the anchoring and sparsity constraints by construction, while consistently achieving lower relevance error.

Abstract

Explore similar work

Probabilistic Linear Explanations

Beyond Correlation: Learning Supervised, Sample-Distinct, and Eigenimage-Interpretable Representations

ICON Decomposition: Auditing deep neural networks for shortcuts by decomposing layer-wise representations using concepts