acceptodds
Under review as a conference paper at ICLR 2027

On Metric Robustness, Generalization and Over-parameterization

Abstract

Metric learning has attracted significant attention since it can substantially improve the performance of subsequent tasks such as classification. Current theories of metric learning have mostly focused on the goodness of the learned metric, but how this metric affects subsequent classification performance remains an open problem. In this paper, we study the relationship between the generalization of metric learning and classification. Firstly, we introduce metric robustness of classification algorithms with respect to metrics, which quantifies the influence of metrics on classification performance. Secondly, we establish classification generalization guarantees through metric robustness for a range of commonly used metrics and classifiers. Thirdly, we prove that over-parameterization does not necessarily lead to overfitting for a class of distance metric learning methods, addressing an open problem that remains unresolved in the metric learning literature.

Primary area:
learning theory
Keywords:
Metric learning, Generalization, Over-parameterization, Overfitting, Algorithm robustness

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_SuQ8OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the generalization of metric learning, focusing on how learned metrics affect the generalization performance of downstream classifiers. The authors introduce metric robustness to characterize classification-loss variations within neighborhoods induced by the learned metric, and establish bounds on classification generalization and risk. They further analyze LogDet metric learning to investigate how increasing the number of pairwise constraints affects the classification-risk bound and generalization behavior. The paper also presents theoretical examples involving different metric-learning methods and classifiers to illustrate how metric regularization, classifier complexity, and decision margins influence the resulting guarantees.

Critical strengths
  1. A unified robustness-based framework for downstream classification generalization. The paper introduces metric robustness to connect the geometry induced by a learned metric with the generalization behavior of the resulting classifier. By establishing bounds on classification generalization and risk, the framework extends the analysis beyond the metric-learning objective itself and provides a common perspective for studying different metric-learning methods and downstream classifiers. This is a meaningful theoretical contribution to understanding when learned metrics can support reliable classification.
  2. A theoretically grounded analysis of generalization with increasing pairwise constraints. The paper studies LogDet metric learning and analyzes how the number of pairwise constraints affects classification-risk bounds, including the regime where the number of constraints grows quadratically with the number of training samples. By accounting for the dependence among pairwise constraints and identifying conditions under which the bounds improve, the analysis provides useful insight into the relationship between constraint coverage and downstream generalization. This aspect gives the theoretical framework a concrete application and strengthens the paper's overall value.
Critical weaknesses

None

Questions for authors
  1. Theoretical novelty and the distinction from existing robustness frameworks need to be clarified. The paper defines metric robustness as the variation of classification loss within neighborhoods induced by metric learning. This idea is reasonable, but it has strong connections to existing robustness-based generalization theories that rely on sample-space partitions and local loss variations. The authors are advised to clarify, at the theorem level, the substantive increment of this work compared with existing studies, especially the related work by Bellet and Habrard. Specifically, they should explain whether the proposed framework brings weaker assumptions, tighter generalization bounds, or broader applicability, and highlight its distinctive theoretical value through a comparison table and concrete corollaries, rather than merely applying an existing framework to classification losses after metric learning.

  2. The practical applicability and operability of the core generalization theorem still need further clarification. Theorem 3.5 decomposes the upper bound on the classification generalization gap into a metric robustness term and a sampling term related to partition complexity, and the theoretical structure is clear. However, the practical value of this framework depends not only on the validity of the theoretical bound, but also on whether the relevant terms can be reasonably estimated in practice and can provide guidance for model selection. Specifically, the theorem requires the partition to be fixed before observing the training sample and to satisfy label purity, while the granularity of the partition affects the tightness of the generalization bound. Moreover, although the paper provides several theoretical upper bounds for metric robustness, it has not sufficiently explained how practitioners can estimate or approximate metric robustness, or how to use it to select models or tune hyperparameters. Therefore, the authors are advised to add a brief conceptual discussion in the main text on possible ways to estimate metric robustness in practice and its potential role in model evaluation and hyperparameter selection, so as to further clarify the applicability conditions and practical value of the theoretical framework.

  3. The meaning and scope of “over-parameterization” require further clarification. In Section 4, the number of pairwise constraints m grows quadratically with the number of training samples n, but this does not necessarily imply a corresponding increase in the number of free model parameters. For a symmetric metric matrix of input dimension d, the number of free parameters is p=d(d+1)/2, which remains constant with respect to n when d is fixed. Moreover, pairwise constraints are constructed from the same set of training observations, so increasing their number does not amount to obtaining an equivalent number of independent new observations. The authors are therefore encouraged to clarify what “over-parameterization” specifically refers to in this work, distinguish between the number of pairwise constraints, the number of dual variables, and the model's parameter capacity, and carefully explain how their theoretical results relate to Zhou et al. (2021) on over-parameterization in deep neural networks. The title, abstract, and statement of contributions should also be reviewed, where necessary, to make the intended meaning and scope of the term more explicit and avoid interpretations that extend beyond what the theoretical results establish.

4 comments

We sincerely thank the reviewer for the generous appreciation and positive assessment of our paper! Your suggestions are very valuable to us. We have revised the manuscript accordingly and explain the specific changes below. We sincerely appreciate your help in making the contribution and scope of our work clearer!

Q1: ... The authors are advised to clarify, at the theorem level, the substantive increment of this work compared with existing studies, especially the related work by Bellet and Habrard. Specifically, they should explain whether the proposed framework brings weaker assumptions, tighter generalization bounds, or broader applicability, and highlight its distinctive theoretical value through a comparison table and concrete corollaries, rather than merely applying an existing framework to classification losses after metric learning.

A1: Thank you very much for recognizing the value of our framework and for this helpful suggestion! We have added an explicit comparison after Theorem 3.5 and expanded Section 5, now entitled "Related Work and Discussions," to explain the contribution and its relation to prior analyses. Here, we provide a further detailed explanation.

Our central contribution is to establish a general connection between metric learning and downstream classification generalization. To our knowledge, this is the first unified framework expressing this connection through the learned geometry and the classifier's response across different metric-classifier combinations. Earlier connections, such as Bellet et al. (2012), Guo and Ying (2014), and Nicolae et al. (2015), concern particular similarity-learning formulations and their associated linear or landmark classifiers.

Bellet and Habrard (2015) analyze generalization of the pairwise metric-learning loss. Our question goes further: how does learning this metric control the loss and generalization of the resultant classifier? Proposition 3.3 makes the distinction precise: empirical and population metric losses can both vanish while the classification generalization gap is maximal. Thus, a guarantee for the metric loss alone does not establish the required connection.

Metric robustness addresses this issue by combining two quantities: the learned metric determines the neighborhood radii, and the classifier determines the loss response within those neighborhoods. Theorem 3.5 converts their joint control into a classification guarantee. Applying algorithmic robustness to the composite classifier is possible, but does not itself derive these quantities from metric learning. Our examples supply this step through objective values, regularization, norms, and margins.

The same condition covers different metric-classifier combinations. Section 3.3 treats Mahalanobis and kernel metrics, several classifier constructions, and jointly trained neural representations. This connection has theoretical value independently of any improvement to the underlying robustness inequality.

For the same partition, sample size, and confidence level, write [ \tau_n=\sqrt{\frac{K\log 2+\log(1/\delta)}{2n}}. ] For classification loss in ([0,1]), use the same local bounds (c_i=\omega_i(a_i)). For pairwise loss in ([0,B_d]), let (c_{ij}\in[0,B_d]) be common bounds on loss variation within the corresponding product cells.

AnalysisLoss being controlledGeneralization-gap bound
Xu and Mannor (2012)Classificationmaxici+2τnmax_i c_i+2\tau_n
Our Theorem 3.5Classificationn−1∑ici+τnn^{-1}\sum_i c_i+\tau_n
Bellet and Habrard (2015)Pairwise metric lossmax⁡i,jcij+4Bdτn\max_{i,j}c_{ij}+4B_d\tau_n
Our Proposition D.1Pairwise metric lossn−2∑i,jcij+2Bdτnn^{-2}\sum_{i,j}c_{ij}+2B_d\tau_n

