Extreme Classification (XC) architectures, which utilize a massive One-vs-All (OvA) classifier layer at the output, have demonstrated remarkable performance on problems with large label sets. Nonetheless, these architectures falter on tail labels with few representative samples. This phenomenon has been attributed to factors such as classifier over-fitting and missing label bias, and solutions involving regularization and loss re-calibration have been developed. This paper explores the impact of label variance - a previously unexamined factor - on the tail performance in extreme classifiers. It also develops a method to systematically reduce label variance in XC by transferring the knowledge from a specialized tail-robust teacher model to the OvA classifiers. For this purpose, it proposes a principled knowledge distillation framework, LEVER, which enhances the tail performance in extreme classifiers with formal guarantees on generalization. Comprehensive experiments are conducted on a diverse set of XC datasets, demonstrating that LEVER can enhance tail performance by around 5\% and 6\% points in PSP and coverage metrics, respectively, when integrated with leading extreme classifiers. Moreover, it establishes a new state-of-the-art when added to the top-performing Renee classifier. Extensive ablations and analyses substantiate the efficacy of our design choices. Another significant contribution is the release of two new XC datasets that are different from and more challenging than the available benchmark datasets, thereby encouraging more rigorous algorithmic evaluation in the future. Code for LEVER is available at: aka.ms/lever.

Deep Neural Networks (dnns) are known to make over-confident mistakes, which makes their use problematic in safety-critical applications. State-of-the-art (sota) calibration techniques improve on the confidence of predicted labels alone, and leave the confidence of non-max classes (e.g. top-2, top-5) uncalibrated. Such calibration is not suitable for label refinement using post-processing. Further, most sota techniques learn a few hyper-parameters post-hoc, leaving out the scope for image, or pixel specific calibration. This makes them unsuitable for calibration under domain shift, or for dense prediction tasks like semantic segmentation. In this paper, we argue for intervening at the train time itself, so as to directly produce calibrated dnn models. We propose a novel auxiliary loss function: Multi-class Difference in Confidence and Accuracy (mdca), to achieve the same. mdca can be used in conjunction with other application/task specific loss functions. We show that training with mdca leads to better calibrated models in terms of Expected Calibration Error (ece), and Static Calibration Error (sce) on image classification, and segmentation tasks. We report ece (sce) score of 0.72 (1.60) on the cifar 100 dataset, in comparison to 1.90 (1.71) by the sota. Under domain shift, a ResNet-18 model trained on pacs dataset using mdca gives a average ece (sce) score of 19.7 (9.7) across all domains, compared to 24.2 (11.8) by the sota. For segmentation task, we report a 2× reduction in calibration error on pascal-voc dataset in comparison to Focal Loss [32]. Finally, mdca training improves calibration even on imbalanced data, and for natural language classification tasks.