Kernel methods, such as Support Vector Machines (SVMs) and kernel logistic regression, owe their success to a elegant mathematical guarantee: if a similarity function satisfies Mercer's condition—meaning it is positive semi-definite (PSD)—the underlying optimization landscape is guaranteed to be a convex bowl. This ensures that optimization algorithms will reliably converge to a unique global optimum.
To leverage this framework for complex data like text, time series, or probability distributions, researchers often try to convert domain-specific distance metrics $d(x, y)$ into kernels using an exponential framework:
$$K(x, y) = \exp(-\gamma d(x, y))$$
However, a profound mathematical hurdle arises. As Corinna Cortes et al. and Bram Vanschoenwinkel et al. observe, you cannot simply plug any intuitive distance metric into this formula. For the resulting kernel to be valid (PSD), the underlying distance must be conditionally negative definite (CND). When domain-specific metrics lack this property, the mathematical foundation of kernel learning fractures.
Why Intuitive Distances Break Definiteness
Many of the most effective metrics for structured data deliberately violate the flatness of Euclidean space. They typically rely on a minimization operator over a discrete or curved space:
- Edit Distances: Levenshtein or Needleman-Wunsch distances find the minimum cost sequence of operations to transform one string or video sequence into another (Marco Bertini 0001 et al.).
- Dynamic Time Warping (DTW): Compares variable-length time series by finding the single best alignment path through a grid of temporal points (marco cuturi).
- Optimal Transport (Wasserstein Distance): Measures the distance between probability distributions by finding the cheapest way to move mass from one configuration to another (marco cuturi).
The "min" operator in these definitions introduces sharp, non-differentiable geometric corners. Because these distances do not behave like straight lines in a flat space, they fail to be conditionally negative definite. As Soheil Kolouri et al. and Henri De Plaen et al. note, this non-zero curvature creates a "compatibility gap" where exponential kernels become indefinite (possessing negative eigenvalues).
When a kernel is indefinite, the optimization guarantees vanish. As Fanghui Liu 0001 et al. explain, the loss of convexity means standard training algorithms can suffer from severe mathematical instabilities, fail to converge, or produce invalid geometric projections in the reproducing kernel Hilbert space.
To overcome this, a major research direction focuses on two primary strategies: smoothing the optimization landscape, or altering the underlying geometry.
Strategy 1: Soft-Max and Polytope Aggregation
If choosing the single best path or alignment introduces the non-smoothness that breaks positive definiteness, why not consider all possible paths?
This is the core intuition behind the Global Alignment (GA) kernel proposed by marco cuturi et al.. Instead of using DTW to find the minimum-cost alignment, the GA kernel computes a soft-max (log-sum-exp) over the entire set of possible alignments. By exponentiating and summing over every valid path, the sharp geometric corners are smoothed away, yielding a mathematically rigorous, positive definite kernel that retains the alignment power of DTW.
Traditional DTW (Indefinite):
Path Space ---> [ Min Operator ] ---> Sharp Corners (Non-CND)
Global Alignment Kernel (Positive Definite):
Path Space ---> [ Soft-Max / Sum ] ---> Smooth Geometry (CND)
The author applied this same insight to optimal transport in Permanents, Transport Polytopes and Positive Definite Kernels on Histograms. Rather than computing only the Earth Mover's Distance (the single optimal transport plan), the author proved that integrating over the entire transportation polytope—the space of all valid ways to redistribute mass—yields a valid positive definite kernel.
Strategy 2: Embedding into Well-Behaved Geometries
A second strategy avoids the complexity of general spaces by projecting the data into alternative geometries where negative definiteness is mathematically guaranteed.
While the Wasserstein distance is not naturally CND on general high-dimensional spaces or graphs, it is CND when restricted to one-dimensional lines or tree structures. Capitalizing on this, Tam Le et al. developed "tree-sliced" variants of the Wasserstein distance. By partitioning the underlying space into tree structures, they obtained a distance metric that naturally satisfies negative definiteness, allowing for the seamless construction of valid positive definite kernels.
General Space (Non-zero curvature) ---> Wasserstein Distance ---> Indefinite Kernel
Tree-Structured Space (Flat/Tree) ---> Tree Wasserstein ---> Positive Definite Kernel
Similarly, when dealing with the complex topological features of persistence diagrams, Tam Le et al. bypassed the problematic Wasserstein metric entirely. They instead mapped the diagrams into a Riemannian manifold governed by Fisher information geometry. Because this geometry possesses a naturally compatible metric, the resulting Persistence Fisher Kernel is guaranteed to be positive definite, stable, and highly efficient.
This paradigm of geometric reformulation has proven highly versatile. By designing regularized variants of transport problems on graphs—such as Sobolev Transport (Tam Le et al.), Unbalanced Sobolev Transport (Tam Le et al. et al.), and Sobolev Integral Probability Metrics (Tam Le et al.)—the authors have consistently derived closed-form, kernel-compatible solutions. These methods bypass the compatibility gap entirely, allowing advanced structural and distributional metrics to be deployed safely within standard kernel-based machine learning workflows.
Key Foundational Work
Rational Kernels: Theory and Algorithms (2004) — contributed 1 concept elements to this direction.
A Weighted Polynomial Information Gain Kernel for Resolving Prepositional Phrase Attachment Ambiguities with Support Vector Machines (2003) — contributed 1 concept elements to this direction.