Abstract: Deep learning excels at capturing complex data representations, yet quantifying the discriminative quality of these representations remains challenging. While unsupervised metrics often assess pairwise sample similarity, classification tasks fundamentally require class-level discrimination. To bridge this gap, we propose a novel loss function that evaluates representation discriminability via the Euclidean distance between the learned similarity matrix and the true class adjacency matrix.We identify random consistency—an inherent bias in Euclidean distance metrics—as a key obstacle to reliable evaluation, affecting both fairness and discrimination. To address this, we derive the expected Euclidean distance under uniformly distributed label permutations and introduce its closed-form solution, the Pure Square Euclidean Distance (PSED), which provably eliminates random consistency. Theoretically, we demonstrate that PSED satisfies heterogeneity and unbiasedness guarantees, and establish its generalization bound via the exponential Orlicz norm, confirming its statistical learnability.Empirically, our method surpasses conventional loss functions across multiple benchmarks, achieving significant improvements in accuracy, $F_1$ score, and class-structure differentiation. (Code is published in https://github.com/FeijiangLi/ICML2025-PSED)

Lay Summary:

Deep learning is powerful because it can learn meaningful patterns from data. Traditionally, researchers have measured this ability by comparing how similar individual samples are to each other. However, for tasks like classification, what matters more is whether the model can distinguish between entire categories of data—not just individual examples. In this paper, we propose a new way to evaluate deep learning models by measuring how well their learned patterns align with the true class structure of the data. We also identify and correct for random biases that can skew these evaluations. Our method provides a mathematically sound and unbiased measure, leading to more reliable model assessments. Experiments show that it improves accuracy and helps models better separate different classes.