arXiv CSopen access

A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification

A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification Sushovan Majhi1 , Atish Mitra2 , Žiga Virk3 , and Pramita Bagchi4

arXiv:2605.04046v1 [cs.LG] 5 May 2026

1 Data Science, George Washington University, USA ([email protected])

2 Department of Mathematical Sciences, Montana Technological University, USA ([email protected])

3 Faculty of Computer and Information Science, University of Ljubljana, Slovenia ([email protected]) 4 Biostatistics and Bioinformatics, George Washington University, USA ([email protected])

Abstract We introduce PALACE (Persistence Adaptive-Landmark Analytic Classification Engine), the dataadaptive companion to the closed-form PLACE pipeline, paying a small cross-validation tier on three knobs (budget, radii, bandwidth; ≤ 5 choices each). The summation embedding lifts into an RKHS via an additive landmark kernel. A self-contained cover-theoretic core—a Lebesgue-number criterion on the landmark cover—yields four closed-form guarantees. (i) A structural lower distortion bound 𝜆(𝜏; 𝜈) on D𝑛 under cross-diagram non-interference, with a (𝐷/𝐿) 2 budget reduction over the uniform grid when diagrams concentrate (data diameter 𝐷 vs. domain extent 𝐿). (ii) Equal landmark weights 𝑤𝑘 = 𝐾 −1/2 maximizing the certificate 𝜆 of (i), and farthest-point-sampling positions 2-approximating the optimal 𝑘-center covering radius; both derived training labels alone, no gradient training. (iii) A √ from √ kernel-RKHS classification rate 𝑂 ((𝑘−1) 𝐾/(𝛾 𝑚 min )) (𝑘 classes, 𝐾 landmarks) with binary necessity √ threshold 𝑚 = Ω( 𝐾/𝛾) from a matching Le Cam lower bound; and a closed-form filtration-selection rule. The kernel-Mahalanobis margin 𝜌ˆMah is the strongest closed-form ranker across the chemical√ ˆ 𝐾 graph pool, positive on every benchmark (mean Spearman 𝜌 ≈ +0.60); the isotropic surrogate 𝛾/ admits a closed-form selection-consistency rate, and 𝜆b from (i) provides an independent data-level signal complementing the kernel-margin rankers (positive on COX2 and PTC). (iv) A per-prediction certificate, in non-asymptotic Pinelis and asymptotic Gaussian forms, with no calibration split. Empirically, PALACE is the strongest closed-form diagram-based method on Orbit5k (91.3 ± 1.0%, matching Persformer’s gradient-trained black-box transformer), leads every diagram-based competitor on COX2 and MUTAG, and is competitive on DHFR (within 1 pp of ECP); descriptor blindness persists on NCI1 and PTC. At 8× domain inflation, adaptive placement maintains 94% while the uniform grid collapses to chance (25% on 4-class data).

1

Introduction

Persistent homology produces a canonical topological signature of structured data—graphs, point clouds, shapes—called the persistence diagram: a finite multiset of points in the half-plane above the diagonal, augmented by a formal diagonal point ∗. Stability under perturbation is well-understood (Chazal et al., 2009, 2016; Cohen-Steiner et al., 2007), but the varying cardinality and non-Hilbertian geometry of diagrams make them incompatible with standard machine learning. Existing vectorizations—persistence images (Adams et al., 2017), landscapes (Bubenik, 2015), kernels (Carrière et al., 2017; Kusano et al., 2016;

1

(a) Uniform grid G𝑅 𝐿

(b) Adaptive configuration 𝜈 𝐿

𝑑

𝑑

𝐷

𝑑= 𝑏

𝑑= 𝑏

𝐷

𝑏

𝑏

Figure 1: Uniform vs. data-adaptive landmark configurations on the birth–death plane. Both panels show the same five-point data cluster (red) of bottleneck-diameter 𝐷 in a domain of extent 𝐿; here 𝐿/𝐷 ≈ 7. (a) PLACE’s uniform grid G𝑅+ covers the full half-plane [0, 𝐿] 2 with balls of fixed radius 3𝑅 2 , irrespective of where data lies; most balls fall in empty regions. (b) PALACE’s adaptive configuration 𝜈 places 𝐾 landmarks via class-aware farthest-point sampling on training diagrams (here 𝐾=3 selected from the 5 training points) with radii from local nearest-neighbor spacing, concentrating coverage where data lives. The required budget drops from Θ((𝐿/𝜏) 2 ) to Θ((𝐷/𝜏) 2 ) when data diameter 𝐷 ≪ 𝐿 (Theorem 2.2). Le and Yamada, 2018; Reininghaus et al., 2015), learned weights (Zhao and Wang, 2019), and neural extensions (Carrière et al., 2020; Gabrielsson et al., 2020; Hofer et al., 2017; Reinauer et al., 2021)—all offer Lipschitz upper bounds on embedding distortion. None comes with a lower bound with explicit constants, so there is no guarantee that bottleneck-separated diagrams remain separated after vectorization. Each method further carries hyperparameters—kernel bandwidth, image resolution, landscape level count, learned weight function—whose selection requires held-out data, so any downstream accuracy claim inherits the dependence on a validation split. Despite a decade of work, there is no way to inspect a trained persistence-diagram classifier and certify, before seeing test data, whether its predictions will be correct. Our companion paper (Majhi et al., 2026) closes these gaps on a fixed-grid backbone; we adopt its persistence-diagram setup throughout (bottleneck distance, 𝑛-point diagram space, top-persistence filter; see Majhi et al., 2026, Sec. 2). PLACE places landmarks on a uniform lattice in the birth–death plane at 𝑁 geometrically spaced scales and sums a compactly supported hat coordinate over diagram points; from training labels alone, the construction yields a tight minimax classification rate, a closed-form Mahalanobismargin descriptor-selection rule, and a per-prediction correctness certificate. The construction is fully tuning-free, but three residual trade-offs limit how far it can be pushed: (i) Coverage. The uniform grid covers the full birth–death domain regardless of where diagrams concentrate, inflating embedding capacity relative to the data support. (ii) Positions. Landmark positions are combinatorial and change the embedding dimension in discrete jumps as the grid is refined or thinned, leaving the placement axis outside Majhi et al. (2026)’s closed-form recipe. (iii) Linear-only analysis. The classification rate of Majhi et al. (2026, Thm. 3.1) is stated for a linear SVM on Φ; non-linear lifts (kernel SVM, RKHS lift) are not analyzed and cannot be deployed without forfeiting the per-prediction certificate (which requires an analytically fixed embedding). PALACE relaxes all three. This paper introduces PALACE, the data-adaptive companion that addresses (i)–(iii) in turn. The fixed grid is replaced by an adaptive configuration 𝜈 of 𝐾 weighted landmarks placed by class-aware farthestpoint sampling on training diagrams (Figure 1; formal definition in Section 2). This makes landmark positions analytic from the data and concentrates coverage where diagrams live, dropping the required budget 2

from Θ((𝐿/𝜏) 2 ) to Θ((𝐷/𝜏) 2 ) when diagrams cluster in a region of 𝑑 B -diameter 𝐷 ≪ 𝐿 (Theorem 2.2)— addressing (i) and (ii). The single-point coordinate 𝜑𝑝,𝑟 and the bottleneck geometry are inherited from Mitra and Virk (2024) unchanged; we sum the coordinate over diagram points—the summation diagonalization of Majhi et al. (2026)—evaluated at the adaptive positions, then lift the resulting embedding into an RKHS via the additive landmark kernel 𝑘 𝜈 , addressing (iii). The kernel lift is empirically necessary: on the same embedding, linear classifiers leave a structural 30-percentage-point gap (Section 6.1). The price is a small cross-validation tier (budget 𝐾, radius factor 𝛼, bandwidth 𝜎; ≤ 5 choices each) replacing PLACE’s tuning-free regime. √ The theory mirrors PLACE’s contribution list under a single correspondence: 𝑅 ↔ 𝐾, Δ ↔ 2𝛾, where 𝑅 is PLACE’s embedding radius, Δ its class-mean separation, 𝐾 the PALACE landmark budget, and 𝛾 the kernel-RKHS class-mean margin. Under this map, PLACE’s grid-tied constant-floor distortion bound becomes PALACE’s configuration-intrinsic certificate 𝜆(𝜏; 𝜈) on arbitrary admissible 𝜈 via a self√ contained non-uniform cover theory. PLACE’s 𝑂 ((𝑘−1)𝑅/(Δ 𝑚 min )) classification rate (with (𝑘−1) from the OvO√majority-vote reduction and 𝑚 min the smallest class size) becomes the kernel-RKHS analogue √ 𝑂 ((𝑘−1) 𝐾/(𝛾 𝑚 min )), with the same Le Cam binary lower bound and the same polynomial necessaryvs-sufficient gap (the RKHS lift introduces no information-theoretic loss). PLACE’s Δ-based per-prediction certificate carries through on R𝐾 at the raw-embedding class-mean separation Δ̂𝑐ˆ (Theorem 5.1), with identical structure. The one piece that does not carry over is PLACE’s nested-scale weight rule, which optimizes a different problem; the free-configuration argmax is the equal-weight rule 𝑤𝑘 = 𝐾 −1/2 , 𝜆maximizing among 𝜏-admissible equal-weight configurations of cardinality 𝐾 (Prop. 2.2), with admissibility itself preventing memorization (no gradient training of weights is needed). Section 1.1 states each result formally. Empirically, PALACE reaches 91.3 ± 1.0% on Orbit5k with the certified landmark kernel at a triplefiltration concatenation (Table 8), matching Persformer (Reinauer et al., 2021) and surpassing every other diagram-based method, including PLACE’s 87.2 ± 0.6% (linear SVM, ℓ=1,366). On the structurally discriminative chemical benchmarks (COX2, DHFR, MUTAG; Table 10), PALACE leads every diagram-based competitor on COX2 and MUTAG and is competitive on DHFR (within 1 pp of ECP); it exceeds both PLACE and PersLay on each, with accuracies 81.7%/81.0%/90.9%. On the heterogeneous chemical pool of Section 6.3.2, the Mahalanobis-margin selector 𝜌ˆMah is the only ranker positive on every completed dataset (MUTAG, COX2, DHFR, PTC, NCI1; mean Spearman 𝜌 ≈ +0.60); the certificate-as-ranker 𝜆b gives an in› ker inverts (notably COX2), dependent positive signal on COX2 and PTC where the trace-corrected Fisher confirming the two mechanisms (kernel-margin vs. data-level bottleneck) are orthogonal. At 8× domain inflation on a synthetic task, adaptive placement maintains 94% while the uniform grid collapses to the 25% chance level on 4-class data, validating the (𝐷/𝐿) 2 budget-reduction mechanism. Section 6 reports the full empirical comparison across Orbit5k, five chemical graph benchmarks, and the controlled synthetic task; on PROTEINS, DD, IMDB-B, IMDB-M, and NCI109 (Zhao and Wang, 2019), the linear-SVM baseline, nearest-centroid accuracies, and certificate firing diagnostics are in hand, with the LK-SVM headline accuracies deferred to a future revision (Section 7).

1.1

Our Contribution and Organization

Adaptive landmark placement on persistence diagrams admits a closed-form theory (modulo a small CV tier) for the four steps of the classification pipeline—embedding, optimization, selection, deployment—replacing learned vectorizations, gradient training of weights, held-out validation, and post-hoc calibration with provable choices. PALACE realizes this theory; PLACE (Majhi et al., 2026) is the discrete uniform-grid special case. The single-point coordinate 𝜑𝑝,𝑟 and bottleneck geometry 𝑑 B are inherited from Mitra and Virk (2024); the summation diagonalization and Δ-based certificate form are inherited from Majhi et al. (2026). 3

