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

Sep 16, 2026cs.LG

Probabilistic Linear Explanations

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.

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

Ask PDF

Jul 22, 2025cs.LG

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

Conventional dimensionality reduction methods mainly optimize variance or correlation, leaving statistical dependence, data diversity, contrast, and interpretability under addressed. We propose three new independence criteria for designing supervised and unsupervised dimensionality reduction (DR) methods, aiming to improve feature extraction and representation quality. Our framework combines linear and nonlinear formulations and is evaluated using contrast, classification accuracy, and interpretability measures. The interpretability of eigenfaces helps to effectively summarize dominant class-specific structures and trends within representative images. Evaluated on MNIST and a Gender face dataset for classification and reconstruction, our methods achieve significant improvements in contrast (up to

+

20.1%), accuracy (up to

+

17.4%), and interpretability (up to

+

120.0%) over Principal Component Analysis (PCA), t-distributed Stochastic Neighbor Embedding (t-SNE), Linear Discriminant Analysis (LDA), and Variational Autoencoder (VAE) baselines, while also improving VAE reconstruction performance by 9.5%. These results suggest a promising direction for interpretable representation learning based on statistical dependence and independence criteria.

Mojtaba Moattari

Independent Researcher

Dimensionality Reduction Face Recognition Model Interpretability Semi-Supervised Learning Spurious Correlations

Ask PDF

Aug 26, 2026cs.LG

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

Deep neural networks often exploit spurious associations, a failure known as shortcut learning. Before deployment, models should be audited for reliance on a set of concepts, such as acquisition artifacts or demographics. Current methods, such as linear probes and concept activation vectors, measure reliance by asking whether each concept, in isolation, is decodable from a layer. Their scores therefore reflect not only reliance but also correlations in the audit dataset. We introduce Independent Canonical cONcept (ICON) decomposition, which quantifies the share of a layer's variance each concept explains, conditional on all other concepts and the outcome. ICON scores are variance shares, comparable across layers and between continuous and categorical concepts. ICON also reports the share the set leaves unexplained. On simulated data, ICON recovers the true importance more accurately than seven baselines. On skin-cancer and neuroimaging models, ICON distinguishes learned shortcuts from correlated concepts, confirmed by retraining and out-of-distribution tests.

Roshan Prakash Rane, Marco Simnacher, Manuel Pfeuffer +7

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

Explainability Shortcut Learning Model Auditing Out-Of-Distribution

Ask PDF