Breaking the curse of dimensionality with Isolation Kernel

2021/09/29 by Kai Ming Ting, Ting, Kai Ming, Takashi Washio +5
Computer Science · #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Metaheuristic Optimization Algorithms Research #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2109.14198

openalex publication_date 2021/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The curse of dimensionality has been studied in different aspects. However, breaking the curse has been elusive. We show for the first time that it is possible to break the curse using the recently introduced Isolation Kernel. We show that only Isolation Kernel performs consistently well in indexed search, spectral & density peaks clustering, SVM classification and t-SNE visualization in both low and high dimensions, compared with distance, Gaussian and linear kernels. This is also supported by our theoretical analyses that Isolation Kernel is the only kernel that has the provable ability to break the curse, compared with existing metric-based Lipschitz continuous kernels.

Citations

• k-NN Regression Adapts to Local Intrinsic Dimension
• Estimating the Support of a High-Dimensional Distribution

Related

• Isolation Kernel: The X Factor in Efficient and Effective Large Scale Online Kernel Learning
• MIK: Modified Isolation Kernel for Biological Sequence Visualization, Classification, and Clustering
• Solving Interpretable Kernel Dimension Reduction
• Parsimonious Mahalanobis Kernel for the Classification of High Dimensional Data
• Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect