Research map / Detection and segmentation / CNN features

Mathematical Justification of Hard Negative Mining via Isometric Approximation Theorem

ICLR 2024 · Detection and segmentation › CNN features · approach: Efficient DETR query design · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

The paper uses isometric approximation theory to show that triplet loss with hard negative mining is equivalent, within constant factors, to minimizing a Hausdorff-like distance between the network and its ideal Triplet-Separated counterpart, and uses this to explain network collapse.

Problem

Hard negative mining for triplet loss works inconsistently (sometimes succeeds, sometimes causes network collapse), and existing work lacks a theoretical explanation for this behavior.

Approach

Applies the isometric approximation theorem in Euclidean subsets to show that the Hausdorff-like distance to the set of Triplet-Separated functions and the isometric error upper-bound each other linearly, and that the hard-negative-mined triplet loss is equivalent to the isometric error within constant factors; collapse arises when the nearest ideal function is collapsed.

Key results

• On a toy example with N=5 points in R^2, the constant relating d_haus and d_iso is calculated as c=0.53, showing near-linear equivalence.
• Theory shows d_haus and d_iso upper bound each other within factors c_n/theta_* and 2, and the hard-negative triplet loss and d_iso bound each other by a factor of 2.

Surprising findings

• Hard negative mining is predicted to collapse when N is much greater than the embedding dimension n, and not otherwise, which is consistent with prior reports (Schroff et al. with thousands of samples vs Herman et al. with N=72).

Limitations

• Margin alpha is assumed to be zero, which may not hold when the margin affects the optimum.
• Collapse hypothesis is supported only by toy examples and literature comparison, not by controlled experiments on real networks.
• Theorem requires a minimum thickness condition on the embedding set.

Experimental setup

Builds on: triplet loss isometric approximation theorem

Closest papers by meaning

• The Dilemma of TriHard Loss and an Element-Weighted TriHard Loss for Person Re-Identification (NeurIPS 2020 · similarity 0.86)
• Stochastic Class-Based Hard Example Mining for Deep Metric Learning (CVPR 2019 · similarity 0.86)
• A Theoretically Sound Upper Bound on the Triplet Loss for Improving the Efficiency of Deep Distance Metric Learning (CVPR 2019 · similarity 0.85)
• Symmetrical Synthesis for Deep Metric Learning (AAAI 2020 · similarity 0.84)
• How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings (ICLR 2025 · similarity 0.82)
• Collapse-Aware Triplet Decoupling for Adversarially Robust Image Retrieval (ICML 2024 · similarity 0.82)