CS Paper Radar

Evolutionary Adaptive Metric Learning: A Multi-Objective Framework for Learning Local Distance Functions in Nearest Neighbor Classification

Isaac Touza

cs.LG ·submitted 2026-11-05 09:39 UTC · v1

Abstract

Nearest neighbour classifiers inherit the geometry of their distance function. Fixed distances and globally learned metrics apply the same geometry throughout the input space, although relevant feature directions may vary across regions. We propose EAML (Evolutionary Adaptive Metric Learning), a framework that learns instance-dependent positive-definite metrics through a low-dimensional parameterization. Each local metric combines an input-dependent diagonal scaling, generated by softmax interpolation between anchor points, with a global low-rank correlation component. A real-coded elitist genetic algorithm optimizes the parameters using a scalar objective combining leave-one-out prediction error, robustness, metric smoothness, and regularization. We establish positive definiteness, metric equivalence, existence of an optimal solution, and Lipschitz continuity of the metric field. We further investigate prediction stability, generalization bounds, and evolutionary convergence under explicit assumptions. Experiments on synthetic data with region-dependent feature relevance show that EAML can recover local metric variations and outperform global metrics. Evaluation on thirteen public datasets using nested 5-fold cross-validation reveals a more nuanced picture: EAML improves performance on selected datasets but does not significantly outperform global metric baselines overall. Additional experiments show that global diagonal metrics can be preferable under nuisance features and test-time noise. These findings identify the conditions under which evolutionary local metric learning is beneficial and highlight its practical limitations.

Closest papers

Nearest neighbours by meaning across the whole index.

Evolutionary Adaptive Neighborhood Learning: A Genetic Algorithm for Instance-Dependent k Optimization in Nearest Neighbor Classification

cs.LG cs.AI ·2026-11-05 ·Isaac Touza, Kaladzavi Guidedi, Kolyang
similarity 0.72
Abstract

The number of neighbours k is the central hyperparameter of the k-nearest neighbour (k-NN) classifier and is usually selected globally through cross-validation or evolutionary search. However, the bias-variance trade-off is inherently local: dense and noise-free regions may favour small neighbourhoods, whereas sparse or noisy regions may require larger ones. Since global-k optimization is one-dimensional, replacing exhaustive search with a genetic algorithm offers little computational advantage. We therefore optimize an instance-dependent neighbourhood policy instead. We propose EANK (Evolutionary Adaptive Neighborhood K), which uses a low-dimensional policy to map local neighbourhood descriptors, including density, label entropy, vote margin, and concentration, to an adaptive number of neighbours k(x). A real-coded elitist genetic algorithm optimizes this policy using leave-one-out accuracy with a neighbourhood-smoothness penalty. Precomputed neighbour votes reduce fitness evaluation costs. We investigate theoretical properties of the method, including dominance over global-k solutions on the training criterion, evolutionary convergence, policy regularity, and generalization guarantees. Experiments on synthetic data with spatially heterogeneous structure and twelve public datasets evaluate predictive performance, robustness, and computational cost. Under nested cross-validation, EANK achieves competitive performance relative to tuned global-k baselines and improves upon the default k=5. We also examine the gap between training and test performance to assess the practical value of adaptive neighbourhood selection.

0.31

Curvature-Aware Radius Shrinkage for Adaptive Nearest Neighbor Classification

cs.LG cs.AIcs.CVstat.ML ·2026-08-27 ·Alexandre L. M. Levada
similarity 0.62
Abstract · 28 pages, 2 figures and 3 tables

Nearest neighbor classification relies fundamentally on how locality is defined, yet conventional $k$-NN imposes the same neighborhood cardinality throughout the feature space. This assumption can be inadequate for data whose local geometry varies substantially across the underlying manifold. We introduce Curvature-Aware Radius Shrinkage for Adaptive Nearest Neighbor Classification (CARSANN), a geometry-driven framework that adapts the spatial support of each neighborhood according to local geometric complexity. CARSANN first estimates intrinsic dimensionality using TwoNN and constructs an intrinsic representation through principal component analysis. Local mean curvature is then estimated using a shape-operator-based formulation and controls neighborhood scale: highly curved regions receive stronger radius shrinkage, whereas approximately flat regions retain broader spatial support. Unlike methods that modify only the number of neighbors or the local metric, CARSANN explicitly adapts the spatial extent of local evidence. Experiments on more than 70 real-world OpenML datasets show that CARSANN consistently improves upon standard $k$-NN and is competitive with adaptive nearest-neighbor methods. In a controlled comparison using the same base neighborhood size, CARSANN achieves higher balanced accuracy on 40 of 45 datasets, increasing mean balanced accuracy from 0.6506 to 0.7528. The advantage also persists against $k$-NN with fixed $k=5$. Friedman and Nemenyi tests confirm that the improvements are statistically significant. These results indicate that local manifold curvature can serve as an effective geometric control variable for adapting neighborhood support, providing a complementary paradigm to cardinality-based nearest-neighbor adaptation.

