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

Introduction

The $k$-nearest neighbour ($k$-NN) rule [3] classifies a point by looking at its closest training examples, so its behaviour is entirely determined by the notion of closeness. The Euclidean distance treats all features alike. The Mahalanobis distance [19] rescales and decorrelates them using the global covariance. Metric learning goes further and fits a Mahalanobis matrix to the labels: from side information [29], by maximising a stochastic leave-one-out score (NCA, [12], with large-margin constraints (LMNN, [27]) or with an information-theoretic regulariser (ITML, [4]); see Bellet et al. [2], Kulis [17] for surveys.

All these metrics are global. They apply a single linear geometry to the entire input space, yet in real data the relevant features, their correlations and the noise level can depend on the region. A feature that separates two classes in one part of the space may be pure noise elsewhere. Locally adaptive rules address this. DANN [13] and the method of Domeniconi et al. [11] reshape the neighbourhood of each query from local statistics. Multi-metric LMNN [27] learns one metric per class or cluster. Parametric local metric learning (PLML, [26]) combines basis metrics anchored in the input space with manifold regularisation. Adaptive neighbourhood sizes form a related line of work [18, 20].

Question. Can we learn, jointly, a local metric field, its smoothness and its robustness, while keeping the complexity of the learned object under explicit mathematical control? And does local adaptivity actually help on standard benchmarks once every competitor is tuned with the same care? We study these questions with an evolutionary approach. The optimisation problem combines non-convex, non-differentiable-looking terms (margins, minima over training points) with box constraints, and a GA handles it without gradients.

Contributions.

1. Model. We introduce a family of local metrics $M_\theta(x) = D_\theta(x) + UU^\mathsf{T} + \epsilon I$ generated by $D = Rp + pq$ parameters, with $R$ anchors and rank $q$, independent of the sample size $n$. The family contains the Euclidean metric, global diagonal metrics ($R = 1$) and global low-rank corrections (§ 3).

2. Algorithm. EAML evolves these parameters with an elitist real-coded GA [6, 7]. Its fitness is a continuous scalarisation of four objectives: classification, robustness, smoothness and complexity (§ 3).

3. Theory. We prove positivity and metric equivalence, existence of an optimal metric, Lipschitz regularity of the metric field, robustness of $k$-NN decisions to perturbations, a uniform generalisation bound and the almost-sure convergence in value of the GA (§ 4).

4. Evidence. We compare EAML with seven baselines (Euclidean, Manhattan, Mahalanobis, NCA, LMNN, ITML and an evolved global diagonal metric) on a controlled problem and on thirteen datasets, including a Fashion-MNIST subsample [28], with nested $5 \times5$-fold cross-validation, noise-robustness tests and ablations (§ 5). We report where the local model helps and where it does not.

Related work

Global metric learning. Most supervised metric learning methods learn a single positive semi-definite matrix $M$ such that $d_M(x,z)^2 = (x-z)^\mathsf{T}M(x-z)$ brings same-class points together. Xing et al. [29] posed it as a convex problem with pairwise constraints. NCA [12] maximises the expected LOO accuracy of a stochastic neighbour rule, which is the classification term we also use. LMNN [27] enforces large margins between target neighbours and impostors. ITML [4] regularises $M$ towards a prior with a LogDet divergence. Generalisation guarantees for metric learning have been derived through algorithmic robustness [1].

Local metrics and adaptive neighbourhoods. DANN [13] and ADAMENN [11] estimate a query-specific metric from local class statistics. Multi-metric LMNN [27] assigns one metric per cluster. PLML [26] expresses each local metric as a combination of anchored basis metrics with smooth weights, and our gating construction is close in spirit. Closely related are methods that adapt the neighbourhood size rather than its shape, for instance with neural networks [20] or with curvature estimates of the data manifold [18].

Evolutionary metric and feature weighting. GAs were used early on to learn feature weights for $k$-NN [15], and later for joint feature selection, weighting and extraction [23]. These approaches evolve a global diagonal metric, which corresponds to our GA-GLOBAL baseline ($R = 1$, $q = 0$). Multi-objective evolutionary algorithms such as NSGA-II [8] return Pareto fronts. We use a scalarisation instead and leave the Pareto analysis for future work. Our GA analysis follows the classical argument for elitist algorithms [24].

The EAML model and algorithm

A parametric family of local metrics

Let $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{n} \subset\mathbb{R}^{p} \times\{1, \ldots, C\}$, with standardised features. We choose $R$ anchors $c_1, \ldots, c_R$ (the $k$-means centres of the training fold) and the gating

where $\tau$ is the median squared distance from a training point to its closest anchor. Each anchor carries a vector of log-scales $s_r \in[-B, B]^p$. The local log-scale field and the local metric are

with $U \in[-B_U, B_U]^{p \times q}$. This is the factorisation $M_\theta= L_\theta L_\theta^\top+ \epsilon I$ with $L_\theta(x) = [D_\theta(x)^{1/2}, U]$. The distance from a query $x$ to a reference point $z$ uses the metric of the query:

The genome is $\theta= (s_1, \ldots, s_R, U)$, of dimension $D = Rp + pq$. The case $R = 1$, $q = 0$ is a global diagonal metric, and $\theta= 0$ gives the Euclidean metric (up to the factor $1 + \epsilon$).

Objective

Let $S \subseteq\{1, \ldots, n\}$ be the query points used in the fitness: all points, or a random subset of size $s = 800$ when $n > 800$. We minimise

with the following four terms.

• Classification (stochastic-neighbour LOO error, as in NCA):

Algorithm 1: EAML: Evolutionary Adaptive Metric Learning

Input: standardised training set $\mathcal{D}$; anchors $R$; rank $q$; weights $\lambda_{1:3}$; GA settings Output: metric parameters $\hat{\theta}$ and number of neighbours $\hat{k}$

1. Compute $R$ anchors by $k$-means, the temperature $\tau$ and the gating $\pi(x_i)$;

2. Select the query set $S$ and the Euclidean 5-NN graph of $S$;

3. Initialise the population with $\theta= 0$ (Euclidean) and small random genomes;

4. for $g = 1,\ldots,G$ do

   5. Tournament selection; SBX crossover; annealed Gaussian mutation; reflection into $\Theta$;

   6. Evaluate $\mathcal{J}(\theta)$ for every offspring (two matrix products of size $|S| \times p \times n$);

   7. Elitist replacement;

   8. if no improvement during 15 generations then break;

5. $\hat{\theta} \leftarrow$ best genome; $\hat{k} \leftarrow\arg\max_k$ LOO accuracy of $k$-NN under $d_{\hat{\theta}}$;

6. Prediction for $x$: compute $\pi(x)$, $M_{\hat{\theta}}(x)$, the distances $d_{\hat{\theta}}(x,x_j)$, and return the majority label of the $\hat{k}$ nearest neighbours.

• Robustness (relative margin hinge): with $d_i^{h}$ and $d_i^{m}$ the distances from $x_i$ to its nearest same-class and other-class training points, and $\rho_i = (d_i^{m} - d_i^{h})/(d_i^{m} + d_i^{h})$, we set $\mathcal{L}_{\mathrm{rob}} = \frac{1}{|S|}\sum_i \max(0,\bar{\rho} - \rho_i)/\bar{\rho}$ with target $\bar{\rho} = 0.2$. Theorem 4 links these margins to decision stability.

• Smoothness of the metric field on the Euclidean 5-NN graph of $S$:

• Complexity (shrinkage towards the Euclidean metric): $\mathcal{C} = \frac{1}{R_pB^2}\sum_r \lVert s_r\rVert^2 + \frac{1}{pqB_U^2}\lVert U\rVert_F^2$.

We use $\lambda_1 = 0.5$, $\lambda_2 = 0.1$ and $\lambda_3 = 0.01$ on every dataset. All terms are continuous in $\theta$, which is what Theorems 2 and 6 require.

Genetic search

Algorithm 1 summarises the method. The GA uses a population of 30 genomes and 40 generations, i.e. at most 1230 objective evaluations. Selection is by tournament of size 3. Simulated binary crossover [6, 7] is applied with probability 0.9 and index 15. Mutation is Gaussian with per-gene probability 0.1 (at least one gene per offspring) and a step that anneals from 0.25 to 0.02 of the box width. Offspring are reflected into the box $\Theta$. The two best parents survive, and the run stops early after 15 generations without improvement. The initial population contains the Euclidean genome $\theta= 0$ and 29 genomes drawn uniformly in $[-0.05, 0.05]$ times the box. After evolution, the number of neighbours $k \in\{1,\ldots,25\}$ is chosen by LOO accuracy of the $k$-NN rule under the learned metric, exactly as for all baselines.

Theoretical analysis

Throughout this section the training sample, the anchors $c_r$ and the gating temperature $\tau$ are fixed. We assume the following.

Assumption 1. The (standardised) inputs lie in the ball $\mathcal{X} = \{x : \lVert x\rVert_2 \le\varrho\}$, the anchors satisfy $\lVert c_r\rVert_2 \le\varrho$, and the genome lies in the box $\Theta= [-B,B]^{Rp} \times[-B_U,B_U]^{pq}$.

All proofs are given in Section A.

Positivity and existence

The continuity of $\mathcal{J}$ is the reason why we use the stochastic neighbour error instead of the 0–1 error of the $k$-NN rule: the latter is piecewise constant in $\theta$ and need not attain its infimum.

Regularity of the metric field

Small temperatures $\tau$ (sharp gating) and large log-scales $B$ allow the metric to change quickly; the smoothness penalty $\mathcal{L}_{\mathrm{sm}}$ controls the same quantity empirically on the training graph.

Robustness to perturbations

The theorem explains the role of the robustness term: $\mathcal{L}_{\mathrm{rob}}$ enlarges the relative hit/miss margins on the training points, while $\kappa$, controlled by $B$, $B_{U}$, $\epsilon$ and the gating, bounds how fast distances can move.

Generalisation

Let $\ell_{\theta}(x,y)=1-\sum_{j:y_{j}=y}p_{j}(x;\theta)$ with $p_{j}(x;\theta)\propto\exp(-d_{\theta}^{2}(x,x_{j}))$ over the training points: this is the probability of error of the stochastic neighbour rule, whose empirical LOO version is $\mathcal{L}_{\mathrm{cls}}$. Write $R(\theta)=\mathbb{E}\,\ell_{\theta}(X,Y)$ and $\widehat{R}_{m}(\theta)$ for its average on an i.i.d. sample of size $m$ independent of the training sample.

Convergence of the evolutionary search

The result is asymptotic: $\varepsilon_\eta$ can be extremely small when $D$ is large, so it guarantees that the search cannot stall at a non-optimal value forever, not that a finite budget suffices. We measure the finite-budget behaviour empirically in § 5.

Experiments

Setup

Datasets. We use thirteen public datasets (Table 1). Iris, Wine, Breast cancer and Digits ship with scikit-learn [22]; eight others come from the UCI repository [16]. Fashion-MNIST [28] is represented by a stratified subsample of 3000 test images. For this dataset the pixels are standardised and reduced to 40 principal components inside each training fold.

Dataset	$n$	$p$	$C$	Imb. ratio
Fashion-MNIST	3000	$783 \to40$	10	1.0
Digits	1797	61	10	1.1
Iris	150	4	3	1.0
Wine	178	13	3	1.5
Breast cancer	569	30	2	1.7
Sonar	208	60	2	1.1
Ionosphere	351	33	2	1.8
Pima	768	8	2	1.9
Glass	214	9	6	8.4
Seeds	210	7	3	1.0
Banknote	1372	4	2	1.2
Haberman	306	3	2	2.8
Ecoli	336	7	8	71.5

Methods. All methods use the same $k$-NN rule, with $k$ chosen by LOO accuracy on the training fold among $\{1,\ldots,25\}$, so they differ only in the metric. The baselines are: Euclidean; Manhattan; Mahalanobis (regularised inverse covariance); NCA [12] (scikit-learn, 100 iterations); LMNN [27] and ITML [4] (metric-learn, 5, default settings, 3 target neighbours and 200 iterations for LMNN); and GA-global, which is EAML with $R = 1$ and $q = 0$, i.e. an evolved global diagonal metric in the spirit of Kelly and Davis [15], Raymer et al. [23]. EAML uses $R = 4$, $q = 2$, $B = 3$, $B_U = 1$ and $\epsilon= 10^{-2}$. These values were fixed before running the benchmark and are identical for all datasets. LMNN could not be run on any Ecoli fold, because metric-learn rejects classes with fewer training points than target neighbours, and ITML failed on one Haberman fold. In these cases the method falls back to its initial (Euclidean) metric, so on Ecoli LMNN coincides with the Euclidean baseline.

Protocol. We use $5\times$ repeated stratified 5-fold cross-validation (25 splits per dataset, 325 in total). All preprocessing, metric learning and the choice of $k$ take place inside the training fold [25]. Besides accuracy and macro-F1, we measure robustness by adding Gaussian noise $\mathcal{N}(0,\sigma^2 I)$, $\sigma\in\{0.25,0.5\}$, to the standardised test points. Across datasets we use the Friedman test, the Nemenyi critical difference and Wilcoxon signed-rank tests with Holm correction [9, 10]. Within a dataset we use the corrected resampled $t$-test of Nadeau and Bengio [21]. Ablations are run on the first repetition (5 splits) of the eleven datasets other than Digits and Fashion-MNIST, for which five additional EAML runs per split were too costly.

Controlled study: a region-dependent relevant feature

We draw $x \in[-1,1]^{3+m}$ uniformly. The coordinate $x_0$ selects a region, and the label is $y = \mathbf{1}[\sin(2\pi x_1) > 0]$ if $x_0 < 0$ and $y = \mathbf{1}[\sin(2\pi x_2) > 0]$ otherwise. The other $m \in\{0,4,8\}$ coordinates are nuisance features. A global metric has to keep both $x_1$ and $x_2$; a local metric can drop the irrelevant one in each region. We train on 800 points, test on 3000, and repeat 10 times.

Without nuisance features (Table 2, Figure 1), EAML learns what the problem requires. On the left it gives $x_1$ a weight about 2.3 times that of $x_2$, and on the right the ratio is reversed. It is the most accurate method (93.2% against 91.4% for GA-global, $p = 0.002$). With nuisance features the order changes: GA-global stays above 90%, whereas EAML falls to 88.2% and 83.1% (both $p = 0.002$ in favour of GA-global). The learned weights show why. With 4 or 8 nuisance features, the weights of $x_1$ and $x_2$ no longer swap between the regions. The $k$-means anchors are computed in the full noisy space, so they do not align with the region boundary $x_0 = 0$. The genome also grows with the dimension ($D = Rp + pq$) while the evaluation budget does not. Global metric learners that ignore nuisance features (Euclidean, LMNN) collapse to about 59%, and NCA degrades to 75%.

$m$	Euclidean	NCA	LMNN	GA-global	EAML	$p$	left $x_1/x_2$	right $x_1/x_2$
0	90.95	89.91	90.90	91.40	93.22	0.002	13.95/5.95	5.20/14.99
4	64.91	86.51	66.14	91.46	88.23	0.002	11.49/12.42	10.14/13.32
8	58.47	75.34	58.94	90.43	83.12	0.002	10.17/10.88	9.70/11.04

Vector (PDF)

Dataset	Euclidean	Manhattan	Mahalanobis	NCA	LMNN	ITML	GA-global	EAML
Fashion-MNIST	80.2 ± 1.3	80.3 ± 1.3	80.2 ± 1.3	76.6 ± 1.7	80.8 ± 1.0	80.5 ± 1.1	79.8 ± 1.1	79.9 ± 1.4
Digits	97.6 ± 0.5	98.0 ± 0.6	95.6 ± 1.2	97.8 ± 0.6	98.0 ± 0.7	98.0 ± 0.8	97.7 ± 0.9	97.5 ± 0.7
Iris	96.3 ± 3.5	94.5 ± 4.1	90.3 ± 4.5	95.9 ± 3.9	96.3 ± 3.5	96.9 ± 2.5	94.5 ± 3.6	94.5 ± 4.4
Wine	96.3 ± 2.5	97.2 ± 2.3	93.5 ± 3.4	96.6 ± 2.9	96.4 ± 3.3	98.3 ± 2.3	95.7 ± 2.8	97.4 ± 2.9
Breast cancer	96.6 ± 1.5	96.7 ± 1.8	84.0 ± 2.7	95.3 ± 1.4	96.7 ± 1.5	95.5 ± 1.7	95.1 ± 1.6	96.3 ± 1.6
Sonar	84.9 ± 5.1	85.2 ± 5.2	76.5 ± 5.6	86.7 ± 3.9	87.3 ± 4.7	78.3 ± 4.8	85.0 ± 6.4	84.6 ± 6.2
Ionosphere	85.7 ± 3.7	90.6 ± 3.1	85.5 ± 3.8	89.2 ± 3.1	87.3 ± 3.5	88.1 ± 2.7	90.0 ± 3.1	90.3 ± 2.8↑
Pima	75.0 ± 3.0	75.0 ± 2.8	73.6 ± 3.5	69.0 ± 3.9	74.9 ± 3.5	75.7 ± 3.7	76.1 ± 3.3	73.6 ± 3.5
Glass	69.8 ± 5.6	71.6 ± 6.0	66.0 ± 5.5	71.1 ± 5.3	69.2 ± 6.1	61.0 ± 5.9	77.4 ± 5.3	76.8 ± 5.4↑
Seeds	92.5 ± 3.7	92.3 ± 3.2	94.3 ± 3.3	93.2 ± 3.7	92.5 ± 3.8	95.8 ± 2.9	93.0 ± 2.9	91.7 ± 3.5
Banknote	99.8 ± 0.3	99.9 ± 0.2	100.0 ± 0.0	100.0 ± 0.0	99.8 ± 0.3	100.0 ± 0.0	99.8 ± 0.3	99.9 ± 0.3
Haberman	74.8 ± 3.7	74.4 ± 3.6	75.0 ± 4.1	71.0 ± 6.3	74.8 ± 3.5	74.4 ± 3.4	74.6 ± 4.3	73.2 ± 3.8
Ecoli	86.3 ± 3.6	85.2 ± 3.2	85.9 ± 3.5	74.0 ± 14.4	86.3 ± 3.6	85.9 ± 3.5	84.8 ± 4.2	84.6 ± 3.4
Mean acc.	87.37	87.76	84.65	85.88	87.72	86.80	87.98	87.72
Mean rank	4.65	3.65	5.69	5.00	3.54	3.46	4.77	5.23

Baseline	W/T/L	$p$	$p_{\mathrm{Holm}}$	sig. better/worse
Euclidean	4/0/9	0.414	1.000	2/0
Manhattan	3/1/9	0.062	0.438	0/0
Mahalanobis	7/0/6	0.110	0.659	4/0
NCA	8/0/5	0.146	0.732	2/0
LMNN	4/0/9	0.376	1.000	2/0
ITML	4/0/9	0.635	1.000	1/1
GA-global	5/1/7	0.395	1.000	0/0

Benchmark results

Tables 3 and 4 summarise the benchmark. Overall, no method stands out: the Friedman test does not reject equal performance ($\chi^2_F = 11.0$, $p = 0.14$). ITML (3.46), LMNN (3.54) and Manhattan (3.65) have the best mean ranks. GA-global has the highest mean accuracy (87.98%) but a middle rank (4.77). EAML ranks 5.23, with a mean accuracy of 87.72%. The differences between EAML and every baseline are not significant across datasets (all Holm-adjusted $p \ge0.44$).

The local model helps on two datasets. On Glass, EAML improves on the Euclidean metric by 7.0 points (76.8% vs. 69.8%), and on Ionosphere by 4.6 points; both differences are significant. On these datasets the global evolved metric does about as well (77.4% and 90.0%), so the gain mainly comes from evolving feature weights rather than from locality. Elsewhere EAML loses up to 1.7 points to the Euclidean metric (Iris, Ecoli, Haberman, Pima), although no loss is significant.

Robustness. Table 5 and Figure 2 show that the robustness term does not translate into better robustness to test-time noise. At $\sigma= 0.5$, EAML loses 5.8 points on average, against 3.8 for the Euclidean metric and 4.1 for LMNN. It nevertheless degrades less than GA-GLOBAL (6.4),

Vector (PDF)

	Euclidean	Manhattan	Mahalanobis	NCA	LMNN	ITML	GA-global	EAML
Mean acc., $\sigma= 0$	87.37	87.76	84.65	85.88	87.72	86.80	87.98	87.72
Mean rank, $\sigma= 0$	4.65	3.65	5.69	5.00	3.54	3.46	4.77	5.23
Mean acc., $\sigma= 0.25$	86.08	86.54	77.71	83.46	86.22	84.24	85.80	86.02
Mean rank, $\sigma= 0.25$	3.77	2.69	6.54	5.96	2.92	5.04	4.54	4.54
Mean acc., $\sigma= 0.5$	83.57	83.49	70.31	79.39	83.62	78.44	81.57	81.93
Mean rank, $\sigma= 0.5$	2.19	2.69	6.77	6.00	2.42	6.27	4.88	4.77
Mean drop at $\sigma= 0.5$	3.80	4.27	14.34	6.49	4.10	8.36	6.41	5.79

NCA (6.5), ITML (8.4) and Mahalanobis (14.3). The main reason is that the learned metrics are sharp: the stochastic-neighbour term rewards metrics under which the nearest same-class point dominates. As a result, EAML and GA-global select $k = 1$ in most folds (median $k = 1$, as for NCA, against 4 to 6 for the other metrics, Table 6), and the 1-NN rule is the most sensitive to noise. This is consistent with Theorem 4: the guarantee depends on the hit/miss margin relative to $\kappa$, a ratio that a mere rescaling of $M_\theta$ leaves unchanged, so sharper metrics do not buy robustness by themselves.

	Euclidean	Manhattan	Mahalanobis	NCA	LMNN	ITML	GA-global	EAML
Macro-F1 (mean)	84.04	84.25	80.86	82.41	84.40	82.86	84.91	84.28
Macro-F1 (rank)	4.69	3.92	6.00	5.00	3.54	3.46	4.46	4.92
Fit time, median over datasets (s)	0.00	0.00	0.00	0.09	0.51	0.25	3.62	3.93
Fit time, Fashion-MNIST (s)	0.2	0.1	0.1	22.7	9.1	29.7	162.2	171.1
Median selected $k$	6	5	4	1	6	6	1	1

Cost. The median training time of EAML is 3.9 s per fold, against less than 0.6 s for NCA, LMNN and ITML. On the largest problem (Fashion-MNIST, 2400 training points, 40 dimensions) it takes 171 s, against 9–30 s for the gradient-based learners.

Search behaviour

The GA reduces the training objective to 0.58 times its Euclidean value on average, from 0.08 on Banknote to 0.89 on Haberman. However, every run used all 40 generations without triggering the stagnation stop, and the curves in Figure 3 are still decreasing at the end. The search budget is therefore binding. This is consistent with the asymptotic nature of Theorem 6: almost-sure convergence in value says nothing about the speed at which a 366-dimensional genome (Digits) is optimised with 1230 evaluations.

Vector (PDF)

Variant	Acc.	Rank	Acc. $\sigma=0.5$	$\mathcal{J}/\mathcal{J}_{\mathrm{Eucl}}$	$\mathcal{L}_{\mathrm{cls}}$	$\mathcal{L}_{\mathrm{rob}}$	Time
EAML	87.95	2.88	81.70	0.577	0.114	0.293	3.8
EAML (no robustness)	87.25	4.14	81.16	0.477	0.113	0.332	3.3
EAML (no smoothness)	88.33	2.50	81.48	0.543	0.117	0.289	2.9
EAML (no low-rank, $q=0$)	87.97	3.95	80.34	0.565	0.119	0.299	3.2
EAML (random search)	87.31	3.23	80.69	0.684	0.138	0.331	1.9
EAML (NCA term only)	87.55	3.95	81.53	0.442	0.113	0.331	3.1

Ablation study

Table 7 isolates the design choices. The numbers in the $\mathcal{J}$ column are not comparable across rows when the objective itself differs.

• Robustness term. Removing it lowers accuracy (87.25% vs. 87.95%) and the noisy accuracy (81.16% vs. 81.70%), and gives the worst rank. This is the only term whose removal clearly hurts.

• Smoothness term. Removing it slightly improves accuracy (88.33%, best rank), so with our default weight the smoothness prior is too strong for these datasets.

• Low-rank term. With $q=0$ the clean accuracy is unchanged but the noisy accuracy drops by 1.4 points.

• Search. Random search with the same budget reaches a worse objective (0.68 vs. 0.58 of the Euclidean value) and a lower accuracy (87.31%). The genetic operators do matter.

• NCA term only. Optimising only $\mathcal{L}_{\mathrm{cls}}$ lowers accuracy by 0.4 points.

Learned geometry. Figure 4 shows the anchor log-scales learned on Glass, the dataset where EAML gains most. The anchors disagree substantially. For example, the refractive index (RI) and potassium (K) are strongly up-weighted near anchor 1 and down-weighted near anchor 4. This confirms that the model does use its local degrees of freedom when the data allow it.

Vector (PDF)

Discussion and limitations

When do local metrics pay off? Locality helps when (i) the relevant directions genuinely change across the space and (ii) the gating can see the regions. The controlled study meets both conditions without nuisance features, and EAML then outperforms every global metric. When nuisance dimensions blur the unsupervised gating, or when the data are close to homogeneous, the additional degrees of freedom cost more search effort and variance than they bring. A global evolved metric is then preferable. On the thirteen benchmarks, no metric learner, global or local, significantly beats the others, which is a useful reminder that careful nested evaluation of metric learning often yields small differences.

Limitations. (i) The search budget is binding (Figure 3). Our convergence theorem is asymptotic and does not bound the number of generations. (ii) The anchors are unsupervised; supervised or evolved anchors, or a gating on the learned metric itself, are natural fixes for the misalignment observed with nuisance features. (iii) The stochastic-neighbour term produces sharp metrics and $k = 1$, which hurts robustness. A temperature or margin constraint on the scale of $M$ would counter this. (iv) The generalisation bound concerns the stochastic neighbour risk on an independent sample, not the LOO-selected majority vote. (v) The objective is a fixed scalarisation; a Pareto approach (e.g. NSGA-II, [8]) would expose the accuracy–robustness trade-off directly. (vi) Training is one to two orders of magnitude slower than gradient-based metric learners.

Future work. The results point to three concrete steps: a larger or adaptive evaluation budget with warm starts from GA-GLOBAL; supervised placement of anchors; and multi-objective evolution of local metrics, with the theory above applied to each Pareto-optimal solution.

Conclusion

We introduced EAML, an evolutionary framework that learns a field of local Mahalanobis metrics from a small set of generating parameters, under a continuous multi-objective criterion. The framework comes with guarantees on positivity, existence, regularity, robustness, generalisation and convergence in value of the search. Experiments show that local metrics recover region-dependent geometry when it exists and the regions are identifiable. On standard benchmarks their benefit is confined to a few datasets and does not survive nuisance features or test-time noise, where a global evolved metric is more reliable. These positive and negative findings delimit the regime in which evolutionary local metric learning is worth its cost.

Code and data availability. The Python implementation of EAML, the baselines and the scripts that reproduce every table and figure of this paper are available from the corresponding author upon request. All datasets used in this study are publicly available (Table 1).

Proofs

Proof of Theorem 1. $D_\theta(x)$ is diagonal with entries $e^{h_j(x)}>0$, and $UU^\top\succeq0$, so $M_\theta(x) \succeq\epsilon I$. Since $h_\theta(x)$ is a convex combination of vectors in $[-B,B]^p$, every entry of $D_\theta(x)$ is at most $e^B$. Moreover $\lVert UU^\top\rVert_{\mathrm{op}}=\lVert U\rVert_{\mathrm{op}}^2\leq\lVert U\rVert_F^2\leq pqB_U^2$. Hence $M_\theta(x)\preceq\Lambda I$. For fixed $x$, $z\mapsto\lVert M_\theta(x)^{1/2}(x-z)\rVert_2$ is a norm of $x-z$, and the two-sided bound follows from the eigenvalue bounds.

Proof of Theorem 2. For fixed $(i,j)$, $d^\theta(x_i,x_j)$ is a finite sum of products of exponentials and polynomials in $\theta$, hence continuous. $\mathcal{L}_{\mathrm{cls}}$ is a finite combination of $\log\sum\exp$ of these quantities, hence continuous. Each $d_i^h$ and $d_i^m$ is the square root of a minimum of finitely many continuous functions, hence continuous. (If a class has a single training point, $d_i^h$ is set to the constant $0$.) Since the implemented ratio $\rho_i$ has denominator $d_i^m+d_i^h+10^{-12}>0$, $\mathcal{L}_{\mathrm{rob}}$ is continuous. $\mathcal{L}_{\mathrm{sm}}$ and $C$ are polynomials in $\theta$ (the gating does not depend on $\theta$). Thus $\mathcal{J}$ is continuous on the compact box $\Theta$, and the Weierstrass theorem gives a minimiser.

Proof of Theorem 3. Write $a_r(x)=-\lVert x-c_r\rVert^2/\tau$ and $g_r=\nabla a_r=-2(x-c_r)/\tau$, so that $\lVert g_r\rVert\leq2(\lVert x\rVert+\lVert c_r\rVert)/\tau\leq4\varrho/\tau=G$. The softmax gives $\nabla\pi_r=\pi_r(g_r-\bar{g})$ with $\bar{g}=\sum_s\pi_sg_s$, hence $\lVert\nabla\pi_r\rVert\leq2G\pi_r$. Therefore $\lVert\nabla h_j\rVert\leq\sum_r\lvert s_{rj}\rvert\lVert\nabla\pi_r\rVert\leq2BG$, and by the mean value theorem on the convex set $\mathcal{X}$, $\lvert h_j(x)-h_j(x')\rvert\leq2BG\lVert x-x'\rVert$. Since $\lvert h_j\rvert\leq B$, $\lvert e^{h_j(x)}-e^{h_j(x')}\rvert\leq e^B\lvert h_j(x)-h_j(x')\rvert$. The terms $UU^\top$ and $\epsilon I$ do not depend on $x$, and the operator norm of a diagonal matrix is its largest absolute entry, which gives the claim.

Proof of Theorem 4. Let $x'=x+\delta$, $a=(x'-z)^\top M_\theta(x')(x'-z)$ and $b=(x'-z)^\top M_\theta(x)(x'-z)$. By the triangle inequality,

The second term is at most $\lVert\delta\rVert_{M_\theta(x)}\leq\sqrt{\Lambda}\lVert\delta\rVert$ (Theorem 1). For the first, $a,b\geq\epsilon\lVert x'-z\rVert^2$, so $\lvert\sqrt{a}-\sqrt{b}\rvert=\lvert a-b\rvert/(\sqrt{a}+\sqrt{b})\leq\lvert a-b\rvert/(2\sqrt{\epsilon}\lVert x'-z\rVert)$. By Theorem 3, $\lvert a-b\rvert\leq\operatorname{Lip}_M\lVert\delta\rVert\lVert x'-z\rVert^2$, so the first term is at most $\operatorname{Lip}_M\lVert\delta\rVert\lVert x'-z\rVert/(2\sqrt{\epsilon})\leq\operatorname{Lip}_M\varrho\lVert\delta\rVert/\sqrt{\epsilon}$, because $\lVert x'-z\rVert\leq2\varrho$. This proves the bound with $\kappa$. Every distance from the query to a training point therefore moves by at most $\kappa\lVert\delta\rVert$. If two such distances differ by more than $2\kappa\lVert\delta\rVert$, their order is preserved. Applied to the nearest hit and miss, this gives (i): applied to the $k$-th and $(k+1)$-th neighbours, it shows that the $k$-NN set, and hence the vote, is unchanged, which gives (ii).

Proof of Theorem 5. Lipschitz property in $\theta$. Fix $(x,y)$ and let $u_j=-d^\theta(x,x_j)$. Writing $P_S=\sum_{j\in S}p_j$ with $S=\{j:y_j=y\}$, we have $\partial P_S/\partial u_l=p_l(\mathbb{1}[l\in S]-P_S)$, so $\lVert\nabla_u\ell\rVert_1\leq\sum_l p_l=1$ and $\lvert\ell(u)-\ell(u')\rvert\leq\lVert u-u'\rVert_\infty$. Next, with $\Delta=x-x_j$ and $\lVert\Delta\rVert\leq2\varrho$, $\partial d^2/\partial s_{rf}=\pi_re^{h_f}\Delta_f^2$ and $\partial d^2/\partial U_{fl}=2\Delta_f(U^\top\Delta)_l$. Summing absolute values, $\sum_{r,f}\pi_re^{h_f}\Delta_f^2\leq e^B\lVert\Delta\rVert^2\leq4\varrho^2e^B$ and $\sum_{f,l}2\lvert\Delta_f\rvert\lvert(U^\top\Delta)_l\rvert\leq2pqB_U\lVert\Delta\rVert^2\leq8pqB_U\varrho^2$. Hence $\lVert\nabla_\theta d^2\rVert_1\leq L$, and for $\theta,\theta'\in\Theta$ (a convex set), $\lvert d_{\theta}^{2}-d_{\theta'}^{2}\rvert\leq L\lVert\theta-\theta'\rVert_\infty$. Combining both steps, $\lvert\ell_\theta(x,y)-\ell_{\theta'}(x,y)\rvert\leq L\lVert\theta-\theta'\rVert_\infty$ for all $(x,y)$, so the same holds for $R$ and $\widehat{R}_m$.

