Research map / Learning theory and algorithms / Kernels and regression theory

A general kernel framework for non-CND distance measures using $|\mathcal{D}|$-dimensional sparse landmark embeddings

NeurIPS 2026 · Learning theory and algorithms › Kernels and regression theory · approach: RKHS kernel methods

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes the Sparse Landmark Embedding (SLE) kernel, which embeds inputs via compactly supported bump functions centered at all training points and applies a Euclidean PSD kernel, yielding a provably PSD kernel for arbitrary (non-CND) distances in GP regression.

Problem

Gaussian process and kernel methods require a CND (Hilbertian) distance to guarantee PSD kernels, which fails for geodesic distances on manifolds and Wasserstein distances between distributions.

Approach

Embed each input into a sparse |D|-dimensional vector of compactly supported bump functions of its distances to all training points, then apply a standard Euclidean kernel (e.g., Matérn) in that space; PSD holds for any distance, and compact support gives sparsity and well-conditioned matrices without landmark selection.

Key results

• On the Dragon manifold at 400 training points, SLE reaches RMSE 0.062 ± 0.002 and CRPS 0.030 ± 0.001, versus best Riemannian Matérn RMSE 0.109 and CRPS 0.100.
• On the Teddy Bear manifold, SLE achieves PICP 0.929–0.941 across training sizes while the Geometric kernel gets 0.100–0.138, with RMSE comparable (e.g., 41.8 vs 42.1 at n=200).
• On SAXS distributions at n=150, SLE-Wass RMSE 0.467 ± 0.010 vs Matérn-Sliced Wass 0.489 ± 0.010, showing competitiveness rather than clear superiority.

Surprising findings

• The Geometric kernel's PICP of 8–27% on Teddy Bear indicates severe overconfidence despite RMSE matching SLE.
• SLE applied on top of sliced Wasserstein has higher RMSE and CRPS than SLE with exact W2, suggesting accuracy gains come mainly from exact distances.

Limitations

• Forming the full N x |D| distance matrix requires O(N|D|) distance computations.
• Predictive performance is sensitive to bump radius, which is only learned globally via marginal likelihood.
• Global geometric structure beyond bump radii is discarded, so tasks needing long-range structure may need larger radii.

Experimental setup

Datasets: Dragon mesh (100,179 vertices) Teddy Bear mesh (1,598 vertices) synthetic SAXS images (500)

Benchmarks: Dragon manifold GP regression Teddy Bear manifold GP regression SAXS distribution regression

Metrics: RMSE CRPS PICP (95%)

Baselines: Riemannian Matérn kernel Geometric kernel Matérn with sliced Wasserstein distance

Builds on: D2KE Matérn kernel Riemannian Matérn kernel sliced Wasserstein kernel

Closest papers by meaning

• Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.86)
• Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.85)
• Kernel Quantile Embeddings and Associated Probability Metrics (ICML 2025 · similarity 0.84)
• Metric Space Magnitude for Evaluating the Diversity of Latent Representations (NeurIPS 2024 · similarity 0.84)
• Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.83)
• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.83)