0.18

Learning Variable Metrics for Convergent Proximal Splitting Algorithms

eess.IV ·2026-10-15 ·Yodai Suzuki, Shunsuke Ono
similarity 0.58
Abstract

We propose learned variable metric (LVM), a framework that learns metrics of proximal splitting algorithms adapted to each problem instance, coordinate, and iteration with a convergence guarantee. Proximal splitting algorithms can solve a wide variety of convex optimization problems but often require many iterations to converge. Choosing a suitable metric is an effective remedy, and variable metric theory naturally extends convergence guarantees to metrics that vary over the iterations. Learning is a promising way to design such adaptive metrics beyond the reach of manual design, but a naive implementation leads to (i) an expensive evaluation of a network at every iteration and (ii) difficulty in satisfying the conditions that the theory imposes on the whole infinite sequence of metrics. To resolve these difficulties, we first train a neural network to generate a few representative metrics once per problem instance, and then obtain the metric of every iteration by combining them with basis functions of the normalized iteration index. We present LVM for the proximal gradient method with a quadratic term and the primal-dual hybrid gradient method, and prove their convergence under a mild spectral condition, which is ensured by a rescaling of the representative metrics. In experiments on deblurring and inpainting, LVM reduces the number of iterations to reach a target accuracy in most tested settings compared with several baselines, and the computation time at high accuracies.

0.16

A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings

cs.LG stat.MLmath.PR ·2026-09-16 ·Marcus M. Noack, Maher B. Alghalayini, Mark D. Risser
similarity 0.56
Abstract

Kernel methods, and Gaussian Processes (GPs) in particular, require a Hilbertian distance measure---one whose square is conditionally negative definite (CND)---to guarantee positive semi-definiteness (PSD) of the kernel matrix; a condition that fails for many natural input spaces, including smooth manifolds and spaces of probability distributions. We propose the Sparse Landmark Embedding (SLE) kernel, which eliminates this requirement entirely. Each input is embedded into a sparse feature vector via compactly supported bump functions centered at all |D| training points; applying any standard PSD kernel in this embedding space yields a kernel that is provably PSD for arbitrary distance measures. The compact support automatically controls embedding sparsity, keeping kernel matrices well-conditioned and computationally tractable despite the high ambient dimension. We provide theoretical guarantees on PSD, sparsity, stability, and universal approximation, and show that the SLE kernel matches or substantially exceeds domain-specific baselines in both predictive accuracy and uncertainty quantification using geodesic and Wasserstein distances.

0.18

Learning Kernels by Alignment for Multiclass Bayes Classification

cs.LG ·2026-09-06 ·Hollan Haule, Javier Escudero
similarity 0.56
Abstract

Kernel methods separate data representation from decision-making, but typically require the kernel to be chosen in advance. We show that this kernel can instead be learned by alignment, and develop the resulting framework through the recently introduced Collaborative Learning and Inference (CLaI). We show that Collaborative Learning can be viewed as a kernel alignment process, in which an embedding is trained so that its induced similarity matches a label-derived target kernel. We also prove that Collaborative Inference is equivalent to kernel Bayes classification with Parzen-window density estimation. Motivated by these perspectives, we generalise CLaI by replacing cosine similarity with a learned Mahalanobis distance and extend it to multiclass classification. On CIFAR-10, PathMNIST, and SleepEDF, the Mahalanobis formulation improves accuracy, converges faster, and yields lower calibration error than the cosine-based variant. Auxiliary experiments further support these connections, showing that CLaI produces latent signals of the same form as a Gaussian process, while achieving competitive calibration on sepsis prediction. Together, these results establish a principled learned-kernel framework that unifies representation learning, kernel alignment, and Bayesian classification, and extends naturally to the multiclass setting.

0.23

Is High Local Accuracy Enough? Geometric Consensus with Support-Adaptive Statistical Personalization for Federated Learning

cs.LG ·2026-10-22 ·Junyu Lin, Bosong Qi, Pengcheng Shi, Jiayuan Li
code/data similarity 0.56
Abstract · 27 pages, including 9 pages of supplementary material. Code: https://github.com/JL181/FedGRC-Benchmark