Covering and union bound. A grid with $\lceil\bar{B}L/\eta\rceil$ points per coordinate covers $\Theta$ within $\ell_\infty$-distance $\eta/L$, so it has $N\leq\lceil\bar{B}L/\eta\rceil^D$ points. Since $\ell\in[0,1]$, Hoeffding’s inequality [14] and a union bound give, with probability at least $1-\delta$, $\lvert R(\theta')-\widehat{R}_m(\theta')\rvert\leq\sqrt{\ln(2N/\delta)/(2m)}$ for all grid points $\theta'$. For any $\theta$, choosing the closest grid point changes $R$ and $\widehat{R}_m$ by at most $\eta$ each, which yields the bound.

Proof of Theorem 6. Monotonicity. The best parents enter the truncated merged population, so the best value never increases.

Hitting probability. Fix $\eta> 0$ and let $A_\eta= \{\theta\in\Theta: \mathcal{J}(\theta) < \mathcal{J}^{\star} + \eta\}$. By continuity (Theorem 2), $A_\eta$ is relatively open in $\Theta$ and contains a minimiser, so $\operatorname{Leb}(A_\eta) > 0$. Consider any offspring, with pre-mutation genome $\tilde{\theta} \in\Theta$. All $D$ genes are mutated with probability at least $0.1^{D-1}$: one gene is forced, and the others mutate independently with probability $0.1$. Conditionally on this, the offspring is the coordinate-wise reflection into $\Theta$ of $\tilde{\theta} + \sigma_g S \xi$, $\xi\sim\mathcal{N}(0, I_D)$, where $S$ holds the box widths $w_j$ and $\sigma_g \in[\sigma_{\min}, \sigma_0]$. Its density at any $t \in\Theta$ is at least that of the unreflected Gaussian. Since $\lvert t_j - \tilde{\theta}_j\rvert\le w_j$, this density is at least $c = \prod_j(\sqrt{2\pi}\sigma_0 w_j)^{-1}e^{-1/(2\sigma_{\min}^2)} > 0$. Hence each offspring lands in $A_\eta$ with probability at least $\varepsilon_\eta= 0.1^{D-1}c\operatorname{Leb}(A_\eta) > 0$, whatever the past. With at least one offspring per generation, $\mathbb{P}\{\mathcal{J}^{\mathrm{best}}_g \ge\mathcal{J}^{\star} + \eta\} \le(1-\varepsilon_\eta)^g$.