Under these matched conditions, our bounds retain average local variation and improve the sampling coefficient using total variation of cell masses. Averaging is already present at an intermediate step of Xu and Mannor's proof; our result retains it explicitly. The comparison refines their stated bounds using the same partition-based concentration principle.

The comparison does not assert universally weaker assumptions: the fixed-partition and bounded-loss conditions remain. Moreover, our learned-distance balls can extend beyond a partition cell, so their responses need not be smaller than the best cellwise constants.

The concrete consequences further explain the contribution. Corollary 3.6 controls the pairwise loss through the same learned geometry used in Theorem 3.5. Example 3.10 connects a metric-learning objective to classification risk, and Section 4 quantifies how pair coverage affects that risk guarantee. These results establish what must connect the two stages and how learning controls that connection.

Thank you very much for the detailed questions in Q2! We have organized your main suggestions into two parts: Part 1 concerns constructing and estimating the quantities in Theorem 3.5; Part 2 concerns using them for model evaluation and hyperparameter selection. We have revised the manuscript accordingly and respond to these two points below.

Q2 (Part 1): How can the quantities in Theorem 3.5 be constructed and estimated in practice, particularly the fixed, label-pure partition and metric robustness?

A2 (Part 1): Thank you very much for this helpful feedback! Your suggestion has guided us in making the practical use of the theorem more explicit. We have expanded Remark 3.4 to explain the partition construction, added computable bounds in Section 4.4, and provided the derivations and estimation conditions in Appendix B.8. Here, we give a further detailed explanation.

1. For the fixed, label-pure partition.

Label purity concerns a partition of the labeled space X×Y\mathcal{X}\times\mathcal{Y}. Given any finite measurable input partition V1,…,VNV_1,\ldots,V_N fixed before observing the training sample, we construct

Π={Vℓ×{y}:ℓ=1,…,N, y∈Y}.\Pi=\{V_\ell\times\{y\}:\ell=1,\ldots,N,\ y\in\mathcal{Y}\}.

Each cell then has one label by construction. Different labels may occur in the same input region; they belong to different cells of the labeled space. Thus, this construction allows noisy labels and requires no knowledge of the true decision boundary. It is an analysis device, and prediction does not require the test label.

For a bounded Euclidean input domain, one can use a predefined grid or a finite cover made disjoint by assigning each point to the first covering set containing it. The number of resulting labeled cells gives KK, so the sampling term is directly determined once the partition, sample size, and confidence level are specified.

The fixed-partition requirement does not require fixing the metric or classifier in advance. Both are learned from the sample; the radii and loss responses are then evaluated under these learned outputs. The input partition is fixed so that the cell-count concentration argument applies. Its construction alone does not guarantee a small robustness term: the learned geometry and classifier still determine that quantity.

2. For computable bounds on metric robustness.

Section 4.4 now gives a concrete calculation. Consider binary classification with fA(x)=A1/2xf_A(x)=A^{1/2}x, A⪰0A\succeq0, an affine head g(v)=w⊤v+bg(v)=w^\top v+b, and clipped hinge evaluation loss h(s)=min⁡{1,[1−s]+}h(s)=\min\{1,[1-s]_+\}. If the input cells have Euclidean diameter at most rr, then

ai≤r∥A∥op=:aˉ.a_i\le r\sqrt{\|A\|_{\mathrm{op}}}=:\bar{a}.

Since hh is 1-Lipschitz and the score changes by at most ∥w∥2t\|w\|_2t over a learned-distance ball of radius tt,

\varepsilon_{\mathrm{mr}}\le \min\{1,\|w\|_2r\sqrt{\|A\|_{\mathrm{op}}}\}.$$ All quantities on the right are available from the specified partition and fitted parameters. The diameter bound must hold over the entire input cell, rather than only over the observed training points. Appendix B.8 also gives a sharper bound using individual margins. Let $s_i=Y_i(w^\top A^{1/2}X_i+b)$ and $v=\|w\|_2\bar{a}$. Monotonicity of the clipped hinge loss gives $$\omega_i(a_i)\le \max\{h(s_i-v)-h(s_i),\ h(s_i)-h(s_i+v)\}.$$ Averaging these computable quantities gives a valid robustness upper bound. For example, when $s_i-v\ge1$, the loss is zero throughout the comparison neighborhood and this point contributes zero. This uses the fitted margins to improve the uniform norm bound. These calculations illustrate a general procedure: bound the learned-distance radius of each cell, bound the classifier's response at that radius, and average the resulting controls. Section 3.3 supplies such calculations for other metric-classifier combinations. **3. For estimation and approximation in practice.** The theorem can use a valid upper bound on metric robustness; exact computation of every supremum is unnecessary. Norm inequalities, margin calculations, and certified local-response bounds provide this control. Neighbor checks and random perturbations can also examine how loss changes locally, and are useful empirical diagnostics. However, evaluating finitely many points does not establish an upper bound over the entire neighborhood. We have made this distinction explicit in Section 4.4 and Appendix B.8: an empirical approximation can describe observed local behavior, while a theoretical risk certificate requires a valid upper bound. These additions explain how the quantities can be constructed and bounded from a fitted model. In Part 2, we explain how the resulting bounds guide model and partition selection.

Q2 (Part 2): How can metric robustness guide model evaluation and hyperparameter selection, and how should the partition granularity be chosen?

A2 (Part 2): Thank you very much for this valuable suggestion! Your comments have helped us make the model-selection implications of our theory explicit. We have added Corollary 4.4 in Section 4.4 and its proof in Appendix B.8, together with the selection criterion and its conditions. Here, we provide a further detailed explanation.

1. For model evaluation and hyperparameter selection.

Theorem 3.5 controls the generalization gap. For model selection, we also include the empirical classification loss, because a small gap alone does not imply a small classification risk. Let θ=(f,g)\theta=(f,g) denote a candidate metric-classifier pair, and use an evaluation loss in [0,1][0,1] that upper-bounds the misclassification indicator, such as the clipped hinge loss.

Fix δ∈(0,1)\delta\in(0,1) and choose a finite family of JJ measurable label-pure partitions Π1,…,ΠJ\Pi_1,\ldots,\Pi_J, with KjK_j cells, before observing the sample of nn independent observations. For each candidate pair, obtain a valid measurable upper bound εˉj(θ,S)\bar{\varepsilon}_j(\theta,S) on its metric robustness under Πj\Pi_j, using the controls discussed in Part 1. Define

