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

• URL: http://arxiv.org/abs/2605.04046v1
• Date: Tue, 05 May 2026 17:59:18 GMT
• Title: A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification
• Abstract summary: PALACE is the strongest closed-form diagram-based method on OrbitHS5k ($91.3pm 1.0%$, matching Persformer)<n>At $8$ domain inflation, placement maintains $94%$ while the uniform grid collapses to chance ($25%$ on 4-class data)<n> Empirically, PALACE is the strongest closed-form diagram-based method on OrbitHS5k ($91.3pm 1.0%$, matching Persformer)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce PALACE (Persistence Adaptive-Landmark Analytic Classification Engine), the data-adaptive companion to PLACE, paying a small cross-validation tier on three knobs (budget, radii, bandwidth; $\leq 5$ choices each). A cover-theoretic core (Lebesgue-number criterion on the landmark cover) yields four closed-form guarantees. (i) A structural lower distortion bound $λ(τ;ν)$ on $\mathcal{D}_n$ under cross-diagram non-interference, with a $(D/L)^2$ budget reduction over the uniform grid when diagrams concentrate. (ii) Equal weights $w_k = K^{-1/2}$ maximizing $λ$, and farthest-point-sampling positions $2$-approximating the optimal $k$-center covering radius; both derived from training labels alone, no gradient training. (iii) A kernel-RKHS classification rate $O((k-1)\sqrt{K}/(γ\sqrt{m_{\min}}))$ with binary necessity threshold $m = Ω(\sqrt K/γ)$ from a matching Le Cam lower bound, and a closed-form filtration-selection rule. The kernel-Mahalanobis margin $\hatρ_{\mathrm{Mah}}$ is the strongest closed-form ranker across the chemical-graph pool (mean Spearman $ρ\approx +0.60$); the isotropic surrogate $\hatγ/\sqrt{K}$ admits a selection-consistency rate, and $\widehatλ$ from (i) provides an independent data-level signal (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 \pm 1.0\%$, matching Persformer), leads every diagram-based competitor on COX2 and MUTAG, and is competitive on DHFR (within 1 pp of ECP). At $8\times$ domain inflation, adaptive placement maintains $94\%$ while the uniform grid collapses to chance ($25\%$ on 4-class data).

Related papers

• Multi-Modal Spatio-Temporal Graph Neural Network with Mixture of Experts for Soil Organic Carbon Prediction [0.0]
  Existing approaches face two limitations: they pair hand-crafted co-modals with classical ML or single-modal deep models that miss rich spectral and temporal information.<n>We introduce SpTG-NN, a multi-temporal graph neural network addressing both SpTGNN and grid-based architectures.<n>A fine-tuned TerraMind encoder extracts node features from Sentinel-2, Sentinel-1 and DEM signals.
  arXiv  Detail & Related papers  (2026-06-15T11:25:38Z)
• UR-JEPA: Uniform Rectifiability as a Regularizer for Joint-Embedding Predictive Architectures [0.0]
  We propose emphUR-JEPA, which targets a uniformly $n$-rectifiable measure of local dimension tangent $n$ at small scales.<n>We show that on all four datasets UR--JEPA($mathcalLtextCGLT$) produces a global geometric spectrum with a $4$ to $5$ order-of-magnitude drop at index $sim 20$ to $25$ out of $D = 32$, while LeJEPA's spectrum is near-flat (top-to-bottom ratio at most $3.6$)
  arXiv  Detail & Related papers  (2026-05-31T20:26:54Z)
• Matching Rates and Optimal Allocation for Federated Probe-Logit Distillation under Heterogeneous Bandwidth Budgets [12.805268849262243]
  In language modeling, $K$ nodes each hold $n$ samples but cannot pool data or exchange full-precision gradients or weights.<n>We study the minimax rate at which a conditional distribution over $V$ tokens can be estimated when each node may upload at most $B$ bits per query in a public probe set.
  arXiv  Detail & Related papers  (2026-05-28T09:08:39Z)
