High-dimensional Semi-supervised Classification via the Fermat Distance

• URL: http://arxiv.org/abs/2604.23573v1
• Date: Sun, 26 Apr 2026 07:28:21 GMT
• Title: High-dimensional Semi-supervised Classification via the Fermat Distance
• Abstract summary: Semi-supervised classification, where unlabeled data are massive but labeled data are limited, often arises in machine learning applications.<n>We propose the weighted $k$-nearest neighbors (NN) classifier and multidimensional scaling (MDS)-induced classifiers.<n>We explicitly quantify the utility of unlabeled data by showing that the error arising from estimating the Fermat distance decays exponentially with the pooled sample size.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semi-supervised classification, where unlabeled data are massive but labeled data are limited, often arises in machine learning applications. We address this challenge under high-dimensional data by leveraging the manifold and cluster assumptions. Based on the Fermat distance, a density-sensitive metric that naturally encodes the cluster assumption, we propose the weighted $k$-nearest neighbors (NN) classifier and multidimensional scaling (MDS)-induced classifiers. The use of MDS with a large target dimension allows the effective application of linear classifiers to complex manifold data. Theoretically, we derive a sharp lower bound for the expected excess risk within clusters and prove that the weighted $k$-NN classifier utilizing the true Fermat distance is minimax optimal. Furthermore, we explicitly quantify the utility of unlabeled data by showing that the error arising from estimating the Fermat distance decays exponentially with the pooled sample size. Such a rate is much faster than the related rates in the literature. Extensive experiments on synthetic and real datasets demonstrate competitive or superior performance of our approaches compared to state-of-the-art graph-based semi-supervised classifiers.

Related papers

• A scalable version of MADD for big-data classification [0.7837881800517111]
  In high-dimensional, low-sample-size situations, a data-driven semi-metric called the Mean Absolute Difference of Distances (MADD) is known to circumvent these issues.<n>We propose a scalable version of MADD that significantly reduces its computational complexity while retaining its advantages.
  arXiv  Detail & Related papers  (2026-07-09T10:19:57Z)
• When and How Unlabeled Data Provably Improve In-Context Learning [31.201385551730926]
  In-supervised learning can be effective even when demonstrations have missing or incorrect labels.<n>We show that multilayer or looped transformers can effectively leverage unlabeled data by implicitly constructing estimators of the form $sum_ige 0 a_i (Xtop X)iXtop y$ with $X$ and $y$ denoting features and partially-observed labels.
  arXiv  Detail & Related papers  (2025-06-18T10:01:17Z)
• The Exploration of Error Bounds in Classification with Noisy Labels [7.657250843344973]
  In this paper, we focus on the error bounds of excess risks for classification problems with noisy labels within deep learning frameworks.<n>We derive error bounds for the excess risk, decomposing it into statistical error and approximation error.<n>Under the low-dimensional manifold hypothesis, we further refine the approximation error to mitigate the impact of high-dimensional input spaces.
  arXiv  Detail & Related papers  (2025-01-25T10:06:50Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Categorical Data Clustering via Value Order Estimated Distance Metric Learning [53.28598689867732]
  This paper introduces a novel order distance metric learning approach to intuitively represent categorical attribute values.<n>A new joint learning paradigm is developed to alternatively perform clustering and order distance metric learning.<n>The proposed method achieves superior clustering accuracy on categorical and mixed datasets.
  arXiv  Detail & Related papers  (2024-11-19T08:23:25Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  We introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs) Our proposed method first trains SOMs on unlabeled data and then a minimal number of available labeled data points are assigned to key best matching units (BMU) Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques.
  arXiv  Detail & Related papers  (2024-01-12T22:51:48Z)
• Beyond Labels: Advancing Cluster Analysis with the Entropy of Distance Distribution (EDD) [0.0]
  Entropy of Distance Distribution (EDD) is a paradigm shift in label-free clustering analysis. Our method employs the Shannon information entropy to quantify the 'peakedness' or 'flatness' of distance distributions in a data set. EDD's potential extends beyond conventional clustering analysis, offering a robust, scalable tool for unraveling complex data structures.
  arXiv  Detail & Related papers  (2023-11-28T09:22:17Z)
• Riemannian classification of EEG signals with missing values [67.90148548467762]
  This paper proposes two strategies to handle missing data for the classification of electroencephalograms. The first approach estimates the covariance from imputed data with the $k$-nearest neighbors algorithm; the second relies on the observed data by leveraging the observed-data likelihood within an expectation-maximization algorithm. As results show, the proposed strategies perform better than the classification based on observed data and allow to keep a high accuracy even when the missing data ratio increases.
  arXiv  Detail & Related papers  (2021-10-19T14:24:50Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  In particular, we seek to understand the behaviour of the em generalization error of iterative SSL algorithms using information-theoretic principles. Our theoretical results suggest that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates.
  arXiv  Detail & Related papers  (2021-10-03T05:38:49Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46: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.