+\bar{\varepsilon}_j(\theta,S) +\sqrt{\frac{K_j\log 2+\log(J/\delta)}{2n}}.$$ Corollary 4.4 establishes that, with probability at least $1-\delta$, simultaneously for all $j$ and candidate pairs, $$R_{01}(g\circ f)\le\min\{1,B_j(\theta)\}.$$ Thus, the empirical loss, robustness upper bound, and sampling term together provide a risk certificate for each candidate. For a finite candidate list, one can select the model and partition minimizing $B_j(\theta)$, with a fixed rule for ties. Candidates may correspond to different metric regularization strengths, classifier penalties, or other hyperparameters. The selected pair retains the guarantee because the bound holds simultaneously before selection. This selects the smallest certified upper bound; it does not assert that the selected model has the smallest unknown population risk. **2. For the partition granularity and the validity of selection.** The certificate makes the granularity tradeoff explicit. Refining a partition can reduce its within-cell radii and loss responses, while increasing the number of cells in the sampling term. A very coarse partition may give a large robustness bound; a very fine partition may give a large sampling term. The appropriate comparison therefore uses the complete certificate $B_j(\theta)$, including empirical fitting, rather than robustness alone. A practical implementation can specify a finite collection of input partition scales in advance, cross each partition with the label set, and evaluate the certificate at each scale. The term $\log(J/\delta)$ accounts for choosing among these partitions. The proof explains an important point about hyperparameter selection. For each fixed partition, the event in Theorem 3.5 depends only on the cell counts and holds simultaneously for every measurable learned metric-classifier pair. Applying it with confidence parameter $\delta/J$ and taking a union bound over the $J$ partitions establishes Corollary 4.4. Consequently, trying additional models does not require an extra model-count penalty in this argument. This does not remove the effect of model complexity: the fitted geometry, classifier sensitivity, and margins enter $\bar{\varepsilon}_j(\theta,S)$. A model that fits the training data well but has large local loss variation can therefore receive a poor certificate. If partitions are constructed from data, Appendix B.8 gives an independent pilot-sample option. Conditional on the pilot sample, the partitions are fixed for the remaining analysis sample, and the same argument applies. Here $n$, the empirical loss, and the cell counts refer to that remaining sample. Arbitrarily fitting the partition to the same analysis sample and using the fixed-partition formula is not justified by this result. **3. For the practical meaning of the guarantee.** The certificate evaluates empirical fitting together with local loss variation and partition complexity. It can distinguish candidates with similar training losses but different certified local behavior. Its numerical usefulness depends on the sharpness of the local bounds and the partition complexity. In high-dimensional settings the certificate can exceed one, in which case the clipped risk bound is uninformative. We have stated this limitation explicitly in Section 4.4. The result provides a valid selection criterion; its ability to distinguish models depends on these quantities. We sincerely appreciate your suggestion, which has helped us make this use of metric robustness explicit. We would be very happy to discuss any further questions!

Q3: The meaning and scope of “over-parameterization” require further clarification. ... The authors are encouraged to distinguish between the number of pairwise constraints, the number of dual variables, and the model's parameter capacity, and explain the relation to Zhou (2021).

A3: Thank you very much for this helpful suggestion! Your comments have helped us clarify the parameter count and the scope of our conclusions. We have clarified these distinctions in Section 4.1 and Remark 4.3, revised the contribution statement in the Introduction and the horizontal-axis labels in Figure 2, and expanded the discussion of neural networks in Section 5. We explain these points below.

1. For the meaning of over-parameterization.

Our terminology follows the metric-learning example in Zhou (2021), which considers LogDet metric learning and counts the dual variables associated with pairwise constraints. Section 4 analyzes this setting, where the count can exceed the training sample size.

We distinguish three quantities:

  • (n): the number of independent training observations;
  • (m): the number of selected pairwise constraints;
  • (p=d(d+1)/2): the number of free entries of the symmetric metric matrix.

Equation (14) expresses the inverse learned metric using one dual multiplier for each selected constraint; thus, (m) also counts the associated dual coordinates.

With (d) fixed, (m) can grow as (\Theta(n^2)) while (p) remains fixed. Moreover, dual coordinates may be redundant and some multipliers may be zero. Consequently, this count does not represent (m) independent degrees of freedom of the metric matrix. The meaning of “over-parameterization” in Section 4 is specifically the growth of the constraint-associated dual representation relative to the training sample size.

2. For dependent constraints and the theoretical contribution.

All selected pairs are constructed from the same (n) observations. Our analysis accounts for this dependence: conditional on the training sample, pairs are selected without replacement from the corresponding pair pools. The pair-coverage terms quantify how well the selected constraints control violations over these pools. The sampling term for population generalization remains determined by the original (n) independent observations.

Theorem 4.1 then connects pair coverage to downstream classification. The selected constraints control an empirical-loss comparison and the classifier norm; together with the LogDet spectral control, these quantities bound metric robustness and hence classification risk. This quantifies how additional pair constraints affect the classification guarantee.

Under the stated realizability, geometric and regularization conditions, Corollary 4.2 further proves that training and population classification errors both vanish when (m=\Theta(n^2)), so that (m/n) diverges. Thus, a growing dual parameter count is compatible with vanishing classification errors. As explained in Remark 4.3 and Appendix C.10, the same asymptotic rate can also hold for the reference metric; the finite-sample analysis identifies how pair coverage can improve the bound.

3. For the connection to neural networks.

Zhou (2021) motivates the problem through the distinction between feature-space transformation and classifier construction. Metric learning provides a concrete setting in which the learned transformation affects the subsequent classifier. Our metric-robustness framework makes this relationship quantitative.

Section 4 analyzes the dual parameterization of LogDet metric learning. Increasing neural-network width adds free network parameters and therefore requires a separate analysis. Example 3.11 provides such an analysis for a jointly regularized neural representation and classification head. In its concrete scalar three-interval example, a width-(q) network has (3q+2) scalar parameters. With the specified regularization schedule and returned-objective condition, both training and population errors are (O(n^{-1/3})), uniformly over finite widths, including (q=n^2). The guarantee applies to every returned model satisfying this condition; it does not establish that an arbitrary training procedure attains the required objective value.

We have expanded Section 5 to explain this distinction and the further geometric and optimization conditions needed for broader neural architectures. The revised Introduction also states the Section 4 contribution precisely as vanishing classification errors with “quadratically many pairwise constraints and associated dual variables.”

We sincerely thank you again for your generous appreciation of our work and for your valuable suggestions! Your comments have helped us further improve the paper and clarify its contribution and scope. We respectfully hope that you will continue to support our work, and we would be very happy to discuss any further questions!

Reviewer_Dq66OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the relationship between metric learning and the generalization performance of subsequent classifiers. The authors introduce the concept of Metric Robustness to characterize how the learned metric affects classification loss, and establish corresponding generalization guarantees for different metric learning methods and classifiers. In addition, the paper studies LogDet metric learning and proves that, under certain assumptions, over-parameterization does not necessarily lead to overfitting, even when the number of pairwise constraints grows quadratically with the sample size.

Critical strengths
  1. The paper is provides relatively detailed proofs. It also discusses the assumptions required for the theoretical results.
  2. The paper studies a meaningful problem by considering not only the quality of the learned metric but also its effect on the generalization of the downstream classifier.
Critical weaknesses
  1. The novelty of the proposed Metric Robustness framework is not clear enough. It is closely related to existing work on algorithmic robustness and metric learning generalization, and some previous results can be recovered as special cases. I am still not sure what substantial new theoretical conclusions the framework provides. The authors should explain more clearly what is genuinely new compared with existing analyses.
  2. The over-parameterization result in Section 4 relies on relatively strong assumptions, especially the existence of a metric satisfying the required class-wise distance thresholds. Although the result shows that training and population errors can both vanish with quadratically many pairwise constraints, its actual advance over previous work is unclear. What specific open issue does this result resolve, and can it be extended to more general settings?。
  3. The experimental evaluation is limited to a single breast cancer dataset, mainly illustrating how the number of pairwise constraints affects SVM and Lasso errors. These results are consistent with the theory, but provide limited additional evidence for the broader claims. The experimental results do not substantially strengthen the practical significance of the framework.
  4. Overall, I consider the contribution somewhat incremental. The paper mainly introduces a new robustness measure, connects it to existing generalization theory, and applies it to different learning settings. While this is a reasonable theoretical extension, I do not yet see a substantial advance over existing work or a clear explanation of what new understanding the framework provides.
Questions for authors

Please see the questions raised in the Weaknesses above. In particular, I would like the authors to clarify the substantive differences between Metric Robustness and existing robustness-based generalization analyses, the specific advances made by the over-parameterization result compared with previous work, and the extent to which the theoretical conclusions can be supported beyond the current experimental setting.

6 comments

We sincerely thank the reviewer for the careful assessment! We address your concerns below and look forward to further discussion.

Q1: What substantial new theoretical conclusions does the Metric Robustness framework provide? What is genuinely new compared with existing analyses?

