Machine Learning with Indefinite Kernels

This direction is merged into another direction: positive semi-definite constraint. Its last version stays readable and citable here.

Version 1 of 120 papers20 conceptsfrozen 2026-10-04

In classical kernel methods, the "Mercer condition" is a strict gatekeeper. It dictates that for a similarity function to be valid, its resulting kernel matrix must be positive semi-definite (PSD). This requirement ensures that the optimization problem is convex and that the data can be implicitly mapped into a high-dimensional Hilbert space.

However, real-world similarity measures—such as those derived from protein sequences, graph matching, or human perception—frequently violate this condition. These "indefinite" kernels contain negative eigenvalues, breaking the geometric assumptions of standard Support Vector Machines (SVMs). Rather than forcing these measures into a PSD framework through distortion, a growing body of research focuses on learning directly within Reproducing Kernel Kreĭn Spaces (RKKS).

The Geometry of Kreĭn Spaces

A Hilbert space is like a standard Euclidean space where distances are always positive. A Kreĭn space is more permissive: it is an inner product space that can be decomposed into a "positive" Hilbert space and a "negative" Hilbert space.

Mathematically, an indefinite kernel $K$ can be viewed as the difference between two PSD kernels: $K = K_+ - K_-$. As Fanghui Liu, Xiaolin Huang, and Johan Suykens demonstrate in Fast Learning in Reproducing Kernel Krein Spaces via Generalized Measures, this decomposition allows us to treat indefinite kernels using "signed measures." This perspective reveals that even modern architectures like the Neural Tangent Kernel (NTK) can be non-PSD on certain domains, making the study of Kreĭn spaces essential for understanding deep learning theory.

Optimization via Decomposition

The primary challenge with indefinite kernels is that the standard SVM dual objective becomes non-convex. Researchers have developed several strategies to bypass this:

  1. Convex Proxies: Ronny Luss and Alexandre d'Aspremont proposed in Support Vector Machine Classification with Indefinite Kernels a method to simultaneously learn the support vector weights and a "proxy" Mercer kernel that is close to the original indefinite one.
  2. Difference of Convex (DC) Programming: Since the kernel is a difference of two PSD components, the objective function can be framed as a difference of two convex functions. Hui Xue utilizes this in Multiple Indefinite Kernel Learning for Feature Selection to perform feature selection without discarding the descriptive power of indefinite measures.
  3. The 1-norm Solution: In a surprising finding, Ibrahim Alabdulmohsin and Xin Gao showed in Large margin classification with indefinite similarities that the 1-norm SVM is naturally robust to indefiniteness. Unlike the standard 2-norm SVM, the 1-norm formulation remains a linear program (and thus convex) even when the kernel is not PSD, while providing much sparser solutions.

Scaling Indefinite Learning

Standard kernel methods scale poorly with data size, a problem exacerbated by the complexity of Kreĭn spaces. To address this, researchers have extended classical approximation techniques to the indefinite setting.

Dino Oglić and Thomas Gärtner provided the first mathematically rigorous extension of the Nyström method to indefinite kernels in Large Scale Learning with Kreĭn Kernels. By performing a low-rank eigendecomposition that accounts for both positive and negative eigenvalues, they enabled scalable Kernel Ridge Regression on massive datasets that were previously computationally inaccessible.

Similarly, for random features—a popular way to avoid computing the full kernel matrix—Fanghui Liu and colleagues developed an unbiased random features algorithm in Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures. This allows indefinite kernels to be used in a "linearized" fashion, matching the speed of linear models while retaining the flexibility of non-PSD similarity measures.

Why It Works

The intuition behind the success of these methods is that indefiniteness is information, not noise. When we force an indefinite similarity matrix to be PSD (e.g., by flipping negative eigenvalues to zero), we discard the "dissimilarity" information encoded in those negative directions.

By using frameworks like RKKS, we allow the model to learn in a space where "negative similarity" is a first-class citizen. As Fanghui Liu proves in Analysis of regularized least-squares in reproducing kernel Kreĭn spaces, learning rates in these spaces can match those of standard Hilbert spaces, provided the non-convexity is managed through appropriate constraints. This theoretical bridge justifies the use of intuitive but mathematically "messy" similarity functions in high-stakes domains like bioinformatics and structural pattern recognition.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_machine_learning_with_indefinite_kernels_317d4675,
  title = {Machine Learning with Indefinite Kernels},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/machine-learning-with-indefinite-kernels/rdr_317d46756e6249989f0dd57979922962},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_machine_learning_with_indefinite_kernels_317d4675_v1,
  title = {Machine Learning with Indefinite Kernels},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/machine-learning-with-indefinite-kernels/rdr_317d46756e6249989f0dd57979922962/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}