Almost-sure convergence. By Borel–Cantelli, $\mathcal{J}^{\mathrm{best}}_g < \mathcal{J}^{\star} + \eta$ eventually, almost surely, for each rational $\eta> 0$. Intersecting over these countably many events and using monotonicity gives $\mathcal{J}^{\mathrm{best}}_g \to\mathcal{J}^{\star}$ almost surely.

Proof of Theorems 7 and 8. For $\theta= 0$, $h_\theta\equiv0$, $D_\theta\equiv I$ and $U = 0$, so $M_\theta= (1+\epsilon)I$. The seed is evaluated at generation 0, and by monotonicity the returned genome satisfies $\mathcal{J}(\hat{\theta}) \le\mathcal{J}(0)$. For the cost, the squared distances are $d_{ij}^{2} = \sum_f E_{if}x_{if}^{2} - 2\sum_f E_{if}x_{if}x_{jf} + \sum_f E_{if}x_{jf}^{2} + \cdots$, with $E = e^{\Pi S}$. This requires the products $(E \circ X_S)X^{\mathsf{T}}$ and $E(X \circ X)^{\mathsf{T}}$ ($O(snp)$), the low-rank term ($O(snq)$), the gating products ($O(sRp)$) and row-wise reductions ($O(sn)$).

Hyper-parameters

Setting	Value	Setting	Value
anchors $R$, rank $q$	$4$, $2$	population, generations	$30$, $40$ (patience $15$)
bounds $B$, $B_U$	$3$, $1$	tournament size	$3$
$\epsilon$	$10^{-2}$	SBX probability, index	$0.9$, $15$
$\lambda_1,\lambda_2,\lambda_3$	$0.5$, $0.1$, $0.01$	mutation probability per gene	$0.1$
margin target $\bar{\rho}$	$0.2$	mutation step $\sigma_0 \to\sigma_{\min}$	$0.25 \to0.02$
query rows $s$	$\min(n,800)$	elites	$2$
$k$ search range	$\{1,\ldots,25\}$	smoothness graph	Euclidean 5-NN