The theoretical results provide a principled non-cross-validated alternative to the classical n rule, and cross-validation remains the strongest k-selection strategy when computationally feasible.
Abstract
The k-nearest neighbor (KNN) algorithm remains one of the most fundamental and widely-used methods in machine learning. A common rule of thumb sets the number of neighbors as k=n, where n is the size of the training set. Despite its widespread adoption, the theoretical justification for this choice has remained obscure. We provide a comprehensive rate-based analysis. First, we derive the minimax-optimal exponent β*=4/(d+4) for k=nβ under standard Hölder-smoothness assumptions, recovering as a special case Theorem 1: under these second-order Hölder-smoothness assumptions, k=n attains the asymptotic minimax-optimal exponent if and only if the feature space has dimensionality d=4; this concerns the asymptotic rate exponent, not the finite-sample optimal value of k. Second, Theorem 2 quantifies the sub-optimality of any fixed β as Rn(nβ)=Θ(n−r(β,d)) with r(β,d)=min{β,4(1−β)/d}, yielding an asymmetric penalty for the classical rule when d≠4 that we make precise in Corollary 1. The predicted rate is empirically verified across d∈{2,…,20} on controlled synthetic data. On 48 datasets from the OpenML-CC18 benchmark suite, the dimension-aware rule k=⌊n4/(d+4)⌋ outperforms the classical n rule in 32 of 48 head-to-head comparisons (paired Wilcoxon p=4.6×10−4, mean accuracy gain +2.5 percentage points), demonstrating that the theoretical improvement translates to a practical one. We further test the Hassanat distance metric against Euclidean across all KNN variants on the same 48 datasets, finding that Hassanat outperforms Euclidean in five of six configurations (paired Wilcoxon p<0.05), with the largest gains on unstandardized data. Cross-validation remains the strongest k-selection strategy when computationally feasible, and the theoretical results provide a principled non-cross-validated alternative.
Random feature methods provide a scalable approximation to kernel ridge regression (KRR), but the regularization parameter that yields the oracle learning rate depends on unknown smoothness and capacity parameters. In this work, we propose a neighboring early-stopping rule for adaptive regularization in KRR with random features (KRR-RF). The method uses a grid that is uniform in inverse regularization and compares only adjacent estimators, reducing the number of discrepancy comparisons relative to standard all-pairs Lepskii-type procedures. Both the neighboring discrepancy and its empirical complexity term can be computed directly in the random feature space, without constructing the exact kernel Gram matrix. We establish a high-probability comparison bound for neighboring KRR-RF estimators and show that, under standard source and capacity conditions together with suitable grid and random feature budget conditions, the selected estimator attains the oracle polynomial learning rate up to logarithmic factors. The result allows the regularization parameter to be selected without prior knowledge of the source and capacity exponents and covers both well-specified and partially misspecified regimes. Our analysis is based on an empirical random feature effective dimension that connects the observable stopping threshold with the population complexity of the random feature model. Simulation and real-data experiments illustrate the prediction performance and computational behavior of the proposed method in comparison with standard tuning procedures.
The $k$-Nearest Neighbor~(KNN) algorithm is widely used across various tasks. The selection of the $k$ value is a key issue because it significantly impacts performance. In this paper, an adaptive and efficient KNN approach via granular-ball computing is proposed. The method consists of two stages. \textcolor{black}{In the training stage, the dataset is first coarsely partitioned to reduce the complexity of data distributions within a granular ball, and then the Fisher criterion is introduced to control ball splitting and stopping, yielding a multi-granularity granular ball representation. In the prediction stage, the nearest granular ball is first located through a weighted distance mechanism, and an adaptive neighborhood is then constructed around the test sample. The effective $k$ value is dynamically determined by the actual number of samples contained in this neighborhood. The neighborhood induced by the nearest granular ball provides more stable local group information, thereby improving robustness against noise and local perturbations.} Experimental results demonstrate that the proposed method outperforms existing KNN variants across multiple datasets in terms of both accuracy and efficiency. The code has been open-sourced for reproducibility: https://github.com/lianxiaoyu724/Adaptive-GBKNN.
Xiaoyu Lian, Shuyin Xia, Hongxuan He et al.· 0 citations
Chernoff information is a fundamental divergence measure characterizing the optimal error exponent in Bayesian binary hypothesis testing, with applications in information fusion, time-series analysis, and statistical learning theory. However, closed-form expressions exist only for simple parametric families, and nonparametric estimation remains difficult because the quantity is defined as an optimization of the unnormalized R\'enyi divergence over its order. We reformulate this optimization via a derivative condition, whose zero locates the optimal mixture parameter, and estimate the derivative directly using a $k$-nearest-neighbor method. We prove the $L_2$-consistency of the derivative estimator under mild regularity conditions on the densities and their domain. Coupled with a bisection procedure that locates the optimal parameter up to arbitrary precision, this yields an estimator for Chernoff information.
Clustering is a fundamental class of data analysis techniques with the most important representatives being centroid-based methods like $k$-means. Such methods are strongly connected to quantization problems, which aim to approximate general probability measures with discrete ones. For example, $k$-means corresponds to quantization with respect to the Wasserstein distance. While Wasserstein quantization clusters points within a fixed space, this paper studies Gromov-Wasserstein (GW) quantization, which additionally aims at clustering the ambient geometry of the space. We show existence of solutions to the GW quantization problem and give a characterization that justifies an analogue to the $k$-means algorithm (Lloyd's algorithm) to approximate them numerically. We further calculate the quantization rate for usual Euclidean geometries that are used in the GW context, and relate it to standard Wasserstein quantization rates. Finally, numerical experiments show that GW quantization opens up many modeling possibilities beyond normal clustering methods (e.g., for geodesic distances of 3D shapes or structured pruning of neural networks) and that the introduced algorithm leads to useful numerical solutions with approximation quality often in line with theoretically optimal rates.
The null distribution of distance covariance is usually approximated by permutation, which is prohibitive when very small p-values are needed, or by matching a few moments to a parametric family, which is inaccurate in the tails. A third option is to approximate the limiting distribution, a weighted sum of chi-square variables, directly through the spectra of the doubly centred distance matrices. This is used for kernel-based tests but has lacked a rigorous justification. We prove that the empirical spectra give a uniformly consistent approximation of the limiting null distribution, and hence an asymptotically valid test, for a general class of distances of negative type on separable metric spaces. The result covers the Hilbert-Schmidt independence criterion as a special case. We also give an adaptive algorithm that brackets the p-value from a partial eigendecomposition, reducing the cost from $O(n^3)$ to $O(k n^2)$, and a shrinkage correction matching the first two moments. In simulations, the proposed tests are the only non-Monte-Carlo procedures whose empirical type I error converges to the nominal level.
Dimensionality-reduction (DR) methods are routinely judged by how well each point's k nearest neighbors survive the 2-D embedding (recall@k, trustworthiness, continuity). We argue this family is a biased measure of distance fidelity: its per-point variable radius and hard inclusion threshold favor neighbor-graph methods (t-SNE, UMAP) and penalize methods that preserve absolute distances. We instead score DR fidelity with a fixed-radius distance-band Shepard rho: the Spearman correlation between high-D and 2-D pairwise distances, restricted to cumulative distance bands so that near and global structure are reported separately, with every point judged on the same absolute radius. On synthetic datasets with known ground-truth geometry (non-uniform density, dense clusters, a closed-loop transition, off-subspace outliers, imbalanced two-population data) at realistic noise (SNR=1, D=768, N=1000), we benchmark eight methods -- PCA, Isomap, t-SNE, UMAP, PyMDE, PCC, DREAMS, and the closed-source toorPIA -- and show that (i) high global Shepard rho can coexist with a ~93x collapse of within-cluster scale, invisible to rank-based scores but obvious in a value-based over-compression metric; (ii) recall@k and the fixed-radius band disagree systematically, in the direction the bias predicts; (iii) a membership-restricted Shepard rho resolves single-point and minority-population questions that many-pair statistics cannot -- questions on which even DREAMS, a recent local-plus-global hybrid, fails silently. A supplementary out-of-sample (addplot) test asks whether a never-seen anomaly lands outside the normal region and whether its direction identifies its source. All metrics are computed exactly on all pairwise distances, independently of any method's internals, and every number is reproducible offline: the closed-source method's output coordinates (not its algorithm) are committed to the artifact.