A1: Thank you for the feedback! To our knowledge, our paper provides the first unified framework for analyzing how metric learning affects downstream classification generalization across such a broad range of metric-classifier pairs. Metric robustness establishes the connection between the two learning stages. Applying an existing robustness bound to a classifier does not by itself establish this connection. We explain the new conclusions and the technical differences below.

1. For the theoretical contribution.

A guarantee for the metric-learning loss leaves a fundamental question unanswered: what does learning this metric imply for the resulting classifier? Earlier work, including Bellet et al. (2012), Guo and Ying (2014), and Nicolae et al. (2015), addresses this connection for particular similarity-learning and classifier constructions. Our framework formulates a common condition for analyzing this connection beyond those constructions.

Proposition 3.3 shows that both empirical and population metric losses can be zero while the resulting classifier has zero training error and population error one. Thus, even perfect metric-loss generalization is insufficient to guarantee classification generalization. Controlling the interaction between the learned metric and the classifier is essential.

Metric robustness expresses this interaction naturally. The learned geometry determines a radius aia_i covering the partition cell around each training point, while the classifier determines its local loss response ωi(ai)\omega_i(a_i). Definition 3.1 combines the two through εmr=1n∑iωi(ai).\varepsilon_{\rm mr}=\frac1n\sum_i\omega_i(a_i). Theorem 3.5 then bounds the classification generalization gap by εmr+τn\varepsilon_{\rm mr}+\tau_n, where τn\tau_n is the partition sampling term. When the evaluation loss dominates misclassification, adding the empirical classification loss gives a classification-risk guarantee.

Corollary 3.6 controls metric-loss generalization through the same learned radii. Section 3.3 derives controls for Mahalanobis and kernel metrics, nearest-neighbor classifiers, and regularized linear and neural models. Example 3.10 further connects a contrastive metric objective to empirical classification loss. Together, these results explain which properties of metric learning support the subsequent task.

Section 4 quantifies how additional pairwise constraints can improve a classification-risk bound under explicit conditions. It also establishes vanishing training and population errors even with quadratically many constraints. These counts refer to constraint-associated variables; the independent observations remain the original nn samples.

Establishing this general connection is a contribution to metric-learning theory in its own right. Its significance does not depend on replacing the concentration inequality underlying robustness analysis.

2. For the distinction from algorithmic robustness.

Xu and Mannor (2012) relate within-cell variation of a predictor's loss to its generalization. Their framework can be applied to the composite predictor gS∘fSg_S\circ f_S once this variation is controlled. However, that application leaves open how the metric-learning objective controls the learned geometry, how the classifier responds to that geometry, and how its empirical loss is controlled. Bellet and Habrard (2015) analyze pairwise metric-loss generalization, but Proposition 3.3 shows why that guarantee alone cannot answer the downstream question.

Our analysis establishes these additional steps. Definition 3.1 separates learned radii from classifier responses, and the examples derive their controls from objectives, norms, and margins. Theorem 3.5 preserves the average pointwise response rather than replacing every response by a uniform maximum. Its proof also uses total variation of the cell masses, and the probability event depends only on the fixed partition counts. Consequently, both learning stages may use the same observations.

In Section 4, spectral control from LogDet regularization, uniform approximation of the training-pair pools, and an SVM objective comparison connect the pair constraints to the classifier's empirical loss and local response. These arguments must be established before applying the generalization theorem; they are not supplied by an existing robustness bound.

Recovering earlier results confirms consistency with established analyses. The new contribution is the common relation between the two stages and its downstream guarantees. Our proofs build on the robustness principle, while establishing the metric-dependent controls needed to answer this different theoretical question.

Q2: Although training and population errors can both vanish with quadratically many pairwise constraints, what is the advance over previous work? What specific open issue does this resolve, can it extend to more general settings, and how restrictive are the threshold assumptions?

A2: Thank you for the feedback!

To our knowledge, this is the first work to provide a theoretical explanation of the metric-learning over-parameterization question raised by Zhou (2021). The question is why a metric-learning procedure can support good downstream classification when its constraint-associated parameter count exceeds the number of training observations. A generalization guarantee for the metric-learning loss alone does not answer this question: the final prediction is produced by a classifier fitted using the learned metric. Our contribution is to connect the metric-learning procedure to this final classification guarantee.

Theorem 4.1 shows how pair coverage controls the fitted classifier's empirical loss and metric robustness, yielding a classification-risk bound. Corollary 4.2 then establishes conditions under which both training and population classification errors vanish while the constraint count grows as Θ(n2)\Theta(n^2).

The analysis identifies why this is possible. Comparison with a common feasible metric bounds the LogDet objective and hence the learned metric's spectrum uniformly across pair budgets. Increasing coverage reduces the error in approximating the full training-pair pools. A mean-distance comparison classifier converts the resulting violation control into bounds on the fitted SVM's loss and norm. Metric robustness then connects these quantities to population classification risk.

Thus, the result follows the actual outputs of both learning stages. It explains how increasing the constraint count can improve the explicit risk guarantee while the statistical sampling term remains governed by the original nn observations.

For the open issue and broader implications.

Zhou (2021) distinguishes feature-space transformation from the subsequent classifier and discusses metric learning as an example of the former. Our result addresses the corresponding question for LogDet metric learning: under what conditions can a learned transformation and its fitted classifier generalize despite a quadratic number of constraint-associated variables?

Following that example, we count the dual variables associated with pair constraints. The matrix has d(d+1)/2d(d+1)/2 independent entries, with dd fixed. The result establishes compatibility of quadratic constraint growth with vanishing errors; it does not require treating the pairs as independent observations. Remark 4.3 and Appendix C.10 also distinguish this conclusion from a claim that quadratic budgets are necessary for consistency.

The connection to neural networks is a further motivation. A neural representation also changes the geometry seen by its prediction head. Example 3.11 already gives a width-uniform guarantee for a jointly regularized shallow ReLU representation and affine head, subject to an objective-value bound. Extending this analysis to broader architectures and training procedures is a promising route toward understanding neural-network over-parameterization. Such an extension requires establishing the corresponding geometric and response controls under joint training.

For the assumptions and more general settings.

The population threshold condition in equation (21) is a sufficient condition for the zero-error conclusion of Corollary 4.2. It is not required by the general metric-robustness framework, and our analysis also includes a finite-sample guarantee without a zero-violation comparison metric.

Specifically, Appendix C.7 studies an averaged hinge metric-learning objective with LogDet regularization. Let OS=min⁡A≻0L+(A)+L−(A)+λdDld(A,A0),O_S=\min_{A\succ0}{L_+(A)+L_-(A)+\lambda_dD_{\rm ld}(A,A_0)}, where L+L_+ and L−L_- are the full training-pool violation losses. Equation (39) proves L+(Am)+L−(Am)≤OS+2[e+(m+)+e−(m−)].L_+(A_m)+L_-(A_m)\le O_S+2[e_+(m_+)+e_-(m_-)]. Equation (40) turns this inequality into a downstream classification-risk guarantee. No metric satisfying every threshold is required; the formulation even permits identical inputs with different labels. The quantity OSO_S retains the best full-pool tradeoff between violations and regularization, while additional pairs reduce the approximation terms.

Accordingly, the theory provides a risk bound in the general case and a vanishing-error conclusion under the stated realizability conditions. These are different levels of guarantee. Appendix C.8 further treats Gaussian-kernel SVMs, and Appendix C.12 incorporates optimization errors and constraint residuals. The scope of the analysis therefore extends beyond the exact hard-constraint setting used to state the main consistency result.

Q3: The experiments are limited to a single dataset and lack a reference-metric baseline.

A3: Thank you very much for the feedback! The experiment in Section 4 introduces the motivating observation that over-parameterization in metric learning need not cause overfitting. Our contribution is the theoretical explanation under explicit conditions; the observation itself is not claimed as a new contribution. Accordingly, the experiment examines how classification errors change with the constraint count, without aiming to establish a performance advantage over a reference-metric baseline. Its role is illustrative, rather than an algorithmic benchmark or a numerical verification of the theory.