The four contributions, all closed-form modulo the CV tier above, correspond to the four pipeline steps and parallel the four contributions of Majhi et al. (2026): (i) A self-contained non-uniform cover theory for arbitrary admissible landmark configurations 𝜈, yielding a structural lower distortion bound 𝜆(𝜏; 𝜈) via a Lebesgue-number criterion under cross-diagram non-interference (Theorem 2.1) and a (𝐷/𝐿) 2 budget reduction over the uniform grid (Theorem 2.2, Section 2); this generalizes the constant-floor lower bound of Majhi et al. (2026, contribution (i)) from the grid G𝑅 to arbitrary admissible 𝜈. A per-dataset audit (Section 6) finds the non-interference hypothesis of Theorem 2.1 essentially never met on chemical persistence diagrams; Theorem 2.1 should therefore be read as a structural admissibility statement, with the empirical workhorse living at the kernel-margin level (contribution (iii) below). (ii) Closed-form configuration choices: equal weights 𝑤𝑘 = 𝐾 −1/2 maximize the certificate 𝜆 on the worst-case kernel-RKHS bound (Proposition 2.2(i)); the effective certificate is sharpened by the Lebesgue number, which under uniform radii reduces to a 𝑘-center covering-radius minimization (Proposition 2.2(ii)), solved within a factor of 2 by farthest-point sampling (Theorem 2.3, Corollary 2.1). Admissibility prevents memorization (Definition 2.2(i) forces max𝑘 𝑟𝑘 ≥ 𝜏/4, ruling out the degenerate 𝑟𝑘 → 0 configurations a learned placement could otherwise reach), so no gradient training of 𝑤𝑘 or {𝑝𝑘 } is needed. PLACE’s nested-scale rule 2 −𝑑 2 )/𝑅 2 (part of Majhi et al., 2026’s contribution (i)) optimizes a different problem (nested scales 𝑤𝑘2 ∝ (𝑑𝑘+1 𝑘 𝑘 with fixed support size) and does not carry the free-configuration argmax is equal weights. (iii) A √ over: √ kernel-RKHS classification rate 𝑂 ((𝑘−1) 𝐾/(𝛾 𝑚 min )) via Theorem 3.1, with binary necessity threshold √ 𝑚 = Ω( 𝐾/𝛾) from Theorem 3.2’s Le Cam two-point construction (the polynomial gap between necessary √ 𝐾/𝛾 and sufficient 𝐾 log(𝑘/𝛿)/𝛾 2 thresholds is the same one Majhi et al. (2026) leaves open;√Remark 3.3). › ker , Closed-form filtration selection (Section 4) then provides three Σ-treatment selectors (ˆ 𝛾/ 𝐾, Fisher 𝜌ˆMah ) covering the spherical, scalar-trace, and full-operator regimes (Remark 4.1; the Mahalanobis pivot parallels Majhi et al., 2026, Sec. 4.1), with selection-consistency theorem (Proposition 4.1, paralleling Majhi et al., 2026, Prop. 4.4); a complementary data-level 𝜆b recovers signal in the bottleneck-orthogonal regime where the Σ-aware selectors miss (Section 6.3.2). This unifies the analogues of Majhi et al. (2026)’s contributions (ii) (classification rate) and (iii) (descriptor selection) into a single RKHS framework. (iv) A per-prediction correctness certificate 𝑟𝑚 < 12 Δ̂𝑐ˆ (Theorem 5.1, Section 5.1) in non-asymptotic Pinelis and asymptotic Gaussian forms, no calibration split; this parallels Majhi et al., 2026’s contribution (iv) at the raw-embedding class-mean separation Δ on R𝐾 (the certificate operates on the raw ℓ 2 embedding, not the RKHS lift, with raw embedding radius 𝑅¯ ≤ 𝑁 max𝜏 replacing PI’s 𝑅 in the constants). Section 2 develops the cover theory, the summation embedding Φ, the certificate 𝜆(𝜏; 𝜈), and the budget reduction; Section 3 the kernel-RKHS framework and the selection statistic; Section 5.1 the certified nearest-centroid classifier; Section 6 the experiments; Section 7 limitations.

1.2

Related Work

For a survey of persistence diagram vectorizations (landscapes, persistence images, kernels, learned weightings, neural extensions), certified machine learning (conformal prediction, selective classification, learning with rejection), and topological data analysis for classification (diagram-based, neural-augmented, Eulercharacteristic methods), we refer the reader to Majhi et al. (2026, Section 1.2); PALACE inherits PLACE’s positioning relative to those literatures and adds two new contact points discussed below. Table 1 extends the feature matrix of Majhi et al. (2026, Table 1) with two columns specific to PALACE (Adaptive, Kernel/RKHS); PLACE and PALACE remain the only methods with both an explicit lower-distortion bound and a per-prediction certificate, and PALACE adds adaptive placement and the RKHS lift in exchange for a small CV tier. Landmarks and coresets. Landmark-based embeddings are classical in manifold learning and metricspace approximation (e.g., 𝑘-medoids embedding, landmark MDS (de Silva and Tenenbaum, 2004)). In 4

input & diagram

adaptive placement

kernel embedding

𝑑 𝑝𝑘

𝐴∗ 𝜇ˆ𝑐

𝑟𝑘 𝑘𝜈 𝑑

certified classify

Φ(𝐴; 𝜈 ) ∈ R𝐾

filtration

2𝛾

𝜇ˆ𝑐 ′ 𝑟𝑚

𝜇𝑐 ′

𝜇𝑐 𝐴

Δ̂𝑐ˆ

sum-pool + LK lift 𝑘 𝜈

𝑦ˆ with 𝑟𝑚 < 12 Δ̂𝑐

𝑏

𝑏

graph or point cloud, diagram 𝐴

H𝑘 𝜈

FPS on training data, |𝜈 | = 𝐾

Figure 2: The PALACE pipeline. A graph or point cloud is converted to a persistence diagram 𝐴 through a filtration. Class-aware farthest-point sampling on training diagrams fixes the landmark configuration 𝐾 . The diagram is sum-pooled into Φ(𝐴; 𝜈) ∈ R𝐾 and lifted to the RKHS H 𝜈 = {(𝑝𝑘 , 𝑟𝑘 , 𝑤𝑘 )}𝑘=1 𝑘 𝜈 via the additive landmark kernel 𝑘 𝜈 . The kernel-SVM prediction 𝑦ˆ is audited per input by the certificate 𝑟𝑚 < 12 Δ̂𝑐 (Theorem 5.1). The middle two stages are PALACE-specific; stages 1 and 4 share form with PLACE (Majhi et al., 2026). kernel methods, Nyström approximation (Drineas and Mahoney, 2005; Williams and Seeger, 2001) uses a random or adaptive landmark subset to approximate the gram; it produces dimension-reduced embeddings but no lower distortion bounds in the bottleneck metric on D𝑛 , in contrast to Theorem 2.1. PALACE’s cover-theoretic analysis via Lebesgue numbers is closer in spirit to the coreset literature for geometric clustering (Agarwal et al., 2005; Feldman and Langberg, 2011), with the Lebesgue-number criterion playing the role of a coreset’s coverage radius. √ Kernel-RKHS minimax theory. PLACE’s classification rate 𝑂 (𝑘𝑅/(Δ 𝑚 min )) uses the metric-SVM machinery of Vapnik (Vapnik, 1998) and Mohri–Rostamizadeh–Talwalkar (Mohri et al., 2018), with a matching Le Cam lower bound (Le Cam, 1973; Tsybakov, 2009; Yu, 1997) for bounded Hilbert-space inputs. Theorems 3.1–3.2 lift to the RKHS induced by the PALACE landmark kernel, establishing the kernel ana√ this √ √ logue 𝑂 ((𝑘−1) 𝐾/(𝛾 𝑚 min )) with matching binary lower bound (tight up to the OvO (𝑘−1) factor): 𝐾 plays the role of the input norm bound, and the kernel margin 𝛾 replaces Δ/2. The lower bound is, to our knowledge, the first matching minimax rate for the landmark-kernel construction on persistence diagrams.

2

Non-Uniform Cover Theory

This section develops PALACE’s intrinsic distortion certificate 𝜆(𝜏; 𝜈) for arbitrary admissible landmark configurations. The summation embedding Φ is constructed in Section 2.1 from a per-landmark coordinate function 𝜑𝑝,𝑟 ; Section 2.2 establishes the lower distortion bound ∥Φ(𝐴; 𝜈) − Φ(𝐵; 𝜈) ∥ ℓ 2 ≥ 𝜆(𝜏; 𝜈) on 𝜏separated cross-class pairs, under 𝜏-admissibility (a Lebesgue-number criterion on the cover, Definition 2.2) and a non-interference condition inherited from Majhi et al. (2026, Prop. 2.1(b)) (Definition 2.3; the top𝑁 max persistence filter controls part of this risk in practice, and Remark 2.1 reports the empirical audit). The adaptive placement reduces the landmark budget by (𝐷/𝐿) 2 over the uniform grid when data concentrates with diameter 𝐷 ≪ 𝐿 (Theorem 2.2). Within the broader theory 𝜆 is an admissibility guarantee: 𝜏-separated diagrams remain separated in ℓ 2 (and in H𝑘 𝜈 ), the precondition under which the classification quantities Δ and 𝛾 of Section 3 are nondegenerate. The classification error bound is stated in the kernel margin 𝛾 (Theorem 3.1); the per-prediction 5

Table 1: Persistence-diagram vectorizations. Lipschitz: upper stability ∥Φ(·)−Φ(·) ∥ ≤ 𝑐 + 𝑑 B . Lower dist.: explicit constant 𝑐 − in 𝑐 − 𝑑 B ≤ ∥Φ(·)−Φ(·) ∥; “config-intrinsic” for PALACE means the constant depends only on 𝜈, not a specific grid. Adaptive: landmark positions/radii fixed analytically from training data (not a grid, not a learned optimizer). Kernel/RKHS: explicit positive-definite kernel with RKHS-level analysis; PALACE additionally provides non-degeneracy on 𝜏-separated pairs (Cor. 3.1). No-CV: embedding hyperparameters fixed analytically (no held-out validation). Cert.: correctness certificate (metric / classification / per-prediction). PALACE trades No-CV for Adaptive vs. PLACE. Method Landscapes (2015) Persistence images (2017) SW / PSS kernels (2017; 2016) WKPI (2019) PersLay / Persformer (2020; 2021) Mitra–Virk 𝑛-fold (2024) Uniform PLACE (2026) PALACE (this work)

Lipschitz

Lower dist.

Adaptive

Kernel/RKHS

✓ ✓ ✓ ✓

— — — — —

— — —

implicit

learned

✓ ✓ ✓

× (learned 𝑤) × (learned) ✓ 𝜌 − on D𝑛 × (𝑁 𝑀 𝑛 grid) ✓ 𝜆 (𝜈 ) on D𝑛 , constant floor × (grid G𝑅 ) ✓ 𝜆 on D𝑛 , config-intrinsic ✓ (FPS on data)

✓ ✓ ✓ × × × (linear SVM) ✓ (𝑘 𝜈 , Cor. 3.1)

No-CV

Cert.

× (levels) × × (𝜎, grid, weight) × × (bandwidth) × × (learned 𝑤) × × (end-to-end) × ✓ metric only ✓ classification × (𝐾, 𝛼, 𝜎) per-prediction

certificate is stated in the raw class-mean separation Δ on R𝐾 (Section 5.1, matching the framework of Majhi et al., 2026). 𝜆 enters both via the bridges 𝛾 ≥ 21 (𝜅𝜆 − 2𝐷 max ) and Δ ≥ 𝜆 − 2𝐷¯ max (Proposition 3.1). A landmark configuration is a finite set 𝜈 =



(𝑝𝑘 , 𝑟𝑘 , 𝑤𝑘 )

𝐾 , 𝑘=1

𝑝𝑘 ∈ D1, 𝑟𝑘 > 0, 𝑤𝑘 > 0,

𝐾 ∑︁

𝑤𝑘2 = 1,

(2.1)

𝑘=1

generalizing the conventional offset grid (fixed positions, uniform support radius 3𝑅 2 ) to adaptive positions, radii, and weights. The Mitra–Virk grid (Mitra and Virk, 2024) achieves bounded cover multiplicity (≤ 4) at every point above the diagonal; the Lebesgue-number criterion below extends the admissibility test to non-uniform configurations.

2.1

Coordinate Functions and the Embedding

The PALACE embedding is built from a single primitive: a per-landmark pyramid evaluated at diagram points. We give the construction in two steps—first on D1 , then extended to D𝑛 —and record the Lipschitz property used throughout the cover-theoretic analysis. For (𝑝, 𝑟 ) ∈ D1 × (0, ∞) and 𝑥 ∈ D1 , the coordinate function 𝜑𝑝,𝑟 (𝑥) := max{𝑟 − 𝑑 B (𝑝, 𝑥), 0}

(2.2)

is the piecewise-linear cap with peak 𝑟 at 𝑥 = 𝑝 and support on the closed ball 𝐵(𝑝, 𝑟 ) ⊂ D1 . Geometrically, 𝜑𝑝,𝑟 is a pyramid over 𝐵(𝑝, 𝑟 ): apex of height 𝑟 at 𝑥 = 𝑝, decaying linearly to zero at the boundary, and zero outside. This generalizes the Mitra–Virk coordinate 𝜑𝑅,𝑝 (Mitra and Virk, 2024), whose support ball has uniform radius 3𝑅 2 , to landmark-specific radii 𝑟 𝑘 . The lift to 𝑛-point diagrams is by summation over diagram points. For 𝐴 ∈ D𝑛 , the sum-pool coordinate extends the single-point cap function additively: ∑︁ ∑︁ 𝜑𝑝,𝑟 (𝑎) = max{𝑟 − 𝑑 B (𝑝, 𝑎), 0}. (2.3) 𝜑𝑝,𝑟 (𝐴) := 𝑎∈𝐴

𝑎∈𝐴

The symbol 𝜑𝑝,𝑟 is overloaded by argument type: a single point 𝑎 ∈ D1 returns the pyramid height of (2.2); a diagram 𝐴 ∈ D𝑛 returns the sum-pool above. The structural property used throughout the cover-theoretic analysis is the per-point Lipschitz behavior of 𝜑𝑝,𝑟 . 6

Lemma 2.1 (Bottleneck-Lipschitz coordinate). For every (𝑝, 𝑟 ) ∈ D1 × (0, ∞), |𝜑𝑝,𝑟 (𝑥) − 𝜑𝑝,𝑟 (𝑦)| ≤ 𝑑 B (𝑥, 𝑦)

for all 𝑥, 𝑦 ∈ D1 .

Proof. 𝑥 ↦→ 𝑑 B (𝑝, 𝑥) is 1-Lipschitz on D1 by the triangle inequality for 𝑑 B , and 𝑡 ↦→ max(𝑟 − 𝑡, 0) is 1-Lipschitz on R. Composition preserves the Lipschitz constant. □ The embedding aggregates sum-pool coordinates over the configuration with per-landmark weights. 𝐾 as in (2.1), the summation Definition 2.1 (Summation landmark embedding). Given 𝜈 = {(𝑝𝑘 , 𝑟𝑘 , 𝑤𝑘 )}𝑘=1 landmark embedding is the map Φ( · ; 𝜈) : D𝑛 → R𝐾 with coordinates

Φ𝑘 (𝐴; 𝜈) := 𝑤𝑘 𝜑𝑝𝑘 ,𝑟𝑘 (𝐴),

𝑘 = 1, . . . , 𝐾 . (2.4)
Í The summation form generalizes the per-scale block Φ𝑅 (𝐴) = 𝑎∈𝐴 𝜑𝑅,𝑝 (𝑎) 𝑝 ∈G+ of PLACE’s multi𝑅 scale embedding (Majhi et al., 2026) from a fixed parity-constrained grid to arbitrary data-adaptive configurations. Each coordinate costs one bottleneck evaluation per (landmark, diagram point) pair, total 𝑂 (𝐾 · |𝐴|) linear in diagram cardinality. Lemma 2.1 extends from single points to diagrams via bijective matching: for any 𝐴, 𝐵 ∈ D𝑛 of cardinality at most 𝑁 max and an optimal 𝜎 : 𝐴 → 𝐵 realizing 𝑑 B (𝐴, 𝐵), ∑︁ |𝜑𝑝𝑘 ,𝑟𝑘 (𝐴) − 𝜑𝑝𝑘 ,𝑟𝑘 (𝐵)| ≤ |𝜑𝑝𝑘 ,𝑟𝑘 (𝑎𝑖 ) − 𝜑𝑝𝑘 ,𝑟𝑘 (𝑏𝜎 (𝑖 ) )| ≤ 𝑁 max 𝑑 B (𝐴, 𝐵). 𝑖

Squaring, summing over 𝑘, and using

2 𝑘 𝑤 𝑘 = 1 yields the unconditional upper distortion bound

Í

∥Φ(𝐴; 𝜈) − Φ(𝐵; 𝜈)∥ ℓ 2 ≤ 𝑁 max 𝑑 B (𝐴, 𝐵),

(2.5)

−1 Φ is 1-Lipschitz; we keep the unnormalized summatching Majhi et al. (2026, Eq. (2.5)). Equivalently, 𝑁 max pool form to preserve the semantics inherited from Majhi et al. (2026) and to keep downstream certificate constants (𝑅¯ ≤ 𝑁 max𝜏, Section 5.1) parallel. The complementary lower distortion bound—non-trivial and governed by the geometry of the landmark cover plus a non-interference condition—is the subject of the next subsection.

2.2

The Non-Uniform Distortion Certificate

Throughout this subsection and the next, fix a data support R ⊂ D1 ∩ [0, 𝐿] 2 of 𝑑 B -diameter 𝐷 := diam𝑑 B (R) ≤ 𝐿. The distortion certificate depends on a single geometric quantity of the landmark cover: its (classical) Lebesgue number 𝜆0 (Lebesgue’s covering lemma; see Munkres, 2000, Thm. 27.5), made precise for our cover in Definition 2.2. Picture the family of cap functions {𝜑𝑝𝑘 ,𝑟𝑘 } as a landscape of overlapping pyramids—one of peak height 𝑟𝑘 at each landmark 𝑝𝑘 , decaying linearly to zero at the ball boundary. Then 𝜆0 is the lowest point of the upper envelope of these pyramids over the data support: every 𝑥 ∈ R lies under some pyramid that still rises to at least 𝜆0 above it, and the admissibility conditions below force this minimum height to be commensurate with the separation scale 𝜏 (Figure 3(a)). 𝐾 be a configuration whose balls cover the data Definition 2.2 (𝜏-admissibility). Let 𝜈 = {(𝑝𝑘 , 𝑟𝑘 , 𝑤𝑘 )}𝑘=1 Ð support, R ⊆ 𝑘 𝐵(𝑝𝑘 , 𝑟𝑘 ). Define its Lebesgue number

𝜆0 (𝜈) := inf max 𝜑𝑝𝑘 ,𝑟𝑘 (𝑥). 𝑥∈R

(2.6)

𝑘

Equivalently, 𝜆0 (𝜈) is the largest 𝜌 ≥ 0 for which the shrunk cover {𝐵(𝑝𝑘 , 𝑟𝑘 − 𝜌)}𝑘 still contains R (the maximum uniform shrinkage of the cover balls that preserves coverage of R). The configuration is 𝜏-admissible at separation scale 𝜏 > 0 if 7

𝑑

(a) Lebesgue number

(b) Cover separation

𝑑

𝑏𝜎 (𝑖 ★ )

𝑥★

𝑎𝑖 ★ 𝑝𝑘 ★

𝜆0

𝜆0

𝑏

𝑏

Figure 3: 𝜏-admissibility (Def. 2.2). (a) The Lebesgue number is the lowest point of the upper envelope of the cap-function pyramids over the data support: 𝜆0 = inf 𝑥 ∈ R max𝑘 𝜑𝑝𝑘 ,𝑟𝑘 (𝑥). Highlighted: a point 𝑥 ★ realizing this minimum. Condition (i) requires 𝜆0 ≥ 𝜏/4; condition (ii) bounds radii max𝑘 𝑟𝑘 ≤ (𝜏 + 𝜆0 )/2. (b) The single-point step in Theorem 2.1’s proof. For a 𝜏-separated pair (𝐴, 𝐵), fix the worst-matched pair (𝑎𝑖★ , 𝑏𝜎 (𝑖★ ) ). The Lebesgue number applied at 𝑎𝑖★ ∈ D1 yields some pyramid 𝜑𝑝𝑘★ ,𝑟𝑘★ with 𝜑𝑝𝑘★ ,𝑟𝑘★ (𝑎𝑖★ ) ≥ 𝜆0 ; admissibility (ii) then places 𝑏𝜎 (𝑖★ ) outside that pyramid’s support, so 𝜑𝑝𝑘★ ,𝑟𝑘★ (𝑏𝜎 (𝑖★ ) ) = 0. Crossclass non-interference shows the remaining 𝑏-points lie outside the ball as well, so Φ𝑘 ★ (𝐵; 𝜈) = 0; 𝑎-side contributions are non-negative. (i) 𝜆0 (𝜈) ≥ 𝜏/4, (ii) max𝑘 𝑟𝑘 ≤ (𝜏 + 𝜆0 )/2. Two immediate consequences of Definition 2.2 are recorded for downstream use. First, conditions (i) and (ii) jointly bound max𝑘 𝑟𝑘 ≤ 𝜏: combining max𝑘 𝑟𝑘 ≤ (𝜏 + 𝜆0 )/2 with 𝜆0 ≤ max𝑘 𝑟𝑘 (immediate from (2.6)) gives max𝑘 𝑟𝑘 ≤ (𝜏 + max𝑘 𝑟𝑘 )/2, i.e., max𝑘 𝑟𝑘 ≤ 𝜏, hence 𝜆0 ≤ 𝜏. Second, the upper-envelope winner at any 𝑥 ∈ R has 𝑟𝑘 ★ ≥ 𝜏/4: the maximum in (2.6) at 𝑥 is attained at some 𝑘 ★ with 𝜑𝑝𝑘★ ,𝑟𝑘★ (𝑥) ≥ 𝜆0 , ≥ hence 𝑟𝑘 ★ ≥ 𝜆0 ≥ 𝜏/4. Hence {𝑘 : 𝑟𝑘 ≥ 𝜏/4} ≠ ∅, and the minimum-weight quantity 𝑤 min (𝜏; 𝜈) := min{𝑤𝑘 : 𝑟𝑘 ≥ 𝜏/4} appearing in Theorem 2.1 is well-defined. 𝜏-admissibility is operationally cheap to check. The Lebesgue number 𝜆0 is computable in 𝑂 (𝑛𝑚𝐾) time from the training diagrams (𝑚 diagrams of at most 𝑛 points each, 𝐾 landmarks); for the square uniform grid at spacing 𝑅 with ball radius 3𝑅/2 (Theorem 2.2’s uniform model), 𝜆0 (G𝑅 ) = 𝑅 and conditions (i) and (ii) yield the admissibility window 𝑅 ∈ [𝜏/4, 𝜏/2]. For non-uniform configurations produced by FPS (Theorem 2.3), both conditions can be verified directly once landmarks are placed; if either fails, 𝜏 is rescaled to the largest value compatible with the cover. Definition 2.3 (Non-interference). A pair (𝐴, 𝐵) ∈ D𝑛 × D𝑛 satisfies non-interference if either 𝑛 = 1 (vacuous), or 𝑛 ≥ 2 and there exists an optimal matching 𝜎 : 𝐴 → 𝐵 realizing 𝑑 B (𝐴, 𝐵) such that every cross-diagram pair (𝑎𝑖 , 𝑏𝜎 ( 𝑗 ) ) with 𝑖 ≠ 𝑗 is strictly farther than three times the bottleneck distance: min 𝑑 B (𝑎𝑖 , 𝑏𝜎 ( 𝑗 ) ) > 3 𝑑 B (𝐴, 𝐵). 𝑖≠𝑗

(2.7)

Definition 2.3 mirrors Majhi et al. (2026, Definition 2.1); the partial-matching extensions needed when 𝑑 B projects some points to the diagonal are straightforward bookkeeping and do not appear in the experiments. A sufficient condition for non-interference, expressed purely in within-class diagram geometry, decouples this hypothesis from any cross-pair check. 8

Proposition 2.1 (Non-interference from scale separation). Suppose that for every cross-class pair (𝐴, 𝐵) arising in the classification, the within-diagram minimum separation satisfies min 𝑑 B (𝑎𝑖 , 𝑎 𝑗 ) > 4 𝑑 B (𝐴, 𝐵).

(2.8)

𝑖≠𝑗

Then the non-interference condition (2.7) holds for (𝐴, 𝐵). Proof. For 𝑖 ≠ 𝑗, using 𝑑 B (𝑎 𝑗 , 𝑏𝜎 ( 𝑗 ) ) ≤ 𝑑 B (𝐴, 𝐵) and the triangle inequality, 𝑑 B (𝑎𝑖 , 𝑏𝜎 ( 𝑗 ) ) ≥ 𝑑 B (𝑎𝑖 , 𝑎 𝑗 ) − 𝑑 B (𝑎 𝑗 , 𝑏𝜎 ( 𝑗 ) ) > 4 𝑑 B (𝐴, 𝐵) − 𝑑 B (𝐴, 𝐵) = 3 𝑑 B (𝐴, 𝐵). The analogous within-𝐵 condition min𝑖≠𝑗 𝑑 B (𝑏𝑖 , 𝑏 𝑗 ) > 4 𝑑 B (𝐴, 𝐵) also implies non-interference by the same argument routed through 𝑏 𝑗 ; either condition alone is sufficient. □ Remark 2.1 (Empirical scope of non-interference). Condition (2.8) requires within-diagram features to sit at a scale strictly larger than the cross-class separation scale. The top-𝑁 max persistence filter (Majhi et al., 2026), which retains only the 𝑁 max points with largest persistence 𝑑 B (𝑎, Δ), controls part of this risk by discarding low-persistence features clustered near the diagonal. On the chemical graph benchmarks of Section 6, however, the filter is not tight enough to make non-interference hold pointwise: an audit on four datasets at the perdataset headline filtration finds essentially 0% of cross-class pairs satisfying condition (2.7), with median crossratios min𝑖≠𝑗 𝑑 B (𝑎𝑖 , 𝑏𝜎 ( 𝑗 ) )/𝑑 B (𝐴, 𝐵) at or near zero (audit reported in Section 6). The hypothesis is therefore structural; remarkably, the conclusion of Theorem 2.1 (the certificate ∥Φ(𝐴) − Φ(𝐵) ∥ ℓ 2 ≥ 𝜆(𝜏; 𝜈)) holds on 99.9–100% of cross-class pairs in the same audit (Table 3), with median embedded distance 3–14× the certificate—non-interference is sufficient but not necessary for the bound, and the proof is overcautious on these diagrams. The working classification machinery in Section 3 operates at the kernel-margin level 𝛾 > 0 (Theorem 3.1), independent of pairwise non-interference. We now establish the main result: an explicit lower distortion bound for admissible configurations. At its core, Theorem 2.1 is a quantitative Lebesgue-number lemma1 for the landmark cover 𝜈. 𝐾 be a 𝜏-admissible configuration. Theorem 2.1 (Non-uniform distortion certificate). Let 𝜈 = {(𝑝𝑘 , 𝑟𝑘 , 𝑤𝑘 )}𝑘=1 For any 𝐴, 𝐵 ∈ D𝑛 with all points of 𝐴 and 𝐵 in R, 𝑑 B (𝐴, 𝐵) ≥ 𝜏, and the non-interference condition (2.7) holding, ∥Φ(𝐴; 𝜈) − Φ(𝐵; 𝜈)∥ ℓ 2 ≥ 𝜆(𝜏; 𝜈), (2.9)

where the non-uniform distortion certificate is ≥ 𝜆(𝜏; 𝜈) := 41 𝜏 · 𝑤 min (𝜏; 𝜈),

≥ 𝑤 min (𝜏; 𝜈) := min 𝑤𝑘 . 𝑘: 𝑟𝑘 ≥𝜏/4

(2.10)

√ In particular, for equal weights 𝑤𝑘 = 𝐾 −1/2 and all 𝑟𝑘 ≥ 𝜏/4, the certificate is 𝜆(𝜏; 𝜈) = 𝜏/(4 𝐾). Proof. The strategy is to exhibit a single witnessing coordinate 𝑘 ★ that contributes the certificate value to the ℓ 2 distance: at the worst-matched cross-class pair (𝑎𝑖★ , 𝑏𝜎 (𝑖★ ) ), the Lebesgue number forces some pyramid 𝜑𝑝𝑘★ ,𝑟𝑘★ to rise above 𝜆0 at 𝑎𝑖★ , while admissibility (ii) plus non-interference force every 𝑏𝜎 ( 𝑗 ) to ≥ lie outside this pyramid’s support; the 𝑘 ★-th coordinate alone then witnesses the floor 𝑤𝑘 ★ 𝜆0 ≥ 𝑤 min 𝜏/4. By Definition 2.3, fix the optimal matching 𝜎 : 𝐴 → 𝐵 realizing 𝑑 B (𝐴, 𝐵) for which (2.7) holds (vacuous and trivial for 𝑛 = 1). Let 𝑖 ★ be an index of a worst-matched pair, so 𝑑 B (𝑎𝑖★ , 𝑏𝜎 (𝑖 ★ ) ) = 𝑑 B (𝐴, 𝐵) ≥ 𝜏. 1 Henri Léon Lebesgue (1875–1941): his Lebesgue-number lemma (see Munkres, 2000, Thm. 27.5) guarantees that every open

cover of a compact metric space admits a positive uniform scale at which every ball lies in some cover element. The non-uniform distortion certificate below makes that scale explicit for the landmark cover 𝜈. We dedicate this work to his memory.

9

By Definition 2.2, 𝜆0 (𝜈) ≥ 𝜏/4, so applied at the single point 𝑎𝑖★ ∈ R there exists 𝑘 ★ with 𝜑𝑝𝑘★ ,𝑟𝑘★ (𝑎𝑖★ ) = 𝑟𝑘 ★ − 𝑑 B (𝑝𝑘 ★ , 𝑎𝑖★ ) ≥ 𝜆0 (𝜈).

(2.11)

≥ In particular 𝑟𝑘 ★ ≥ 𝜆0 ≥ 𝜏/4, so 𝑘 ★ ∈ {𝑘 : 𝑟𝑘 ≥ 𝜏/4} and 𝑤𝑘 ★ ≥ 𝑤 min (𝜏; 𝜈). The triangle inequality and admissibility’s upper-radius bound 𝑟𝑘 ★ ≤ (𝜏 + 𝜆0 )/2 give 0 0 = 𝜏+𝜆 ≥ 𝑟𝑘 ★ , 𝑑 B (𝑝𝑘 ★ , 𝑏𝜎 (𝑖★ ) ) ≥ 𝑑 B (𝑎𝑖★ , 𝑏𝜎 (𝑖★ ) ) − 𝑑 B (𝑝𝑘 ★ , 𝑎𝑖★ ) ≥ 𝜏 − (𝑟𝑘 ★ − 𝜆0 ) ≥ 𝜏 − 𝜏 −𝜆 2 2

so 𝜑𝑝𝑘★ ,𝑟𝑘★ (𝑏𝜎 (𝑖★ ) ) = 0. For 𝑗 ≠ 𝑖 ★, if 𝑑 B (𝑝𝑘 ★ , 𝑏𝜎 ( 𝑗 ) ) ≤ 𝑟𝑘 ★ , the triangle inequality and the same upper-radius bound would give 𝑑 B (𝑎𝑖★ , 𝑏𝜎 ( 𝑗 ) ) ≤ 𝑑 B (𝑎𝑖★ , 𝑝𝑘 ★ ) + 𝑑 B (𝑝𝑘 ★ , 𝑏𝜎 ( 𝑗 ) ) ≤ (𝑟𝑘 ★ − 𝜆0 ) + 𝑟𝑘 ★ = 2𝑟𝑘 ★ − 𝜆0 ≤ 𝜏, contradicting (2.7) since 𝑑 B (𝑎𝑖★ , 𝑏𝜎 ( 𝑗 ) ) > 3 𝑑 B (𝐴, 𝐵) ≥ 3𝜏 > 𝜏. Hence 𝜑𝑝𝑘★ ,𝑟𝑘★ (𝑏𝜎 ( 𝑗 ) ) = 0 for every 𝑗, and Φ𝑘 ★ (𝐵; 𝜈) = 0. By non-negativity of 𝜑𝑝𝑘★ ,𝑟𝑘★ , ∑︁ Φ𝑘 ★ (𝐴; 𝜈) = 𝑤𝑘 ★ 𝜑𝑝𝑘★ ,𝑟𝑘★ (𝑎) ≥ 𝑤𝑘 ★ 𝜑𝑝𝑘★ ,𝑟𝑘★ (𝑎𝑖★ ) ≥ 𝑤𝑘 ★ 𝜆0 . 𝑎∈𝐴 ≥ ≥ Using 𝜆0 ≥ 𝜏/4 and 𝑤𝑘 ★ ≥ 𝑤 min (𝜏; 𝜈), the 𝑘 ★-th coordinate alone contributes at least 𝑤 min (𝜏; 𝜈) · 𝜏/4 = 2 𝜆(𝜏; 𝜈) to the ℓ distance. □

2.3

Budget Comparison and Optimal Configuration

Section 2.2 established the cover-level certificate 𝜆(𝜏; 𝜈) as a structural admissibility statement. This subsection builds the configuration: how many landmarks suffice (Theorem 2.2), the weight and position choices that maximize the worst-case and effective certificates (Proposition 2.2), and the algorithmic realization via farthest-point sampling (Theorem 2.3, Corollary 2.1). The data-adaptive advantage manifests as a (𝐷/𝐿) 2 budget reduction over the uniform grid when diagrams concentrate. Theorem 2.2 (Budget reduction). For any separation scale 𝜏 > 0, there is a 𝜏-admissible configuration whose balls cover R with at most 𝐾adapt ≤ (4𝐷/𝜏) 2 landmarks. Every uniform-grid construction covering [0, 𝐿] 2 at admissible spacing 𝑅 ∈ [𝜏/4, 𝜏/2] uses 𝐾unif = (𝐿/𝑅) 2 ≥ 4(𝐿/𝜏) 2 landmarks (PLACE’s parity-restricted offset variant of Mitra and Virk, 2024 keeps the same Θ((𝐿/𝜏) 2 ) scaling, halved by the parity sieve). Consequently 𝐾adapt (4𝐷/𝜏) 2 𝐷2 ≤ = 4 . 𝐾unif 4(𝐿/𝜏) 2 𝐿2

(2.12)

Proof. Adaptive. Take a maximal (𝜏/4)-separated set {𝑝 1, . . . , 𝑝 𝐾 } ⊂ R, which is also a (𝜏/4)-net of R: by maximality, every 𝑥 ∈ R lies within 𝑑 B -distance 𝜏/4 of some 𝑝𝑘 (otherwise 𝑥 could be added without violating separation). Equip each landmark with radius 𝑟𝑘 = 𝜏/2. The net property gives 𝜑𝑝𝑘 ,𝑟𝑘 (𝑥) ≥ 𝜏/2 −𝜏/4 = 𝜏/4 for some 𝑘, hence 𝜆0 (𝜈) ≥ 𝜏/4 and admissibility (i). Admissibility (ii) is also met: max𝑘 𝑟𝑘 = 𝜏/2 ≤ (𝜏 + 𝜏/4)/2 = 5𝜏/8. The separated property bounds the cardinality: standard packing in (D1, 𝑑 B ) 2 gives 𝐾 ≤ (𝐷/(𝜏/4)) 2 = (4𝐷/𝜏) 2 (the doubling constant 4 on R2 with the ℓ ∞ metric is the elementary observation that an ℓ ∞ -ball of radius 2𝑟 is covered by 4 axis-aligned ℓ ∞ -balls of radius 𝑟 ). Uniform. Take the square grid G𝑅 = 𝑅 · Z2 ∩ [0, 𝐿] 2 with spacing 𝑅 and ball radius 𝑟 = 3𝑅/2 (an ℓ ∞ tiling with 4× overlap; the offset variant of Mitra and Virk (2024) differs only in the half-plane truncation and shares the same Lebesgue-number scaling). By direct computation, 𝜆0 (G𝑅 ) = 𝑅 (the pyramid height at any cell-corner point covered by four adjacent balls). Admissibility (i) 𝜆0 ≥ 𝜏/4 requires 𝑅 ≥ 𝜏/4; admissibility (ii) 3𝑅/2 ≤ (𝜏 + 𝑅)/2 requires 𝑅 ≤ 𝜏/2. The feasible window 𝑅 ∈ [𝜏/4, 𝜏/2] gives |G𝑅 | = (𝐿/𝑅) 2 landmarks, and |G𝑅 | ≥ 4(𝐿/𝜏) 2 since 𝑅 ≤ 𝜏/2. □ 2 The data-relevant region of (D , 𝑑 ) has doubling dimension 𝑑 = 2: away from the diagonal, 𝑑 coincides with ℓ ∞ on R2 , 1 B 0 B

which has doubling constant 4 and hence doubling dimension log2 4 = 2 (Heinonen, 2001, Ch. 10).

10

𝑑 (a) Uniform grid: 𝑟 > 𝜏

𝑑

(b) Adaptive: 𝑟 < 𝜏

𝑑=𝑏

𝑑=𝑏

𝜏 𝐴

𝜏 𝐵

𝐴

𝐵

𝑏

𝑏

Figure 4: Budget-regime distinction (Theorem 2.2). (a) Single-scale uniform grid with 𝑟 > 𝜏 (here 𝑟 = 2𝜏 for visual clarity): two 𝜏-separated diagrams 𝐴, 𝐵 at the same 𝑑-height share the same containing balls and sit at equal distances within them, while landmarks not containing 𝐴, 𝐵 contribute 𝜑𝑘 (𝐴) = 𝜑𝑘 (𝐵) = 0. Either way the coordinate gap vanishes. (b) Adaptive placement with smaller radii (here √︁ 𝑟 = 2𝜏/3) and ∗ positions chosen so that 𝐴, 𝐵 fall in distinct balls: Theorem 2.1 certifies 𝜆(𝜏; 𝜈 ) ≥ 𝜏/(4 |𝜈 ∗ |) > 0. For data concentrated in R with 𝐷 ≪ 𝐿, the bounds of Theorem 2.2 open a budget window in which the adaptive configuration 𝜈 ∗ (equal weights, radii 𝑟𝑘 = 𝜏/2, |𝜈 ∗ | ≤ (4𝐷/𝜏) 2 landmarks) is 𝜏-admissible √︁ and Theorem 2.1 certifies 𝜆(𝜏; 𝜈 ∗ ) = 𝜏/(4 |𝜈 ∗ |) > 0, while any single-scale uniform grid G𝑅 with spacing 𝑅 > 𝜏/2 (equivalently |G𝑅 | < 4(𝐿/𝜏) 2 landmarks) violates admissibility (ii)—since 𝑟 = 3𝑅/2 > (𝜏 + 𝑅)/2 = (𝜏 + 𝜆0 )/2—and falls outside Theorem 2.1’s hypothesis. Two qualifications follow. The single-scale restriction in the comparison above is essential: Majhi et al. (2026)’s multi-scale uniform construction combines 𝑁 scales 𝑅1 < · · · < 𝑅𝑁 and achieves positive 𝜆 at any 𝐾 by spanning scales both above and below 𝜏. PALACE’s adaptive 𝜈 ∗ matches this at the smaller single-scale budget 𝐾 = (4𝐷/𝜏) 2 without multi-scale machinery. Second, in the both-admissible regime 𝐾 ≥ 16(𝐿/𝜏) 2 , a 𝐾-landmark uniform grid and a 𝐾-landmark √ adaptive configuration (equal weights, both 𝜏-admissible) deliver identical worst-case certificates 𝜏/(4 𝐾)—the formula depends on the cover only ≥ through 𝜏 · 𝑤 min , and equal weights flatten any positional advantage. The substantive 𝐿/𝐷-scaling advantage of adaptive placement therefore manifests at the admissibility boundary (Theorem 2.2), not as a power-law gain inside the both-admissible window. We now identify the configuration choices that maximize 𝜆(𝜏; 𝜈), then refine to the data-dependent effective certificate via the Lebesgue number. Definition 2.4 (Effective certificate). Given an admissible configuration 𝜈, the effective certificate is ≥ 𝜆 eff (𝜈) := 𝜆0 (𝜈) · 𝑤 min (𝜏; 𝜈),

(2.13)

≥ sharpening Theorem 2.1’s worst-case 𝜆(𝜏; 𝜈) = (𝜏/4) 𝑤 min by using the actual Lebesgue number 𝜆0 (𝜈) ≥ 𝜏/4 at the witnessing-coordinate step (2.11) of Theorem 2.1’s proof rather than the admissibility floor 𝜏/4.

Proposition 2.2 (Optimal weights and effective certificate). Fix a support R ⊂ D1 ∩ [0, 𝐿] 2 on which diagrams are observed. Among 𝜏-admissible configurations 𝜈 of cardinality 𝐾 with 𝑟𝑘 ≥ 𝜏/4 for every 𝑘: √ (i) equal weights 𝑤𝑘 = 𝐾 −1/2 maximize the certificate 𝜆(𝜏; 𝜈) of Theorem 2.1, giving 𝜏/(4 𝐾) independent of positions {𝑝𝑘 } and radii {𝑟𝑘 }; (ii) the effective certificate 𝜆 eff (𝜈) of Definition 2.4 equals 𝜆0 (𝜈) 𝐾 −1/2 at equal weights. For uniform radii 𝑟𝑘 = 𝑟 , 𝜆0 (𝜈) = 𝑟 − 𝛿𝐾 (𝜈), where 𝛿𝐾 (𝜈) := sup𝑥 ∈ R min𝑘 𝑑 B (𝑥, 𝑝𝑘 ) is the covering radius of R by the landmarks. Maximizing 𝜆 eff over positions therefore reduces to minimizing 𝛿𝐾 on R. 11

Í Proof. (i) From Theorem 2.1, 𝜆(𝜏; 𝜈) = (𝜏/4) · min𝑘: 𝑟𝑘 ≥𝜏/4 𝑤𝑘 . Subject to 𝑘 𝑤𝑘2 = 1 on 𝐾 landmarks, Í the symmetric max-min bound 𝐾 · (min𝑘 𝑤𝑘 ) 2 ≤ 𝑘 𝑤𝑘2 = 1 gives min𝑘 𝑤𝑘 ≤ 𝐾 −1/2 , with equality iff √ all weights equal: 𝑤𝑘 = 𝐾 −1/2 . This yields 𝜆 = 𝜏/(4 𝐾). With equal weights and every 𝑟𝑘 ≥ 𝜏/4, this value has no further dependence on positions or radii, so it is invariant across all admissible equal-weight configurations. (ii) The witnessing-coordinate step (2.11) of Theorem 2.1’s proof gives Φ𝑘 ★ (𝐴) ≥ 𝑤𝑘 ★ 𝜆0 (𝜈) at any 𝑎𝑖★ ∈ R; the theorem then weakens this to 𝑤𝑘 ★ (𝜏/4) via admissibility (i). Keeping the actual 𝜆0 yields 𝜆 eff = ≥ 𝜆0 · 𝑤 min , equal to 𝜆0 𝐾 −1/2 at equal weights. For uniform radii 𝑟𝑘 = 𝑟 , max𝑘 𝜑𝑝𝑘 ,𝑟 (𝑥) = 𝑟 − min𝑘 𝑑 B (𝑥, 𝑝𝑘 ) on R, so 𝜆0 (𝜈) = inf 𝑥 ∈ R (𝑟 − min𝑘 𝑑 B (𝑥, 𝑝𝑘 )) = 𝑟 − 𝛿𝐾 (𝜈). Minimizing 𝛿𝐾 therefore maximizes 𝜆 eff . □ The quantity 𝛿𝐾 (𝜈) = sup𝑥 ∈ R min𝑘 𝑑 B (𝑥, 𝑝𝑘 ) in part (ii) is the covering radius of R by the landmarks {𝑝𝑘 }—the worst data-point’s 𝑑 B -distance to its nearest landmark. Minimizing 𝛿𝐾 over positions {𝑝𝑘 } is the classical 𝑘-center problem on R, NP-hard in general; the next theorem shows that farthest-point sampling solves it within a factor of 2. Theorem 2.3 (FPS as a 𝑘-center 2-approximation). Take R to be a finite set of diagram points (the trainingdiagram-point support), and let 𝐾 ≤ |R|. Let 𝛿𝐾∗ := min |𝑃 |=𝐾, 𝑃 ⊂ R max𝑥 ∈ R min𝑝 ∈𝑃 𝑑 B (𝑥, 𝑝) be the optimal 𝑘-center covering radius of R. Farthest-point sampling, the greedy selection 𝑝𝑡 +1 = arg max min 𝑑 B (𝑞, 𝑝𝑘 ) 𝑞 ∈ R 𝑘 ≤𝑡

(𝑡 = 1, . . . , 𝐾 − 1)

(2.14)

from an arbitrary seed 𝑝 1 ∈ R, produces 𝑃 = {𝑝 1, . . . , 𝑝 𝐾 } with covering radius 𝛿𝐾 (𝑃) := max min 𝑑 B (𝑥, 𝑝) ≤ 2 𝛿𝐾∗ . 𝑥 ∈ R 𝑝 ∈𝑃

(2.15)

Proof (Gonzalez, 1985). Suppose an optimal 𝐾-set 𝑃 ∗ = {𝑐 1∗, . . . , 𝑐 𝐾∗ } achieves covering radius 𝛿𝐾∗ . Define the FPS insertion distance 𝐷𝑡 := min𝑘 <𝑡 𝑑 B (𝑝𝑡 , 𝑝𝑘 ) (𝑡 ≥ 2); the rule (2.14) picks 𝑝𝑡 +1 to maximize 𝐷𝑡 +1 , and 𝐷𝑡 is non-increasing in 𝑡 (each new candidate has more existing landmarks to be close to). Run (2.14) for one additional step (𝑡 = 𝐾) to obtain a candidate 𝑝 𝐾+1 ; 𝐷 𝐾+1 = 𝛿𝐾 (𝑃) by (2.14), and by monotonicity of 𝐷𝑡 every pair (𝑝𝑖 , 𝑝 𝑗 ) with 𝑖 < 𝑗 ≤ 𝐾+1 satisfies 𝑑 B (𝑝𝑖 , 𝑝 𝑗 ) ≥ 𝐷 𝑗 ≥ 𝐷 𝐾+1 = 𝛿𝐾 (𝑃). Pigeonhole assigns two of the 𝐾+1 points to the same optimal cluster {𝑠 : arg min𝑘 𝑑 B (𝑠, 𝑐𝑘∗ ) = 𝑗 }, so they are within 2𝛿𝐾∗ of each other by triangle inequality through 𝑐 ∗𝑗 . Hence 𝛿𝐾 (𝑃) ≤ 2𝛿𝐾∗ . □ Combining Theorem 2.3 with Proposition 2.2(ii) yields a concrete 𝜏-admissible FPS configuration as soon as the optimal covering radius is small enough relative to 𝜏. Corollary 2.1 (Admissible cover from FPS). Fix 𝜏 > 0 and let R be the (finite) training-diagram point set of Theorem 2.3. Suppose the budget 𝐾 is large enough that the optimal 𝑘-center radius satisfies 𝛿𝐾∗ ≤ 𝜏/8 (which holds for 𝐾 ≥ (4𝐷/𝜏) 2 by the packing argument in Theorem 2.2’s proof). Equip the FPS-placed landmarks 𝑃 = {𝑝 1, . . . , 𝑝 𝐾 } with uniform radii 𝑟𝑘 = 𝜏/2 and equal weights 𝑤𝑘 = 𝐾 −1/2 . Then 𝜈 ★ = (𝑃, 𝜏/2, 𝐾 −1/2 ) is 𝜏-admissible (Definition 2.2) with Lebesgue number 𝜆0 (𝜈 ★) = 𝜏/2 − 𝛿𝐾 (𝑃) ≥ 𝜏/2 − 2𝛿𝐾∗ ≥ 𝜏/4, √ and Theorem 2.1 gives the worst-case certificate 𝜆(𝜏; 𝜈 ★) = 𝜏/(4 𝐾).

(2.16)

Proof. 𝛿𝐾∗ ≤ 𝜏/8 combined with Theorem 2.3 yields 𝛿𝐾 (𝑃) ≤ 2𝛿𝐾∗ ≤ 𝜏/4. Proposition 2.2(ii) at uniform radius 𝑟 = 𝜏/2 gives 𝜆0 (𝜈 ★) = 𝜏/2 − 𝛿𝐾 (𝑃) ≥ 𝜏/4, satisfying admissibility (i); admissibility (ii) max𝑘 𝑟𝑘 = 𝜏/2 ≤ (𝜏 + 𝜏/4)/2 = 5𝜏/8 also holds. The certificate value follows from Proposition 2.2(i). □ 12

Where FPS contributes content beyond existence is the effective certificate of Proposition 2.2(ii): at uniform radius 𝑟 = 𝜏/2, 𝜆0 (𝜈) = 𝜏/2 − 𝛿𝐾 (𝑃), and the 2-approximation 𝛿𝐾 (𝑃) ≤ 2𝛿𝐾∗ gives √
√ 𝜆 eff (𝜈 ★) = 𝜆0 (𝜈 ★)/ 𝐾 ≥ 𝜏/2 − 2𝛿𝐾∗ 𝐾, √ within a factor of 2 of the best 𝜆 eff achievable at 𝐾 landmarks. The worst-case certificate 𝜏/(4 𝐾) itself is not FPS-specific (Proposition 2.2(i)): every admissible equal-weight 𝐾-landmark configuration attains it, and Corollary 2.1’s constructive content is the guarantee that FPS produces such a configuration. Remark 2.2 (Practical radius choice). The pipeline of Section 6 uses scaled nearest-neighbor radii 𝑟𝑘 = 𝛼 · 𝑑 NN (𝑝𝑘 ) with 𝑑 NN (𝑝𝑘 ) := min 𝑗≠𝑘 𝑑 B (𝑝𝑘 , 𝑝 𝑗 ), clipped to [𝜏/2, 4𝜏], in place of the uniform 𝑟𝑘 = 𝜏/2 of Corollary 2.1. The upper clip can violate admissibility (ii), max𝑘 𝑟𝑘 ≤ (𝜏 + 𝜆0 )/2, in which case Theorem 2.1 no longer applies. The empirical guarantees of the pipeline flow through the kernel margin 𝛾 > 0 (Theorem 3.1), which is independent of admissibility and 𝜆, so the loss of admissibility (ii) does not affect the empirical results. This closes the Section 2 construction: the FPS-placed equal-weight configuration 𝜈 ★ is 𝜏-admissible with no further optimization, attains both the worst-case and 2-approximate effective certificates as above, and inherits the (𝐷/𝐿) 2 budget reduction of Theorem 2.2 when data concentrates in R ⊊ [0, 𝐿] 2 .

3

Kernel-RKHS Classification Guarantees

This section develops the classification theory for the embedded features √ of Section 2. We first establish the two key quantities—kernel margin 𝛾 and embedding radius 𝑅 = 𝐾—and the 𝜆-bridge linking them to bottleneck-support separation (Proposition 3.1); √ the√landmark kernel 𝑘 𝜈 is constructed in Section 3.1; the data-dependent classification rate 𝑂 ((𝑘−1) 𝐾/(𝛾 𝑚 min )) follows in Section 3.2, with a structural√ √ anchored rate 𝑂 ((𝑘−1) 𝐾/(𝜅𝜆 𝑚 min )) as a corollary; a matching Le Cam sample-starved lower bound closes Section 3.3. Closed-form filtration selection from a candidate pool is the subject of the separate Section 4, paralleling Majhi et al. (2026, Sec. 4)’s descriptor-selection theory; the per-prediction certificate follows in Section 5.1. Let (𝐴, 𝑌 ) be a random pair with joint distribution P on D𝑛 × [𝑘], where 𝑌 ∈ [𝑘] := {1, . . . , 𝑘 } is the class label (here 𝑘 is the class count; the landmark index of Section 2 appears only as a subscript Φ𝑘 , 𝑤𝑘 , 𝑟𝑘 , 𝑝𝑘 , and is disambiguated by context). The summation embedding Φ( · ; 𝜈) : D𝑛 → R𝐾 of Definition 2.1 is lifted to a reproducing kernel Hilbert space (RKHS) via the landmark kernel 𝑘 𝜈 defined in Section 3.1; we associate to P the class-conditional embedding mean 𝜇𝑐 := E[Φ𝜈 (𝐴) | 𝑌 = 𝑐] ∈ H𝑘 𝜈 and the two population quantities driving every bound in this section, √ 𝛾 := 12 min′ ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 (kernel margin), 𝑅 := sup ∥Φ𝜈 (𝐴)∥ H𝑘𝜈 = 𝐾 (embedding radius), 𝑐≠𝑐

𝐴

(3.1) √ with 𝑅 = 𝐾 following from 𝑘 𝜈 (𝐴, 𝐴) = 𝐾 (Remark 3.1 below). Thus 𝑅 is fixed by the configuration cardinality, and 𝛾 is the leading data-dependent quantity entering the classification bounds (the withinclass radius 𝐷 max enters the linear-separability and anchored-rate results below). As in Majhi et al. (2026, Sec. 3), 𝛾 > 0 is possible even when some cross-class diagram pairs are bottleneck-close, since the class means aggregate information from all diagram points. Notation. Throughout Sections 3–5, 𝛾 denotes the population kernel margin, 𝐾 the landmark budget √ (equivalently 𝑅 = 𝐾 the RKHS embedding radius), and 𝑚 the training-sample size with 𝑚𝑐 the count in class 𝑐 and 𝑚 min := min𝑐 𝑚𝑐 . The letter 𝛿 has three uses in this section: 𝛿 ∈ (0, 1) denotes the failure probability (confidence 1 − 𝛿); 𝛿𝑐𝑐 ′ := 𝑑 B (supp P𝑐 , supp P𝑐 ′ ) and 𝛿 ∗ := min𝑐≠𝑐 ′ 𝛿𝑐𝑐 ′ are bottleneck separations 13

between class supports; the covering radius 𝛿𝐾 (𝜈) of Section 2 does not appear after that section. Withinclass radii come in two flavors: 𝐷𝑐 := sup𝐴:𝑌 =𝑐 ∥Φ𝜈 (𝐴) − 𝜇𝑐 ∥ H𝑘𝜈 with 𝐷 max := max𝑐 𝐷𝑐 in the RKHS, used by the classification bounds of this section (Sections 3.2–3.3); and 𝐷¯ 𝑐 := sup𝐴:𝑌 =𝑐 ∥Φ(𝐴; 𝜈) − 𝜇¯𝑐 ∥ ℓ 2 with 𝐷¯ max := max𝑐 𝐷¯ 𝑐 in raw ℓ 2 , used by the nearest-centroid certificate of Section 5.1. The admissibility parameter of Section 2 is always written 𝜏, and the cardinality cap on individual diagrams is 𝑁 max . Í Empirical class means are 𝜇ˆ𝑐 := 𝑚𝑐−1 𝑖: 𝑦𝑖 =𝑐 Φ𝜈 (𝐴𝑖 ). Because Φ is linear in the empirical diagram measure, each 𝜇ˆ𝑐 is an ordinary sample average of i.i.d. bounded H𝑘 𝜈 -vectors, so standard concentration inequalities (Pinelis, McDiarmid) apply directly; a full treatment including Berry–Esseen rates and functional CLTs is developed in (Bagchi et al., 2026). The cover-level certificate 𝜆(𝜏; 𝜈) of Section 2 enters the classification theory through the following bridge, which ties 𝛾 (and the raw-coordinate class-mean separation Δ := min𝑐≠𝑐 ′ ∥ 𝜇¯𝑐 − 𝜇¯𝑐 ′ ∥ ℓ 2 , where 𝜇¯𝑐 := E[Φ(𝐴; 𝜈) | 𝑌 =𝑐]) to the bottleneck-support separation 𝛿 ∗ . The hypothesis 𝛿 ∗ ≥ 𝜏 pairs with noninterference to ensure every cross-class pair is 𝜏-separated, so that Theorem 2.1 delivers a non-trivial lower bound on embedding-space separation. Proposition 3.1 (𝜆-separation bridge). Suppose every cross-class pair satisfies non-interference (Definition 2.3) and 𝛿 ∗ ≥ 𝜏. Then
Δ ≥ 𝜆(𝜏; 𝜈) − 2 𝐷¯ max, 𝛾 ≥ 12 𝜅 𝜆(𝜏; 𝜈) − 2𝐷 max , (3.2) where 𝐷¯ max and 𝐷 max√ are the within-class radii in raw ℓ 2 and the RKHS respectively (notation paragraph above), and 𝜅 = 1/(𝜎 2) is the constant of Corollary 3.1. Proof. For any cross-class pair 𝐴 ∈ supp P𝑐 , 𝐵 ∈ supp P𝑐 ′ , 𝑑 B (𝐴, 𝐵) ≥ 𝛿𝑐𝑐 ′ ≥ 𝛿 ∗ ≥ 𝜏, so non-interference plus Theorem 2.1 give ∥Φ(𝐴; 𝜈) − Φ(𝐵; 𝜈)∥ ℓ 2 ≥ 𝜆(𝜏; 𝜈). The triangle inequality 𝜆 ≤ ∥Φ(𝐴) − Φ(𝐵) ∥ ≤ ∥ 𝜇¯𝑐 − 𝜇¯𝑐 ′ ∥ + 𝐷¯ 𝑐 + 𝐷¯ 𝑐 ′ ≤ Δ + 2𝐷¯ max (after taking the minimum over 𝑐 ≠ 𝑐 ′ ) yields the first half of (3.2). For the second half, Corollary 3.1 applies uniformly to every cross-class pair (𝐴, 𝐵) satisfying the hypotheses, giving 𝐷 𝜈 (𝐴, 𝐵) ≥ 𝜅 𝜆 for each. The RKHS triangle inequality then gives 𝜅 𝜆 ≤ 𝐷 𝜈 (𝐴, 𝐵) ≤ ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 + ∥Φ𝜈 (𝐴) − 𝜇𝑐 ∥ H𝑘𝜈 + ∥Φ𝜈 (𝐵) − 𝜇𝑐 ′ ∥ H𝑘𝜈 ≤ ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 + 2𝐷 max , so ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 ≥ 𝜅 𝜆 − 2𝐷 max ; taking the minimum over 𝑐 ≠ 𝑐 ′ and dividing by 2 yields 𝛾 ≥ 21 (𝜅 𝜆 − 2𝐷 max ). □ Proposition 3.1 has three consequences, paralleling the three roles of Majhi et al. (2026, Prop. 3.1)’s 𝜆-bridge. First, it propagates 𝜆 into the structural classification rate via the bridge-anchored alternative form in Section 3.2. Second, it upgrades the interpretation of the Section 5.1 per-prediction certificate: when the empirical condition 𝑟𝑚 < 12 Δ̂𝑐ˆ fires, the proposition translates this back into a statement about the bottleneck-support separation 𝛿 ∗ , certifying that the class-conditional diagram distributions are genuinely 𝑑 B -separated rather than merely empirically concentrated. Third, it lifts the cover-level certificate of Theorem 2.1 from individual cross-class pairs to first moments of the class-conditional distributions: bottleneck-separated class supports remain ℓ 2 -separated and RKHS-separated in the mean, modulo the within-class spread 2𝐷¯ max (resp. 2𝐷 max ). A persistence vectorization without an explicit lower distortion bound has no analogue of Proposition 3.1. Empirically the non-interference hypothesis essentially never holds pointwise on chemical benchmarks (Section 6, ≤ 0.2% pass rates), so Proposition 3.1 is best read as a structural admissibility-to-separation translation rather than as a verifiable inequality; the operational classification rate flows through Theorem 3.1 (which takes 𝛾 > 0 alone)—see Remark 3.3 and Remark 3.2.

3.1

Landmark Kernel

We now construct the RKHS lift Φ𝜈 of the summation embedding Φ of Definition 2.1 on which Sections 3.2– 3.3 operate. 14

𝐾 be a landmark configuration and 𝜎 > 0 a Definition 3.1 (Landmark kernel). Let 𝜈 = {(𝑝𝑘 , 𝑟𝑘 , 𝑤𝑘 )}𝑘=1 bandwidth parameter. The landmark kernel (LK) is the function 𝑘 𝜈 : D𝑛 × D𝑛 → R defined by

𝑘 𝜈 (𝐴, 𝐵) :=

𝐾 ∑︁ 𝑘=1

 (Φ𝑘 (𝐴; 𝜈) − Φ𝑘 (𝐵; 𝜈)) 2 exp − , 2𝜎 2 

(3.3)

where Φ𝑘 (𝐴; 𝜈) = 𝑤𝑘 𝜑𝑝𝑘 ,𝑟𝑘 (𝐴) is the 𝑘-th embedding coordinate. Each summand in (3.3) is a valid positive-definite kernel (a Gaussian in one coordinate), so 𝑘 𝜈 is positive definite. Let H𝑘 𝜈 denote the RKHS of 𝑘 𝜈 and Φ𝜈 : D𝑛 → H𝑘 𝜈 the canonical feature map. Remark 3.1 (Why an additive landmark kernel). The additive form (3.3) is chosen for theoretical reasons over √ the joint Gaussian exp(− ∥Φ(𝐴)−Φ(𝐵)∥ 2 /2𝜎 2 ). First, 𝑘 𝜈 (𝐴, 𝐴) = 𝐾 gives the clean sup𝐴 ∥Φ𝜈 (𝐴)∥ H𝑘𝜈 = 𝐾 √ used in Theorem 3.1 and Corollary 3.2, while the joint RBF would give 𝑘 (𝐴, 𝐴) = 1 and collapse the 𝐾 factor. É 2 Second, the orthogonal RKHS decomposition H𝑘 𝜈 = H makes MMD decompose coordinate-wise, (𝑘 ) 𝑘 𝑘𝜈 supplying the bridge 𝛾 ≥ Δ/(2𝜎) of Corollary 4.1 (Section 4). The two forms agree empirically up to noise on the benchmarks of Section 6; the non-linear lifting itself is methodologically required, as linear classifiers on the dense adaptive embedding fail (see Section 6.1). The induced RKHS distance is 𝐷 𝜈 (𝐴, 𝐵) := ∥Φ𝜈 (𝐴) − Φ𝜈 (𝐵) ∥ H𝑘𝜈 =

√︁ 𝑘 𝜈 (𝐴, 𝐴) + 𝑘 𝜈 (𝐵, 𝐵) − 2 𝑘 𝜈 (𝐴, 𝐵).

(3.4)

Expanding (3.3): 𝐷 𝜈2 (𝐴, 𝐵) =

𝐾 ∑︁

𝑔𝑘 (𝐴, 𝐵; 𝜈),

2 2
𝑔𝑘 (𝐴, 𝐵; 𝜈) := 2 1 − 𝑒 − (Φ𝑘 (𝐴) −Φ𝑘 (𝐵) ) /(2𝜎 ) .

(3.5)

𝑘=1

√ Corollary 3.1 (Non-degeneracy of the kernel distance). Let 𝜈 be 𝜏-admissible and 𝜎 ≥ 2 𝑁 max𝜏. Then for any 𝐴, 𝐵 ∈ D𝑛 with 𝑑 B (𝐴, 𝐵) ≥ 𝜏 satisfying the non-interference condition (2.7), 𝐷 𝜈 (𝐴, 𝐵) ≥ 𝜅 𝜆(𝜏; 𝜈),

1 𝜅 := √ . 𝜎 2

(3.6)

Í Proof. Let 𝜌 := 𝜆(𝜏; 𝜈) and write 𝑢𝑘 := Φ𝑘 (𝐴; 𝜈) −Φ𝑘 (𝐵; 𝜈). By Theorem 2.1, 𝑘 𝑢𝑘2 = ∥Φ(𝐴; 𝜈) −Φ(𝐵; 𝜈) ∥ ℓ22 ≥ 𝜌 2 . The per-coordinate bound |𝑢𝑘 | ≤ 2𝑁 max𝜏 (each |Φ𝑘 (𝐴; 𝜈)| = 𝑤𝑘 𝜑𝑝𝑘 ,𝑟𝑘 (𝐴) ≤ 𝑤𝑘 𝑁 max𝑟𝑘 ≤ 𝑁 max𝜏, using √ 𝑤𝑘 ≤ 1 and 𝑟𝑘 ≤ 𝜏 from admissibility) together with the hypothesis 𝜎 ≥ 2 𝑁 max𝜏 ensures 𝑢𝑘2 /(2𝜎 2 ) ≤ 1 for every 𝑘, so the Taylor lower bound 1 − 𝑒 −𝑦 ≥ 𝑦/2 valid on 𝑦 ∈ [0, 1] yields 2

2

𝑔𝑘 (𝐴, 𝐵; 𝜈) = 2 1 − 𝑒 −𝑢𝑘 /(2𝜎 )

≥

𝑢𝑘2

(𝑘 = 1, . . . , 𝐾).

2𝜎 2

Summing across coordinates, 𝐷 𝜈2 (𝐴, 𝐵) =

𝐾 ∑︁

𝜌2 1 ∑︁ 2 𝑢 ≥ . 𝑘 2𝜎 2 2𝜎 2 𝐾

𝑔𝑘 (𝐴, 𝐵; 𝜈) ≥

𝑘=1

𝑘=1

Taking the square root yields (3.6).

□

15

√ The hypothesis 𝜎 ≥ 2 𝑁 max𝜏 scales with the worst-case raw embedding range (the same 𝑁 max𝜏 scaling as 𝑅¯ in Section 5.1) and forces a large bandwidth, whereas experiments use 𝜎 ∈ {10−3, 10−2 } to keep the kernel discriminative on observed coordinate gaps. Corollary 3.1 is therefore a worst-case admissibility statement (the kernel does not collapse 𝜏-separated cross-class pairs), not a quantitative bound calibrated to the experimental 𝜎; the empirical classification rate flows through Theorem 3.1 on the data-dependent margin 𝛾, independent of Corollary 3.1. All configuration choices feeding 𝑘 𝜈 are inherited from Section 2: positions and radii from FPS (Theorem 2.3), weights 𝑤𝑘 = 𝐾 −1/2 from Proposition 2.2(i).

3.2

Classification Error Bound

The classification rate that follows is the kernel-RKHS analogue of Majhi et al. (2026, Thm. 3.1): a marginbased excess-risk bound on the maximum-margin SVM in H𝑘 𝜈 , driven by the population kernel margin 𝛾 alone (no structural hypothesis on the cover). We then derive a structural anchored variant (Corollary 3.2) that uses Corollary 3.1’s per-pair RKHS distance bound to bypass the class-mean concentration step, and record the weaker bridge-anchored form (immediately following) for cross-paper continuity with Majhi et al. (2026, Cor. 3.1). We train a maximum-margin SVM 𝑓ˆ on the embedded training data {(Φ𝜈 (𝐴𝑖 ), 𝑦𝑖 )}𝑚 𝑖=1 in H𝑘 𝜈 via the OvO majority-vote reduction (matched directly by the kernel-SVM backend in Section 6, sklearn.svm.SVC with kernel=’precomputed’, which uses OvO by default), and measure its quality by the generalizab𝜌 ( 𝑓ˆ) tion 0-1 risk R ( 𝑓ˆ) := P( 𝑓ˆ(𝐴) ≠ 𝑌 ). For a margin parameter 𝜌 > 0, the empirical 𝜌-margin loss R is the fraction of training points whose signed margin under 𝑓ˆ falls below 𝜌 (Mohri et al., 2018, Sec. 5.4); b𝜌 is aggregated across the binary OvO sub-problems as made precise in the proof of for the multiclass 𝑓ˆ, R Theorem 3.1. Theorem 3.1 (Classification error bound). Let {(𝐴𝑖 , 𝑦𝑖 )}𝑚 𝑖=1 be 𝑚 i.i.d. training samples from a distribution on finite persistence diagrams with 𝑘 classes and kernel margin 𝛾 > 0. Let 𝜈 be a configuration with 𝐾 landmarks, 𝑚𝑐 the per-class sample count, 𝑚 min := min𝑐 𝑚𝑐 , and 𝑓ˆ the maximum-margin SVM in H𝑘 𝜈 trained via OvO with majority voting. Assume 𝑚 min ≥ 32𝐾 log(4𝑘/𝛿)/𝛾 2 (so that empirical class means concentrate at scale below 𝛾/2). Set 𝜌 := 𝛾/2. Then with probability at least 1 − 𝛿 over the draw, √︄ √ log(𝑘/𝛿) ª 4(𝑘 − 1) 𝐾 © b𝜌 ( 𝑓ˆ) + R ( 𝑓ˆ) ≤ R + 𝑂­ (3.7) ®. √ 𝑚 min 𝛾 𝑚 min « ¬ √ Equation (3.7) is the kernel-RKHS analogue of Majhi et al. (2026, Thm. 3.1) under 𝑅 ↔ 𝐾, Δ ↔ 2𝛾. The proof structure is the same: per-pair margin lower bound, Pinelis concentration of empirical class
means, MRT margin bound on each OvO sub-problem, union bound across 𝑘2 sub-problems, and the √ 3/2 𝐾/(𝛾 √𝑚)) (𝑘−1)-max OvO majority-vote √ bound. For balanced classes 𝑚𝑐 ≍ 𝑚/𝑘 the rate term is 𝑂 (𝑘 in the total sample 𝑚; the 𝑘 overhead is the price of OvO, since each binary sub-problem trains on only Θ(𝑚/𝑘) samples. √ Proof. Since 𝑘 𝜈 (𝐴, 𝐴) = 𝐾 (Definition 3.1 sums 𝐾 diagonal Gaussians), sup𝐴 ∥Φ𝜈 (𝐴)∥ H𝑘𝜈 = 𝐾, and in √ √ particular ∥𝜇𝑐 ∥ H𝑘𝜈 ≤ 𝐾 by Jensen, so ∥Φ𝜈 (𝐴𝑖 ) − 𝜇𝑐 ∥ H𝑘𝜈 ≤ 2 𝐾 for every training point. Per-pair margin. For each unordered pair {𝑐, 𝑐 ′ }, the population class means are separated by pairwise kernel margin 𝛾𝑐𝑐 ′ := 21 ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 ≥ 𝛾 = 2𝜌. Concentration of empirical class means. Conditional on √ the per-class counts {𝑚𝑐 }, the centered RKHS 𝜈 vectors {Φ (𝐴𝑖 ) − 𝜇𝑐 : 𝑌𝑖 = 𝑐} are i.i.d. with norm bound 2 𝐾. Pinelis’s Hilbert-space Hoeffding inequality

16

(Majhi et al., 2026, Lemma A.1) and a union bound over the 𝑘 classes yield, with probability ≥ 1 − 𝛿/2, √︄ √ 2 log(4𝑘/𝛿) 𝜀𝑚 := max ∥ 𝜇ˆ𝑐 − 𝜇𝑐 ∥ H𝑘𝜈 ≤ 2 𝐾 . 𝑐 𝑚 min The sample-size hypothesis 𝑚 min ≥ 32𝐾 log(4𝑘/𝛿)/𝛾 2 gives 𝜀𝑚 ≤ 𝛾/2 = 𝜌, so by the reverse triangle inequality the empirical pairwise kernel margin 𝛾ˆ𝑐𝑐 ′ := 12 ∥ 𝜇ˆ𝑐 − 𝜇ˆ𝑐 ′ ∥ H𝑘𝜈 ≥ 𝛾𝑐𝑐 ′ − 𝜀𝑚 ≥ 𝜌 for every pair 𝑐 ≠ 𝑐 ′. Per-pair OvO bound. The OvO sub-problem between 𝑐, 𝑐 ′ trains √ on 𝑚𝑐 + 𝑚𝑐 ′ ≥ 2𝑚 min samples from 𝜈 the unit-norm linear hypothesis class on H𝑘 𝜈 with ∥Φ (𝐴) ∥ H𝑘𝜈 ≤ 𝐾. The margin-based Rademacher
bound (Mohri et al., 2018, Cor. 5.11) at margin 𝜌 and confidence 𝛿 ′ := 𝛿/(2 𝑘2 ) yields, with probability ≥ 1 − 𝛿 ′, √︄ √︄ √ √ log(𝑘/𝛿) 2 𝐾 4 𝐾 © © log(𝑘/𝛿) ª ª b𝜌 (ℎ𝑐𝑐 ′ ) + √ b𝜌 (ℎ𝑐𝑐 ′ ) + √ R (ℎ𝑐𝑐 ′ ) ≤ R + 𝑂­ + 𝑂­ ® = R ®, 𝑚 min 𝑚 min 𝜌 𝑚 min 𝛾 𝑚 min « « ¬ ¬ using log(2/𝛿 ′ ) = 𝑂 (log(𝑘/𝛿)).
Aggregation. A union bound over the 𝑘2 OvO sub-problems at level 𝛿/2, combined with the 𝛿/2 budget for the class-mean concentration step, gives total coverage ≥ 1−𝛿. The OvO majority-vote rule errs at 𝑦 = 𝑐 only if some pairwise classifier ℎ𝑐𝑐 ′ (𝑐 ′ ≠ 𝑐) misclassifies, so R ( 𝑓ˆ) ≤ (𝑘 − 1) max𝑐≠𝑐 ′ R (ℎ𝑐𝑐 ′ ). Substituting b𝜌 ( 𝑓ˆ) := (𝑘 − 1) max𝑐≠𝑐 ′ R b𝜌 (ℎ𝑐𝑐 ′ ) yields (3.7). the per-pair bound and defining R □ Remark 3.2 (Empirical scope of Theorem 3.1). Theorem 3.1 requires only 𝛾 > 0 and the sample-size√hypothesis 𝑚 min ≥ 32𝐾 log(4𝑘/𝛿)/𝛾 2 (the same hypothesis as Majhi et al. (2026, Thm. 3.1) under 𝑅 ↔ 𝐾, Δ ↔ 2𝛾: 128𝑅 2 /Δ2 = 32𝐾/𝛾 2 ); no structural hypothesis on the cover is invoked (no non-interference, no 𝜆, no constraint on 𝜎). This makes Theorem 3.1 the empirical workhorse of Section 6 and the natural pairing with the matching Le Cam lower bound (Theorem 3.2); the non-interference audit and the 𝜎-regime caveat (the post-proof discussion of Corollary 3.1 in Section 3.1, and the Section 6 audit) are relevant only to the structural Corollary 3.2 (and the bridge-anchored form below) that follow, not to Theorem 3.1 itself. Under admissibility plus non-interference, the SVM’s geometric margin is determined by the closest cross-class data pair (rather than by the class means), and Corollary 3.1 bounds that distance directly by 𝜅𝜆. This gives the structural classification rate below; the alternative class-mean route via the bridge of Proposition 3.1 (the Majhi et al. (2026, Cor. 3.1) parallel) is recorded as a follow-up paragraph. Corollary 3.2 (Structural rate via per-pair distance). Let the training data be drawn i.i.d. from a distribution on D𝑛 with 𝑘 classes whose cross-class pairs are 𝜏-separated and √ satisfy non-interference (Definition 2.3). Let 𝜈 be a 𝜏-admissible configuration with 𝐾 landmarks and 𝜎 ≥ 2 𝑁 max𝜏. Let 𝑓ˆ be the maximum-margin SVM classifier in H𝑘 𝜈 . Then with probability at least 1 − 𝛿, √︄ √ log(𝑘/𝛿) ª 4(𝑘 − 1) 𝐾 © b𝜌 ( 𝑓ˆ) + R ( 𝑓ˆ) ≤ R + 𝑂­ ®, √ cls 𝑚 min 𝜅 𝜆(𝜏; 𝜈) 𝑚 min « ¬

(3.8)

√ b𝜌 ( 𝑓ˆ) = 0 identically (every cross-class where 𝜅 = 1/(𝜎 2) and 𝜌 cls := 𝜅 𝜆(𝜏; 𝜈)/2. Under the hypotheses, R cls training pair is at RKHS distance ≥ 𝜅𝜆 by Corollary 3.1, so the SVM achieves geometric margin ≥ 𝜌 cls on every training point), and (3.8) reduces to a 𝜆-anchored excess-risk bound that requires no sample-size hypothesis (the proof routes through pairwise data distances rather than class-mean concentration).

17

Proof. By hypothesis, any two diagrams 𝐴𝑖 , 𝐴 𝑗 from different classes satisfy 𝑑 B (𝐴𝑖 , 𝐴 𝑗 ) ≥ 𝜏. Corollary 3.1 therefore gives ∥Φ𝜈 (𝐴𝑖 ) − Φ𝜈 (𝐴 𝑗 ) ∥ H𝑘𝜈 ≥ 𝜅 𝜆(𝜏; 𝜈), so the maximum-margin separating hyperplane has geometric margin (half the closest cross-class distance) at least 𝜌 cls := 𝜅 𝜆/2. Every training point sits at b𝜌 ( 𝑓ˆ) = 0. Applying the Rademacher complexity signed distance ≥ 𝜌 cls from 𝑓ˆ’s decision boundary, so R cls √ bound for margin classifiers (Mohri et al., 2018, Cor. 5.11) at margin 𝜌 cls with sup𝐴 ∥Φ𝜈 (𝐴) ∥ H𝑘𝜈 ≤ 𝐾 on √ √
each OvO sub-problem gives per-pair rate 2 𝐾/𝜌 cls = 4 𝐾/(𝜅𝜆); union bound over 𝑘2 pairs and the OvO majority-vote (𝑘−1)-max aggregation (R ( 𝑓ˆ) ≤ (𝑘 − 1) max𝑐≠𝑐 ′ R (ℎ𝑐𝑐 ′ ), as in Theorem 3.1) yields (3.8). □ A bridge-anchored variant routing through Proposition 3.1’s 𝛾 ≥ 12 (𝜅𝜆−2𝐷 max ) gives the strictly looser PALACE analogue of Majhi et al. (2026, Cor. 3.1); Corollary 3.2 above is the load-bearing form here. √︁ Replacing an ℓ-landmark uniform grid with 𝐾 ≪ ℓ adaptive landmarks tightens (3.8) by ℓ/𝐾 in the numerator, compounded by the certificate improvement 𝜆(𝜏; 𝜈) ≥ 𝜆(𝜏; G𝑅 ) in the denominator: on a MUTAG configuration with ℓ in the low thousands and adaptive 𝐾 = 50, the combined effect is on the order of 5–10×. PALACE’s coordinate sparsity√(𝜏-admissibility plus 𝑁 max bound the nonzero coordinates per diagram) further tightens the worst-case 𝐾 in practice (see Remark 5.2 in Section 5.1, MUTAG Σ̂𝑐 (𝜈 ∗ ) op ≈ 0.023). √ Substituting Proposition 2.2(i)’s equal-weight certificate 𝜆 = 𝜏/(4 𝐾) into Corollary 3.2’s rate term √ gives 16(𝑘−1)𝐾/(𝜅𝜏 𝑚 min )—a bound shared by every 𝜏-admissible equal-weight 𝐾-landmark configuration but monotone increasing in 𝐾, so the structural rate alone does not justify larger budgets. Empirically, larger 𝐾 helps via the data-dependent Theorem 3.1’s 𝛾ˆ growing with 𝐾 as additional landmarks expose discriminative coordinates (Section 6 sweeps). Beyond the equal-weight optimality just established, the admissibility constraint of Definition 2.2(i) acts as structural regularization on the configuration 𝜈. It rules out memorization: any candidate 𝜈 mem that places landmarks at training points with radii 𝜖 < 𝜏/4 has Lebesgue number 𝜆0 (𝜈 mem ) ≤ max𝑘 𝑟𝑘 = 𝜖 < 𝜏/4 ≥ and so violates Definition 2.2(i) (𝜆 = 0 in such configurations, since no landmark has 𝑟𝑘 ≥ 𝜏/4 and 𝑤 min is undefined in Theorem 2.1’s formula). Equivalently, admissibility enforces max𝑘 𝑟𝑘 ≥ 𝜏/4 on every valid configuration. This is the landmark-cover analogue of ℓ2 regularization for SVM weights—unlike ℓ2 , which penalizes large weights, the certificate forbids configurations with arbitrarily small radii that pin landmarks at training points—and it explains the small empirical generalization gap (test–train at 2.5–3.5% across all landmark budgets 𝐾, Section 6). The classification rate of Theorem 3.1 together with the structural-anchored Corollary 3.2 translates a fortiori to an excess-risk bound, since E ( 𝑓ˆ) := R ( 𝑓ˆ) − 𝑅 ∗ ≤ R ( 𝑓ˆ). These results pair directly with the matching Le√Cam two-point lower bound that follows in Section 3.3 (Theorem 3.2), under the correspondence 𝑅 ↔ 𝐾, Δ ↔ 2𝛾 with Majhi et al. (2026, Sec. 3.2).

3.3

Matching Lower Bound, Consistency, and Linear Separability

√ √ The rate 𝐾/(𝛾 𝑚 min ) of Theorem 3.1 is the standard Rademacher–margin rate; its sample-size hypothesis 𝑚 min ≳ 𝐾 log(𝑘/𝛿)/𝛾 2 is sufficient for non-trivial accuracy. The two-point minimax lower bound √ below (stated for 𝑘 = 2, where 𝑚 min = 𝑚/2 for balanced classes) shows that 𝑚 min ≳ 𝐾/𝛾 is necessary: no classifier achieves small excess risk on samples below that scale. The polynomial gap between the nec√ essary 𝐾/𝛾 and sufficient 𝐾 log(𝑘/𝛿)/𝛾 2 thresholds is the moderate-sample regime, the same gap Majhi √ et al. (2026, Rem. 3.3) leaves open under 𝑅 ↔ 𝐾, Δ ↔ 2𝛾 (see Remark 3.3). The argument is Le Cam’s two-point method in a Hilbert-space ball, mirroring the linear lower bound of (Majhi et al., 2026, Thm. 3.2). Definition 3.2 (Problem class). For 𝐾 ∈ N and 𝛾 > 0, let Π(𝐾, 𝛾) denote the class of binary distributions Q

18

on H𝑘 𝜈 × {±1} satisfying sup 𝑧 ∈supp(Q)

∥𝑧 ∥ H𝑘𝜈 ≤

√ 𝐾,

∥𝜇+1 − 𝜇 −1 ∥ H𝑘𝜈 = 2𝛾,

where 𝜇±1 are the class means under Q. The push-forward Φ#𝜈 P of any binary diagram distribution P on √ D𝑛 × {±1} with kernel margin 𝛾 lies in Π(𝐾, 𝛾), since sup𝐴 ∥Φ𝜈 (𝐴)∥ H𝑘𝜈 = 𝐾 realizes the radius constraint and the kernel margin defines √ the mean separation. This mirrors the (𝑅, Δ) family of Majhi et al. (2026) under the correspondence 𝑅 ↔ 𝐾 and Δ ↔ 2𝛾. √ Theorem 3.2 (Minimax lower bound in the RKHS). Let 𝐾 ∈ N and 𝛾 > 0 with 𝛾 ≤ 𝐾/3 (the binary-regime 𝑘 = 2, where 𝑚 min = 𝑚/2 for√balanced classes), and let 𝑐 2 be the R2 Hellinger constant of Step 2 below. For every sample size 𝑚 ≤ 𝑚★ := 𝐾/(12 𝑐 2 𝛾), inf 𝑓ˆ

sup Q∈Π (𝐾,𝛾 )

E ( 𝑓ˆ) ≥ 18 ,

(3.9)

where the infimum is over classifiers 𝑓ˆ : H𝑘𝑚𝜈 → {±1}. Consequently no classifier—regardless of computational √ budget or model class—can reach vanishing excess risk on Π(𝐾, 𝛾) without 𝑚 = Ω( 𝐾/𝛾) samples. Under the √ correspondence 𝑅 ↔ 𝐾, Δ ↔ 2𝛾 this matches Majhi et al. (2026, √ √ Thm. 3.2) exactly: PI’s threshold 𝑚 ≤ 𝑐𝑅/Δ with hypothesis Δ ≤ 2𝑅/3 becomes 𝑚 ≤ 𝑐 𝐾/(2𝛾) with 𝛾 ≤ 𝐾/3, the same scaling. Proof. We construct an instance of Π(𝐾, 𝛾) directly in H𝑘 𝜈 and apply Le Cam’s two-point method, exactly as in (Majhi et al., 2026, Thm. 3.2). Every binary diagram distribution with kernel margin 𝛾 pushes forward into Π(𝐾, 𝛾) (Definition 3.2), so the Hilbert-space bound applies a fortiori to the diagram subfamily. Step 1: Two class-conditional distributions. Pick any unit vector 𝑒 ∈ H𝑘 𝜈 and set 𝜇 := 𝛾𝑒, so ∥𝜇+1 − 𝜇 −1 ∥ = 2𝛾 with 𝜇 ±1 = ±𝜇 (the factor 2 aligns the definitions: our kernel margin is 21 min𝑐≠𝑐 ′ ∥𝜇𝑐 − 𝜇𝑐 ′ ∥, √ √ √ so the raw mean separation is 2𝛾). Let 𝑟 := 𝐾 − 𝛾; by 𝛾 ≤ 𝐾, 𝑟 ≥ 0 (strictly positive if 𝛾 < 𝐾). Define Q+1 := Unif (𝐵(+𝜇, 𝑟 )),

Q−1 := Unif (𝐵(−𝜇, 𝑟 )),

as uniforms on Hilbert-space balls (projected √ onto any 2-dimensional subspace containing 𝑒, by rotational symmetry). By construction Q±1 ⊂ 𝐵(0, 𝐾) and the mean separation is 2𝛾, so Q ∈ Π(𝐾, 𝛾). Step 2: Hellinger on two translated uniform balls. For uniforms on two radius-𝑟 balls in R2 (after projecting onto the 2-dimensional subspace spanned by 𝑒 and one orthogonal direction; by rotational symmetry of the construction, this reduces the squared Hellinger to a 2d ball-overlap calculation), translated by 2𝜇 with ∥𝜇 ∥ ≤ 𝑟 /2 (verified below), the volume-of-intersection identity 𝐻 2 (Q+1, Q−1 ) = 1 − vol(𝐵(𝜇, 𝑟 ) ∩ 𝐵(−𝜇, 𝑟 ))/vol(𝐵(0, 𝑟 )) together with the linearization 1 − vol ratio ≤ 𝑐 2 ∥𝜇 ∥ /𝑟 (Majhi et al., 2026, Lem. A.2; the constant 𝑐 2 depends only on the surface-to-volume ratio of the unit ball in R2 , with 𝑐 2 ≤ 2/𝜋) gives ∥𝜇 ∥ 𝑐2 𝛾 3𝑐 2 𝛾 𝐻 2 (Q+1, Q−1 ) ≤ 𝑐 2 ≤ √ , = √ 𝑟 𝐾 −𝛾 2 𝐾 √ √ √ where the hypothesis √ 𝛾 ≤ 𝐾/3√ gives 𝑟 = 𝐾 − 𝛾 ≥ 2 𝐾/3 ≥ 2𝛾 (so ∥𝜇 ∥ = 𝛾 ≤ 𝑟 /2 as required) and the last inequality uses 𝐾 − 𝛾 ≥ 2 𝐾/3. (The KL divergence is infinite for translated uniforms on distinct balls: on 𝐵 + \ 𝐵 − , 𝑝 + > 0 and 𝑝 − = 0, making the integrand 𝑝 + log(𝑝 + /𝑝 − ) = +∞ on a set of positive measure. Pinsker’s inequality is therefore vacuous in this setting; the Hellinger route is the correct one, as in Majhi et al., 2026, Lem. A.2.)

19

⊗𝑚 2 Step 3: Le Cam + Hellinger tensorization. Hellinger tensorizes as 𝐻 2 (Q+1 , Q⊗𝑚 −1 ) ≤ 𝑚 𝐻 (Q+1, Q −1 ) √ (Tsybakov, 2009, Ch. 2.4), and TV ≤ 2𝐻 2 , so √︃ √︁ √ ⊗𝑚 ⊗𝑚 2 TV(Q+1 , Q−1 ) ≤ 2𝑚 𝐻 (Q+1, Q−1 ) ≤ 3𝑐 2 𝑚 𝛾/ 𝐾 .

√ For 𝑚 ≤ 𝐾/(12 𝑐 2 𝛾) =: 𝑚★, TV ≤ 1/2, and Le Cam’s two-point lemma gives E ( 𝑓ˆ) ≥ 14 (1 − TV) ≥ 14 · 12 = 18 . √ Step 4: Necessity threshold. The bound E ≥ 1/8 holds for every 𝑚 ≤ 𝑚★ = 𝐾/(12 √ 𝑐 2 𝛾), establishing the necessity claim: no classifier reaches vanishing excess risk without 𝑚 = Ω( 𝐾/𝛾) samples. For 𝑚 > 𝑚★ the Hellinger tensorization bound exceeds the Le Cam usability√threshold and the two-point argument yields no information; the polynomial gap between the necessary 𝐾/𝛾 and sufficient 𝐾 log(𝑘/𝛿)/𝛾 2 thresholds (the latter from Theorem 3.1’s sample-size hypothesis) is the moderate-sample regime, recorded in Remark 3.3. □ √ √ Remark 3.3 (Scope of the lower bound). Theorem 3.1 delivers an upper rate of 𝑂 ((𝑘−1) 𝐾/(𝛾 𝑚 min )) for 2 . Theorem 3.2 delivers a constant lower bound all 𝑚 min above its sample-size hypothesis 32𝐾 log(4𝑘/𝛿)/𝛾 √ ≥ 1/8 in the sample-starved regime 𝑚 min ≲ 𝐾/𝛾; beyond that regime the specific two-point Le Cam construction used here yields no information because the Hellinger-tensorized TV approaches 1, making the lower-bound argument vacuous for that pair of hypotheses. Combined, non-trivial accuracy requires 𝑚√min = √ Ω( 𝐾/𝛾) and is achievable at 𝑚 min = 𝑂 (𝐾 log(𝑘/𝛿)/𝛾 2 ). The polynomial gap between the necessary 𝐾/𝛾 2 thresholds is the same gap Majhi et al. (2026, Rem. 3.3) documents in linear and sufficient 𝐾 log(𝑘/𝛿)/𝛾 √ form (under 𝑅 ↔ 𝐾, Δ ↔ 2𝛾); closing it can proceed by either (i) an Assouad/Fano construction over √ √ √ Θ( 𝑚 min )-spaced hypotheses, tightening the lower bound to a matching Ω( 𝐾/(𝛾 𝑚 min )) rate; or (ii) a Mammen–Tsybakov margin condition tightening the upper bound to 𝑂 (1/𝑚 min ). Both directions are open. For multi-class problems (𝑘 > 2), the upper bound additionally carries the (𝑘−1) factor from the OvO majorityvote reduction in Theorem 3.1—the same 𝑘-dependent gap Majhi et al. (2026, Thm. 3.1) carries, since the Le Cam two-point construction √is intrinsically binary in both papers. The practical takeaway is the samplestarved threshold 𝑚 min = Ω( 𝐾/𝛾): no classifier on the landmark-kernel embedding can hope for non-trivial accuracy below it. Theorem 3.2 is stated in 𝛾 rather than 𝜆(𝜏; 𝜈) because 𝜆 is a property of the configuration 𝜈, not of the data distribution, and is therefore not a quantity an adversarial Q may choose; the structural classification rate (Corollary 3.2) and the worst-case 𝜆 at fixed 𝐾 (Proposition 2.2) are the right cross-references for the configuration side. The classification rate of Theorem 3.1 depends on the population kernel margin 𝛾; for the rate to be operationally useful, 𝛾 must be estimable from training data. The next proposition gives the concentration √ ˆ validating its use as a plug-in for 𝛾 in the closed-form selection statistic 𝛾/ ˆ 𝐾 of the empirical estimator 𝛾, of Section 4, and mirroring Majhi et al. (2026, Prop. 3.2). ˆ Let 𝛾ˆ = 12 min𝑐≠𝑐 ′ ∥ 𝜇ˆ𝑐 − 𝜇ˆ𝑐 ′ ∥ H𝑘𝜈 be the empirical kernel margin (DefiProposition 3.2 (Consistency of 𝛾). nition 4.1). For every 𝜀 > 0,   2 𝜀 𝑚 min P(|𝛾ˆ − 𝛾 | > 𝜀) ≤ 2𝑘 exp − . 8𝐾 √︁ In particular, |𝛾ˆ − 𝛾 | = 𝑂 𝑃 ( 𝐾/𝑚 min ).

20

Proof. By the reverse triangle inequality |𝛾ˆ − 𝛾 | ≤ max𝑐 ∥ 𝜇ˆ𝑐 − 𝜇𝑐 ∥ H𝑘𝜈 . Conditional on 𝑌𝑖 = 𝑐, the centered √ RKHS vectors Φ𝜈 (𝐴𝑖 ) − 𝜇𝑐 are i.i.d. with norm bound ∥Φ𝜈 (𝐴𝑖 ) − 𝜇𝑐 ∥ H𝑘𝜈 ≤ 2 𝐾 (triangle on ∥Φ𝜈 (𝐴)∥ H𝑘𝜈 ≤ √ √ 𝐾 and Jensen on ∥𝜇𝑐 ∥ H𝑘𝜈 ≤ 𝐾). Pinelis’s Hilbert-space Hoeffding inequality (Majhi et al., 2026, Lemma A.1) √ □ with bound 2 𝐾 and a union bound over the 𝑘 classes yield the result. √ While 𝛾 > 0 alone delivers the 1/ 𝑚 min excess-risk rate of Theorem 3.1, a stronger structural condition— small within-class spread relative to 𝛾—yields population-level perfect classification with an explicit RKHS margin, mirroring Majhi et al. (2026, Prop. 3.3). Proposition 3.3 (Linear separability in the RKHS). With 𝐷𝑐 := sup𝐴:𝑌 =𝑐 ∥Φ𝜈 (𝐴) − 𝜇𝑐 ∥ H𝑘𝜈 and 𝐷 max := max𝑐 𝐷𝑐 , if 𝐷 max < 𝛾 then the nearest-centroid classifier in H𝑘 𝜈 achieves zero error with geometric margin ≥ 𝛾 − 𝐷 max > 0. Proof. For 𝐴 from class 𝑐 and any 𝑐 ′ ≠ 𝑐, ∥Φ𝜈 (𝐴) − 𝜇𝑐 ∥ H𝑘𝜈 ≤ 𝐷𝑐 ≤ 𝐷 max and the reverse triangle inequality gives ∥Φ𝜈 (𝐴) − 𝜇𝑐 ′ ∥ H𝑘𝜈 ≥ ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 − 𝐷 max ≥ 2𝛾 − 𝐷 max . Subtracting yields a closer-to-𝜇𝑐 gap of ≥ 2𝛾 − 2𝐷 max = 2(𝛾 − 𝐷 max ) > 0, so Φ𝜈 (𝐴) is strictly closer to 𝜇𝑐 than to any other class mean (zero error) with half-gap ≥ 𝛾 − 𝐷 max (the geometric margin). □ Although the proof is a generic Hilbert-space geometric fact, whether the hypothesis 𝐷 max < 𝛾 can plausibly hold on PALACE depends on structural properties of the embedding. Each landmark coordinate Φ𝑘 (𝐴; 𝜈) = 𝑤𝑘 𝜑𝑝𝑘 ,𝑟𝑘 (𝐴) is supported on a 𝑑 B -ball of radius 𝑟𝑘 , and FPS spacing forces each diagram point 𝑎 ∈ 𝐴 to activate a constant number 𝑂 (𝛼 2 ) of landmarks (Remark 5.2 in Section 5.1). The embedding Φ(𝐴; 𝜈) therefore has at most 𝑂 (|𝐴|) ≤ 𝑂 (𝑁 max ) nonzero coordinates out of 𝐾, so 𝐷𝑐 is effectively confined to the low-rank subspace of active coordinates and remains small relative to 𝛾 when the descriptor exposes a structural class gap. Persistence images and landscapes, whose Gaussian-blurred or order-statistic coordinates are weakly active on every diagram, spread within-class variation across all 𝐾 directions, so 𝐷𝑐 scales with 𝐾 rather than with the descriptor’s effective rank —a regime where 𝐷 max < 𝛾 is harder to achieve even when classes are bottleneck-separated. This is the same sparsity ingredient that makes Theorem 5.1’s certificate non-vacuous on PALACE (Remark 5.2), instantiated here at the level of the within-class-radius hypothesis instead of the operator-norm certificate condition; the parallel to Majhi et al. (2026, Prop. 3.3)’s discussion is exact under Δ ↔ 2𝛾. Both Proposition 3.2 (consistency) and Proposition 3.3 (separability) treat 𝛾 as a fixed property of a given configuration and descriptor. Section 4 (the next section) addresses how to choose the configuration and filtration that maximize 𝛾ˆ from a candidate pool, paralleling Section 4 of Majhi et al. (2026)’s descriptorselection theory.

4

A Data-Dependent Selection Statistic

This section addresses filtration and configuration selection from a candidate pool, paralleling Majhi et al. (2026, Sec. 4)’s descriptor-selection theory: given a fixed budget 𝐾 and admissibility hypotheses, which choice of filtration 𝐹 and configuration 𝜈 should one make? Here 𝐹 denotes a filtration of the input—for graphs, the sublevel-set filtration of a real-valued descriptor 𝑓 : 𝑋 → R (degree, centrality, Ricci curvature, heat-kernel signature, etc.); for point clouds, a radius-parameterized construction (Vietoris–Rips, √ 𝛼-complex) (Majhi et al., 2026, Sec. 2). By Proposition 2.2, the cover-level certificate 𝜆(𝜏; 𝜈) = 𝜏/(4 𝐾) at fixed 𝐾 with equal weights is uniform over admissible configurations—independent of filtration, landmark positions, and radii—yet empirical accuracy varies substantially across these choices (Table 4), so 𝜆 cannot rank. A data-dependent statistic based on the kernel margin (computable in 𝑂 (𝑚 2 ) from the gram matrix already used for SVM fitting, no extra training) is needed. 21

Definition 4.1 (Kernel margin). Let 𝑘 𝜈 be the landmark kernel (Definition 3.1). For a distribution P on D𝑛 × [𝑘] with class means 𝜇𝑐 := E[Φ𝜈 (𝐴) | 𝑌 =𝑐] ∈ H𝑘 𝜈 , the (population) kernel margin 𝛾 = 𝛾 (𝑘 𝜈 ; P) is 𝛾 := 12 min′ ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 .

(4.1)

𝑐≠𝑐

Given i.i.d. samples {(𝐴𝑖 , 𝑦𝑖 )}𝑚 𝑖=1 with per-class counts 𝑚𝑐 , the empirical kernel margin 𝛾ˆ = 𝛾ˆ (𝑘 𝜈 ) is 𝛾ˆ := 21 min′ ∥ 𝜇ˆ𝑐 − 𝜇ˆ𝑐 ′ ∥ H𝑘𝜈 , 𝑐≠𝑐

𝜇ˆ𝑐 :=

1 ∑︁ 𝜈 Φ (𝐴𝑖 ). 𝑚𝑐 𝑖: 𝑦 =𝑐

(4.2)

𝑖

We suppress the arguments (𝑘 𝜈 , P) throughout when the configuration and population are fixed by context, ˆ in parallel with Majhi et al. (2026)’s suppressed notation for Δ and Δ̂. writing simply 𝛾 and 𝛾,

4.1

Kernel–Mahalanobis margin

The Mahalanobis pivot of Majhi et al. (2026, Sec. 4.1) lifts directly into the RKHS via the kernel-FDA realization: the same LDA-Bayes-margin form, with Σ now an operator on H𝑘 𝜈 rather than a Rℓ matrix. Definition 4.2 (Kernel–Mahalanobis margin). Paralleling the Mahalanobis pivot of (Majhi et al., 2026, Í Sec. 4.1), let Σ(𝑘 𝜈 ; P) := 𝑘1 𝑐 Cov(Φ𝜈 (𝐴) | 𝑌 =𝑐) be the population pooled within-class covariance operator on H𝑘 𝜈 , and define the kernel–Mahalanobis margin √︃ 𝜌 Mah (𝑘 𝜈 ; P) := min′ ⟨𝜇𝑐 − 𝜇𝑐 ′ , Σ −1 (𝜇𝑐 − 𝜇𝑐 ′ )⟩ H𝑘𝜈 , (4.3) 𝑐≠𝑐

the LDA-Bayes-margin form of the kernel Fisher discriminant ratio. The empirical counterpart 𝜌ˆMah (𝑘 𝜈 ) replaces 𝜇𝑐 , Σ by sample mean 𝜇ˆ𝑐 and a Ledoit–Wolf-shrunk pooled estimator Σ̂LW (𝑘 𝜈 ). We recommend 𝜌ˆMah as the default filtration/fusion selector on heterogeneous candidate pools (widely −1 varying 𝐾 and 𝑟¯ := max𝑘 𝑟𝑘 across √ filtrations or fusion settings), where the full Σ correction is needed; the ˆ 𝐾 is the right pick on structurally homogeneous pools and is developed simpler kernel-margin Score 𝛾/ in Section 4.2 below. Both selectors are computable in closed form from the same gram matrix [𝑘 𝜈 (𝐴𝑖 , 𝐴 𝑗 )] already needed for SVM fitting, with no additional kernel evaluations. The kernel margin 𝛾ˆ expands as Í Í Í ∥ 𝜇ˆ𝑐 − 𝜇ˆ𝑐 ′ ∥ 2 = 𝑚12 𝑖,𝑗: 𝑦𝑖 =𝑦 𝑗 =𝑐 𝑘 𝜈 (𝐴𝑖 , 𝐴 𝑗 ) − 𝑚𝑐 2𝑚 ′ 𝑖: 𝑦𝑖 =𝑐, 𝑗: 𝑦 𝑗 =𝑐 ′ 𝑘 𝜈 (𝐴𝑖 , 𝐴 𝑗 ) + 𝑚12 𝑖,𝑗: 𝑦𝑖 =𝑦 𝑗 =𝑐 ′ 𝑘 𝜈 (𝐴𝑖 , 𝐴 𝑗 ), giving 𝑐

𝑐′

𝑐

𝑂 (𝑚 2 ) cost given the gram. The kernel–Mahalanobis margin 𝜌ˆMah is computed via the standard kernelFDA realization (Mika et al., 1999): a single 𝑂 (𝑚 3 ) Cholesky factorization of the Ledoit–Wolf-shrunk pooled centered gram per fold, with pairwise 𝜌 Mah (𝑐, 𝑐 ′ ) then obtained by triangular solves.

4.2

Score statistic and the selector hierarchy

The kernel margin 𝛾ˆ of (4.2) is the kernel-isotropic Fisher-ratio surrogate for 𝜌ˆMah : under the assumption Σ(𝑘 𝜈 ; P) ⪯ 𝑠 2 𝐼 H𝑘𝜈 (per-coordinate variance bounded by a common 𝑠 2 , distinct from the kernel bandwidth 𝜎 of Definition 3.1), 𝜌 Mah (𝑘 𝜈 ; P) ≥ 2𝛾/𝑠, so 𝛾ˆ is a Fisher-ratio lower bound that is ranking-consistent for 𝜌ˆMah on configurations where the kernel covariance is operator-bounded by a common scalar (tight when the kernel covariance is spherical). An intermediate selector replaces the full Σ −1 by a scalar trace-correction: Definition 4.3 (Kernel–Fisher trace ratio). The kernel–Fisher trace ratio is the pooled-trace approximation 2 , of 𝜌 Mah ∑︁ ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ 2H𝑘 𝜈 Fisherker (𝑘 𝜈 ; P) := min′ , Σ̄ := 𝑘1 Σ𝑐 , (4.4) 𝑐≠𝑐 2 tr( Σ̄) 𝑐 22

where Σ𝑐 := Cov(Φ𝜈 (𝐴) | 𝑌 =𝑐) and the operator Σ −1 of equation (4.3) has been replaced by the inverse of the pooled scalar trace. The pooled denominator (constant across class pairs) gives the classical kernel-FDA Fisherratio Fisherker ∝ tr(𝑆 𝐵 )/tr(𝑆𝑊 ) at the generalized-eigenproblem level (Mika et al., 1999); the factor of 2 in the denominator preserves scale comparability with a per-pair Welch denominator tr(Σ𝑐 ) +tr(Σ𝑐 ′ ), which we have verified to give the same sign of Spearman correlation with WLK accuracy on every chemical-graph dataset tested (|𝜌 pooled −𝜌 Welch | ≤ 0.025 on COX2/MUTAG/DHFR/NCI1; see experiments/compare_fisher_pp_vs_pool.py). › ker uses biased gram-block sums for the numerator and the pooled empirical The empirical counterpart Fisher Í Í 1 Í trace 𝑣ˆ := 𝑘 𝑐 𝑣ˆ𝑐 with class trace 𝑣ˆ𝑐 := 𝑚1𝑐 𝑖:𝑦𝑖 =𝑐 𝑘 𝜈 (𝐴𝑖 , 𝐴𝑖 ) − 𝑚12 𝑖,𝑗:𝑦𝑖 =𝑦 𝑗 =𝑐 𝑘 𝜈 (𝐴𝑖 , 𝐴 𝑗 ) (the trace of the 𝑐 empirical class covariance, distinct from the kernel bandwidth 𝜎 of Definition 3.1). Remark 4.1 (Hierarchy of selectors). The three selectors form a hierarchy in their treatment of the withinclass covariance Σ, from the most restrictive assumption to the least: 𝛾ˆ ⪯ |{z} Σ≡𝐼

› 1/2 Fisher ker | {z }

Σ = tr( Σ̄) 𝐼 /𝐾

⪯

𝜌ˆMah |{z}

.

Σ full operator

› ker allows a single pooled scalar scale via tr( Σ̄) = 1 Í𝑐 tr(Σ𝑐 ) 𝛾ˆ assumes spherical Σ (or ignores it entirely); Fisher 𝑘 but treats the covariance as isotropic and class-independent; 𝜌ˆMah uses the full operator structure. The empirical evidence of Section 6.3.2 confirms that this hierarchy translates to selection accuracy: 𝜌ˆMah is the only ranker positive on every augmented dataset (COX2 𝜌=+0.59, DHFR 𝜌=+0.72, MUTAG 𝜌=+0.48, PTC 𝜌=+0.48). › ker wins on MUTAG and PTC (both +0.60) but inverts on COX2 (𝜌=−0.30) where the diagonal-Σ apFisher √ ˆ 𝐾 is negative or near zero on every chemical dataset (Table 13). proximation fails; 𝛾/ Corollary 4.1 (Explicit bound via embedding-coordinate separation). Let 𝜇¯𝑐 := E[Φ(𝐴; 𝜈) | 𝑌 =𝑐] ∈ R𝐾 be the raw-coordinate class mean, and define Δ := min𝑐≠𝑐 ′ ∥ 𝜇¯𝑐 − 𝜇¯𝑐 ′ ∥ ℓ 2 and 𝐵 := sup𝐴,𝑘 |Φ𝑘 (𝐴; 𝜈)|. Assume the regularity condition 𝐾𝐵 4 ≤ 21 𝜎 2 Δ2 and the sample-size hypothesis 𝑚 min ≥ 256 𝐾𝜎 2 log(4𝑘/𝛿)/Δ2 (the √ √ analogue of Theorem 3.1’s hypothesis with 𝛾 replaced by its lower bound Δ/(2𝜎 2)). Set 𝜌 Δ := Δ/(4𝜎 2). Then with probability at least 1 − 𝛿, √︄ √ √ log(𝑘/𝛿) ª 8 2 (𝑘−1) 𝜎 𝐾 © b𝜌 Δ ( 𝑓ˆ) + R ( 𝑓ˆ) ≤ R (4.5) + 𝑂­ ®. √ 𝑚 min Δ 𝑚 min ¬ « √ Proof. We bound the kernel margin 𝛾 from below by Δ/(2𝜎 2) via a Taylor expansion of the per-coordinate Gaussians, and substitute into Theorem 3.1. 2 2 Per-coordinate Taylor expansion. Let 𝑔(𝑢) := 𝑒 −𝑢 /(2𝜎 ) , and write 𝑘 𝜈(𝑘 ) (𝐴, 𝐵) := 𝑔(Φ𝑘 (𝐴) − Φ𝑘 (𝐵)) for the 𝑘-th summand of 𝑘 𝜈 . The Taylor expansion 𝑔(𝑢) = 1 − 𝑢 2 /(2𝜎 2 ) + 𝑢 4 /(8𝜎 4 ) + 𝑂 (𝑢 6 /𝜎 6 ) gives, for |𝑢 | ≤ 2𝐵, the second-order remainder bound |𝑔(𝑢) − 1 + 𝑢 2 /(2𝜎 2 )| ≤ 2𝐵 4 /𝜎 4 (the leading 𝑢 4 /(8𝜎 4 ) term at |𝑢 | = 2𝐵 is 2𝐵 4 /𝜎 4 , with higher-order corrections 𝑂 (𝐵 6 /𝜎 6 ) absorbed when 𝐵 ≪ 𝜎). Taking expectations over independent samples 𝐴, 𝐴′ ∼ 𝑐 and 𝐵, 𝐵 ′ ∼ 𝑐 ′ , and using E[(𝑋 − 𝑌 ) 2 ] = 2 Var(𝑋 ) for i.i.d. 𝑋, 𝑌 : E 𝑘 𝜈(𝑘 ) (𝐴, 𝐴′ ) = 1 − Var𝑐 (Φ𝑘 )/𝜎 2 + 𝑂 (𝐵 4 /𝜎 4 ), E 𝑘 𝜈(𝑘 ) (𝐵, 𝐵 ′ ) = 1 − Var𝑐 ′ (Φ𝑘 )/𝜎 2 + 𝑂 (𝐵 4 /𝜎 4 ), E 𝑘 𝜈(𝑘 ) (𝐴, 𝐵) = 1 −

( 𝜇¯𝑐𝑘 − 𝜇¯𝑐𝑘′ ) 2 + Var𝑐 + Var𝑐 ′ + 𝑂 (𝐵 4 /𝜎 4 ), 2𝜎 2

where 𝜇¯𝑐𝑘 := E[Φ𝑘 | 𝑌 =𝑐].

23

Cancellation in the MMD combination. The within-class variance terms cancel in E𝑘 𝜈(𝑘 ) (𝐴, 𝐴′ ) +

E𝑘 𝜈(𝑘 ) (𝐵, 𝐵 ′ ) − 2 E𝑘 𝜈(𝑘 ) (𝐴, 𝐵):

MMD2 (𝑘 ) (𝑐, 𝑐 ′ ) = ( 𝜇¯𝑐𝑘 − 𝜇¯𝑐𝑘′ ) 2 /𝜎 2 + 𝑂 (𝐵 4 /𝜎 4 ). 𝑘𝜈

The summation kernel decomposes the RKHS as H𝑘 𝜈 =

Í 2 2 𝑘 H𝑘 𝜈(𝑘 ) , so MMD𝑘 𝜈 = 𝑘 MMD𝑘 (𝑘 ) . Summing

É

and bounding the aggregate remainder by 𝐶 𝐾𝐵 4 /𝜎 4 for an absolute constant 𝐶:

𝜈

MMD𝑘2 𝜈 (𝑐, 𝑐 ′ ) ≥ Δ2 /𝜎 2 − 𝐶 𝐾𝐵 4 /𝜎 4 . The regularity condition 𝐾𝐵 4 ≤ 12 𝜎 2 Δ2 controls the remainder so MMD𝑘2 𝜈 ≥ Δ2 /(2𝜎 2 ). √ √ Substitution. Hence ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 ≥ Δ/(𝜎 2), giving 𝛾 = 12 min𝑐≠𝑐 ′ ∥𝜇𝑐 − 𝜇𝑐 ′ ∥ H𝑘𝜈 ≥ Δ/(2𝜎 2). This implies 32𝐾 log(4𝑘/𝛿)/𝛾 2 ≤ 32𝐾 log(4𝑘/𝛿) ·8𝜎 2 /Δ2 = 256 𝐾𝜎 2 log(4𝑘/𝛿)/Δ2 ≤ 𝑚 min by hypothesis,√so Theorem 3.1’s sample-size hypothesis holds bound 𝛾 ≥ Δ/(2𝜎 2) √ at√the 𝛾 at hand. Substituting √ the lower √ √ √ into√Theorem 3.1’s rate term 4(𝑘 − 1) 𝐾/(𝛾 𝑚 min ) yields 4(𝑘 − 1) 𝐾 · 2𝜎 2/(Δ 𝑚 min ) = 8 2 (𝑘 − √ √ 1)𝜎 𝐾/(Δ 𝑚 min ), giving (4.5) with 𝜌 Δ = 𝛾/2 ≥ Δ/(4𝜎 2). □ Definition 4.4 (Scale-corrected ranking statistic). To rank configurations of different cardinality on the same footing, the scale-corrected ranking statistic is the dimension-normalized kernel margin 𝛾ˆ Score(𝐹, 𝜈) := √ , 𝐾

(4.6)

√ which absorbs the 𝐾 factor of the leading term in (3.7): larger Score implies√a tighter excess-risk bound. For ˆ ℓ. the uniform-grid special case 𝜈 = G𝑅 of cardinality ℓ, Score specializes to 𝛾/

4.3

Selection consistency

√ ˆ 𝐾 ranks admissible configurations to a selectionWe now upgrade the empirical observation that 𝛾/ consistency theorem: when the bound-optimal configuration is well-separated from the rest of the pool, the data-driven argmax recovers it with high probability. This is the PALACE analogue of Majhi et al. (2026, Prop. 4.4); as there, a fully data-driven consistency rate for the Ledoit–Wolf-shrunk Mahalanobis selector 𝜌ˆMah is deferred to companion work (Bagchi et al., 2026). √ ˆ 𝐾). Let F be a finite pool of admissible configurations√︁{𝜈 𝑓 } 𝑓 ∈ F Proposition 4.1 (Selection consistency of 𝛾/ with kernel margins 𝛾 𝑓 := 𝛾 (𝑘 𝜈𝑓 ; P), landmark budgets 𝐾 𝑓 , and population score 𝜂 𝑓 := 𝛾 𝑓 / 𝐾 𝑓 . Set 𝑓 ∗ := arg max 𝑓 𝜂 𝑓 and assume the gap 𝑔 := 𝜂 𝑓 ∗ − max∗ 𝜂 𝑓 > 0. 𝑓 ≠𝑓

√︁ Then 𝑓ˆ := arg max 𝑓 𝜂ˆ 𝑓 with 𝜂ˆ 𝑓 := 𝛾ˆ𝑓 / 𝐾 𝑓 satisfies  2  𝑔 𝑚 min ∗ ˆ P( 𝑓 = 𝑓 ) ≥ 1 − 2𝑘 |F | exp − . 32

(4.7)

In particular, 𝑓ˆ = 𝑓 ∗ with probability ≥ 1 − 𝛿 once 𝑚 min ≥ 32 log(2𝑘 |F |/𝛿)/𝑔2 , independently of the pool’s 𝐾 𝑓 values.

24

√︁ √︁ Proof. For each 𝑓 , |𝜂ˆ 𝑓 − 𝜂 𝑓 | = |𝛾ˆ𝑓 − 𝛾 𝑓 |/ 𝐾 𝑓 , so {|𝜂ˆ 𝑓 − 𝜂 𝑓 | > 𝑡 } = {|𝛾ˆ𝑓 − 𝛾 𝑓 | > 𝑡 𝐾 𝑓 } for every 𝑡 > 0. √︁ Applying Proposition 3.2 at 𝜀 = 𝑡 𝐾 𝑓 ,   2  𝑡 2𝐾 𝑓 𝑚 min 𝑡 𝑚 min = 2𝑘 exp − , P(|𝜂ˆ 𝑓 − 𝜂 𝑓 | > 𝑡) ≤ 2𝑘 exp − 8𝐾 𝑓 8 √︁ the 𝐾 𝑓 cancelling because 𝑅 𝑓 = 𝐾 𝑓 is exact on the landmark kernel (𝑘 𝜈𝑓 (𝐴, 𝐴) = 𝐾 𝑓 ). Taking 𝑡 = 𝑔/2 and applying a union bound over |F | configurations, on the event A := {|𝜂ˆ 𝑓 − 𝜂 𝑓 | ≤ 𝑔/2 for every 𝑓 }, which has probability ≥ 1 − 2𝑘 |F | exp(−𝑔2𝑚 min /32), every 𝑓 ≠ 𝑓 ∗ satisfies 𝜂ˆ 𝑓 ≤ 𝜂 𝑓 + 𝑔/2 ≤ 𝜂 𝑓 ∗ − 𝑔/2 ≤ 𝜂ˆ 𝑓 ∗ , so 𝑓ˆ = 𝑓 ∗ on A. □ 

2ℓ 2 log(|F |/𝛿)/(𝑔 The sample complexity 𝑚 min ≳ log(|F |/𝛿)/𝑔2 is strictly cleaner than the 𝑚 min ≳ 𝑅max min ) √ 2 rate of Majhi et al. (2026, Prop. 4.4): the 𝑅 /ℓ factor in Paper I arises from the loose envelope 𝑅 ≤ 𝐵 ℓ used √ to bound the embedding radius, whereas 𝑅 = 𝐾 is tight on PALACE because the additive landmark kernel satisfies 𝑘 𝜈 (𝐴, 𝐴) = 𝐾 identically. The parallel rate-driven corollary (cf. Majhi et al., 2026, Cor. 4.1) follows by combining Proposition 4.1 with Theorem 3.1 via a 𝛿/2-budget union bound. The Score statistic of Definition 4.4 is the formally analyzable end of the hierarchy in Remark 4.1. √ √ √ √ ˆ 𝐾). Theorem 3.1 bounds the excess risk by 2 𝐾/(𝛾 𝑚 min ), so 𝛾/ ˆ 𝐾 measures the Remark 4.2 (Scope of 𝛾/ tightness of that upper bound, not the error itself. The statistic has predictable selection scope: Faithful axes: radius factor 𝛼 (within the under-to-full-coverage range), and filtration choice within a scale-homogeneous family at fixed slot structure. These change which diagram points activate which coordi√ ˆ 𝐾 tracks accuracy monotonically (Section 6.3.1). Cross-scale filtration concatenation and homologynates; 𝛾/ dimension concatenation at matched total 𝐾 rescale embedding values without adding discriminative signal and are not faithful in this sense (Remark 4.1). Anti-correlated axes: landmark budget 𝐾, placement algorithm, and bandwidth√𝜎. These rescale either ˆ 𝐾 anti-correlates with 𝑘 𝜈 (𝐴, 𝐴) = 𝐾 or pairwise gram values without changing discriminative signal; 𝛾/ accuracy on Orbit5k (Spearman 𝑟 ≤ −0.8). Cross-validation is required on these axes. Complementarity with 𝜆.√𝜆 is insensitive to positions and radii among admissible equal-weight configˆ 𝐾 discriminates between them within a fixed structure. Together they split urations (Proposition 2.2); 𝛾/ the configuration space: 𝜆 certifies non-degeneracy and enables per-prediction correctness guarantees (Theo√ ˆ 𝐾 ranks within the admissible set. rem 5.1); 𝛾/

5

Deployment: Certificate and Pipeline

Sections 3–4 produced training-time risk guarantees for the kernel SVM in H𝑘 𝜈 together with a datadependent statistic for ranking configurations. We now address the deployment side: per-prediction certificates that audit individual test diagrams (Section 5.1) and an end-to-end pipeline that assembles the cover construction, landmark kernel, selection statistic, and certified prediction into a single algorithm (Section 5.2). The certified classifier is nearest-centroid in the raw embedding, with the certificate driven by the class-mean separation in ℓ 2 ; the kernel SVM and its margin 𝛾 in the RKHS continue to govern training-time risk via Theorem 3.1.

5.1

Certified Nearest-Centroid Classifier

Classifiers typically expose a confidence score—a margin to the SVM decision boundary, an SVM probability calibration, a posterior estimate—that does not, on its own, tell the user whether a specific prediction will be correct. Conformal prediction (Vovk et al., 2005) attaches distribution-free coverage, but the guarantee applies to prediction sets rather than point predictions and requires a held-out calibration split that 25

competes with training data for information. The raw embedding of Section 2 closes this gap for a specific classifier. The structural concentration of the raw embedding makes this possible: define the raw ∥Φ(𝐴; 𝜈) ∥ ℓ 2 on the support of P (this is the R𝐾 raw ℓ 2 norm, distinct from the embedding radius 𝑅¯ := sup𝐴 √ 𝜈 RKHS norm ∥Φ (𝐴)∥ H𝑘𝜈 = 𝐾 used by the kernel-SVM analysis of Section 3). Each landmark coordinate Í satisfies |Φ𝑘 (𝐴; 𝜈)| = 𝑤𝑘 |𝜑𝑝𝑘 ,𝑟𝑘 (𝐴)| ≤ 𝑤𝑘 |𝐴| 𝑟𝑘 , so under 𝑘 𝑤𝑘2 = 1 and admissibility 𝑟𝑘 ≤ 𝜏 (cf. Section 2), Í 𝑅¯2 = sup𝐴 𝑘 𝑤𝑘2 𝜑𝑝𝑘 ,𝑟𝑘 (𝐴) 2 ≤ (𝑁 max𝜏) 2 , giving 𝑅¯ ≤ 𝑁 max𝜏. Thus each empirical class mean 𝜇¯ˆ𝑐 is a sam¯ and 𝜇¯ˆ𝑐 − 𝜇¯𝑐 2 concentrates at rate ple average of i.i.d. bounded R𝐾 -vectors with ∥Φ(𝐴; 𝜈) − 𝜇¯𝑐 ∥ ℓ 2 ≤ 2𝑅, ℓ √ ¯ 𝑚𝑐 ) via Pinelis (Lemma A.1 of (Majhi et al., 2026)). The nearest-centroid (NC) classifier on the raw 𝑂 (𝑅/ embedding is the natural target: its decision rule depends on the sample only through the 𝜇¯ˆ𝑐 , so whether the empirical and population rules agree on a given test input reduces to a single scalar check—is the input far enough from the population Voronoi boundary that sample fluctuations cannot move it across? When Δ > 0, this check has a particularly simple form: a single training-time inequality 𝑟𝑚 < 21 Δ certifies all predictions, with no per-test overhead beyond the nearest-centroid rule itself and no calibration split required. The certificate is a diagnostic, not a competitor to the landmark-kernel SVM. When the condition 𝑟𝑚 < 12 Δ fails, the failure is itself informative: the embedding’s sample-mean concentration radius exceeds half the class gap, so the closed-form certificate admits no correctness guarantee at the given sample size. The kernel SVM and√its margin 𝛾 in H𝑘 𝜈 continue to govern training-time risk via Theorem 3.1, and the ˆ 𝐾 (Definitions 4.1, 4.4) ranks configurations even when the certificate has not yet selection statistic 𝛾/ fired. The PALACE-specific link to the cover certificate is Proposition 3.1, which gives Δ ≥ 𝜆(𝜏; 𝜈) − 2𝐷¯ max : when 𝜆(𝜏; 𝜈 ∗ ) > 2𝐷¯ max at training time, the bridge implies Δ > 0, so the per-prediction firing condition 𝑟𝑚 < 12 Δ is underwritten by a structural lower bound on Δ rather than only by empirical class-mean estimates. Classify test diagrams by nearest centroid: ∑︁ ℎˆ = arg min Φ(𝐴test ; 𝜈) − 𝜇¯ˆ𝑐 ℓ 2 , Φ(𝐴𝑖 ; 𝜈), 𝜇¯ˆ𝑐 := 𝑚𝑐−1 𝑐

𝑦𝑖 =𝑐

where 𝜇¯𝑐 := E[Φ(𝐴; 𝜈) | 𝑌 = 𝑐] ∈ R𝐾 is the population class mean (Definition 2.1 coordinates) and 𝜇¯ˆ𝑐 its empirical estimate from 𝑚𝑐 training diagrams. Let 𝑟𝑚 denote a sample-mean-concentration radius (the subscript 𝑚 is mnemonic for the smallest-class size 𝑚 min that governs the rate) satisfying Ptrain (max𝑐 𝜇¯ˆ𝑐 − 𝜇¯𝑐 ℓ 2 ≤ ⊗𝑚 with the 𝑟𝑚 ) ≥ 1 − 𝛿, where Ptrain = P ⊗𝑚 denotes probability over training draws {(𝐴𝑖 , 𝑦𝑖 )}𝑚 𝑖=1 ∼ P population P and the test diagram held fixed. Two explicit choices—a non-asymptotic Pinelis radius and an asymptotic Gaussian plug-in—are derived in Theorem 5.1. If 𝑟𝑚 < 12 Δ, every prediction is certified; −1/2 ) (equation (5.2)), so abstention otherwise the classifier abstains globally. The radius shrinks as 𝑂 (𝑚 min disappears at sample size ∝ 1/Δ2 (the global analogue of equation (5.4)). The global threshold Δ is conservative when classes differ in separation. Replacing Δ by the classspecific gap Δ𝑐 (𝜈) := min𝑐 ′ ≠𝑐 ∥ 𝜇¯𝑐 − 𝜇¯𝑐 ′ ∥ ℓ 2 ≥ Δ, and 𝑟𝑚 by the per-class radius defined in (i)/(ii) below, yields a tighter global certificate that fires when 𝑟𝑚(𝑐 ) < 12 Δ𝑐 (𝜈) holds for every class 𝑐. Two concrete choices of the concentration radius enter the theorem below (the per-class form uses the same expression with 𝑚 min replaced by 𝑚𝑐 ), both with an explicit Bonferroni split of 𝛿 over 𝑘 classes: √︁ (i) Non-asymptotic (Pinelis). 𝑟𝑚Pin := 2𝑅¯ 2 log(2𝑘/𝛿)/𝑚 min ; valid for every 𝑚 min ≥ 1 (equation (5.2) in the proof). √︃ 2 2 (ii) Asymptotic (Gaussian plug-in). 𝑟˜𝑚G := max𝑐 Σ̂𝑐 op · 𝜒𝐾, /𝑚𝑐 , where 𝜒𝐾, is the 1 − 𝛿/𝑘 𝛿/𝑘 𝛿/𝑘 quantile of the chi-squared distribution with 𝐾 degrees of freedom. The bound envelopes the multivariateGaussian norm via ∥ 𝜇¯ˆ𝑐 − 𝜇¯𝑐 ∥ ℓ22 ≤ ∥Σ𝑐 ∥ op 𝜒𝐾2 on the asymptotic N (0, Σ𝑐 /𝑚𝑐 ) approximation, valid 26

√ once 𝑚𝑐 ≥ 𝑚 † = 𝑂 ( 𝐾) (Berry–Esseen) under finite third moments. The bound is conservative when Σ𝑐 is low-rank, with conservatism governed by tr(Σ𝑐 )/(𝐾 ∥Σ𝑐 ∥ op ). √︁ ¯ the Pinelis form scales as 𝑅¯ log(2𝑘/𝛿)/𝑚 min Which form is tighter is regime-dependent: for fixed ∥Σ𝑐 ∥ op , Δ𝑐 , 𝑅, √︃ and the Gaussian form as ∥Σ𝑐 ∥ op · 𝐾/𝑚𝑐 for large 𝐾, so Pinelis dominates whenever ∥Σ𝑐 ∥ op · 𝐾 ≳ 8𝑅¯2 log(2𝑘/𝛿). Theorem 5.1 (Certified prediction). Let {(𝐴𝑖 , 𝑦𝑖 )} be i.i.d. from the distribution P on D𝑛 × [𝑘] of Section 3 ★ be either of the concentration radii (i) or (ii) above; for (ii) with class-mean separation Δ > 0, and let 𝑟𝑚 additionally assume finite third moments E ∥Φ(𝐴; 𝜈) − 𝜇¯𝑐 ∥ ℓ32 < ∞ and 𝑚𝑐 ≥ 𝑚 † for every class 𝑐. Then   ★ Ptrain max 𝜇¯ˆ𝑐 − 𝜇¯𝑐 ℓ 2 ≤ 𝑟𝑚 ≥ 1 − 𝛿, 𝑐

and on this coverage event the following hold. (a) (Containment.) If

★ 𝑟𝑚 < 12 Δ,

(5.1)

the empirical nearest-centroid classifier ℎˆ agrees with the population nearest-centroid classifier ℎ ∗ at ★ -tube around each population Voronoi boundary. every 𝑧 ∈ R𝐾 outside a 2𝑟𝑚 ★ for every class 𝑐 (cf. the raw-embedding analogue of (b) (Classification.) If additionally 𝐷¯ 𝑐 < 21 Δ − 𝑟𝑚 ★ → 0 limit), then for any test diagram 𝐴 drawn from class Proposition 3.3, whose 𝐷¯ max < Δ/2 is the 𝑟𝑚 ∗ ˆ 𝑦, Ptrain (ℎ(Φ(𝐴; 𝜈 )) = 𝑦) ≥ 1 − 𝛿.

Proof. Write Ψ𝑖 := Φ(𝐴𝑖 ; 𝜈 ∗ ) ∈ R𝐾 and Σ𝑐 := Cov(Ψ | 𝑌 = 𝑐), with ∥Ψ𝑖 ∥ ℓ 2 ≤ 𝑅¯ and therefore ∥Σ𝑐 ∥ op ≤ 𝑅¯2 . Step 1a (non-asymptotic concentration, radius (i)). Conditional on 𝑌𝑖 = 𝑐, the centered random variables ¯ Pinelis’s Hilbert-space Hoeffding Ψ𝑖 − 𝜇¯𝑐 are i.i.d. with ∥Ψ𝑖 − 𝜇¯𝑐 ∥ ℓ 2 ≤ 2𝑅¯ (both Ψ𝑖 and 𝜇¯𝑐 lie in 𝐵(0, 𝑅)). ¯ inequality (Lemma A.1 of Majhi et al., 2026) applied with bound 2𝑅 gives, for every 𝑡 > 0,  
𝑚𝑐 𝑡 2 ˆ P 𝜇¯𝑐 − 𝜇¯𝑐 ℓ 2 > 𝑡 ≤ 2 exp − 2 . 8𝑅¯ Set

√︄ 𝑟𝑚Pin := 2𝑅¯

2 log(2𝑘/𝛿) 𝑚 min

(5.2)

(an explicit Bonferroni split of 𝛿 over the 𝑘 classes). A union bound over the 𝑘 classes then yields the non-asymptotic coverage   (5.3) P max 𝜇¯ˆ𝑐 − 𝜇¯𝑐 ℓ 2 ≤ 𝑟𝑚Pin ≥ 1 − 𝛿, 𝑐

for every 𝑚 min ≥ 1 and 𝛿 ∈ (0, 1). Step 1b (asymptotic concentration, radius (ii)). Under the additional hypotheses of the theorem (finite √ third moments, 𝑚𝑐 ≥ 𝑚 † ), 𝑚𝑐 ( 𝜇¯ˆ𝑐 − 𝜇¯𝑐 ) is approximately N (0, Σ𝑐 ) in R𝐾 . For 𝑋 ∼ N (0, Σ𝑐 ), the squared Í norm ∥𝑋 ∥ 2 = 𝑖 𝜆𝑖 𝑍𝑖2 is a weighted sum of 𝜒 12 variables with 𝜆𝑖 the eigenvalues of Σ𝑐 ; the upper bound ∥𝑋 ∥ 2 ≤ ∥Σ𝑐 ∥ op 𝜒𝐾2 gives, with probability ≥ 1 − 𝛿/𝑘, √︃ 2 𝜇¯ˆ𝑐 − 𝜇¯𝑐 ℓ 2 ≤ ∥Σ𝑐 ∥ op · 𝜒𝐾, /𝑚𝑐 . 𝛿/𝑘 √ By the multivariate Berry–Esseen theorem applied to the convex set 𝐴 = 𝐵(0, 𝑟˜𝑚(𝑐 ) 𝑚𝑐 ), the true dis√ √ tribution of 𝑚𝑐 ( 𝜇¯ˆ𝑐 − 𝜇¯𝑐 ) deviates from N (0, Σ𝑐 ) in total variation by 𝑂 (𝐾 1/4 𝛽 3 /(∥Σ𝑐 ∥ 3/2 𝑚𝑐 )), where op 27

𝛽 3 := E∥Φ(𝐴; 𝜈) − 𝜇¯𝑐 ∥ ℓ32 . Replacing Σ𝑐 by the sample covariance Σ̂𝑐 incurs the matrix-Bernstein error √︃ 1/2 Σ̂𝑐 − Σ𝑐 op = 𝑂 (𝑅¯ ∥Σ𝑐 ∥ op log(𝐾)/𝑚𝑐 ), which propagates into the radius via | Σ̂𝑐 op − ∥Σ𝑐 ∥ 1/2 op | ≤ √︃ 1/2 1/4 𝜒 2 Σ̂𝑐 − Σ𝑐 op as an additional term of order 𝑂 (𝑅¯1/2 ∥Σ𝑐 ∥ 1/4 /𝑚𝑐 ). Taking the worstop (log 𝐾/𝑚𝑐 ) 𝐾,𝛿/𝑘 √︃ 2 /𝑚𝑐 Σ̂𝑐 op · 𝜒𝐾, case class and applying a Bonferroni correction over the 𝑘 classes gives the plug-in radius 𝑟˜𝑚G := max𝑐 𝛿/𝑘 √ 1/4 satisfying (5.3) up to a Berry–Esseen error of 𝑂 (𝐾 / 𝑚 min ) and a covariance-estimation error of leading √︁ 1/4 𝐾/𝑚 1/2 . Whether 𝑟˜ G < 𝑟 Pin depends order 𝑂 (𝑅¯1/2 ∥Σ𝑐 ∥ 1/4 min ), both 𝑜 (1) once 𝑚 min ≫ 𝐾 op (log 𝐾/𝑚 min ) 𝑚 𝑚 2 on the spectral structure of Σ𝑐 relative to 𝑅¯ and 𝐾; since 𝜒𝐾,𝛿/𝑘 ≈ 𝐾 for large 𝐾, the condition reduces to ∥Σ𝑐 ∥ op · 𝐾 ≲ 8𝑅¯2 log(2𝑘/𝛿). ★ ★ -tube). Condition on the coverage event {max 𝜇¯ Step 2 (agreement outside the 2𝑟𝑚 𝑐 ˆ𝑐 − 𝜇¯𝑐 ℓ 2 ≤ 𝑟𝑚 } ★ (probability ≥ 1 − 𝛿). The reverse triangle inequality gives 𝑧 − 𝜇¯ˆ𝑐 ℓ 2 − ∥𝑧 − 𝜇¯𝑐 ∥ ℓ 2 ≤ 𝑟𝑚 for every 𝑧 ∈ R𝐾 and every class 𝑐, hence for any pair 𝑐 ≠ 𝑐 ′ ,
★ . 𝑧 − 𝜇¯ˆ𝑐 ′ ℓ 2 − 𝑧 − 𝜇¯ˆ𝑐 ℓ 2 ≥ ∥𝑧 − 𝜇¯𝑐 ′ ∥ ℓ 2 − ∥𝑧 − 𝜇¯𝑐 ∥ ℓ 2 − 2𝑟𝑚 ★ from the (𝑐, 𝑐 ′ )Whenever the right-hand side is strictly positive—i.e., 𝑧 is at population distance > 2𝑟𝑚 Voronoi boundary—so is the left, and the empirical rule classifies 𝑧 identically to the population rule. This is claim (a). Step 3 (classification guarantee). Fix 𝑦 ∈ [𝑘] and let 𝐴 ∼ P𝑦 . By definition of 𝐷¯ 𝑦 , Φ(𝐴; 𝜈 ∗ ) − 𝜇¯𝑦 ℓ 2 ≤ 𝐷¯ 𝑦 ; ★ , we obtain together with 𝜇¯𝑦 − 𝜇¯𝑐 ′ ℓ 2 ≥ Δ and 𝐷¯ 𝑦 < 12 Δ − 𝑟𝑚 ★ ∥Φ(𝐴; 𝜈 ∗ ) − 𝜇¯𝑐 ′ ∥ ℓ 2 − Φ(𝐴; 𝜈 ∗ ) − 𝜇¯𝑦 ℓ 2 ≥ Δ − 2𝐷¯ 𝑦 > 2𝑟𝑚 , ★ -tube of the (𝑦, 𝑐 ′ )-Voronoi boundary. By Step 2, for every 𝑐 ′ ≠ 𝑦, so Φ(𝐴; 𝜈 ∗ ) lies strictly outside every 2𝑟𝑚 ∗ ˆ the empirical rule therefore assigns Φ(𝐴; 𝜈 ) to class 𝑦 on the coverage event, and Ptrain (ℎ(Φ(𝐴; 𝜈 ∗ )) = 𝑦) ≥ 1 − 𝛿. □

Remark 5.1 (Verifying claim (b) from data). The hypothesis in claim (b) is structural: it constrains the support of each class-conditional distribution, not just the centroids. It is therefore not estimable from the training data alone—the empirical 𝐷¯ˆ 𝑐 := max𝑖:𝑦𝑖 =𝑐 Φ(𝐴𝑖 ; 𝜈 ∗ ) − 𝜇¯ˆ𝑐 ℓ 2 underestimates 𝐷¯ 𝑐 in general (the training sample need not contain the worst-case point of the support). Claim (b) is consequently validated post hoc by test accuracy: full test coverage on a fired certificate confirms (b) for the test points seen, while gaps flag (b)’s failure—claim (a) still holds, but the population NC rule is itself wrong on some test points. The same diagnostic interpretation applies as in (Majhi et al., 2026, Rem. 5.1). Remark 5.2 (Why the certificate is not vacuous on PALACE). The firing condition (5.1) involves Σ̂𝑐 op (or 𝑅¯ in the non-asymptotic regime). For a generic bounded embedding Φ : D𝑛 → R𝐾 the crude bound Σ̂𝑐 op ≤ 𝑅¯2 = Θ(𝐾) is tight for dense vectorizations (persistence images (Adams et al., 2017), landscapes (Bubenik, 2015), WKPI (Zhao and Wang, 2019)); the certificate is then vacuous. PALACE is structurally different: each landmark coordinate Φ𝑘 (𝐴; 𝜈) = 𝑤𝑘 𝜑𝑝𝑘 ,𝑟𝑘 (𝐴) is supported on a 𝑑 B -ball of radius 𝑟𝑘 and FPS spacing forces 𝑂 (𝛼 2 ) landmark activations per diagram point (𝛼 = 𝑟𝑘 /𝑑 NN , the radius factor of Section 6). The embedding therefore has 𝑂 (|𝐴|) nonzero coordinates out of 𝐾, the class-conditional covariance is effectively 𝑂 (𝑁 max )-dimensional, and 𝑅¯ ≤ 𝑁 max𝜏 (independent of 𝐾). On MUTAG at the selected configuration, Σ̂𝑐 (𝜈 ∗ ) op ≈ 0.023, roughly half the PLACE value Σ̂𝑐 (G𝑅 ) ≈ 0.046 (Majhi et al., 2026, Sec. 5) and orders of magnitude below 𝑅¯2 . The op

structural shrinkage is real but does not by itself fire the worst-case Gaussian-plug-in bound at our training sizes (𝐾 = 200, 𝑚 = 57 on MUTAG: 𝑟𝑚 ≈ 0.31 vs. Δ̂/2 ≈ 0.19; same direction across the six benchmarks of Table 2). Operational firing requires either larger 𝑚𝑐 (per (5.4)) or a tighter bound exploiting tr(Σ𝑐 ) rather than ∥Σ𝑐 ∥ op · 𝐾. 28

Algorithm 1: Certified nearest-centroid classifier (PALACE). Per-class Gaussian-plug-in form; substitute 𝑟𝑚Pin from (5.2) for the non-asymptotic variant. 𝑘 𝑘 ; estimated Input: Trained 𝜈 ∗ ; per-class empirical means { 𝜇¯ˆ𝑐 }𝑐=1 ⊂ R𝐾 and covariances { Σ̂𝑐 }𝑐=1 class separation Δ̂𝑐ˆ (from training); confidence level 𝛿; test diagram 𝐴test Output: Predicted class 𝑐ˆ or Abstain 1 𝑐ˆ ← arg min𝑐 ∈ [𝑘 ] 2 𝑟𝑚 ←

√︃

Φ(𝐴test ; 𝜈 ∗ ) − 𝜇¯ˆ𝑐 ℓ 2

2 Σ̂𝑐ˆ op · 𝜒𝐾, /𝑚𝑐ˆ 𝛿/𝑘

// nearest centroid // per-class Gaussian plug-in radius

1 3 if 𝑟𝑚 < 2 Δ̂𝑐ˆ then return 𝑐ˆ

// certificate satisfied

4 5 else return Abstain

// certificate fails

6

Solving 𝑟𝑚(𝑐 ) < 12 Δ𝑐 for 𝑚𝑐 in each of the two regimes of Theorem 5.1 yields explicit per-class thresholds 𝑚𝑐∗, Pin (𝜈)

 32 𝑅¯2 log(2𝑘/𝛿) , = Δ𝑐 (𝜈) 2 

𝑚𝑐∗, G (𝜈)

& =

2 4 ∥Σ𝑐 (𝜈) ∥ op 𝜒𝐾, 𝛿/𝑘

Δ𝑐 (𝜈) 2

' ,

(5.4)

for the Pinelis radius (5.2) and the Gaussian plug-in radius (ii) of the theorem respectively; each carries the Bonferroni correction of level 𝛿/𝑘 per class. Once 𝑚𝑐 ≥ 𝑚𝑐∗ for every 𝑐, every prediction is certified with no abstentions. Which threshold is smaller is regime-dependent: 𝑚𝑐∗, G scales as ∥Σ𝑐 ∥ op · 𝐾 (since 2 𝜒𝐾,𝛿/𝑘 ≈ 𝐾 for large 𝐾), while 𝑚𝑐∗, Pin scales as 𝑅¯2 log(2𝑘/𝛿), so Pinelis is tighter whenever ∥Σ𝑐 ∥ op · 𝐾 ≳ 8𝑅¯2 log(2𝑘/𝛿). Compared to a uniform-grid classifier on the same embedding family, PALACE reduces 𝑚𝑐∗ through both factors in (5.4): (denominator) Δ𝑐 (𝜈 ∗ ) ≥ (1+𝛽) Δ𝑐 (G𝑅 ) with empirical separation-gain 𝛽 ≥ 0; (numerator) ∥Σ𝑐 (𝜈 ∗ ) ∥ op is empirically smaller than ∥Σ𝑐 (G𝑅 )∥ op because the compact adaptive coordinates are more correlated (landmarks concentrated near data) and the cardinality cap controls the worst case. For MUTAG with 𝛽 ≈ 0.41 and empirical variance ratio ≈ 21 , this yields 𝑚𝑐∗ (𝜈 ∗ ) ≈ 𝑚𝑐∗ (G𝑅 )/4—a 4× reduction in the sample size needed for certified prediction. Worked example (MUTAG, deg+HKS10 ). At 𝛿 = 0.05, Majhi et al. (2026, Sec. 5)’s baseline values Δ𝑐 ≈ 0.386, Σ̂𝑐 op ≈ 0.046, 𝑧 0.0125 ≈ 2.24 give 𝑚𝑐∗, G (G𝑅 ) = 7, comfortably below MUTAG’s smallest-class size 𝑚 min = 57 (100% coverage). PALACE’s adjustment (Δ𝑐 ≈ 0.544, Σ̂𝑐 op ≈ 0.023) yields 𝑚𝑐∗, G (𝜈 ∗ ) = 2—a ∼4× reduction. The Pinelis form remains far from firing at our sample sizes (0% rate, Table 2).

5.2

The PALACE Pipeline

Algorithm 2 summarizes the end-to-end pipeline assembled from the preceding sections: cover construction (Section 2), landmark-kernel SVM (Section 3.2), selection statistic (Section 4), and certified prediction (Section 5.1). Steps 1, 2, and 4 are closed form; Step 3 selects 𝜎 via a one-dimensional cross-validation sweep within a kernel-SVM fit and refits at the selected configuration. No gradient-based optimization of 𝜈 appears. Steps 1 and 2 reuse the same gram matrix: the 𝛾ˆ computation is a linear-algebra pass over the gram, and the certified NC of Step 4 is a distance comparison in the raw embedding R𝐾 . Consequently the full pipeline requires only one gram-computation sweep per candidate configuration, plus SVM fits at the CV-selected 𝐾 ★.

29

Algorithm 2: PALACE: Persistence Adaptive Landmark Kernel Pipeline Input: Training diagrams {(𝐴𝑖 , 𝑦𝑖 )}𝑚 𝑖=1 ; candidate filtrations F ; candidate budgets K ⊂ N; candidate radius factors A ⊂ R+ (closed-form-rankable, Remark 4.2); candidate bandwidths Σ ⊂ R+ , or per-fold 𝜎𝑞 quantile selection from training-fold pairwise distances; separation scale 𝜏; confidence level 𝛿. Output: A certified classifier on D𝑛 → [𝑘] ∪ {Abstain}. /* Step 1 (closed form): place landmarks at each (𝐹, 𝐾, 𝛼) .

*/

1 foreach 𝐹 ∈ F , 𝐾 ∈ K, 𝛼 ∈ A do

Run class-aware farthest-point sampling on training diagram points under filtration 𝐹 to get 𝐾 (Theorem 2.3). positions {𝑝𝑘 }𝑘=1 3 Set radii 𝑟𝑘 = 𝛼 · 𝑑 NN (𝑝𝑘 ) clipped to [𝜏/2, 4𝜏]. √ 4 Set weights 𝑤𝑘 = 1/ 𝐾 (Proposition 2.2). 5 Build embedding Φ𝐹 (·; 𝜈) (Definition 2.1) and gram 𝐾𝐹 = 𝑘 𝜈𝐹 (Definition 3.1). 6 end √ ˆ 𝐾. /* Step 2 (closed form): score 𝛼 and within-family filtration by 𝛾/ 2

*/

7 Compute 𝛾ˆ (𝑘 𝜈𝐹 ) (Definition 4.1, 𝑂 (𝑚 2 ) from the gram); within each scale-homogeneous filtration

√ family, rank (𝐹, 𝛼) by 𝛾ˆ (𝑘 𝜈𝐹 )/ 𝐾 (Definition 4.4). √ 8 Retain the top-ˆ 𝛾/ 𝐾 candidate per family per 𝐾. /* Step 3 (CV): select 𝐹 , 𝐾 , 𝛼 , 𝜎 . */ ★ 9 For each retained candidate (𝐹 , 𝐾, 𝛼), fit kernel SVM by 10-fold CV with 𝜎 ∈ Σ and 𝐶 tuned on fam inner 3-fold CV; record CV accuracy. 10 Select the (𝐹 ★, 𝐾 ★, 𝛼 ★, 𝜎 ★) that maximizes CV accuracy and refit kernel SVM on the full training set. /* Step 4 (closed form): certified nearest-centroid.

*/

ˆ𝑐 } and covariances { Σ̂𝑐 } in the embedding space at 𝜈 ★. 11 Compute empirical class means { 𝜇¯ 12 For each test diagram 𝐴, run Algorithm 1 with these statistics and the estimated class separation Δ̂𝑐ˆ (𝜈 ★); the algorithm emits Abstain when the certificate condition 𝑟𝑚 < 21 Δ̂𝑐ˆ (𝜈 ★) fails.

6

Experiments

We evaluate PALACE on 8 benchmarks: point clouds (Orbit5k, Section 6.1), five chemical graph datasets (COX2, DHFR, MUTAG, NCI1, PTC; Section 6.2), and a synthetic 4-class annulus task constructed to validate the 𝐿/𝐷 scaling of Theorem 2.2 (Section 6.4). Headline accuracies are reported in Tables 9 and 10; closed-form selector validation follows in Section 6.3. All experiments use the landmark kernel (Definition 3.1) with equal weights 𝑤𝑘 = 𝐾 −1/2 (Proposition 2.2), SVM classifiers with 𝐶 tuned by 3-fold inner cross-validation, class-aware FPS placement (Theorem 2.3) on training diagram points, separation scale 𝜏 at the median half-persistence per filtration, and top-50 most persistent features per diagram. Reported accuracies use 10-fold stratified cross-validation unless otherwise stated. Knob selection. The remaining configuration consists of four knobs swept on small discrete grids: filtration 𝐹 , landmark budget 𝐾 per filtration, radius factor 𝛼 (with 𝑟𝑘 = 𝛼 · 𝑑 NN (𝑝𝑘 ) clipped to [𝜏/2, 4𝜏]), √ ˆ 𝐾 is faithful for 𝛼 and kernel bandwidth 𝜎 (either fixed or per-fold quantile-tuned). By Remark 4.2, 𝛾/ and for filtration within a scale-homogeneous family at fixed slot structure: we rank these two knobs in 30

closed form on the alpha+density family, then verify by CV; the rankings agree on the headline configuration within 0.02 pp LK accuracy (Tables 6, 12 shaded √ rows). The remaining knobs—𝐾, 𝜎, and cross-family ˆ 𝐾 and are selected by 10-fold CV on a ≤ 5-point grid filtration choice—are not faithfully ranked by 𝛾/ each. Section 6.1 presents the main experiment on Orbit5k, comparing PALACE to the uniform-grid baseline and to prior methods. Section 6.2 evaluates the equal-budget advantage on graph classification benchmarks (cf. (Majhi et al., 2026; Zhao and Wang, 2019)). Section 6.3 then validates the closed-form selectors of Section 3 using accuracy data from both the Orbit5k axis sweeps and the chemical graph pool: axis-faithfulness √ √ b across five chemical graph benchmarks. Secˆ 𝐾 on Orbit5k, then the full hierarchy (ˆ of 𝛾/ 𝛾/ 𝐾, 𝜌ˆMah , 𝜆) tion 6.4 closes with a controlled domain-inflation study validating the 𝐿/𝐷 dependence (Theorem 2.2). Reproducibility. Code, embedding scripts, exact configuration files, and raw fold-level accuracies will be released at https://github.com/akritihq/place-palace prior to publication; each table caption below names its reproduction script. Baseline provenance. PLACE numbers are taken from (Majhi et al., 2026) at matched descriptor and protocol; other topology-based baselines and the non-topology baselines (RetGK (Zhang et al., 2018), GIN (Xu et al., 2019)) come from the cited originals. All graph datasets follow the 10-fold stratified CV protocol of (Zhao and Wang, 2019) under which the baselines were reported, so splits and protocol are matched; “—” marks dataset/baseline pairs not reported in the source. Significance testing. Since published baselines typically report only summary statistics, paired tests are not uniformly computable. We use a one-sample 𝑡-test (Welch’s when a baseline standard deviation is reported) comparing PALACE’s accuracy distribution (𝑛 = 50 outer-fold × seed observations for graph datasets, 𝑛 = 10 for Orbit5k) against each baseline; treating baseline point estimates as noise-free is conservative regardless of which side wins. In the tables, † and ‡ mark baseline cells significantly different from PALACE at 𝑝 < 0.05 and 𝑝 < 0.01 respectively (two-sided); the sign is readable from the numeric comparison. Descriptors and filtrations. For point clouds, we use the alpha complex filtration (Edelsbrunner and Harer, 2010) (𝐻 0 : components, 𝐻 1 : loops) and density-based variants—distance-to-measure (DTM) (Anai et al., 2019) and kNN density. PALACE concatenates two or three filtrations on Orbit5k (Section 6.1) to recover the certified 91.3 ± 1.0% headline. For graphs, scalar values on vertices via 𝑓 : 𝑉 → R extend to edges by 𝑓 (𝑢, 𝑣) = max{𝑓 (𝑢), 𝑓 (𝑣)}. Six descriptors are considered: degree, betweenness centrality, HKS (Sun et al., 2009) at 𝑡=1, 10, Ollivier–Ricci curvature (Ollivier, 2009), Jaccard index, and the discrete node-label indicator on chemical graphs; extended persistence (Cohen-Steiner et al., 2009) doubles feature counts via both sublevel and superlevel events. For multi-descriptor entries (e.g., “deg+HKS10 ”), persistence diagrams are concatenated and the landmark kernel is computed on each filter separately before summing gram contributions. Per-prediction certificate firing. Table 2 reports the firing fraction of the per-prediction certificate 𝑟𝑚 < 21 Δ̂𝑐ˆ (Theorem 5.1, contribution (iv)) across the six benchmarks, in both the non-asymptotic Pinelis form and the asymptotic Gaussian plug-in form (chi-squared envelope), together with nearest-centroid accuracy on the firing folds. Both worst-case forms sit above√the firing threshold at our training-set sizes: Pinelis 0/6, Gaussian essentially 0/6 (3.8% on NCI1). The 𝐾 scaling of the multivariate-norm bound dominates at the 𝐾 ∈ {200, 1,366} landmark budgets used here; the certificate is constructive but not yet

31

Table 2: Per-prediction certificate firing rates on the six Paper II benchmark datasets, averaged across seeds, folds, and filtrations. Pinelis and Gaussian columns report the fraction of test graphs for which 𝑟𝑚 < 12 b Δ𝑐ˆ under the respective tail bound. NC acc | fired is the nearest-centroid accuracy restricted to folds where the Gaussian certificate fires on at least one test point; “—indicates no folds fired. Dataset

𝑛 test

Pinelis (%)

Gaussian (%)

NC acc | fired (%)

Orbit5k MUTAG COX2 DHFR PTC NCI1

500 19 47 76 34 411

0.0 0.0 0.0 0.0 0.0 0.0

0.0 0.0 0.0 0.0 0.0 3.8

— 64.9 — — — 62.7

operational at these sample sizes. The pattern parallels the analogous diagnostics of Majhi et al. (2026), where ℓ takes the role of 𝐾. Non-interference fails empirically; the bound’s conclusion holds. Theorem 2.1, the non-degeneracy bridge of Corollary 3.1, and the structural classification rates of Corollary 3.2 (and the bridge-anchored variant in Section 3.2) are all stated under the non-interference condition of Definition 2.3. Auditing 2,000 crossclass pairs per dataset on the four chemical benchmarks at their headline filtrations under the top-𝑁 max = 50 persistence filter (optimal bottleneck matchings via binary search over edge-weight thresholds; reproduction: experiments/exp_noninterference_audit.py), the strict condition min𝑖≠𝑗 𝑑 B (𝑎𝑖 , 𝑏𝜎 ( 𝑗 ) ) > 3 𝑑 B (𝐴, 𝐵) holds on ≤ 0.2% of pairs across MUTAG, PTC, COX2, and DHFR, with median cross-ratios at or near zero—the hypothesis essentially never holds. We therefore test the theorem’s conclusion directly. For each dataset we build an FPS configuration 𝜈 with 𝐾 = 64 landmarks, equal weights 𝑤𝑘 = 𝐾 −1/2 , and uniform radii at 𝛼 = 0.75 times the nearest-neighbour landmark distance; we set 𝜏 at the 25th percentile of 𝑑 B (𝐴, 𝐵) so that ∼ 75% of crossclass pairs are 𝜏-separated (a different 𝜏 rule than the headline experiments above, chosen here to isolate the bound’s structural reach on the largest admissible cross-class population). For√each pair with 𝑑 B (𝐴, 𝐵) ≥ 𝜏 we measure ∥Φ(𝐴) − Φ(𝐵) ∥ ℓ 2 and the ratio to the certificate 𝜆(𝜏; 𝜈) = 𝜏/(4 𝐾). Reproduction: experiments/exp_certificate_bound_audit.py. Table 3: Empirical certificate bound audit on chemical graph datasets at the per-dataset headline filtration. FPS configuration, 𝐾 = 64, equal weights, 𝛼 = 0.75 NN radii. 𝜏 at the 25th percentile of 𝑑 B (𝐴, 𝐵). 𝑛𝜏 : cross-class pairs with 𝑑 B (𝐴, 𝐵) ≥ 𝜏. bound %: fraction of these pairs with ∥Φ(𝐴)−Φ(𝐵) ∥ ℓ 2 ≥ 𝜆(𝜏; 𝜈). p25 / p50 / p75: percentiles of the ratio ∥Φ(𝐴)−Φ(𝐵) ∥ ℓ 2 /𝜆. min: smallest ratio observed. Dataset

Filt

MUTAG PTC COX2 DHFR

deg+HKS10 deg+betw jaccard+HKS10 HKS10

𝒏𝝉

bound %

p25

p50

p75

min

1,565 1,781 1,500 1,498

100.0 100.0 100.0 99.9

8.49 9.95 3.69 2.84

12.37 13.76 5.16 3.38

18.25 18.98 7.40 4.10

3.00 3.01 1.47 0.77

The certificate holds on 99.9–100% of qualifying pairs across all four datasets, with median embedded distance 3–14× the floor; the lone DHFR violation (min ratio 0.77) is 23% below the floor. Non-interference is therefore sufficient but not necessary for the bound; the proof is overcautious on chemical-graph diagrams, but the certificate itself is robust. Theorem 2.1 and its downstream consequences should accordingly 32

be read as structural admissibility statements about Φ’s coarse-embedding properties on D𝑛 , not pointwise hypotheses verified on observed data. The empirical classification rate of Section 3 rests on 𝛾 > 0 via Theorem 3.1, which depends only on the kernel margin; the per-prediction certificate of Section 5.1 fires on 𝑟𝑚 < 12 Δ̂𝑐ˆ , also independent of non-interference.

6.1

Point Cloud Classification: Orbit5k

The Orbit5k dataset (Adams et al., 2017) consists of 5,000 point clouds (1,000 points each in [0, 1] 2 , 5 classes) from a 2D dynamical system with parameter 𝜌 ∈ {2.5, 3.5, 4.0, 4.1, 4.3}. We compute alpha-complex persistence (GUDHI), retain the top-50 most persistent features, and place class-aware FPS landmarks with equal weights 𝑤𝑘 = 𝐾 −1/2 . Comparison baselines are summarized in Table 9; the uniform-grid PLACE (Majhi et al., 2026) is the relevant within-family reference at 87.2±0.6% (linear SVM, ℓ=1,366). On the same PLACE embedding, nearest-centroid achieves only 33.9 ± 1.5%, and the certificate does not fire (Table 2). Landmark budget and classifier. Table 4 compares non-uniform FPS placement to the uniform grid across landmark budgets 𝐾, both evaluated with the LK-SVM. Table 4: Orbit5k LK-SVM accuracy (%, alpha 𝐻 0 +𝐻 1 ). Non-uniform: 5-fold CV, FPS placement with 𝑤𝑘 = 𝐾 −1/2 , precomputed landmark-kernel gram. Uniform-grid baselines from (Majhi et al., 2026): 10-fold CV; train accuracy and gap not reported there. Protocols differ between blocks (the headline two-filtration baseline of Table 5 uses 10-fold throughout). Bold = operational headline (best dim-accuracy tradeoff vs the uniform baseline). Method

Dim

Test

Train

Gap

Uniform 𝑁 =5 Uniform 𝑁 =10 Uniform 𝑁 =15

803 1653 2508

83.8 84.8 87.1

— — —

— — —

Non-uniform 𝐾=50 Non-uniform 𝐾=100 Non-uniform 𝐾=200 Non-uniform 𝐾=500 Non-uniform 𝐾=800

50 100 200 500 800

74.8±4.7 84.4±1.7 86.2±0.3 87.5±0.3 87.9±0.2

78.0 87.4 89.7 90.8 90.4

3.3 3.0 3.4 3.2 2.5

At 𝐾=500, non-uniform FPS achieves 87.5%—exceeding the best uniform grid (87.1% at dim=2508) with 5× fewer dimensions—and the generalization gap stays below 3.5% across all 𝐾. The landmark kernel’s additive structure (each landmark contributes a bounded [0, 1] similarity term) provides the implicit regularization that controls this gap. 𝐾=800 extends the trend with the overall best accuracy (87.9%, smallest gap 2.5%), but 𝐾=500 is the operational pick: the smallest non-uniform budget that beats the best uniform grid. Radius sensitivity. The FPS initialization sets 𝑟𝑘 = 𝛼 · 𝑑 NN (𝑝𝑘 ), where 𝑑 NN (𝑝𝑘 ) is the nearest-neighbor distance among landmarks and 𝛼 is a shrink factor, clipped to [𝜏/2, 4𝜏]. A sweep over 𝛼 ∈ [0.25, 1.50] at 𝐾=200 shows monotonically improving accuracy with 𝛼: 𝛼=1.50 attains 88.0%, surpassing 𝛼=0.75 at 𝐾=500 (87.5%) with 2.5× fewer dimensions, and the upper clip is rarely binding (most radii hit the 𝜏/2 floor).

33

Bandwidth and placement. At 𝐾=500 on alpha 𝐻 0 +𝐻 1 alone, sweeping 𝜎 over quantiles 𝑞 ∈ {0.05, 0.10, 0.15} of pairwise embedding distances yields a 0.1 pp range; the SVM’s regularization 𝐶 absorbs the bandwidth scale at this single-filtration setting. Per-fold 𝑞-tuning matters once filtrations are concatenated and 𝐾 grows (+0.1–0.6 pp; Table 7). FPS placement is seed-sensitive at small 𝐾 (±5% at 𝐾=50) and stable at 𝐾 ≥ 500 (±0.2%); compared to a 𝑘-Means baseline, FPS underperforms at small 𝐾 (−3% at 𝐾=100, where density peaks help) and outperforms at 𝐾 ≥ 500 (+2.6%, where max-spread coverage dominates). Placement comparison data: results/orbit5k_gamma_placement.csv. Multi-filtration (two-filtration baseline). Concatenating alpha persistence with DTM-density (Anai et al., 2019) filtration (𝑘=10) improves accuracy substantially. With 𝐾=200 landmarks per filtration (dim=400 total), radius factor 𝛼=1.75, bandwidth 𝜎=10−3 , and 10-fold stratified CV, the concatenation achieves 90.4± 1.1% (Table 5)—a +2.4 pp gain over alpha 𝐻 0 +𝐻 1 alone at the same 𝐾=200, 𝛼=1.75 (88.0%, matched-𝛼 row of Table 12). Density persistence alone is weak (53.8%, well above chance 20% but far from alpha), but the density coordinates capture local thickness information complementary to alpha’s shape features. Among DTM bandwidths, 𝑘=10 is optimal; larger 𝑘 degrades the alpha+density concatenation (𝑘=30: 89.8%, see Table 12) as the density signal becomes too smooth. Table 5: Exact configuration reproducing PALACE’s Orbit5k two-filtration baseline (90.4%). Parameters listed are sufficient inputs to Algorithm 1; no gradient-based optimization is used. Reproduction script: experiments/exp_reproduce_orbit5k_90.py. Component

Value

Filtrations (concatenated) Features per diagram Landmarks per filtration Total embedding dim Radius factor Separation scale 𝜏 Weights Kernel Bandwidth Classifier 𝐶 tuning Outer evaluation

alpha 𝐻 0 +𝐻 1 ⊕ DTM-density 𝑘=10 (𝐻 0 +𝐻 1 ) top-50 most persistent (per filtration) 𝐾=200 (class-aware FPS; 40 per class ×5 classes) 400 𝛼=1.75; 𝑟𝑘 = 𝛼 𝑑 NN (𝑝𝑘 ) clipped to [𝜏/2, 4𝜏] median half-persistence of training diagrams (per filtration) 𝑤𝑘 = 𝐾 −1/2 (equal; Prop. 2.2) landmark kernel (Def. 3.1) 𝜎 = 10−3 (fixed) SVM with precomputed gram inner 3-fold CV from {10−2, 10−1, 1, 10, 102, 103 } 10-fold stratified CV, seed 42

Test accuracy Train accuracy Selection statistic 𝛾ˆ √ ˆ 𝐾 𝛾/

90.42 ± 1.12% (rounded to 90.4 ± 1.1% in the headline) 93.95% (generalization gap 3.5%) 0.246 (Def. 4.1) 0.0123 (Definition 4.4)

Pushing the headline from 90.4% to 91.3%. Three knobs lift the baseline to the certified headline: an √ ˆ 𝐾’s argmax tracks the accuracy argmax within 0.02 pp), perextended 𝛼 sweep at 𝐾=300 (Table 6; 𝛾/ fold 𝑞-tuned 𝜎 (Table 7; optimal quantile drifts from ≈ 0.85 to ≈ 0.62 as 𝛼 grows), and triple-filtration concatenation adding density-𝑘 ∈ {15, 20} on top of 𝛼 ⊕ d10 (Table 8; LK-𝑞 = 91.32 ± 1.01). RBF-SVM benefits comparably to LK along this sweep, reaching 91.2% at 𝐾=300, 𝛼=4.0 (matching Persformer (Reinauer et al., 2021)). Comparison with prior methods. Table 9 places PALACE against diagram-based, neural, and Eulercharacteristic baselines. The two-filtration baseline (90.42 ± 1.12%) already surpasses PI, SW-K, PF-K, Per34

Table 6: Extended 𝛼 sweep at 𝐾=300 per filtration, 𝜎=10−2 , alpha ⊕ density-𝑘=10, 10-fold CV. LK-SVM, RBF-SVM, and nearest-centroid evaluated on the same configuration. Cache: results/orbit5k_final_sweep/continuation_partial.csv. LK-SVM (%) RBF-SVM (%)

𝛼

2.5 90.66 ± 0.68 4.0 91.02 ± 1.00 5.0 91.00 ± 0.99

90.42 ± 0.96 90.18 ± 0.93 90.26 ± 0.91

NC (%)

√ ˆ 𝐾 𝛾/

44.7 ± 1.4 0.0013 48.1 ± 1.3 0.0025 51.2 ± 1.4 0.0032

Table 7: Per-fold 𝑞-tuned 𝜎 on Orbit5k (alpha ⊕ density-𝑘=10, 10-fold CV). 𝑞˜ is the median selected quantile across folds. 𝑞˜

𝐾

𝛼

dim

LK-𝑞 (%)

200 300 300 300

1.75 1.75 4.00 5.00

400 90.60 ± 0.93 600 90.36 ± 1.03 600 91.12 ± 0.73 600 91.18 ± 0.69

0.90 0.85 0.62 0.62

RBF-SVM (%) NC (%) 90.4 90.4 91.2 90.9

43.4 44.3 48.1 51.2

sLay, and the uniform-grid PLACE (87.2±0.6% (Majhi et al., 2026)). With triple-filtration concatenation and 𝑞-tuning (Table 8), PALACE reaches the certified 91.3 ± 1.0%, matching Persformer (Reinauer et al., 2021) (91.2 ± 0.8%) and within 0.5 pp of ECS (Hacquard and Lebovici, 2024) (91.8 ± 0.4%). ECS bypasses diagrams via Euler characteristic surfaces on a bifiltration and Persformer learns end-to-end transformer features; PALACE matches both methods while keeping the diagram-level pipeline and the only per-prediction certificate on diagrams (both PALACE and PLACE carry per-prediction certificates of the same 𝑟𝑚 < 12 Δ̂𝑐ˆ form—Theorem 5.1 here, the analogous theorem in Majhi et al., 2026 for PLACE—fully fired on MUTAG; no other method in Table 9 carries a certificate). Kernel and classifier choice. On the two-filtration baseline (𝐾=200 per filtration, 𝛼=1.75), the additive landmark kernel (90.42±1.12%) and joint Gaussian RBF (90.14±1.22%) agree within noise, but a linear SVM on the same embedding collapses to 60.34 ± 2.41%—a 30 pp structural gap: FPS placement concentrates landmarks near data, producing a dense, correlated feature space where linear boundaries cannot exploit the per-landmark signal.√ RKHS lifting is therefore essential; the additive form is preferred on theoretical grounds (it retains the 𝐾 margin-bound advantage of Remark 3.1). Generalization gaps are 3.5% (LKSVM), 5.1% (RBF-SVM), and 0.6% (linear, high-bias), consistent with the admissibility-as-regularization narrative of Section 3.2. Nearest-centroid in ℓ 2 collapses to 42–44% on the top 𝐾=200 configurations (rising to ∼ 51% at 𝐾=300, 𝛼=5, see Table 7) and is reserved for contribution (iv)’s per-prediction certificate (Algorithm 1), the auditing gate of the pipeline.

6.2

Graph Classification

PALACE’s adaptive-placement advantage scales with the concentration ratio 𝐿/𝐷 of domain to data diameter (Theorem 2.2) and is strongest when 𝐿/𝐷 ≫ 1. Standard graph benchmarks have persistence diagrams spanning most of the available birth–death range (𝐿/𝐷 ∈ [1.16, 2.20] on MUTAG, NCI1, and PROTEINS as representatives), so the asymptotic adaptive advantage is small or absent—the failure mode Theorem 2.2 predicts and the controlled domain-inflation study of Section 6.4 reproduces. Table 10 bears this out: PALACE matches or marginally beats every diagram-based baseline on COX2 and MUTAG, is competitive on DHFR (within 1 pp of ECP), and ties PLACE within one standard deviation on the small35

Table 8: Triple-filtration concatenation on Orbit5k. 𝐾=300 landmarks per filtration (𝛼=4.0, 10-fold CV, top-50 persistent features per diagram). “LK” uses fixed 𝜎=10−2 ; “LK-𝑞” uses per-fold adaptive 𝜎 tuned by inner CV. Reproduction script: experiments/exp_orbit5k_push92.py. Filtrations 𝛼 ⊕ d10 (baseline) 𝛼 ⊕ d10 ⊕ d15 𝛼 ⊕ d10 ⊕ d20

LK (%)

LK-𝑞 (%)

91.02 ± 1.00 91.28 ± 0.95 91.08 ± 0.75

90.88 ± 0.70 91.22 ± 0.77 91.32 ± 1.01

Table 9: Classification accuracy (%) on Orbit5k. PLACE and PALACE are the only diagram-based methods carrying a per-prediction certificate; PALACE matches the strongest diagram-based method (Persformer) and reaches within 0.5 pp of the Euler-characteristic state of the art (ECS) at PALACE embedding dimension 900. PI: single-point estimate from (Adams et al., 2017). Significance markers (per the Section 6 opener) omitted; PALACE differs from each baseline below 90% at 𝑝 < 0.001 (one-sample 𝑡-test, 𝑛 = 10).

Vectorization

Acc. (%) Dim Cert.

Neural

Euler

PLACE / PALACE (ours)

PI

SW-K

PF-K

PersLay

Persformer

ECS

PLACE

PALACE

82.5 25 —

83.6±0.9 — —

85.9±0.8 — —

87.7±1.0 — —

91.2±0.8 — —

91.8±0.4 — —

87.2±0.6 1,366 𝜆(𝜈)

91.3±1.0 900 𝜆(𝜏; 𝜈)

𝐿/𝐷 molecular benchmarks PROTEINS (71.8 ± 3.5 vs. 71.5 ± 4.3) and DD (76.2 ± 3.2 vs. 76.3 ± 3.4). PALACE underperforms PLACE by 2–3 pp on the social-network IMDB-B/M benchmarks—the regime Theorem 2.2 predicts is adverse for adaptive placement, since the (𝐷/𝐿) 2 budget reduction vanishes when diagrams already span the available domain (𝐿/𝐷 ∈ [1.16, 2.20] on the chemical pool, comparable on IMDB), removing the adaptive advantage without a compensating gain. PALACE inherits PLACE’s descriptor-blindness gap to label-aware kernels and GNNs on NCI1, PTC, and across the social-network and molecular pools above (≥ 6 pp to WKPI on PROTEINS/DD, ≥ 11 pp on IMDB-B/M), where discriminative power is dominated by discrete node-label features or graph-kernel structural statistics that continuous filtrations cannot capture. On PTC, PALACE (63.0 ± 1.8) sits a hair below PLACE (64.3 ± 5.4, within one standard deviation), so the descriptor-blindness regime trades a modest amount of within-family accuracy for adaptive placement’s other gains elsewhere. PROTEINS, DD, and IMDB-B/M PALACE rows in Table 10 use the linear-SVM-selected headline filtration of Majhi et al. (2026, Table 7)—deg+ricci, √ degree, degree, and betw+ricci respectively—at the same ˆ 𝐾-selection across the full 46-filtration pool is deferred 5 seeds × 10 folds protocol as the other rows; 𝛾/ (the headline-filt protocol matches the linear-SVM evidence already cited in Paper I). NCI109 is rerunning on the cluster and the LK-SVM headline will be included in the camera-ready. Saturation in 𝐾 on MUTAG. A small-𝐾 sweep (experiments/exp_mutag_smallK.py, 5 seeds, mean LK-CV test accuracy on a single fixed filtration) confirms the small-𝐿/𝐷 regime within the nonuniform family: 𝐾=10 attains 81.4%, +0.5 pp above the same-filtration 𝐾=200 baseline (80.9%) at 20× compression; 𝐾=50 matches 𝐾=200 within 0.1 pp at 4× compression. This is a within-single-filtration saturation; the headline 90.9% in Table 10 comes from filtration selection across the 46-filtration pool, not from increasing 𝐾. A handful of adaptive landmarks already saturates the LK signal on MUTAG within a fixed filtration. The decisive 𝐿/𝐷 ≫ 1 evidence for Theorem 2.2 lives outside standard graph benchmarks; the controlled domain-inflation study in Section 6.4 constructs that regime synthetically. 36

Table 10: Method comparison on chemical and social-network graph datasets (𝐾=200 landmarks per fil√ ˆ 𝐾-selected filtration across the full 46-filtration pool tration; 5 seeds × 10 folds). PALACE: closed-form 𝛾/ on COX2/DHFR/MUTAG/NCI1/PTC (rows above the inner rule); linear-SVM-selected headline filtration of Majhi et al. (2026, Table 7) on PROTEINS/DD/IMDB-B/M (rows below the rule, NCI109 rerunning). Baselines from Majhi et al. (2026, Table 7); “Top NT” is the strongest non-topology baseline (graph kernel or GNN) per dataset. Bold = best per row. Cells without error bars are single-point estimates from the cited originals. Significance markers (per the Section 6 opener) omitted; PALACE differs from each NCI1/PTC/IMDB label-aware baseline at 𝑝 < 0.001, ties PLACE on PROTEINS/DD (𝑝 > 0.5), and is within noise of the diagram-based competitors on COX2/DHFR/MUTAG (one-sample 𝑡-test, 𝑛 = 50).

6.3

Dataset

PLACE (Majhi et al., 2026)

PersLay

ECP

Top NT

PALACE

COX2 DHFR MUTAG NCI1 PTC

80.7±1.5 80.0±4.3 89.9±6.4 71.0±1.6 64.3±5.4

80.9 80.3 89.8 73.5 —

80.3 82.0 90.0 76.3 —

RetGK 81.4 RetGK 81.5 RetGK 90.3 WKPI 87.5 WKPI 68.1

81.7±0.9 81.0±0.8 90.9±1.2 71.3±0.5 63.0±1.8

PROTEINS DD IMDB-B IMDB-M

71.5±4.3 76.3±3.4 66.4±4.3 44.5±3.6

74.8 — 71.2 48.8

75.0 — 73.3 48.7

WKPI 78.5 WKPI 82.0 WKPI 75.1 GIN 52.3

71.8±3.5 76.2±3.2 64.0±4.8 41.1±3.9

Closed-Form Selector Validation

This subsection validates the closed-form selectors of Section 3 in two complementary settings. Sec√ ˆ 𝐾’s axis-faithfulness on Orbit5k under controlled axis sweeps, identifying the regimes tion 6.3.1 verifies 𝛾/ in which it ranks correctly and the regimes in which it inverts. Section 6.3.2 then evaluates the full selector √ b across five chemical graph benchmarks, where › ker , 𝜌ˆMah , plus data-level 𝜏ˆ and 𝜆) hierarchy (ˆ 𝛾/ 𝐾, Fisher the heterogeneous-pool regime of Remark 4.1 dominates and 𝜌ˆMah becomes the operational pick. 6.3.1

√ ˆ 𝐾 on Orbit5k Axis-faithfulness of 𝛾/

√ ˆ 𝐾. We verify the classification on the twoRemark 4.2 classifies axes as faithful or anti-correlated for 𝛾/ filtration baseline (alpha 𝐻 0 +𝐻 1 ⊕√DTM-𝑘=10, 𝜎=10−3 , 10-fold CV) by sweeping one axis at a time and ˆ 𝐾 and CV accuracy. recording Spearman 𝑟 between 𝛾/ √ ˆ 𝐾 rank the four con𝛼 sweep (𝐾=200, Table 11). Accuracy rises monotonically with 𝛼; both 𝛾ˆ and 𝛾/ figurations in the same order (Spearman 𝑟 =+1.0; exact one-tailed 𝑝 ≈ 0.042 for 𝑛=4). 𝛾ˆ more than triples across the sweep (0.0784 → 0.2459) as 𝛼 grows from 0.5 to 1.75, with the accuracy-maximizing 𝛼=1.75 ˆ also yielding the largest 𝛾. √ ˆ 𝐾 both rank 𝛼 monotonically Table 11: 𝛼 sweep at 𝐾=200, alpha+density-𝑘=10 baseline filtration. 𝛾ˆ and 𝛾/ with CV accuracy. 𝛼

acc (%)

𝛾ˆ

√ ˆ 𝐾 𝛾/

0.50 1.00 1.50 1.75

87.98 ± 1.35 89.12 ± 0.69 90.16 ± 1.02 90.42 ± 1.12

0.0784 ± 0.004 0.1271 ± 0.022 0.1963 ± 0.027 0.2459 ± 0.026

0.00392 0.00635 0.00981 0.01230

37

Filtration sweep (𝐾=200 per filtration, 𝛼=1.75, Table 12). Sweeping seven base filtrations and their √ ˆ 𝐾 predicted by Remark 4.1: alpha persistences alpha-concatenations exposes the cross-scale failure of 𝛾/ live in [0, 0.2] while eccentricity and KDE values range over [0.5, 5], so at fixed 𝜎 the mis-scaled coordinates dominate RKHS distances between class means without encoding topological discrimination. Restricting to the scale-homogeneous alpha+density family (shaded rows in Table 12) restores monotonic agreement √ ˆ 𝐾 and accuracy. Two additional structural axes also invert—landmark budget 𝐾 and bandbetween 𝛾/ width 𝜎—and require cross-validation; Section 6.3.2 shows that 𝜌ˆMah ’s operator-Σ −1 correction resolves these failure modes on chemical-graph filtration pools. −3 Table 12: Filtration √ sweep on Orbit5k at 𝐾=200 per filtration, 𝛼=1.75, 𝜎=10 , class-aware FPS, 10-fold ˆ 𝐾. Concatenations of alpha with filtrations whose coordinate scale diverges from alCV, sorted by 𝛾/ pha’s (eccentricity, kde) inflate 𝛾ˆ without √ adding discriminative signal; within the scale-homogeneous ˆ 𝐾 and accuracy agree on the top-ranked configuration. alpha+density family (shaded rows), 𝛾/

6.3.2

Configuration

𝐾

acc (%)

𝛾ˆ

√ ˆ 𝐾 𝛾/

alpha ⊕ eccentricity alpha ⊕ kde alpha ⊕ density-𝑘=10 alpha (single) alpha ⊕ density-𝑘=5 kde (single) density-𝑘=10 (single) alpha ⊕ density-𝑘=30 alpha ⊕ knn-𝑘=10 density-𝑘=5 (single) density-𝑘=30 (single) knn-𝑘=10 (single) eccentricity (single)

400 400 400 200 400 200 200 400 400 200 200 200 200

87.70 ± 1.13 87.66 ± 1.61 90.42 ± 1.12 88.00 ± 0.88 89.62 ± 0.84 49.08 ± 1.62 53.80 ± 1.74 89.82 ± 1.16 85.80 ± 0.81 50.46 ± 2.24 53.40 ± 2.25 43.02 ± 1.53 51.24 ± 1.53

0.4533 0.3629 0.2459 0.1636 0.2287 0.1383 0.1257 0.1725 0.1639 0.0912 0.0542 0.0141 0.0040

0.02267 0.01815 0.01230 0.01157 0.01144 0.00978 0.00889 0.00862 0.00820 0.00645 0.00384 0.00100 0.00028

Multi-dataset evaluation across chemical benchmarks

√ ˆ The Orbit5k validation above identifies the structural axes on which 𝛾/ 𝐾 misranks (Remark 4.1). A com√ ˆ 𝐾 succeeds across datasets at fixed (𝐾, 𝜎) and FPS placement, varying plementary question is whether 𝛾/ only the filtration—the operational use case for selecting a filtration on a new benchmark. We evaluate on four chemical graph datasets at the full 46-filtration pool and on NCI1 at the restricted 14-filtration cluster pool, all at 𝐾=200, 𝜎=10−3 , class-aware FPS, 5 seeds × 10 folds. √ ˆ 𝐾 (spherical We compare five candidate rankers along the Σ-treatment hierarchy of Remark 4.1: (i) 𝛾/ › ker (Definition 4.3, scalar-trace); (iii) 𝜌ˆMah (Definition 4.2, full operator Σ −1 ); plus two dataΣ); (ii) Fisher ˆ the 10th -quantile cross-class bottleneck distance from 50 subsampled training pairs; level rankers: (iv) 𝜏, √ ˆ and (v) 𝜆b = 𝜏/(4 𝐾), the certificate of Theorem 2.1 used as a ranker. The hierarchy translates to selection accuracy. Table 13 reveals a clean correspondence between each selector’s Σ-treatment assumption and its empirical reliability: √ ˆ 𝐾 (no variance correction) is negative on 4/5 datasets and weakly positive (+0.14) on PTC; mean • 𝛾/ 𝜌 = −0.26, confirming Remark 4.2’s scope. › ker (scalar trace correction) is positive on 4/5 datasets (mean 𝜌 = +0.49 on those four) but • Fisher inverts on COX2 (𝜌 = −0.30), exactly the regime where the diagonal-Σ assumption fails. 38

Table 13: Selection-statistic Spearman 𝜌 vs. WLK CV accuracy, per dataset, mean over 5 seeds ×√10 ˆ 𝐾 folds. Selectors form a hierarchy in their treatment of the within-class covariance (Remark 4.1): 𝛾/ assumes spherical Σ; Fisherker uses pooled scalar trace (Definition 4.3); 𝜌ˆMah uses the full operator Σ −1 (Mika et al., 1999 kernel-FDA realisation). Below the line, 𝜏ˆ is the 10th -quantile cross-class bottleneck √ ˆ 𝐾 the certificate of Theorem 2.1 as a ranker. Bold marks the largest positive 𝜌 per distance and 𝜆b = 𝑐𝑛𝜏/ row. Fisherker values were computed with the per-pair Welch denominator tr(Σ𝑐 ) + tr(Σ𝑐 ′ ) of an earlier draft of Definition 4.3; the pooled denominator now adopted gives Spearman within |Δ𝜌 | ≤ 0.025 with sign-match on every dataset re-evaluated (COX2/MUTAG/DHFR/NCI1; the camera-ready will regenerate from scratch). Dataset

|F |

√ ˆ 𝐾 𝛾/

Fisherker

𝜌ˆMah

𝜏ˆ

𝜆b

COX2 DHFR MUTAG NCI1 PTC

64 64 63 14 64

−0.39 −0.13 −0.61 −0.29 +0.14

−0.30 +0.42 +0.60 +0.35 +0.60

+0.59 +0.72 +0.48 +0.71 +0.48

+0.22 −0.27 −0.32 −0.20 +0.24

+0.19 −0.29 −0.33 −0.20 +0.24

• 𝜌ˆMah (full operator Σ −1 ) is positive on every dataset (DHFR +0.72, NCI1 +0.71, COX2 +0.59, MUTAG › ker +0.48, PTC +0.48). It is the only kernel-margin ranker that recovers signal on COX2 where Fisher fails, and the strongest by Spearman magnitude on DHFR. • 𝜆b (data-level certificate) is positive on COX2 (+0.19) and PTC (+0.24); weakly negative on DHFR, MUTAG, and NCI1. The COX2 reversal is mechanistically informative: its accuracy-winning filtration nodelabel+betw encodes a discrete node-label feature whose class-conditional covariance is strongly anisotropic, with the › ker , normalizing by discriminative direction near-orthogonal to the high-variance directions of Σ. Fisher the scalar trace tr(Σ), charges all directions equally and over-penalizes the discriminative direction. 𝜌ˆMah , applying the full Σ −1 , re-weights variance to recover this signal. 𝜆b picks it up via a different mechanism— bottleneck separation between class supports—giving an independent positive signal. Operational recommendation. On heterogeneous filtration pools we recommend 𝜌ˆMah as the primary closed-form selector (no validation split, 𝑂 (𝑛 3 ) per fold via Cholesky on the same gram matrix the SVM uses). When 𝜌ˆMah and 𝜆b agree in sign, the pick is high-confidence; when they disagree, the disagreement diagnoses which mechanism (kernel-margin vs. data-level bottleneck) dominates on that dataset. −2 −3 −4 › (𝐾, 𝜎) sensitivity. Table √ 15 confirms sign stability of Fisherker across (𝐾, 𝜎) ∈ {100, 200, 500}×{10 , 10 , 10 } ˆ 𝐾 is uniformly negative on the grid, as Remark 4.1 predicts. on MUTAG and PTC; 𝛾/

6.4

Domain Inflation: Controlled Validation

Theorem 2.2 predicts that non-uniform placement gains over the uniform grid scale with the ratio 𝐿/𝐷 of domain size to data diameter. The graph benchmarks in Section 6.2 have 𝐿/𝐷 ≈ 1–2, limiting the advantage. To test the theorem in the 𝐿/𝐷 ≫ 1 regime, we construct a synthetic family where 𝐿 grows while the discriminative features remain fixed. Protocol. We construct a 4-class annulus classification task: each class is a noisy annulus with inner radius 𝑟 in ∈ {0.85, 0.70, 0.50, 0.00} and outer radius 1.0, centered at the origin (𝑛 pts = 60 points, Gaussian 39

Table 14: Complementarity of Fisherker and the certificate 𝜆b as filtration rankers. Per dataset, the Spearman 𝜌 of each statistic vs. WLK CV accuracy, and a binary agreement flag (both positive or both negative). At least one of the two statistics is positive on every dataset where some filtration meaningfully separates classes; Fisher captures the embedding-level signal, 𝜆b the data-level (bottleneck-separation) signal. Dataset

Fisherker 𝜌

𝜆b 𝜌

agree?

COX2 DHFR MUTAG NCI1 PTC

−0.30 +0.42 +0.60 +0.35 +0.60

+0.19 −0.29 −0.33 −0.20 +0.24

× × × × ✓

Total

at-least-one-positive ✓ ✓ ✓ ✓ ✓ 5/5

noise 𝜎 = 0.08). The classes differ only in hole size—a purely topological distinction that manifests as varying 𝐻 1 persistence. Alpha complex persistence (GUDHI) is computed; we retain the top-30 most persistent points (the practical maximum for clouds of size 60, where persistence falls off rapidly past 30 features). To inflate the domain without changing the classification task, we add a single off-diagonal point at (𝑏, 𝑑) = (0, ℓ) for ℓ ∈ {1, 2, 3, 4, 5, 8} to every point cloud, stretching the persistence-diagram domain from 𝐿 ≈ 1.05 (no outlier) to 𝐿 ≈ 1.05 ℓ (the table’s 𝐿 column applies a 5% padding 𝐿 = 1.05 · max(persistence) to give grid construction slack); discriminative 𝐻 1 features stay near the origin throughout. Both methods use 𝐾 = 11 landmarks at matched cardinality: 11 corresponds to the offset uniform grid G𝑅+ with 𝑅 chosen at the smallest scale that fits the unperturbed data domain, and is small enough to expose the inflation effect sharply. Setup. 100 point clouds per class (400 total), 10-fold stratified CV with seed 42. Bandwidth 𝜎 is set by the 25th -percentile heuristic per fold; 𝐶 is tuned by inner 3-fold CV on the log grid {10−2, . . . , 103 }. The admissibility scale 𝜏 is set to the mean half-persistence of the strongest 𝐻 1 feature per unperturbed diagram (𝜏 ≈ 0.144), capturing the discriminative-feature scale rather than the alpha-complex noise floor. Reproduction script: experiments/exp_domain_inflation.py. Results. Table 16 reveals a sharp phase transition at the predicted 𝐿/𝐷 scale. At ℓ = 1 both methods perform near-identically (94.8% vs. 94.2%); the uniform grid covers the compact data region adequately. At ℓ = 2 the methods cross (66.5% vs. 94.2%, a 27.7 pp gap), and by ℓ = 4 the uniform grid hits the random baseline and stays there. Non-uniform placement is exactly invariant: the appended outlier is identical across classes, so FPS picks it as one of the 11 landmarks (it is the farthest point from the data cluster) and the remaining 10 FPS landmarks cover the discriminative data region near the origin, unaffected by 𝐿. The √ mechanism is sharp. With 𝐾 = 11 landmarks and 𝐿 ≈ 8 (𝐿/𝐷 ≈ 8), the uniform grid spacing ∼ 𝐿/ 𝐾 ≈ 2.4 is far coarser than the ∼ 0.06 separation between class-specific 𝐻 1 features, so none of the 11 grid landmarks fall in the discriminative region; FPS places 10 landmarks near the origin (with one on the outlier) and achieves effective spacing ∼ 0.05. Quantitatively at 𝐿/𝐷 ≈ 8, Theorem 2.2’s budgetreduction factor (𝐷/𝐿) 2 ≈ 1/64 makes the uniform grid’s 11 landmarks equivalent to ∼ 0.17 effective landmarks in the discriminative region—which the data confirms by collapsing to chance. This is the sharpest experimental validation of Theorem 2.2 on a controlled task; in practice, a single outlier cloud with unusual persistence is enough to trigger the same effect on real data.

40

Table 15: (𝐾, 𝜎) sensitivity of selection statistics. Spearman 𝜌 vs. WLK CV accuracy on each cell of a 3×3 (𝐾, 𝜎) grid, per dataset. Stable sign of Fisherker across the grid is the robustness signal; cells highlighted where Fisher and 𝜆b disagree in sign. MUTAG 𝐾=100 Stat \ 𝜎 √ ˆ 𝐾 𝛾/ Fisherker 𝜌ˆMah 𝜏ˆ 𝜆b

𝐾=200

𝐾=500

10−4

10−3

10−2

10−4

10−3

10−2

10−4

10−3

10−2

−0.00 +0.18 — −0.09 −0.09

−0.49 +0.30 — −0.31 −0.31

−0.55 +0.34 — −0.29 −0.29

−0.03 +0.26 — −0.17 −0.17

−0.60 +0.46 — −0.35 −0.36

−0.63 +0.16 — −0.27 −0.28

+0.04 +0.40 — −0.09 −0.14

−0.63 +0.64 — −0.40 −0.48

−0.67 −0.08 — −0.29 −0.36

PTC 𝐾=100 Stat \ 𝜎 √ ˆ 𝐾 𝛾/ Fisherker 𝜌ˆMah 𝜏ˆ 𝜆b

7

𝐾=200

𝐾=500

10−4

10−3

10−2

10−4

10−3

10−2

10−4

10−3

10−2

+0.24 +0.44 — +0.40 +0.40

+0.27 +0.68 — +0.25 +0.25

+0.34 +0.59 — +0.44 +0.44

−0.00 +0.38 — +0.25 +0.25

+0.08 +0.55 — +0.13 +0.13

+0.34 +0.48 — +0.46 +0.46

−0.07 +0.25 — +0.33 +0.31

−0.18 +0.22 — +0.10 +0.08

+0.36 +0.34 — +0.49 +0.47

Discussion

PALACE replaces the conventional uniform grid with a data-adaptive landmark configuration and contributes three structural results: (i) farthest-point sampling is a 2-approximation to the optimal 𝑘-center covering radius on the training-diagram point set (Theorem 2.3); (ii) equal weights 𝑤𝑘 = 𝐾 −1/2 are provably optimal for the worst-case classification error bound (Proposition 2.2); (iii) admissibility (Definition 2.2(i)) acts as structural regularization on the configuration 𝜈, ruling out√memorization configurations with arbiˆ 𝐾 (Section 4), the configuration search trarily small radii. Combined with the data-dependent statistic 𝛾/ splits into a closed-form tier—radius factor 𝛼 and filtration choice within a scale-homogeneous family at √ ˆ 𝐾—and a small cross-validation tier covering landmark budget 𝐾, bandfixed slot structure, ranked by 𝛾/ width 𝜎, and cross-family filtration choice, each at ≤ 5 points on a discrete grid. Across seven benchmarks—Orbit5k point clouds, five chemical-graph datasets (COX2, DHFR, MUTAG, NCI1, PTC), and a synthetic 4-class annulus task—PALACE leads every diagram-based competitor on Orbit5k, COX2, and MUTAG, and is competitive on DHFR (within 1 pp of ECP) (Tables 9, 10): on Orbit5k it matches Persformer at 91.3% (triple-filtration certified landmark kernel, Table 8) and surpasses PI, SW-K, PF-K, PersLay, and PLACE; on COX2, DHFR, and MUTAG it exceeds both PLACE and PersLay in head-tohead accuracy (81.7%, 81.0%, 90.9%). On MUTAG, 𝐾=10 non-uniform landmarks already attain 81.4% test accuracy on a single fixed filtration, +0.5pp above the same-filtration 𝐾=200 baseline at 20× compression, confirming that the LK signal saturates with a handful of adaptive landmarks within a fixed filtration (the headline 90.9% in Table 10 comes from filtration selection across the 46-filtration pool, not from increasing 𝐾). Under 8× domain inflation on the synthetic annulus task, non-uniform placement maintains 94.2% accuracy while the uniform grid collapses to the 25% random baseline (Table 16).

41

Table 16: Domain inflation experiment. As distant features inflate the domain, the uniform grid collapses while non-uniform placement remains robust. Bold = best per row. Uniform’s ±0.0 at ℓ ≥ 4 reflects embedding collapse: no landmark falls in the data region, so the SVM defaults to a single class, giving exact stratified-CV chance (25% for 4 classes). Outlier ℓ

Domain 𝐿

Uniform (%)

Non-uniform (%)

Δ

1 2 3 4 5 8

1.05 2.10 3.15 4.20 5.25 8.40

94.8 ± 2.1 66.5 ± 3.0 32.2 ± 1.7 25.0 ± 0.0 25.0 ± 0.0 25.0 ± 0.0

94.2 ± 3.5 94.2 ± 3.5 94.2 ± 3.5 94.2 ± 3.5 94.2 ± 3.5 94.2 ± 3.5

−0.6 +27.7 +62.0 +69.2 +69.2 +69.2

When to use PLACE. PLACE (Majhi et al., 2026) remains the right pick under three operating constraints. (i) No validation budget. PLACE is fully tuning-free; PALACE’s three-knob CV tier (budget, radii, bandwidth) consumes labels that small datasets or single-shot inference cannot spare. (ii) Pairwise certification. PLACE’s 𝜆(𝜈) 𝑑 B (𝐴, 𝐵) bound holds on every pair in D𝑛 under non-interference, certifying pairwise metric fidelity; PALACE’s 𝜆(𝜏; 𝜈) is a 𝜏-thresholded class-level statement, optimized for classification certificates rather than embedding distortion. (iii) Determinism and interpretability. PLACE is deterministic given the data and admits per-coordinate interpretation of linear-SVM weights; PALACE’s FPS placement is seed-sensitive at small 𝐾 (Section 6.1) and the RKHS lift trades per-landmark interpretability for accuracy. The two papers together cover both sides of the trade: PLACE is the tuning-free floor with stronger pairwise theory; PALACE buys accuracy and a smaller embedding by spending a small CV budget. The criteria above and the dual conditions in Section 6.3 of Majhi et al. (2026) (When to use PALACE)—CV budget, data concentration 𝐿/𝐷 ≫ 1, and need for non-linear discriminative geometry—are complementary rather than negations: criterion (i) here pairs with criterion (i) there, while criteria (ii) and (iii) on each side identify the operating-condition axes that the other paper does not address (pairwise distortion certification and determinism/interpretability for PLACE; data-concentration regime and RKHS reach for PALACE). Closed-form vs. learned. WKPI (Zhao and Wang, 2019) fits a Gaussian-mixture weight function on diagram space by gradient descent on classification loss and beats PALACE by 5–16 pp on the label-dominated chemical pools NCI1 and PTC, where even non-topology methods (graph kernels, GNNs) outperform every diagram-based method. We do not contest the empirical fact: PALACE’s wins (Orbit5k, MUTAG, COX2) are on topology-discriminative benchmarks, and the label-dominated regime is a different problem. But the trade is categorical, not just quantitative: the per-prediction certificate of Theorem 5.1 requires the configuration to be fixed before data is examined, so gradient-trained weights void its Bonferroni coverage guarantee. Closed-form is also not synonymous with inflexible— 𝜌ˆMah adapts to dataset-specific › ker inverts on covariance structure (one Cholesky per fold) and recovers signal where the simpler Fisher COX2 (Table 13). We submit that closed-form across the entire pipeline is the right target for a principled landmark-embedding theory; the NCI1/PTC accuracy gap is a question for future closed-form variants, not evidence against the closed-form thesis. Limitations. • Certificates apply only to the nearest-centroid classifier (Algorithm 1). On our six benchmarks neither the non-asymptotic Pinelis form nor the asymptotic Gaussian plug-in (chi-squared envelope) 42

fires at our training-set sizes (Pinelis 0/6, Gaussian essentially 0/6 with 3.8% on NCI1; Table 2); the construction is constructive but not yet operational at these sizes. • The landmark kernel gram costs 𝑂 (𝑚 2𝐾), limiting scalability; FPS placement is seed-sensitive at small 𝐾 (±5% at 𝐾=50) but stabilizes at 𝐾 ≥ 500 (±0.2%). • The 0.5 pp gap to ECS (Hacquard and Lebovici, 2024) on Orbit5k (91.3% vs. 91.8%) reflects the 1D filtration concatenation PALACE uses where ECS works directly on a 2D bifiltration surface. • On NCI1 and PTC, where discriminative power lies in discrete node-label features that continuous structural filtrations cannot capture, PALACE inherits the same gap that Majhi et al. (2026) documents to graph-kernel and GNN baselines exploiting node labels (Table 10). Future work. The full inferential theory on the PALACE embedding family— continuous landmark configurations and the associated sample-complexity rates—is developed in (Bagchi et al., 2026).

References Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence images: A stable vector representation of persistent homology. Journal of Machine Learning Research, 18(8):1–35, 2017. Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Geometric approximation via coresets. In Combinatorial and Computational Geometry, volume 52 of MSRI Publications, pages 1–30. Cambridge University Press, 2005. Hirokazu Anai, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hiroya Inakoshi, Raphaël Tinarrage, and Yuhei Umeda. DTM-based filtrations. In International Symposium on Computational Geometry (SoCG), pages 58:1–58:15, 2019. Pramita Bagchi, Sushovan Majhi, Atish Mitra, and Žiga Virk. A statistical-inference pipeline for persistence-landmark kernels. Manuscript in preparation; available from the authors on request, 2026. Peter Bubenik. Statistical topological data analysis using persistence landscapes. Journal of Machine Learning Research, 16(1):77–102, 2015. Mathieu Carrière, Marco Cuturi, and Steve Oudot. Sliced Wasserstein kernel for persistence diagrams. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pages 664–673. PMLR, 2017. Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. PersLay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2786–2796, 2020. Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J. Guibas, and Steve Y. Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the 25th Annual Symposium on Computational Geometry (SoCG), pages 237–246, 2009. doi: 10.1145/1542362.1542407. Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics. Springer, 2016. doi: 10.1007/978-3-319-42545-0.

43

David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103–120, 2007. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Extending persistence using Poincaré and Lefschetz duality. Foundations of Computational Mathematics, 9(1):79–103, 2009. doi: 10.1007/ s10208-008-9027-z. Vin de Silva and Joshua B. Tenenbaum. Sparse multidimensional scaling using landmark points. Technical report, Stanford University, 2004. Petros Drineas and Michael W. Mahoney. On the Nyström method for approximating a Gram matrix for improved kernel-based learning. Journal of Machine Learning Research, 6:2153–2175, 2005. Herbert Edelsbrunner and John L Harer. Computational Topology. American Mathematical Society, Providence, RI, January 2010. Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 569–578, 2011. doi: 10.1145/1993636.1993712. Rickard Brüel Gabrielsson, Bradley J. Nelson, Anjan Dwaraknath, and Primoz Skraba. A topology layer for machine learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293–306, 1985. doi: 10.1016/0304-3975(85)90224-5. Olympio Hacquard and Vadim Lebovici. Euler characteristic tools for topological data analysis. Journal of Machine Learning Research, 25:1–39, 2024. Juha Heinonen. Lectures on Analysis on Metric Spaces. Universitext. Springer-Verlag, New York, 2001. Ch. 10: doubling metric spaces. Christoph Hofer, Roland Kwitt, Marc Niethammer, and Andreas Uhl. Deep learning with topological signatures. In Advances in Neural Information Processing Systems (NeurIPS), 2017. Genki Kusano, Yasuaki Hiraoka, and Kenji Fukumizu. Persistence weighted Gaussian kernel for topological data analysis. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 2004–2013, 2016. Tam Le and Makoto Yamada. Persistence Fisher kernel: A Riemannian manifold kernel for persistence diagrams. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 10028– 10039, 2018. Lucien Le Cam. Convergence of estimates under dimensionality restrictions. Annals of Statistics, 1:38–53, 1973. Sushovan Majhi, Atish Mitra, Žiga Virk, and Pramita Bagchi. A closed-form persistence-landmark pipeline for certified point-cloud and graph classification, 2026. URL https://arxiv.org/abs/2605.02836. Sebastian Mika, Gunnar Rätsch, Jason Weston, Bernhard Schölkopf, and Klaus-Robert Müller. Fisher discriminant analysis with kernels. In Neural Networks for Signal Processing IX (NNSP), pages 41–48, 1999. doi: 10.1109/NNSP.1999.788121.

44

Atish Mitra and Žiga Virk. Geometric embeddings of spaces of persistence diagrams with explicit distortions. arXiv:2401.05298, 2024. URL https://arxiv.org/abs/2401.05298. Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, Cambridge, MA, 2nd edition, 2018. James R. Munkres. Topology. Prentice Hall, Upper Saddle River, NJ, second edition, 2000. Lebesgue number lemma: Theorem 27.5. Yann Ollivier. Ricci curvature of Markov chains on metric spaces. Journal of Functional Analysis, 256(3): 810–864, 2009. doi: 10.1016/j.jfa.2008.11.001. Raphael Reinauer, Matteo Caorsi, and Nicolas Berkouk. Persformer: A transformer architecture for topological machine learning. In arXiv preprint arXiv:2112.15210, 2021. Jan Reininghaus, Stefan Huber, Ulrich Bauer, and Roland Kwitt. A stable multi-scale kernel for topological machine learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4741–4748, 2015. doi: 10.1109/CVPR.2015.7299106. Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. A concise and provably informative multi-scale signature based on heat diffusion. Computer Graphics Forum, 28(5):1383–1392, 2009. doi: 10.1111/j.1467-8659.2009. 01515.x. Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, 2009. doi: 10.1007/b13794. Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998. Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer, 2005. doi: 10.1007/b106715. Christopher K. I. Williams and Matthias Seeger. Using the Nyström method to speed up kernel machines. In Advances in Neural Information Processing Systems (NIPS), volume 13, pages 682–688, 2001. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019. Bin Yu. Assouad, Fano, and Le Cam. In David Pollard, Erik Torgersen, and Grace L. Yang, editors, Festschrift for Lucien Le Cam, pages 423–435. Springer, 1997. Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. RetGK: Graph kernels based on return probabilities of random walks. In Advances in Neural Information Processing Systems (NeurIPS), 2018. Qi Zhao and Yusu Wang. Learning metrics for persistence-based summaries and applications for graph classification. In Advances in Neural Information Processing Systems, volume 32, pages 9855–9866, 2019. NeurIPS 2019.

45