Real-world deployment of personalized federated learning (PFL) requires adapting to heterogeneous clients while preserving recognition performance beyond local distributions. However, high local accuracy can conceal failures on locally rare or absent classes. Effective personalization should therefore strengthen global recognition while raising the personalization floor. We propose an evaluation protocol that complements local accuracy with global, rare-class, and unseen-class evaluations to reveal generalization obscured by local scores, and assesses personalization floors among the worst-performing clients to expose weaknesses hidden by aggregate performance. To meet these deployment challenges, we propose FedGRC, a unified PFL framework integrating generalization and personalization through (i) Consensus-Guided Representation Learning (CGRL), which learns discriminative representations through shared directional and magnitude guidance; (ii) Multilayer Metric Synthesis (MMS), which constructs a shared covariance metric from these multilayer representations for statistical classification; and (iii) Support-Adaptive Shrinkage Personalization (SASP), which adapts class means within this metric by shrinking local estimates toward shared means according to local sample support, enabling adaptation while retaining shared knowledge. Extensive experiments, including benchmarking against 21 methods across 5 heterogeneity settings on 3 datasets and comprehensive ablation studies, validate the effectiveness of FedGRC. On CIFAR-10 and CIFAR-100, FedGRC surpasses state-of-the-art (SOTA) baselines in global recognition and personalization floors by at least 2.17% and 2.13%, respectively. On the real-world heterogeneous FedRS dataset, it outperforms the respective best baselines by 2.15%, 3.30%, and 4.61% in local adaptation, global recognition, and the personalization floor.

0.22

Explaining f-Divergence-Based Regularization via Local Curvature and Sharpness-Aware Minimization

cs.LG cs.IT ·2026-09-08 ·Nour Jamoussi, Marios Kountouris
publishedbenchmark similarity 0.56
Abstract · Published at 5th Conference on Lifelong Learning Agents (CoLLAs), 2026

Divergence-based regularization and Sharpness-Aware Minimization (SAM) are two prominent approaches for improving generalization in deep learning, both motivated by robustness to perturbations. However, their relationship has remained largely unexplored. Building on classical second-order expansions of $f$-divergences, we show that the two methods are locally consistent under parameter-space perturbations: both induce curvature-sensitive penalties, with divergence regularization yielding a Fisher-weighted quadratic form and SAM penalizing sharpness through the dominant Hessian eigenvalue. For negative log-likelihood objectives with exponential-family output distributions, this correspondence becomes especially transparent, since the Fisher and Gauss-Newton matrices coincide. We further show that the same local geometric perspective extends to input-space perturbations, where divergence-based regularization is defined through transformations of the input. In this setting, the regularizer induces a pullback quadratic form on the input space, providing a more general perturbation framework than standard SAM while preserving the same local sensitivity interpretation. To validate the analysis empirically, we use the asymmetric $α$-skew Jensen-Shannon divergence (JSD) family as a controlled testbed. Its local curvature coefficient scales as $α(1-α)$ and is maximized at the symmetric point $α=\tfrac12$, which recovers the standard JSD. Loss-landscape visualizations in the input-perturbation regime show that stronger induced curvature penalization is associated with flatter local minima. Experiments on four benchmark datasets further demonstrate that both accuracy and negative log-likelihood are consistently best near this regime of maximal curvature penalization.

0.57

Adaptive conformal prediction on the Grassmannian

cs.LG stat.ML ·2026-10-16 ·Dimitrios Loukrezis, Zachary J. Grey, Dimitris G. Giovanis
similarity 0.55
Abstract · 21 pages, 6 figures, 3 tables

We introduce a conformal prediction framework for regression with Grassmann-valued responses. The proposed method constructs prediction regions in the form of metric balls directly on the Grassmann manifold, using basis-invariant geometric distances as non-conformity measures and scaling the corresponding non-conformity scores through a learned prediction difficulty estimator. This yields locally adaptive, input-dependent prediction regions that respect the underlying manifold geometry, while retaining the finite-sample marginal coverage guarantee of split conformal prediction under exchangeability. We evaluate several Grassmannian distance metrics and compare their prediction-region efficiency on synthetic benchmarks and an airfoil inverse shape-design problem. The results highlight the advantages of geometry-aware non-conformity scores, while local adaptation improves empirical coverage uniformity across prediction difficulty levels and, in strongly heteroscedastic settings, can substantially reduce prediction-region size while maintaining the target coverage.

0.20