We have conducted experiments with different data sizes and types to show this behavior beyond the example in the main text. Below, we present the settings and results. The accompanying PDF (if the link does not work, please use https://default-anno-bucket.s3.us-west-1.amazonaws.com/experiments.pdf) contains seven plots covering four datasets and two downstream classifiers.

Datasets.

We use four real-world datasets: Rice, Raisin, Diabetes, and Cancer, covering agricultural classification and medical diagnosis, with sample sizes ranging from 569 to 3,810.

  • [Rice] contains 3,810 samples from the Cammeo and Osmancik varieties, represented by seven morphological features extracted from grain images. We use 2,500 samples for training and 1,310 for testing.
  • [Raisin]contains 900 samples from the Kecimen and Besni varieties grown in Turkey, with 450 samples per variety and seven morphological features extracted from images. We use 600 samples for training and 300 for testing.
  • Diabetes is the Pima Indians Diabetes dataset, containing 768 samples with eight features. We use 500 samples for training and 268 for testing.
  • [Cancer] is the Breast Cancer Wisconsin (Diagnostic) dataset, containing 569 samples with 30 numerical features describing cell nuclei. We use 400 samples for training and 169 for testing.

Experimental setting.

For each dataset, we first learn a metric using the LogDet-based metric-learning method considered in Section 4. We then perform classification in the resulting embedding space. We consider SVM and k-NN with k = 3. Figures 1-6 show both classifiers on Rice, Raisin, and Diabetes, respectively; Figure 7 shows SVM on Cancer.

We vary the number of pairwise constraints used by the metric learner while keeping the training sample size fixed. Following the convention in Section 4, the parameter count on the horizontal axis refers to the variables associated with these constraints. This count can exceed the training sample size without increasing the number of independent observations or free entries of the metric matrix.

For Rice, the plotted counts range from 100 to 204,800. For Raisin, they range from 0 to 5,120, while those for Diabetes and Cancer range from 10 to 5,120. The positive counts are displayed on a logarithmic scale.

Evaluation.

We plot training and testing classification errors after metric learning. The orange dashed curve denotes training error, and the blue solid curve denotes testing error. Their difference shows the empirical generalization gap. The two curves distinguish changes in training fit from changes in performance on unseen samples.

Results.

The seven plots show the following behavior:

  1. On Rice, SVM testing error remains approximately 7.4%-7.9% as the count increases from 100 to 204,800. The k-NN curve fluctuates, including a local peak, but does not exhibit a sustained increase and ends near its initial level. Neither shows a progressively widening gap over the full range.
  2. On Raisin, the testing errors of SVM and k-NN fluctuate within approximately 16%-18% and 13.7%-15.3%, respectively. On Diabetes, SVM testing error stays close to 23%, while k-NN testing error is lower at the largest counts than at the smallest count.
  3. On Cancer, SVM testing error fluctuates and ends below its initial level. The training and testing errors remain separated, but increasing the constraint count does not produce a sustained deterioration in testing performance. These observations concern the plotted trends; they do not require either curve to decrease monotonically.

These results show that the motivating observation is not specific to one dataset or one downstream classifier. Across the settings presented, increasing the constraint-associated parameter count beyond the training sample size does not by itself cause testing error to grow systematically. This is the behavior our analysis seeks to explain. The theory identifies conditions under which such behavior is possible, while these experiments provide further illustrations across different data sizes, feature dimensions, and classification methods.

Reviewer_wipPOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the relationship between metric learning and the generalization of downstream classifiers. The authors introduce metric robustness and derive generalization bounds for several metric learning and classification methods. They further analyze LogDet metric learning followed by an SVM. Under specific separation assumptions, they prove that both training and population classification errors converge to zero even when the number of pairwise constraints grows quadratically with the sample size. Experiments on a single dataset investigate the effect of increasing the number of constraints on classification error.

Critical strengths
  1. This paper comes with a clear motivation. Proposition 3.3 shows that the empirical and population metric losses can both vanish while the classification generalization gap is maximal. This demonstrates that controlling the empirical and population metric losses alone is insufficient to guarantee the generalization of the resultant classifier.

  2. The paper establishes generalization bounds for several metric learning and classification methods. It also analyzes how the number of pairwise constraints affects the classification-risk bound for LogDet metric learning followed by an SVM.

Critical weaknesses
  1. Theorem 3.5 builds on the existing algorithmic robustness framework of Xu and Mannor (2012) [1]. The paper does not clearly establish whether the proposed formulation provides tighter generalization bounds or requires weaker assumptions.

  2. Appendix C.10 shows that the reference metric achieves the same asymptotic convergence rate without metric learning. Although increasing pair coverage can tighten the theoretical bound, the paper does not demonstrate a meaningful finite-sample improvement over the reference-metric guarantee.

  3. The experiments are limited to a single dataset and lack a reference-metric baseline. Moreover, the SVM kernel, hyperparameter-selection protocol, and error-bar computation are not sufficiently specified.

[1] Xu, H., and Mannor, S. (2012). Robustness and Generalization. Machine Learning, 86(3), 391–423.

Questions for authors
  1. What is the main theoretical contribution of Theorem 3.5 compared with the existing algorithmic robustness framework of Xu and Mannor (2012) [1]? In particular, does the proposed metric robustness formulation provide tighter generalization bounds or require weaker assumptions? Please clarify the technical advantages over existing robustness-based generalization results.

  2. Appendix C.10 shows that the reference metric achieves the same asymptotic convergence rate without metric learning. Although increasing pair coverage can tighten the theoretical bound, its practical significance remains unclear. Can the authors demonstrate a finite-sample setting where additional pairwise constraints yield a classification-risk bound strictly below one and a meaningful improvement over the reference-metric guarantee?

  3. Which SVM kernel and hyperparameter-selection protocol were used? How were the error bars in Figure 2 computed? Are results available for an otherwise identical reference-metric baseline evaluated on the same splits?

[1] Xu, H., and Mannor, S. (2012). Robustness and Generalization. Machine Learning, 86(3), 391–423.

6 comments

We sincerely thank you for your careful review and valuable comments! We address your concerns below and hope our explanations will clarify the contribution of our work. We look forward to any further discussion!

Q1: What is the main theoretical contribution of Theorem 3.5 compared with the existing algorithmic robustness framework of Xu and Mannor (2012)? In particular, does the proposed metric robustness formulation provide tighter generalization bounds or require weaker assumptions? Please clarify the technical advantages over existing robustness-based generalization results.

A1 (Part 1): Thank you for the feedback! Our main contribution is metric robustness: a general connection between a learned metric and the generalization of its resulting classifier, beyond the specific constructions covered by earlier analyses. The general robustness principle of Xu and Mannor does not by itself establish this connection. We first explain this difference in purpose and contribution, and then address the bound and assumptions in the following comment.

1. For the theoretical question.

Metric learning serves a subsequent task. A guarantee for its pairwise loss leaves a further question: what does learning this metric imply for the classifier trained using it? Our paper addresses this question across representations and classifiers.

Earlier work provides important answers under particular learning formulations. Bellet et al. (2012) and Guo and Ying (2014), for example, connect regularized similarity learning to associated linear classifiers. Nicolae et al. (2015) analyze jointly learned similarities and landmark classifiers using robustness. We formulate the joint property that supports this connection beyond these constructions.

Xu and Mannor study how local variation of a learned predictor's loss controls its generalization. For our question, the local variation itself must be related to two learned objects: the metric and the classifier. Treating their composition as a predictor leaves this relation unspecified. Identifying it, deriving its controls from learning objectives, and showing what it implies for downstream classification constitute the contribution of our framework.

2. For the role of metric robustness.

Proposition 3.3 makes the missing connection explicit. It constructs a representation for which both empirical and population metric losses are zero, yet the resulting classifier has zero training error and population error one. Thus, even perfect metric-loss generalization does not suffice. A condition relating the learned geometry to the classifier's behavior is essential.

Metric robustness expresses exactly this joint requirement. The learned metric determines the radius aia_i needed to cover the partition cell around a training point. The classifier determines the loss response ωi(ai)\omega_i(a_i) over that learned-distance neighborhood. Definition 3.1 averages these responses: εmr=1n∑i=1nωi(ai).\varepsilon_{\rm mr}=\frac1n\sum_{i=1}^n\omega_i(a_i). The same geometry can support different loss responses for different classifiers. Conversely, a classifier with controlled response can benefit from a metric that makes the relevant neighborhoods smaller. The quantity therefore involves both stages.

Theorem 3.5 turns this joint property into a generalization bound and, together with empirical fitting, a classification-risk guarantee. For an evaluation loss in [0,1][0,1] that dominates misclassification, R01(g∘f)≤L^c,f(g)+εmr+τn,R_{01}(g\circ f)\le\widehat L_{c,f}(g)+\varepsilon_{\rm mr}+\tau_n, where τn\tau_n is the partition sampling term. The result identifies separately how empirical fitting, learned local geometry, and classifier sensitivity contribute to the final guarantee.

3. For the generality and significance.

As Remark 3.2 states, the definition covers any measurable representation and classifier with bounded evaluation loss. Section 3.3 derives controls for Mahalanobis and kernel metrics, regularized classifiers, nearest neighbors, and jointly trained neural representations. These cases share one analysis: control the geometry produced by metric learning and the classifier's response to that geometry.

The formulation also supports further conclusions. Example 3.10 connects a contrastive metric objective to empirical classification loss, while Section 4 combines objective comparisons and local-response control to analyze the effect of additional pair constraints. These are conclusions about what metric learning provides for the subsequent task.

To our knowledge, this is the first unified framework through metric robustness that controls both downstream generalization gaps and classification risk across such a range of metric-classifier pairs. Establishing this connection is a substantive contribution to metric-learning theory in its own right. Its significance remains even when the underlying sampling argument is classical.

A1 (Part 2)

1. For what a direct robustness bound establishes.

Xu and Mannor (2012) can be applied to the composite predictor gS∘fSg_S\circ f_S, provided its within-cell classification-loss variation is controlled. Such an application bounds classification generalization in terms of that variation. It does not establish how a metric-learning objective controls the variation, how the same learned geometry controls pairwise metric-loss generalization, or how the fitted classifier's empirical loss is controlled.

These are distinct steps in our analysis. Definition 3.1 connects the learned geometry to classification-loss variation through aia_i and ωi\omega_i. Theorem 3.5 converts their joint control into classification generalization. For a pairwise loss in [0,Bd][0,B_d] that is UU-Lipschitz in distance and finite a=max⁡iaia=\max_i a_i, Corollary 3.6 gives, on the same event, ∣Ld−L^d∣≤min⁡Bd,2Ua+2Bdτn.|L_d-\widehat L_d|\le\min{B_d,2Ua}+2B_d\tau_n. The two guarantees share the learned radii; the examples derive their controls from the learning objectives.

The two losses concern different objects. Bellet and Habrard (2015) already extend robustness reasoning to pairwise metric losses. Our contribution is the connection to the resulting classifier; Proposition 3.3 shows why its guarantee cannot be obtained from pairwise metric-loss generalization alone. Thus, the contribution concerns the relation between the two learning stages, beyond a numerical improvement to a generic classification bound.

2. For tighter generalization bounds.

A precise comparison is possible once the partition and local controls are fixed. Write ci=ωi(ai)c_i=\omega_i(a_i) and τn=Klog⁡2+log⁡(1/δ)2n.\tau_n=\sqrt{\frac{K\log 2+\log(1/\delta)}{2n}}. For losses in [0,1][0,1], a direct use of the standard uniform robustness theorem with these controls gives ∣L−L^∣≤max⁡ici+2τn.|L-\widehat L|\le\max_i c_i+2\tau_n. Theorem 3.5 gives ∣L−L^∣≤1n∑ici+τn.|L-\widehat L|\le\frac1n\sum_i c_i+\tau_n. The local term retains the average response instead of replacing every point's response by the largest one. If only qq training points have nonzero responses, this term is at most q/nq/n, whereas the uniform response can remain one. The fitted-margin calculations in Appendix B.5 provide concrete settings where many local responses vanish.

Appendix B.3 also uses the total variation between empirical and population cell masses. Since the cell-mass differences sum to zero and the loss lies in [0,1][0,1], their contribution is bounded by half their ℓ1\ell_1 difference. This yields the smaller sampling coefficient above. These refinements concern the stated comparison with the same partition and controls; they do not assert superiority over every possible robustness analysis.

3. For the assumptions.

Theorem 3.5 uses i.i.d. observations, a fixed finite measurable partition, and a bounded measurable evaluation loss. It does not require a globally Lipschitz classifier, a particular metric-learning objective, or convex optimization. Lipschitz constants and decision margins appear in the examples as ways to bound the response. The theorem itself retains the response of the fitted pair.

Its average local term permits a useful guarantee when most training points have small responses even if a few have large responses. A uniformly small maximum is therefore unnecessary. This is the specific sense in which the required local control can be less restrictive. We do not claim that every assumption is weaker than in Xu and Mannor.

The label-pure partition is defined on the labeled sample space: refining cells by label ensures that the response is evaluated at the same label. It does not assume noiseless labels or separation in the input space. The refinement is accounted for through the number of cells KK.

4. For the proof and further analysis.

The proof in Appendix B.3 integrates the individual local bounds within each cell and preserves their empirical weights. Its probability event depends only on the counts in the fixed partition, so it holds simultaneously for all admissible learned representations and classifiers. Both stages may use the same observations; the proof does not assume that transformed observations become independent after fitting the representation.

Section 4 further combines spectral control from LogDet regularization, uniform approximation of training-pair pools, and an SVM objective comparison before applying Theorem 3.5. These steps connect the metric-learning objective to the fitted classifier's empirical loss and response. Establishing this connection is the central technical contribution, beyond the general robustness principle.

Q2: Appendix C.10 shows that the reference metric achieves the same asymptotic convergence rate without metric learning. Can the authors demonstrate a finite-sample setting where additional pairwise constraints yield a classification-risk bound strictly below one and a meaningful improvement over the reference-metric guarantee?

A2: Thank you for the feedback! Theorem 4.1 provides finite-sample control of the effect of pair coverage, and Appendix C.10 specifies when this control improves on the reference guarantee. Below, we give a concrete setting in which the certified risk bound decreases from 0.587 for the C.10 reference guarantee to 0.196 with half of the pair pools and 0.144 with full coverage. All three values use the same sample size, confidence level, partition, and classifier regularization.

1. For the asymptotic comparison.

The conclusion of Corollary 4.2 is that training and population classification errors vanish even with quadratically many constraint-associated variables. It establishes that this growth is compatible with generalization. It does not require growing pair budgets to be necessary for consistency.

Appendix C.10 makes this distinction explicit. Under threshold realizability, a bounded affine comparison score can be represented under every metric in the LogDet sublevel set, including the reference metric. This supplies the same asymptotic order. The additional pair constraints provide a separate control of empirical fitting and classifier norm, which can improve the finite-sample constants. Equal asymptotic orders therefore do not imply equal finite-sample guarantees.

2. For the finite-sample improvement.

Use the notation of C.10:

\chi=\frac{\beta}{\underline\beta},\quad v=\frac{\alpha_SV_m}{\Delta}.$$ Here $\beta,\underline\beta$ are the uniform upper and lower spectral bounds. The pair-dependent and reference-comparison objective bounds are $$H_m=\min{1,a+v},\qquad \widetilde H=\min{1,a\chi}.$$ With the remaining quantities fixed, the risk bound is $$F(h)=h+\min{1,r\sqrt{2\beta h/\lambda_c}}+\tau_n.$$ Increasing pair coverage does not increase $v$. Since $F$ is strictly increasing, $a+v<\min{1,a\chi}$ gives strict improvement of the untruncated bound. To answer the question fully, we also need $F(H_m)<1$. The following construction satisfies both requirements. **3. A concrete finite-sample setting.** Let $X$ be uniformly distributed on $[-1.1,-1]\cup[1,1.1]$, with $Y=\operatorname{sign}(X)$. Take $$A_0=1,\quad A^\dagger=4,\quad R=1.1,\quad u=0.04,\quad l=16,\quad \Delta=15.96.$$ Within either class, squared distance under $A^\dagger$ is at most $4(0.1)^2=0.04$; between classes, it is at least $4(2)^2=16$. Thus the population threshold condition holds, and the same comparator is feasible for every training sample and pair budget. Its LogDet divergence is $C=3-\log4$. Consequently, $\beta=4$ and $\underline\beta=b_-(C)\simeq0.0793096$, where $b_-(C)-\log b_-(C)-1=C$. Before sampling, divide each interval into ten cells of width 0.01 and cross these cells with the two labels. This gives a fixed label-pure partition with $K=40$ and $r=0.01$. Set $$n=1000,\qquad \delta=0.05,\qquad \lambda_c=0.05.$$ Use an exact affine SVM minimizer. Equations (16)-(18) and (45)-(48) give $$a\simeq0.00760045,\quad \widetilde H\simeq0.383331,\quad \tau_n=\sqrt{\frac{40\log2+\log40}{2000}}\simeq0.125329.$$ For full hard-constraint pair pools, $V_m=0$, so $H_m=a$. For half coverage, use the first $\lfloor N_\sigma/2\rfloor$ pairs in each uniformly permuted pool, exactly as in Section 4.2. With probability at least $1-2e^{-20}$, each class has between 400 and 600 observations. On this event, $N_+\ge249500$, $N_-\ge240000$, and $\alpha_S\le1.2975$. Substitution into (16) gives $V_m\le0.447740$, hence $H_m\le0.0440004$ for half coverage. Combining this event with Theorem 4.1 gives simultaneous guarantees with probability at least $0.95-2e^{-20}$: | Setting | Objective upper bound | Classification-risk upper bound | | ------------------------- | --------------------- | ------------------------------- | | Reference guarantee, C.10 | 0.383331 | 0.587 | | Half of each pair pool | 0.044001 | 0.196 | | Full pair pools | 0.007601 | 0.144 | The table entries are rounded upward. Both pair-based guarantees are strictly below one and improve substantially over the reference guarantee. Full coverage reduces that upper bound by about 75%, and also improves on the half-coverage guarantee. This example directly instantiates the existing finite-sample results on a continuous distribution. The reference column is the uniform guarantee established in C.10, which applies in particular to $A_0$.
Reviewer_f47ROpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors introduce metric robustness to connect a learned distance metric with the downstream classifier. Rather than asking only whether the metric itself generalizes, they also examine how much the classification loss varies within local neighborhoods defined by that metric.

Critical strengths

1、The paper provides a unified framework for analyzing generalization in metric learning and downstream classification, addressing the limitations of prior work that focused mainly on the metric loss itself. 2、The theoretical analysis is thorough, clarifying the roles of the partition, optimization error, and connections to existing results. 3、The paper also studies over-parameterization, showing that the number of pairwise constraints can grow quadratically with the sample size while the classification error still converges.

Critical weaknesses

1、The theoretical guarantees rely heavily on a label-pure partition fixed in advance, metric robustness, and the classifier’s local loss response. The paper does not clearly explain how these quantities should be defined or estimated in practical settings. 2、The empirical evidence is limited: the experiments are conducted on only one dataset.

Questions for authors

I am not an expert in this area, but the paper seems to present a series of special cases of robustness analysis.

5 comments

We sincerely thank you for the time and effort devoted to our paper and for your valuable comments! We hope our explanations will help clarify our work. We respond to all of the concerns below, and we look forward to any further discussion!

Q1: The theoretical guarantees rely heavily on a label-pure partition fixed in advance, metric robustness, and the classifier's local loss response. The paper does not clearly explain how these quantities should be defined or estimated in practical settings.

A1: Thank you for the feedback! We understand the concern about the strength of these assumptions. Our first point is that downstream guarantees need to account for both the metric and classifier. Our second point is that label purity does not assume class separation, while the local response is explicitly quantified in the bound.

1. On metric robustness.

Previous work, such as [Bellet et al. (2012)] and [Guo and Ying (2014)], establishes downstream guarantees for particular regularized similarity-learning formulations and their associated linear classifiers. Our goal is to characterize this connection beyond these formulations.

Some information linking the representation to the classifier is indispensable: good metric losses alone cannot ensure good classification generalization. Proposition 3.3 gives a simple example with continuous inputs and binary labels. A learned map sends positive/negative training points to +1/-1, but positive/negative unseen points to -1/+1. Within training pairs and within fresh test pairs, same-class points remain together and different-class points remain separated. The empirical and population contrastive losses are both zero. Yet the score g(v)=vg(v)=v fits all training labels and misclassifies almost every test point. This shows why the classifier's behavior must also enter the analysis.

Metric robustness measures how much the classification loss changes within a training point's neighborhood under the learned distance, with the evaluation label held fixed. It therefore describes the learned representation and classifier jointly. Metric robustness is therefore a very general quantity that captures the essential connection between the metric and the classifier, while requiring only a relatively weak assumption.

2. On the label-pure partition and the classifier's local loss response.

The partition is defined on the labeled space X×Y\mathcal X\times\mathcal Y. Any fixed finite measurable input partition {Vj}\{V_j\} gives a label-pure partition {Vj×{y}}j,y\{V_j\times\{y\}\}_{j,y}. This does not require input regions to contain only one class or require knowledge of the decision boundary. It also accommodates noisy labels, as stated in Remark 3.4 and Appendix B.1. The partition is used for analysis; prediction does not require test labels. Fixing it before sampling supports the concentration argument, while the learned metric, classifier, radii, and responses can all depend on the training sample.

The local loss response is not assumed to be uniformly small. Theorem 3.5 states that, with probability at least 1−δ1-\delta, ∣Lc,f(g)−L^c,f(g)∣≤1n∑iωi(ai)+Klog⁡2+log⁡(1/δ)2n.|L_{c,f}(g)-\widehat L_{c,f}(g)|\le\frac1n\sum_i\omega_i(a_i)+\sqrt{\frac{K\log2+\log(1/\delta)}{2n}}. Here KK counts partition cells, aia_i is the supremum of learned distances from XiX_i to its cell, and ωi(t)\omega_i(t) is the supremum of loss changes within distance tt, evaluated at the fixed label YiY_i. Smaller responses give tighter bounds. Global Lipschitz continuity and a prescribed margin are not required by the theorem.

3. On practical evaluation.

Section 3.3 and Appendix B.5 already show how to bound these quantities for concrete methods. The procedure is to fix an input cover, bound distances within its cells under the learned representation, and bound the classifier's loss response using its norm or decision margins. Appendix B.3 allows upper bounds to replace the exact suprema.

For example, consider cells of input diameter at most rr, a Mahalanobis representation f(x)=A1/2xf(x)=A^{1/2}x, and an affine classifier with clipped-hinge evaluation loss. Example 3.7 gives

\varepsilon_{\rm mr}\le\min\{1,r\|w\|_2\sqrt{\|A\|_{\rm op}}\}.$$ The fitted matrix $A$, classifier weights $w$, and chosen scale $r$ determine this upper bound. Appendix B.5.2 further refines it using each training point's fitted margin. Kernel norms and prototype distances provide corresponding bounds for other models. On a known compact input domain, covering-number bounds control $K$. Refining the partition can reduce local radii at the cost of a larger sampling term. Appendix B.3 also explains how to compare a finite family of partitions fixed in advance: allocate confidence levels across the family, then select the smallest resulting bound. These calculations use fitted parameters and a specified input partition.

Q2: The empirical evidence is limited: the experiments are conducted on only one dataset.

A2: Thank you very much for the feedback! The experiment in Section 4 introduces the motivating observation that over-parameterization in metric learning need not cause overfitting. Our contribution is the theoretical explanation under explicit conditions; the observation itself is not claimed as a new contribution. Its role is illustrative, rather than an algorithmic benchmark or a numerical verification of the theory.

We have conducted experiments with different data sizes and types to show this behavior beyond the example in the main text. Below, we present the settings and results. The accompanying PDF (if the link does not work, please use https://default-anno-bucket.s3.us-west-1.amazonaws.com/experiments.pdf) contains seven plots covering four datasets and two downstream classifiers.

Datasets.

We use four real-world datasets: Rice, Raisin, Diabetes, and Cancer, covering agricultural classification and medical diagnosis, with sample sizes ranging from 569 to 3,810.

  • Rice contains 3,810 samples from the Cammeo and Osmancik varieties, represented by seven morphological features extracted from grain images. We use 2,500 samples for training and 1,310 for testing.
  • Raisin contains 900 samples from the Kecimen and Besni varieties grown in Turkey, with 450 samples per variety and seven morphological features extracted from images. We use 600 samples for training and 300 for testing.
  • Diabetes is the Pima Indians Diabetes dataset, containing 768 samples with eight features. We use 500 samples for training and 268 for testing.
  • Cancer is the Breast Cancer Wisconsin (Diagnostic) dataset, containing 569 samples with 30 numerical features describing cell nuclei. We use 400 samples for training and 169 for testing.

Experimental setting.

For each dataset, we first learn a metric using the LogDet-based metric-learning method considered in Section 4. We then perform classification in the resulting embedding space. We consider SVM and k-NN with k = 3. Figures 1-6 show both classifiers on Rice, Raisin, and Diabetes, respectively; Figure 7 shows SVM on Cancer.

We vary the number of pairwise constraints used by the metric learner while keeping the training sample size fixed. Following the convention in Section 4, the parameter count on the horizontal axis refers to the variables associated with these constraints. This count can exceed the training sample size without increasing the number of independent observations or free entries of the metric matrix.

For Rice, the plotted counts range from 100 to 204,800. For Raisin, they range from 0 to 5,120, while those for Diabetes and Cancer range from 10 to 5,120. The positive counts are displayed on a logarithmic scale.

Evaluation.

We plot training and testing classification errors after metric learning. The orange dashed curve denotes training error, and the blue solid curve denotes testing error. Their difference shows the empirical generalization gap. The two curves distinguish changes in training fit from changes in performance on unseen samples.

Results.

The seven plots show the following behavior:

  1. On Rice, SVM testing error remains approximately 7.4%-7.9% as the count increases from 100 to 204,800. The k-NN curve fluctuates, including a local peak, but does not exhibit a sustained increase and ends near its initial level. Neither shows a progressively widening gap over the full range.
  2. On Raisin, the testing errors of SVM and k-NN fluctuate within approximately 16%-18% and 13.7%-15.3%, respectively. On Diabetes, SVM testing error stays close to 23%, while k-NN testing error is lower at the largest counts than at the smallest count.
  3. On Cancer, SVM testing error fluctuates and ends below its initial level. The training and testing errors remain separated, but increasing the constraint count does not produce a sustained deterioration in testing performance. These observations concern the plotted trends; they do not require either curve to decrease monotonically.

These results show that the motivating observation is not specific to one dataset or one downstream classifier. Across the settings presented, increasing the constraint-associated parameter count beyond the training sample size does not by itself cause testing error to grow systematically. This is the behavior our analysis seeks to explain. The theory identifies conditions under which such behavior is possible, while these experiments provide further illustrations across different data sizes, feature dimensions, and classification methods.

Q3: The paper seems to present a series of special cases of robustness analysis.

A3 (Part 1): Thank you for the feedback! We would like to clarify two points. First, metric robustness connects the learned metric to downstream classification, which is an important contribution independently of improvements to robustness theory. Second, our results build on robustness reasoning but require additional analysis. We explain the significance here and the technical differences in the following comment.

1. On the significance of metric robustness.

Building on A1, we further explain why this connection is important. A metric is usually learned for a subsequent task. Controlling its pairwise learning loss answers only part of the question: what does this imply for the classifier that makes predictions? This is the problem identified in the Introduction and addressed throughout Sections 3 and 4.

Proposition 3.3 constructs a learned representation with zero empirical and population metric losses, while an interpolating downstream classifier has population error one. Thus, even perfect metric-loss generalization does not by itself establish classification generalization. Here zero-one metric robustness equals one, detecting the failure that the pairwise losses miss. Some information about how the metric and classifier work together is essential.

Metric robustness provides a natural way to express this relationship. The learned metric determines which inputs are close in the representation space; the classifier determines how its loss changes among those inputs. Definition 3.1 puts these two parts together: the radius aia_i describes the extent of a partition cell under the learned metric, and ωi(ai)\omega_i(a_i) measures the classifier's loss variation over that neighborhood, with the label fixed. Their average, εmr=1n∑i=1nωi(ai),\varepsilon_{\rm mr}=\frac1n\sum_{i=1}^n\omega_i(a_i), quantifies the local compatibility of the learned metric and its resulting classifier.

This connection follows directly from the purpose of metric learning. Bringing inputs close together is useful for classification when the classifier behaves consistently over the resulting neighborhoods. Conversely, the same learned geometry can lead to different loss responses for different classifiers, as Figure 1 illustrates. The quantity therefore reflects both stages. Remark 3.4 also shows that rescaling the representation and compensating in the classifier leaves metric robustness unchanged: the guarantee cannot be improved merely by changing distance units.

Theorem 3.5 turns this relationship into a classification guarantee. For an evaluation loss that upper-bounds misclassification, it gives R01(g∘f)≤L^c,f(g)+εmr+τn,R_{01}(g\circ f)\le\widehat L_{c,f}(g)+\varepsilon_{\rm mr}+\tau_n, where τn\tau_n is the partition sampling term. This separates the requirements for successful classification: fitting the training labels, controlling the joint local response, and controlling sampling error. It also explains why a small generalization gap alone is insufficient for a small classification risk.

Earlier work established important connections for particular learning formulations. For example, Bellet et al. (2012) and Guo and Ying (2014) analyze regularized similarity learning and associated linear classifiers. To our knowledge, our paper provides the first unified formulation through metric robustness that connects learned local geometry to both the generalization gap and risk of downstream classifiers across a broad range of metric-learning and classification methods.

The examples establish what this general connection means for different methods. Mahalanobis regularization controls local expansion; classifier norms control score variation; nearest-neighbor margins control whether predictions change. Section 3.3 also treats kernel methods and jointly trained neural representations. These calculations explain which properties of each learning stage enter the final guarantee through the same quantity.

The analysis also goes beyond bounding a classification gap. Example 3.10 derives an empirical classification-loss bound from a contrastive metric-learning objective and combines it with metric robustness to control population risk. Section 4 then connects additional pair constraints to the fitted classifier's loss and response, leading to vanishing training and population errors under the stated conditions. These conclusions concern the outcome of metric learning.

The significance of this contribution therefore does not rest on inventing a different concentration inequality. Even with the classical sampling term unchanged, identifying a common condition that connects metric learning to downstream classification, and deriving it from learning objectives, addresses an important theoretical question. The examples show how this common connection yields guarantees for different methods.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.