acceptodds
Under review as a conference paper at ICLR 2027

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- set against their combined error. We introduce (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 where Johnson–Lindenstrauss bounds err by up to . This yields a high-probability top- 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) slq-saad estimates the effective dimension within 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 -means++ from to ( 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, converges to faster, trails by at most points and gains up to points on MNIST. Together, these results make the reliability of representer explanations measurable and show where approximation budgets are best spent.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Self-Supervised Learning, Representation Learning, Neural Tangent Kernel, Nyström Approximation, Randomized Numerical Linear Algebra, Landmark Selection, Error Bounds

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_WxoTOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Representer explanations rank the training landmarks that most influence a self-supervised representation. This ranking generally rests on several stacked approximations. Existing analyses bound each approximation separately, but none certifies the top-K set against their combined error. The authors introduce CAIRN (Certified Approximation for Interpretable Representer laNdmarks), a framework that carries this error through to the ranking. These results make the reliability of representer explanations measurable and show where approximation budgets are best spent.

The paper is so hard to follow that I am not able to assess the novelties. I think that this paper is suitable for experts only. Hence, I think that the audience for this paper is very limited in its current state.

Critical strengths

Certifying the top-K set against their combined error is a great idea. It is well known that controlling each error separately does not warrant an accurate global bound.

The authors propose a lot of theoretical results to analyse each part of the proposed pipeline. Calculating theoretical bounds is still very appreciable.

Critical weaknesses

This paper is very hard to follow. I think it is suitable for experts only. The authors do not motivate clearly their work. They do not describe carefully KREPES in the main part of the document. The already published methods KREPES seems to be the main source of motivation.

In Theorem 3.1 for example, the authors propose to compute a variance. I do not figure out what is the role of this variance and why its calculation is relevant. The same comment holds for almost of the results.

The paper gives the feeling to be a collection of results without any clear guide. In other words, the problem addressed in the paper is not well stated. It is very complicated to assess the quality of the paper and its potential impact.

Questions for authors

Clarification request.

  1. The authors should present KREPES in the main part of the paper to clearly motivate their work.

  2. They should also present more clearly the elements composing their pipeline. Figure 1 is a useful addition, but its interpretation remains challenging.

  3. They should explain why their calculations are useful instead of adding more and more technical details that do not help to understand the main contributions of the paper.

5 comments
AuthorsOpenReview ↗

Response to Reviewer WxoT

We thank Reviewer WxoT for the feedback. We have uploaded a revised paper (new text in blue) that addresses each point. Responses to each critical weakness (CW) and question (Q) follow.

CW (Motivation and overall presentation).

  • Motivation. The Introduction now starts from a practical question: when can a top-K explanation be trusted, motivated by the need to identify which training examples shaped a self-supervised representation (e.g., to audit or remove problematic data). Representer methods provide ranked explanations, but at scale these rankings depend on randomized approximations, and a small kernel error alone does not guarantee a reliable top-K ranking.

  • Problem and Roadmap. Section 3 now states the problem formally and introduces a Pipeline paragraph and Roadmap connecting the theoretical results to the final certificate. Section 3.1 defines output heads and Section 3.2 defines the δ\delta-certificate (Definitions K.1–K.2, App. K).

  • Experiments. Section 4 opens with four questions: whether CAIRN matches KREPES at lower cost (Table 2), whether the error model is accurate (Figure 2), how often top-KK sets certify (Table 5, Figure 2(d)), and how initialization and landmark selection affect the explanations (Tables 3–4, Figures 3–4). Table 1 and Table 13 provide the experimental protocol for main-text and appendix results.

  • Worked example. An illustrative example in App. C (Figure 5, Tables 11–12) walks through all four stages with 18 training points, three classes, and six landmarks.

Q1 (KREPES in the main text). A dedicated Background paragraph at the start of Section 3 now introduces KREPES. It explains its eNTK expansion over landmarks, PCI initialization using the leading eigenvectors of the landmark Gram matrix, one Gauss–Newton step on the SSL loss, and coefficient-displacement ranking.

  • CAIRN retains the KREPES model and score while adding an error analysis for the resulting rankings.

  • The full KREPES algorithm is in App. E (Algorithm 1), and its results are reproduced in App. I (Table 23).

Q2 (Pipeline and Figure 1). The Figure 1 caption has been revised, and the new Pipeline paragraph has been added in Section 3 to explain the four stages:

1. Landmark selection: Approximate the eNTK using random output heads and an optional SRHT sketch, then select landmarks using an effective-dimension budget.

2. Coefficient fitting: Fit landmark coefficients to the SSL objective using one of four initializers.

3. Influence ranking: Rank landmarks for each query using kernel similarity and coefficient displacement.

4. Certification and audit: Certify the top-K set when the score intervals separate; otherwise, identify whether coefficient-fit variability limits certification. A deletion audit provides an independent empirical check.

The two arrows beneath the pipeline distinguish the sources of uncertainty: kernel approximation variance determines the score-error radii, while coefficient-fit variance can impose a floor on certification.

Q3 (Practical value of the theoretical analysis). The revised Section 3 introduces each result through the practical question it addresses, with proofs in App. D. Table 25 (App. K) states each result in plain language, with the prior work it builds on and what CAIRN adds.

  • Theorem 3.1 gives the exact variance of a sketched kernel inner product, quantifying the uncertainty in an approximated kernel entry.

  • Proposition 3.2 separates output-head and sketch randomness, showing how the number of heads and sketch width affect that uncertainty.

  • Theorem 3.3 turns the variance estimates into score-error radii and certifies the top-K set when the selected and excluded score intervals separate. The guarantee is conditional on the query, landmark set, and coefficient fit.

  • Theorem 3.4 shows how variability across repeated coefficient fits can impose a floor on the certificate radius. In that case, a wider sketch alone may not help. This limits the certificate but does not imply that the ranking is wrong.

  • Sections 3.3 and 3.4 examine two further practical choices: landmark selection, where a small Nyström residual does not necessarily ensure class coverage, and coefficient initialization, including lower-memory Lanczos and cross-view alternatives to dense PCI.

Together, these results connect randomized kernel approximation to a high-probability statement about the final ranking. The practical results support this purpose: paired MoM certifies 83–88% of top-1 explanations on Adult and 32–57% on MNIST, compared with at most 21% for the basic Chebyshev certificate. None of the 274,728 issued certificates disagreed with their corresponding exact-kernel ranking (Table 5, App. H.3).

These changes aim to make the paper accessible beyond kernel-method specialists. We would be grateful if the reviewer would reconsider their evaluation in that light.

Reviewer_WxoTOpenReview ↗

Response to Authors

Thank you for your detailed response.

CW: The motivation for your work has been significantly improved by your revisions. However, the concept of certification remains rather obscure. There is no clear mathematical definition of what you mean by a certification. Your paper is still clearly aimed at experts in the field. As someone who is not an expert in certification, I find many of your results difficult to understand, despite having a substantial background in statistics and probability.

Q1: KREPES is now better explained. I have reread the paper that introduced KREPES:

Maedeh Zarvandi, Michael Timothy, Theresa Wasserer, and Debarghya Ghoshdastidar. Interpretable self-supervised learning via representer landmarks and Nyström approximation. In Forty-third International Conference on Machine Learning, volume 306 of PMLR, 2026.

In my opinion, this paper is still more accessible than yours in its current form. For example, the experiments in the KREPES paper help readers visualize the landmarks. Your paper would benefit from similar efforts to make the underlying concepts and results more accessible.

Q2: The pipeline is now clearer. Thank you.

Q3: To be honest, I appreciate your efforts to provide interpretations of your results, but I am not sure that they help me very much. For example, you write that "Proposition 3.2 separates output-head and sketch randomness, showing how the number of heads and sketch width affect that uncertainty." However, after carefully searching your paper for the term "head", I could not find a definition of this concept. Consequently, the notion of a "Gaussian head" remains a mystery to me.

Without a clear definition, I cannot relate this concept to other existing results in the literature, nor can I properly assess the novelty and relevance of the proposition. The same comment applies to several other results in the paper.

In conclusion, I genuinely appreciate your efforts to improve the paper and address my questions. However, I am still unable to clearly identify the novelty and assess the relevance of your contributions.

AuthorsOpenReview ↗

Response to Reviewer WxoT

We thank Reviewer WxoT for rereading the paper and for the constructive feedback. Changes are marked in blue in the revised PDF.

CW: What is a certificate? Section 3.2 now defines the term formally. Fix an instance F\mathcal F (data, backbone, landmarks, initialization, fitted coefficients, and query), with reference set Tref=TopK(I⋅tref)T^{\rm ref}=\mathrm{Top}_K(I^{\rm ref}_{\cdot t}). A rule based on randomized scores I^⋅t\widehat I_{\cdot t} either returns a KK-landmark set T^\widehat T or abstains. It is a δ\delta-certificate if

Pr⁡(certificate issued and T^≠Tref∣F)≤δ,\Pr\big(\text{certificate issued and }\widehat T\neq T^{\rm ref}\mid\mathcal F\big)\le\delta,

with probability over the heads and sketch used in evaluation. Thus, the chance of issuing a wrong set is at most δ\delta. Here δ∈(0,1)\delta\in(0,1) is an error budget chosen by the user before any evaluation draw; all real-data results use δ=0.05\delta=0.05, i.e., at most a 5%5\% chance of issuing a wrong set, or 95%95\% confidence per query. The reference is fixed by F\mathcal F. The guarantee does not cover landmark-selection variability or compare with the full-training-set ranking.

Theorem 3.3 uses simultaneous Chebyshev intervals: CAIRN issues a set only if every selected landmark's lower bound exceeds every excluded landmark's upper bound. This builds on rank confidence sets (Mogstad et al., 2024), with widths from our exact variance analysis. App. K gives Definition K.2, a five-step procedure, and the three outcomes (certified, uncertified, fit-limited).

Q3: What is an output head? Section 3.1 now opens with an output-heads paragraph that defines it (Definition K.1 in App. K). For inputs x,x′x,x', the eNTK is the d×dd\times d matrix M=JxJx′⊤M=J_xJ_{x'}^\top, where Jx=∂fθ(x)/∂θJ_x=\partial f_\theta(x)/\partial\theta. An output head w∈Rdw\in\mathbb R^d forms the scalar output w⊤fθ(x)w^\top f_\theta(x), with gradient Jx⊤wJ_x^\top w and scalar kernel kw(x,x′)=w⊤Mw.k_w(x,x')=w^\top M w.

One head needs one backward pass rather than all dd output Jacobians. A Gaussian head draws w∼N(0,d−1Id)w\sim\mathcal N(0,d^{-1}I_d); averaging hh independent heads estimates k⋆(x,x′)=tr(M)/dk^\star(x,x')=\mathrm{tr}(M)/d without bias. "Head" means a random direction in output space, not a trained layer, a projection head (as in SimCLR or BYOL), or an attention head. This construction follows Lee et al. (2020) and KREPES; it differs from the deterministic sum-output pseudo-NTK of Mohamadi et al. (2023). KREPES uses h=1h=1.

This clarifies Proposition 3.2:

  • Known: Without sketching (s=Ps=P), the output-axis variance 2∥Mˉ∥F2/(hd2)2\lVert\bar M\rVert_F^2/(hd^2) is the classical Gaussian Hutchinson variance (Hutchinson, 1990; Avron & Toledo, 2011).

  • New: With one SRHT sketch shared across heads, the parameter-axis variance contains c(s)Φ(Cˉ1)c(s)\Phi(\bar C_1), where c(s)=(P−s)/((P−1)s)c(s)=(P-s)/((P-1)s). This term does not decrease with hh, so adding heads alone cannot remove all sketch error.

Prior work and what CAIRN adds. Section 3 adds citations, and Table 25 (App. K) lists, for each result, its foundations and what CAIRN adds.

Q1: Making the results easier to see. Figure 2(d) shows two MNIST queries and their top-5 landmark images: one has both top-1 and top-5 certified; the other has top-1 certified, but top-5 abstains because ranks 5 and 6 are too close (gap/radius 0.580.58). Figure 12 (App. K) shows four more cases, including a wrong sketch-ranked-first landmark for which the certificate abstains. App. C walks through all four stages on 18 points, three classes, and six landmarks.

Scope of real-data results. None of the 274,728274{,}728 certificates (Table 5; App. H.3) was incorrect. All use the fixed head of Section 3.1 and are checked against its exact kernel KfixK^{\rm fix}. They control sketch error, not head error (Section 4; Remark H.1); Theorem 3.3 also covers fresh-head randomness.

Novelty and relevance. Prior work bounds individual approximation errors or reports empirical ranking preservation (Hu et al., 2026; Tong et al., 2026). CAIRN propagates approximation uncertainty, including coefficient-fit variability, to the final landmark ranking, and returns a top-KK set with a stated error probability or abstains. As mentioned in the Introduction, CAIRN’s novelty is not a new sketching primitive but propagating approximation uncertainty, including a coefficient-fit component, to the final landmark ranking. The Introduction summarizes our contributions, both novelties and performance gains: an exact error model, certificates and the fit floor, the residual-versus-coverage distinction, cross-view initializers, and speed-ups of 28-32× on Adult and 3.8-4.3× on MNIST over KREPES.

We would be grateful if the reviewer would reconsider their evaluation in light of these changes.

Reviewer_RVDiOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper discusses ranking training landmarks in self supervised representations and proposes a framework for certifying the top-K set against their approximation error. The authors identify four sources of approximation error viz., random output heads, a parameter sketch, landmark sampling, and a coefficient fit. The authors note that prior art analyzes these four stacked approximations separately but does not provide any guarantees regarding the top-K set against the combined error. The framework proposed in the paper claims to mitigate this by deriving exact variance expressions for the sketched multi-head (eNTK) and propagates the resulting uncertainty to landmark influence scores. The authors provide theoretical justification and empirical evidence to demonstrate the effectiveness of their approach.

Critical strengths
  1. The paper discusses an important problem of reliability of landmark based explanations in self-supervised learning.
  2. The proposed framework performs meaningful extension of KREPES approach but introducing uncertainty aware certifications of the top-K landmark set.
  3. The authors have gone beyond certification by analyzing landmark selection, budget and initialization.
  4. The paper provides theoretical justifications and empirical evidence to claim the effectiveness of their framework.
Critical weaknesses

Weaknesses:

  1. The authors have identified landmarks as one of the sources of approximation error but in Line 224-230 the authors state that the landmarks are fixed. Therefore, it’s unclear whether the certification considers the approximation error arising from landmarks. The authors should clarify whether their certification guarantees are conditional on a fixed landmark set or takes into account the variability introduced by different landmark sets.

  2. Although the paper provides extensive experiments, but the authors do not report systematic empirical success rates for the proposed top-K certification on real-world datasets like MNIST and Adult. Figure 2 shows a failure case. The authors can report the fraction of queries where certification succeeds across different landmark budgets, values of K, and approximation settings etc. to strengthen the paper.

Minor weakness:

  1. There is no reference to Table 1 in lines 370-410 also, there is no reference to Figure 4 in lines 432-455 and it may confuse readers.
Questions for authors

Please address the weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer RVDi

We thank Reviewer RVDi for the thoughtful feedback. We have uploaded a revised paper (new text in blue). We respond to each critical weakness (CW) below.

CW1 (Does the certificate account for landmark error?). No. The formal certification guarantee is conditional on the realized landmark set and does not account for variability introduced by landmark selection. We have clarified this in the Problem paragraph (Section 3), defined the δ\delta-certificate conditional on this instance in Section 3.2, and formalized it in Remark H.1. Landmark sensitivity is evaluated separately by resampling (Table 14, App. F), and every half-pool certificate agrees with its own exact-kernel reference (App. H.3).

Theorem 3.3 controls fresh output-head and sketch randomness for a fixed query, landmark set, and coefficient fit. It bounds the probability of issuing an incorrect certificate relative to the exact-kernel ranking over that same landmark set. It does not guarantee agreement with a full-training-set ranking or invariance across different landmark sets. Since the guarantee holds for each admissible fixed instance, it also bounds incorrect issuance averaged over randomly drawn landmark sets, provided the evaluation randomness is drawn independently.

  • Landmark sensitivity. We refit on five random subsets of the original landmark pool (50% on MNIST, 75% on Adult) and compare per-query top-KK sets on the landmarks shared by each pair (Table 14, App. F). Jaccard overlap is 0.77–0.96, lower than the 0.98–1.00 across refits on a fixed landmark set but far above chance (at most 0.05). The explanations are thus consistent, though they do depend on the selected landmarks.

  • Empirical soundness. No incorrect certificate is observed among the 223,698 half-pool or 51,030 full-pool certificates (App. H.3). This supports the conditional guarantee but does not establish agreement across landmark sets.

  • Coefficient refitting. Theorem 3.4 separately quantifies score variability across repeated coefficient fits on a fixed landmark set. This variability can impose a floor on the certificate radius, so increasing the kernel budget alone may not be enough to certify a ranking.

  • Landmark approximation quality. The Nyström residual ratio measures how well the selected landmarks represent the kernel for that landmark set (Section 3.3). It is an approximation-quality diagnostic, not part of the top-KK certificate.

The paired-SRHT experiments use the fixed-scalar-head specialization (App. H.3), conditioning on the realized head and certifying against its corresponding unsketched reference kernel. The median-of-means construction in Remark H.2 uses independent complete head-and-sketch draws. For the main certification rates and the matched empirical-Bernstein comparison, see our response to B27A CW2.

CW2 (Empirical certification rates). We now report certification success on MNIST and Adult across the requested settings (Table 5, Section 4; Tables 21–22 and Figure 10, App. H.3–H.4). Each setting uses 200 distinct test queries at 95% per-query confidence. We have also revised Figure 2. Panel (c) is a toy instance in which the top-5 set is stable across 64 refits (overlap 0.99), but refit variability puts the certificate floor 28× above the gap, so the set is correctly reported as fit-limited (Theorem 3.4) rather than certified. Panel (d) shows two MNIST queries with their top-5 landmarks: one has both top-1 and top-5 certified; the other has top-1 certified but abstains on top-5, because ranks 5 and 6 differ by only 0.58 of a radius (more in Figure 12, App. K). With paired MoM, 83–88% of top-1 explanations certify on Adult and 32–57% on MNIST, and none of the 274,728 issued certificates was wrong.

  • Systematic certification rates. The evaluation covers K∈{1,5,10}K\in\lbrace 1,5,10 \rbrace across all three SSL objectives; full sketch-width sweeps; full landmark pools (200 on Adult and 1,024 on MNIST) and five refitted half-pools (100 and 512, respectively); and Chebyshev and MoM radii with per-landmark and paired certificates. Table 22 additionally compares paired empirical-Bernstein certificates at matched budgets. Figure 10 shows that Adult top-1 certification rises from 26–42% at 65,536 rows to 83–88% at 2,097,152 rows.

  • Landmark-budget gains. With refitted half-pools, Adult per-landmark MoM top-10 certification rises from 14–19% to 20–25% (App. H.3). The Adult latent width is reduced from 128 to 100. Each configuration is evaluated against its own exact-kernel ranking.

Minor weakness (Missing references). We have added references to Table 2 (formerly Table 1) in the experiments overview, Setup paragraph, and results discussion. Figure 4 is now cited in the overview and in the discussion of panels (a) and (b).

We are glad to clarify further and would be grateful if the reviewer would reconsider their evaluation in light of the revision.

AuthorsOpenReview ↗

Response to Reviewer RVDi

We thank Reviewer RVDi for the constructive feedback. As the discussion period nears its end, we remain available to answer any further questions or requests. We would be grateful to know whether our response has addressed your concerns.

Reviewer_B27AOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the use of the empirical neural tangent kernel (eNTK) of a frozen backbone for self-supervised learning, to understand the contribution of each training data point to an arbitrary test instance. However, existing approaches rely on four approximations that may affect the resulting rankings: random output heads, landmark selection, random projection, and coefficient fitting.

This paper proposes CAIRN, a framework that introduces three major changes to KREPES: minibatch Adam-based optimization, coefficient initialization informed by self-supervised objectives, and landmark selection using pivoted Cholesky. Additionally, this paper analyzes the variance of eNTK estimates induced by random output heads and SRHT parameter sketching. Based on this analysis, the paper further constructs error bounds for landmark scores, which can be used to certify top-K landmark selections for a fixed coefficient fit. The experimental results show broadly comparable or better performance than KREPES, while requiring substantially less time for coefficient fitting.

Critical strengths
  1. The paper provides a useful framing of approximation errors in the pipeline, distinguishing four stages that can affect the resulting rankings.

  2. The proposed pipeline modifications have understandable motivations and show empirical benefits in several settings.

  3. Evaluating the stability of the final top-K set, rather than kernel approximation quality alone, is a useful perspective. The paper provides theoretical conditions under which this stability can be certified.

Critical weaknesses
  1. I find the results section hard to follow. It would be useful to clearly describe the experiments behind each figure and table. For example, I am unsure which landmark selection algorithm is used in Table 1, and I spent considerable time understanding Figure 3 and the choice of evaluation metrics.

  2. The results do not show how informative the top-K certificates are in practice. It would be useful to report how often the resulting top-K sets can actually be certified.

  3. The practical relevance of the convergence speedup is unclear. Although the paper does not report an end-to-end runtime breakdown, I suspect that landmark selection and kernel computation account for most of the overall cost, rather than coefficient fitting.

Questions for authors
  1. How different are the rankings obtained using coefficient displacement and final coefficient norms? Intuitively, if a landmark’s coefficient vector has a relatively large initial norm but a near-zero final norm, the learning process may simply have found that this example contributes little to the final representation, despite the large displacement.

  2. In Table 2, Kaiming performs best in three of the six settings. How should we interpret this result, given that Kaiming does not consider the task at hand?

  3. Could you report the overall runtime and hardware used for the experiments, so readers can better understand the benefit of accelerating coefficient fitting?

2 comments
AuthorsOpenReview ↗

Response to Reviewer B27A

We thank Reviewer B27A for the thoughtful feedback. We have uploaded a revised paper (new text in blue). We respond to each critical weakness (CW) and question (Q) below.

CW1 (Results are hard to follow). The Experiments section (Section 4) now opens with four guiding questions. A protocol table (Table 1; Table 13, App. F) reports each landmark selector, initialization, seeds, and metric for each result. The CAIRN–KREPES comparison is now in Table 2 (formerly Table 1). CAIRN uses KREPES's k-means++ selector. Figure 3 caption defines the relative Nyström residual, tr(R)/tr(K), as unexplained kernel mass, and a class-coverage metric κC\kappa_C, which counts how many influence-ranked landmarks are needed to represent every class. On Adult, four selectors have nearly identical residuals (1.98–2.07%).

CW2 (How often do top-K sets certify?).

  • Rates. The paired median-of-means (MoM) certifies 83–88% of top-1 explanations on Adult and 32–57% on MNIST, and none of the 274,728 issued certificates were incorrect (Table 5, Section 4; full results in Table 21, Figure 10 and App. H.3). We evaluate 200 test queries per setting at 95% confidence, varying K∈{1,5,10}K\in\lbrace1,5,10\rbrace, sketch width, landmark pool, radius, and certificate type. The basic Chebyshev certificate reaches 5–21% of top-1 sets on Adult and none on MNIST. On Adult, 26–42% of top-1 sets already certify with 65,536 rows.

  • Tighter certificate. At matched verification budgets (Table 22, App. H.4), paired empirical-Bernstein raises top-5 certification from 23.8% to 58.0% on MNIST and from 31.0% to 68.2% on Adult; top-1 rates rise from 51.5% to 77.0% and from 49.8% to 79.3%.

  • Correctness. None of the 274,728 issued certificates (51,030 full-pool and 223,698 refitted half-pool) disagreed with its exact-kernel reference. An independent re-implementation found no incorrect certificate among the 172,800 decisions in the matched comparison.

See our response to RVDi CW1-CW2 for the guarantee's scope.

CW3 and Q3 (End-to-end runtime breakdown). Table 2 reports kernel times and end-to-end speed-ups; Table 20 and Figure 9 (App. H.2) break down every stage. All timings use synchronized float32 measurements on one NVIDIA RTX 4090.

  • Kernel computation dominates, k-means++ takes 0.14 s on Adult and 2.0 s on MNIST, and PCI initialization takes under 10 ms. CAIRN’s batched per-sample gradients replace KREPES’s per-sample backward loop, reducing kernel time from 275 s to 7.9 s on Adult (35×) and from 62.5 s to 13.3 s on MNIST (4.7×), with a maximum relative error of 8.3×10⁻⁶ (Table 19).

  • Speedup. Coefficient Fitting is 2.5–11.3× faster. Overall, runtime falls from 283–293 s to 9.0–10.1 s for Adult (28–32×) and from 73–85 s to 17–21 s for MNIST (3.8–4.3×). Across the nine fits in Table 2, the aggregate speed-ups are 17.6× and 3.6×. Certifying 200 queries adds 2.7–3.7 s for Adult and 1–2 s for MNIST. Even including certification, CAIRN remains about 20× (Adult) and 3.5× (MNIST) faster end-to-end than KREPES.

Q1 (How different rankings are obtained). The rankings differ substantially, and the final norm largely preserves the initial PCI ranking, while displacement captures what optimization changed. Top-10 Jaccard overlap is 0.00–0.11, with Spearman correlation −0.47 to −0.38 on Adult and 0.17 to 0.68 on MNIST (Table 15, App. F). PCI scales coefficients by Λk−1/2\Lambda_k^{-1/2}, and optimization changes them little relative to their initial magnitude. So, final-norm ranking matches initial-norm ranking in all six settings (Spearman 1.000), while displacement removes this baseline. We also add a contribution score that measures how much the final representation uses each landmark (Table 17, App. G.2). Against 30 random deletions, it reaches the 100th percentile in all MNIST and 83rd in all Adult settings.

Q2 (Interpreting Kaiming's performance). All initializers are trained on the same SSL objective; initialization changes the starting point, not the loss. Kaiming's three wins (Table 3) are modest: 0.11 points on MNIST Barlow Twins (small relative to the std. deviations), 0.24 on MNIST VICReg, and 0.58 on Adult VICReg. VICReg's variance and decorrelation objectives may favor a variance-preserving start. Across all six settings, the cross-view initializers CSI and AUI rank best and outperform PCI in every setting (Table 3; Section 4, “Initialization of the coefficients”). On MNIST, SimCLR, CSI beats Kaiming by 4.10 points. Mean ranks are CSI 1.83, AUI 2.17, Kaiming 2.33, and PCI 4.00 and 4.67. We claim that cross-view initializers outperform PCI in all six settings, while Kaiming remains competitive.

We have clarified the motivation by introducing KREPES and its relationship to CAIRN. An illustrative example in App. C walks through CAIRN’s four stages on a synthetic dataset of 18 points and three classes.

We are glad to clarify further and hope the revision merits a stronger recommendation.

AuthorsOpenReview ↗

Response to Reviewer B27A

We thank Reviewer B27A for the constructive feedback. As the discussion period nears its end, we remain available to answer any further questions or requests. We would be grateful to know whether our response has addressed your concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers and the Area Chair

We thank all three reviewers for their careful reading. The reviews raise four shared concerns. We have revised the paper to address each one; all changes are marked in blue.

1. Clarity and motivation (WxoT, B27A). The paper is now organized around one question: when can a ranked explanation be certified, and, when it cannot, which approximation limits certification?

  • Section 3 opens with a Background paragraph introducing KREPES, a formal Problem statement, a Pipeline paragraph tied to Figure 1, and a Roadmap linking each result to the certificate.

  • Section 3.1 defines output heads, and Section 3.2 defines the top-KK certificate and the δ\delta-certificate. App. K gives the formal Definitions K.1–K.2, a step-by-step certification procedure, and a reading guide (Table 25) that states each result in plain language, the prior work it builds on, and what CAIRN adds.

  • Section 4 opens with four guiding questions, and protocol tables (Table 1; Table 13, App. F) list the selector, initialization, seeds, and metric behind every result.

  • Figure 2(d) and Figure 12 (App. K) show real MNIST queries with their top-5 landmarks and the certificate's verdict, and App. C adds a worked example that follows all four stages on 18 points, three classes and six landmarks.

2. How often certification succeeds (B27A, RVDi). Table 5 (Section 4) and App. H.3–H.4 (Tables 21–22, Figure 10) report certification on 200 test queries per setting at 95% per-query confidence, across K∈{1,5,10}K\in\lbrace 1,5,10 \rbrace, sketch widths, landmark pools and certificate types.

  • Paired median-of-means certifies 83–88% of top-1 explanations on Adult and 32–57% on MNIST, against at most 21% for the basic Chebyshev certificate.

  • A paired empirical-Bernstein certificate raises matched-budget top-5 certification from 23.8% to 58.0% (MNIST) and from 31.0% to 68.2% (Adult), and replicates on a second, disjoint query cohort.

  • None of the 274,728 issued certificates disagreed with its exact-kernel reference.

3. Scope of the guarantee (RVDi). The certificate is conditional on the realized query, landmark set, and coefficient fit. We state this in the Problem paragraph and Remark H.1, state the paired fixed-head certificate used on real data in App. K (Table 24) and evaluate it in App. H.3 (median-of-means radii in Remark H.2), and measure landmark sensitivity separately by refitting on random sub-pools (Table 14).

4. End-to-end runtime (B27A). Table 2 now reports kernel and end-to-end times, and App. H.2 (Table 20, Figure 9) gives a per-stage breakdown on one RTX 4090. Kernel computation dominates; batched per-sample gradients make it 35× (Adult) and 4.7× (MNIST) faster. End-to-end, CAIRN is 28–32× (Adult) and 3.8–4.3× (MNIST) faster than KREPES. Certifying the top-KK sets of 200 queries adds 2.7–3.7 s (Adult) and 1–2 s (MNIST), so CAIRN remains about 20× (Adult) and 3.5× (MNIST) faster end-to-end.

Individual responses follow each review below.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.