• Hidden-State Privacy Has an Empty Middle [51.56484100374058]
  We prove a complementary Fisher-ball lower bound: every full-rank Gaussian release at $O(1)$ Fisher utility admits a direction whose Mahalanobis signal grows linearly in hidden width.<n>A split-memory transformer trained from scratch reaches $G_mathrmMah in [20, 33]$ at 90M and maintains a $6$--$24times$ advantage over same-budget GPT baselines from 30M to 1B at a fixed-token language loss penalty.
  arXiv  Detail & Related papers  (2026-05-21T20:12:09Z)
• The Wristband Gaussian Loss: Deterministic, Composable Latents via a Sphere-Interval Decomposition [1.0195618602298684]
  Wristband Gaussian Loss is a deterministic batch loss for Gaussianizing point embeddings without sampling, KL terms, or iterative transport.<n>We compute this reflected- kernel objective in two ways: a nearest three-image pairwise truncation at $O(N2 d)$, and a spectral Neumann path joining angular and radial Mercer modes.<n>A 1D Wasserstein radial term and a moment penalty serve as finite-sample accelerators with the same optimum, and Monte-Carlo$ turns the components into a single standardized statistic.
  arXiv  Detail & Related papers  (2026-05-09T07:25:37Z)
• A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification [0.0]
  PLACE (Persistence-Landmark Analytic Classification Engine) is a closed-form pipeline for classifying point clouds and graphs.<n>Three quantitative guarantees -- a margin-based excess-risk rate, a closed-form descriptor-selection rule, and a per-prediction certificate -- are derived from training labels alone.
  arXiv  Detail & Related papers  (2026-05-04T17:15:01Z)
• High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking [69.90407799170687]
  We study high-probability (HP) convergence guarantees in decentralized optimization.<n>Our results establish the same conditions on the horizon as in achieving comparable times.
  arXiv  Detail & Related papers  (2026-04-30T22:45:21Z)
• Bond-dimension scaling of a local-refinement advantage over hyperoptimized tensor-network contraction on Sycamore like topologies [0.0]
  We identify a missing local-refinement stage in the cotengra tensor-network contraction pipeline.<n>We show that its impact grows monotonically with bond dimension on the emphconnectivity graph of Sycamore-like topologies.
  arXiv  Detail & Related papers  (2026-04-28T11:59:31Z)
• Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence [6.908972852063454]
  Majority-vote ensembles achieve variance reduction by averaging over diverse, approximately independent base learners.<n>We provide a minimax characterization of this phenomenon for discrete classification in a fixed-dimensional Markov setting.<n>Experiments on synthetic Markov chains, 2D spatial grids, the 128-dataset UCR archive, and Atari DQN ensembles validate the theoretical predictions.
  arXiv  Detail & Related papers  (2026-04-15T02:32:30Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization [23.28384210732827]
  We propose ALFCG, the first textitadaptive projection-free framework for composite nontracking variants.<n>Unlike prior methods that use openloop diminishing steps, ALFCG maintains self-normalized accumulators.<n>ALFCG-FS attains $tildemathcalO(2+-2$ and $tildemathcalO(-3+-2) $to 0$, while ALFCG-MVR2 achieve $tildemathcalO(2+
  arXiv  Detail & Related papers  (2026-03-06T15:20:52Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Improved convergence rate of kNN graph Laplacians [11.93971616098517]
  General class of $k$NN graph where the graph affinity is $W_ij = epsilon-d/2 . We prove the point-wise convergence of the $k$NN graph Laplacian to the limiting manifold operator.
  arXiv  Detail & Related papers  (2024-10-30T17:01:00Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  We propose the first computationally efficient horizon-free algorithm for linear mixture MDPs. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic. This also improves upon the best-known algorithms in this setting when $sigma_k2$'s are known.
  arXiv  Detail & Related papers  (2022-05-23T17:59:18Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.