Set Learning for Accurate and Calibrated Models
Authors: Lukas Muttenthaler
Robert A. Vandermeulen
Qiuyi Zhang
Thomas Unterthiner
Klaus Robert Muller
Venue: ICLR 2024 poster (2024)
Keywords: set learning
calibration
overconfidence
class imbalance
long-tailed classification
low data
classification calibration
safety
Primary area: general machine learning (i.e., none of the above)
TL;DR: We introduce odd-k-out learning (OKO), a novel, theoretically grounded training framework for classification based on learning from sets of data to yield accurate and well-calibrated models, even in low data regimes.

Abstract: Model overconfidence and poor calibration are common in machine learning and difficult to account for when applying standard empirical risk minimization. In this work, we propose a novel method to alleviate these problems that we call odd-$k$-out learning (OKO), which minimizes the cross-entropy error for sets rather than for single examples. This naturally allows the model to capture correlations across data examples and achieves both better accuracy and calibration, especially in limited training data and class-imbalanced regimes. Perhaps surprisingly, OKO often yields better calibration even when training with hard labels and dropping any additional calibration parameter tuning, such as temperature scaling. We demonstrate this in extensive experimental analyses and provide a mathematical theory to interpret our findings. We emphasize that OKO is a general framework that can be easily adapted to many settings and a trained model can be applied to single examples at inference time, without significant run-time overhead or architecture changes.

Published as a conference paper at ICLR 2024
SET LEARNING FOR ACCURATE AND CALIBRATED MODELS
Lukas Muttenthaler! 123.", Robert A. Vandermeulen 122"" Qiuyi (Richard) Zhang', Thomas Unterthiner", and Klaus-Robert Müller
Machine Learning Group, Technische Universität Berlin, Germany Berlin Institute for the Foundations of Learning and Data, Berlin, Germany Google DeepMinn
Department of Artificial Intelligence, Korea University, Seoul Max Planck Institute for Informatics, Saarbrücken, Germany
ABSTRACT
Model overconfidence and poor calibration are common in machine learning and difficult to account for when applying standard empirical risk minimization. In this work, we propose a novel method to alleviate these problems that we call odd-k-out learning (OKO), which minimizes the cross-entropy error for sets rather than for single examples. This naturally allows the model to capture correlations across data examples and achieves both better accuracy and calibration, especially in limited training data and hass-imbalanced regimes. Perhaps surprisingly. OKO often yields better calibration even when training with hard labels and dropping any additional calibration parameter tuning, such temperature scaling. We demonstrate this in extensive experimental analyses and provide a mathematical theory to interpret our findings. We emphasize that OKO is a general framework that can be easily adapted to many settings and a trained model can be applied to single examples at inference time, without significant run run-time overhead or architecture changes.
INTRODUCTION
In machine learning, a classifier is typically trained to minimize cross-entropy on individual examples rather than on sets of examples. By construction, this paradigm ignores information that may be found in correlations between sets of data. Therefore, we present odd-k-out learning (OKO), a new training framework based on learning from sets. draws inspiration from the odd-one-out task which is commonly used in the cognitive sciences to infer notions of object similarity from human decision-making processes (Robilotto Zaidi 20044 Fukuzawa al., 1988 Hebart et al. 2020 Muttenthaler et al., 2022 2023a). The odd-one-out task is a similarity task where subjects choose the most similar pair in a set of objects. We use an adapted version of that task to learn better model parameters while not making any changes to the architecture (see Fig. [ a).
Standard classification training often yields overconfident classifiers that are not well-calibrated Mülleer et al. [0119] Guo et al.] 2017 Minderer et al. 2021). Classically, calibration has been treated as an orthogonal problem to accuracy. Miscalibration has been observed to severely worsen while accuracy improves, interesting phenomenon attributed over- wver-parametrization reduced regularization, and biased loss functions (Guo et al. 2017] Vaicenavicius et al. 2019 Roelofs et al.) proper scoring rule to better classification accuracy at the expense of well-calibrated probabilities (Guo et al. 2017 Roelofs et al.] 2022). Other scoring rules were proposed that are differentiable versions of calibrative measures but these approximations can be crude (Karandikar et al. 2021). Thus, calibration methods are often treated as an afterthought, comprised of ad-hoe proce-rrcessing procedures that require an additional hold-out dataset and monotonically transform the output probabilities, usually without affecting the learned model parameters or accuracy.
2022). Even log-likelihood-
accused of biasing network weights
"quual contributions.
Work partly done while Student Researcher at Google DeepMind.

---

Published as a conference paper at ICLR 2024
Calibration is inherently performance metric on sets of data; propose training the classifier on sets of examples rather than individual samples to find models that yield accurate calibration without ad-hoc post-processing. This is especially crucial in low-data and class- buss-imballnced settings, for which there is surprisingly little work on calibration (Dal Pozzolo et al. 2015b).
Various techniques have been proposed to improve accuracy for imbalanced datasets (Branco et al. Dohnson & Khoshgoftaar (019). which are typically based on non- non-uniform class sampling or reweighting of the loss function. However, neural nets can still easily overfit to the few training examples for the rare classes (Wang & Japkowicz 2004). There is growing interest in the development
al. 202T Parisot et al. 2022; Guha Roy et al.) (022). Such techniques are adapted variants of non- uniform sampling, often focusing exclusively on accuracy, and ignoring model calibration. However, tech- niques for mitigating the effects of imbalance on classification accuracy do not improve calibration for minority instances and standard calibration procedures tend to systematically underestimate the probabilities for minority class instances (Wallace & Dahabreh] 2012). Moreover, it is widely known that direct undersampling of overrepresented classes modifies the training set distribution and intro- duces probabilistic biases (Dal Pozzolo et al., 2015a). Bayesian prior readjustments were introduced to manipulate posterior probabilities for ameliorating that issue (Dal Pozzolo et al.) 2015b).
of new techniques for handling class imbalance (Johnson & Khoshgoftaar 2019; Iscen Iscen
It is known that hard labels tend to induce extreme logit values and therefore cause overconfidence in model predictions (Hinton et al. 2015 Bellinger et al., 2020). Label smoothing has been proposed to improve model calibration by changing the cross-entropy targets rather than scaling the logits after training (Müller et al. 2019; Carratino et al. 2022). Label smoothing, in combination with batch balancing- uniformly sampling over the classes rather than uniformly sampling over all samples in the data (see Appx. [B.)). achieves promising results on heavy-tail classification benchmarks, i.e. datasets that contain many classes with few samples and few classes with many samples (Bellinger et al. (020).. Yet, all these methods ignore the need for accuracy on the underrepresented classes, generally lack rigorous theoretical grounding, and require fine-tuned parameters for good empirical performance, such as the noise parameter for label smoothing, or the scaling parameter for temperature scaling for which additional held-out data is required.
In contrast to the popular philosophy of training for accuracy and then calibrating, we pose our main question: Can we provide a training framework to learn network parameters that simultaneously obtain better accuracy and calibration, especially with class imbalance?
Contributions.
Indeed, we find that OKO achieves better calibration and uncertainty estimates than standard cross-entropy training. The benefits of OKO over vanilla cross-entropy even more pronounced in limited training data settings and with heavy-tailed class distributions.
Empirical. First, through extensive experiments, show that OKO often achieves better accuracy while being better or equally well calibrated than other methods for improving calibration, especially in low data regimes and for heavy-tailed class distribution settings (see Fig. [ b). Second, OKO is principled approach that changes the learning objective by presenting a model with sets of examples instead of individual examples, as calibration is inherently metric on sets. As such, OKO does not introduce additional hyperparameters for post-training tuning or require careful warping of the label distribution via a noise parameter as in label smoothing (see Fig. D.. Third, surprisingly, this differently posed set learning problem results in smoothed logits that yield accurate calibration, although models are trained using hard labels. Fourth, we emphasize that OKO is extremely easy to plug into any model architecture, as it provides general training framework that does not modify the model architecture and can therefore be applied to single examples at test time exactly like any network trained via single-example learning (see Fig. [ a). The training complexity scales linearly in O(SI) where [S] denotes the number of examples in a set and hence introduces little computational overhead during training. Last, in sho- settings, OKO achieves compellingly low calibration and classification errors (see Fig. b). Notably, OKO improves test accuracy for 10-shot MNIST by 8.59% over the best previously reported results (Liu al. 2022).
Theoretical. To get a better understanding of OKO's ' exceptional calibration performance, we offer mathematical analyses that show why OKO yields logit values that are not strongly encouraged to diverge as in vanilla cross-entropy training. We develop a new scoring rule that measures excess confidence on a per-datapoint basis to provably demonstrate improved calibration. This scoring rule
'A JAX implementation of OKO is publicly available at: httpp:///g whtb.ccom/lukasaet///o
2

---

Published as a conference paper at ICLR 2024
A Oko
Training
Inference
softmax SoftmaxCxEsf(
softmax(f(
Standard
softmax(f(
))
softmax(f(
B
MNIST
FashionMNIST
CIFAR-10 10
CIFAR-100
D60
Day
0.2
0.2
Uniform
Expected Callbration Error Expected Callbration
0.15
1960
0.15
10:0
0.15
6.15
0.1
0.3
D.1
0.1
0.05
0.05
0.05
0.05
98
Heavy tailed
0.3
0:45
0.45
0.2
0.3
0.3
0.1
0.1
0.15
0.15
0.2 0.4
0.0
6.3
0.3
0.4
35
022
0.3
0,4
0.5
08
0.7
8.75
0.8
0.85
0.0
0.95
3.0
Test classiffftatt
classification
classification
classification
Figure I: OKO minimizes cross- entropy on sets examples rather than on single examples and naturally yields smoothed logits after training. At inference time it can be applied to single examples without additional computational overhead. B: Expected calibration error as a function of the classification error. Each point in the graph represents the performance of single seed; there five for every number of training data points. For each dataset, every model was evaluated on the test Dashed diagonal lines indicate linear regression fit. Top: Uniform class distribution during training. Bottom: Heavy- class distribution during training.
compares the predictive entropies and cross-entropies, and for calibrated predictors, we show that our measure is consistent in that the average excess confidence is O. By using this new scoring rule demonstrate that OKO implicitly performs a form of entropic regularization, giving insight into how prevents excess confidence in certain low entropy regions.
RELATED WORK
The odd-one-out task has been widely used in the cognitive sciences to infer notions of object similarity from human participants (Robilotto & Zaidi 2004 Hebart et al. 22020) Mutienthaler et al. 2022] 2023a), and first uses are slowly percolating into machine learning: Fernando et al. (2017) trained self-supervised video understanding network by predicting which
of three sequences was in reverse time order, Locatello et al. 2020); Mohammadi et al. (2020) used comparisons between samples as weak supervision target. Muttenthaler al. al. (2023b) use human odd-one-out choices to improve pretrained representations for few-shot learning and anomaly detection tasks. However, none of these works investigated calibration or provided any theory for (odd-one-out) set learning.
Improving calibration is of practical interest for many applications. However, deep neural networks often appear badly calibrated (Guo et al. 2017). 7). Even though this depends on the concrete architecture used, scaling up model usually increases accuracy the cost of calibration (Minderer et al.) 2021)
Many post-hoc approaches to increase calibration have been proposed, such as temperature scalin Saaling (Platt et al. 1999), isotonic regression (Zarrzzyy & Elkan| 2002) Nicullscuuueiiii & Caruanal 2005). and Bayesian binning (Nacini et al. 2215)). while improving calibration during training is a less ex explored topic. Most related to approach are techniques that data augmentations that blend
3

---

Published as a conference paper at ICLR 2024
ensembles to combine representations (Lakshminraayaaan et al. 2017). However, none of these works examined calibration for sets of data. The task of classifying sets of instances is known multiple instance learning (Carbonneau
different imputs together Thulasidasan et al. 2019)
eet al., 2018). It is desirable to leverage the set structure, instead of simply using a concatenated A common approach is pool representations, either by mean pooling, which is akin to OKO, or max pooling (Feng & Zhou| 2017 Pinheiro & Collobert
representation of the examples in each
2014). Other approaches include the use of permutation invariant networks (aheer al. (017) or
attention mechanisms (llse et al. 2018 Cordonnier et al. 202T). Also related are crror-corg
output codingDietterich & Bakir (1955), which looks multiclass classification by training several
different binary classifiers. We are unaware of work that leverages set learning for improving the
calibration of standard cross-entropy training.
Learning from imbalanced data has long history in machine learning (Japkowicz & Stephen 2002
He & Garcial 2009 Branco et al. (016). Approaches usually center around resampling the training
data (Chawla et al.
2002; Drummond & Holte
2003
Liu et al.] 2009) modifying the loss function
(Chen et al. 2004
Ting
2000; Wallace et al.
201 Khan et al. 2018 Cui et al., 2019; Lin et al.
2020 Du et al. 2023), or combinations thereof (Huang al. [0166] Liu al. 2019 Tian al. 2022).
Transter learning [Wang et al. [017 [hong et al.
2 Parisot et al. 2. self-superr supe--ueeeiiee learning
(Yang& & Xu 22000; Kang et al. [202]] ). ensembles of experts (Collell al. 2018 Wang et al. 2021
Guha Roy et al. 2022] Cui et al. 20033 Jiang et al.) 2023) can also be helpful for rare classes. Our
method is novel way to improve performance on imbalanced data at excellent calibration.
METHOD
Here we present the core contribution of this work, odd-k-out training (OKO). In OKO a model is simultaneously presented with multiple data points. At least two of these data points are from the same class, while the remaining & data points are each from a different class, i.e., the odd-k-outs, or odd classes. The objective is to predict the pair class. This forces model to consider correlations between sets of examples that would otherwise be ignored in standard. single-example learning.
Notation. More formally, we are interested in the classification setting on training set D { B1.,... ...., (I }n)} C IRd x [C] of inputs I; and labels from C' classes. The number of odd classes le is chosen such that le + S C. We construct an OKO training example as follows:
Let X be the set of all training inputs, Zi, such that = c. One first, uniformly at random, selects a label y' [C] and sets y = v/2 = yy as the pair class. Next v/...., V/42 are sampled uniformly without replacement from [C] \ { as the odd classes. Finally o zi...., _ 2444 are selected uniformly random from K ................................ Ky 12' while enforcing 21 # x/y. So 24 and xz have the same class label, y and x/y,
24 all have unique class labels not equal to y'. training example is then S = (a*), v(), ..., (a 2 2)) Let S. := (z'j..., xk42) and S, (6f....,4445)) Alg.
describes the sampling process. The distribution of S according Alg. Tis st.
Algorithm oo OKO set sampling
Input: D. C.
is the number of classes and is the number of odd classes
Output: Sy,Sy, y/ y' 1 (CC)
Sample pair class for constructing the set
Di V' y
Vá. ........ v442
NR
u (v))
>> Sample k odd classes without replacement
for = k....,k 2
I + - (x,,)
Choose representative input for each of the k + 2 set members
end for
S, t (s/,..., xb42) Syy x ( v(42)
4

---

Published as a conference paper at ICLR 2024
OKO objective For tuple of vectors, Sz (d),...,,<443 2242) and neural network function fo parameterized by 0, we define fo(Sa) = =iin so (x() and the following soft loss for fixed set S:
2+
oko (Sy So (Sx)) -(1: + +2
v log (softmax (So (Sx)));
where e, E IRC is the indicator vector at index a and softmax denotes the softmax function. The soft loss encourages model to learn the distribution of all labels in the set S. One may also consider the case where the network is trained to identify the most common class y', yielding the hard loss:
ghard (Sy, fo (Sx)) == ey log [softmax (fa(Sz))
(2)
In ablation experiments, we found the hard loss to always outperform the soft loss and have thus chosen not to include experimental results for the soft loss in the main text (see Fppx. further de- tails). For OKO set sampling, S (S2:S,) Sy) ~ st, the empirical risk is Es-ot &ooo (Sy, fo (Sx))
4 PROPERTIES OF OKO
Here we theoretically analyze aspects of the OKO loss that are relevant to calibration. First, via rigor- ous analysis of simple problem setting, we demonstrate that OKO implicitly performs regularization by preventing models from overfitting to regions with few samples, thereby lowering certainty for predictions in those regions. We refer to these regions as low-entropy regions, where, for all inputs in such a region, p(y(ær has most of its probability mass assigned to one class. Second, we introduce and analyze novel measure for calibration that is based the model output entropy rather than label entropy. This has the advantage of directly examining the cross- tross-entropy error as function of the model uncertainties and evaluate its correspondence. Additionally, in Appx. C we include an analysis of simplified loss landscape of OKO, and show that it less strongly encourages logit outputs to diverge compared to vanilla cross-entropy, while allowing more flexibility than label smoothing.
OKO is less certain in low-data regions. Imagine a dataset where the majority of the data is noisy. Specifically, most of the data share the same feature vector but have different class labels one- feature-to-munn tone--toommn--lsssee and each class has O < < 1 fraction of data points in a low-entropy region in which the data points are clustered together by one class label - many-aaaaaa secutturesttoooe-clle
In such high-noise dataset it is likely that the low-entropy regions are mislabeled. If fo has high capacity and was fitted via vanilla regression, it would overfit to low-entropy regions by classifying them with high certainty since those examples are well-separated from the noise. As mentioned in the previous section, even label smoothing only slightly alleviates overfitting (Müller et al. 2019).
A simple example should illustrate the previously mentioned setting: We will demonstrate that, for this example, the OKO method assigns low certainty to low-entropy regions. To this end we will consider a binary classification problem set of all functions in {0, 1, + R², this is analogous to the space of all possible models that can be used to classify, e.g., fo from before.
input space consisting of three elements. Let F be the
Now let d with e E [0,1] be defined as in Alg. I where the proportion of the training data, (51,81),.... (1,, yn). having specific values is defined in Table [
Note that n does not matter for the results that we present here.
For < this indicates that the vast majority of the data has r = 0 with equal probability of both labels. The remainder of the data is split between x and x = 2 where the label always matches the feature and is thus a zero-entropy region. For this setting, we introduce the following theorem which we proof in Appx. D
Y/ =
y/ = 2
5. =0
(1
e)/2
(1 -t) e
34
6/2
0
T; =
0
c/2
Theorem 1. For all e E (0, 1) there exists fe such that
Table 1: PMF for Theorem i
fe E arg min Esnat [Maardd (Sy, fo (S.)))
fer
Furthermore, for any collection of such minimizers indexed by 6, fc. as E + 0. then softmax (Je (0) //2, 1/2), softmax (Se (1)) + [2/3, 1/3), and softmax (Je (2)) (1/3,2/3).
5

---

Published as a conference paper at ICLR 2024
The key from Theorem is that, although or 2 have entropy and are low-entropy regions, OKO is still uncertain about these points because they occur infrequently. This may be interpreted as the network manifesting epistemic uncertainty (label uncertainty in input region due to having few training samples) as aleatoric uncertainty (uncertainty in an input region due to the intrinsic variance in the labels for that region) in the OKO test time outputs. The desirability of this property may be somewhat dependent on the application. While it is conceivable that such regions do indeed have low aleatoric uncertainty, and that the few samples do indeed characterize the entire region, for safety-critical applications it is often desirable for the network to err towards uncertainty.
Relative Cross-Entropy for Calibration. We introduce an entropy- measure of sample calibration and demonstrate empirically that is a useful measure of calibration, along with theoretical justification for its utility. sense, our measure is inspired by the ogglikkllhhod scoring function and is normalized scoring rule that gives sample-wise probabilistic insight (for details see Appx. F
Definition 1. Let the relative cross-entropy of distributions P, Q be RC(P, Q) = H(P, Q) - HQ))
Since RC can be computed for each (y. j) datapoint, it is scoring rule. The relative cross- cross-entropy is very similar to KI. divergence but with different entropy term. However, unlike the KI. divergence, it not always non-negative. In fact, note that if an incorrect prediction is overconfident, then RC 1)) + oc is extremely positive, implying that RC' captures some measure of excess confidence. Specifically, we can show when the predictions are inaccurate, we have a provable deviation.
Lemma 1. For hard labels y. if e S 1/|C), then RC 1) 2
Furthermore, show that RCC captures some notion of calibration when averaged across all data points. Specifically, when a predictor is perfectly calibrated, its average RC, a measure of excess confidence, should be O. Note that RC is no longer proper due to this zero mean.
Lemma 2. If ÿ is a predictor that is perfectly calibrated across D. then the average excess confidence, as measured by relative cross-entie entropy B(p.))-/RRC(y [(x)) =0 0
EXPERIMENTAL RESULTS
In this section, we present experimental results for both generalization performance and model calibration. In general, model calibration and generalization performance are orthogonal quantities. classifier can show strong generalization performance while being poorly calibrated, and, vice versa, classifier can be well-calibrated although its generalization performance is weak. Here, we are equally interested in both quantities.
Experimental details. For every experiment we present in this section, we use simple randomly- initialized CNN for MNIST and FashionMNIST and ResNet18 and ResNet34 architectures (He al., 2016) for CIFAR-10 and CIFAR- 100 respectively. We use standard SGD with momentum and schedule the learning rate via cosine annealing. We select hyperparameters and train every model until convergence on held-out validation set. To examine generalization performance and model calibration in low data regimes, we vary the number of training data points while holding the number of test data points fixed. We report accuracy for the official test sets of MNIST, FashionMNIST, CIFAR-10, 10, and CIFAR-100. We are specifically interested in heavy-tailed class distributions. Since heavy-tailed class distributions are a special rather than a standard classification setting, we report experimental results for both uniform and heavy-tailed class distributions during training. We consider heavy-tailed class distributions with probability mass p = 0.9 distributed uniformly across three overrepresented classes and (1 p) = 0.1 distributed across the remaining 7 or 97 underrepresented classes respectively. In ablation experiments we have seen that, although odd class examples are crucial, OKO is not sensitive to the particular choice of & (see App. F.4). Therefore, we set k in OKO to for all experiments. Note that &- = 1 results in the computationally least expensive version of OKO. Since preliminary experiments have shown that generalization performance can be boosted by predicting the odd class using an additional classification head, in the following we report results for version of OKO with k where in addition to the pair class prediction (see Eq. 2 model is trained to classify the odd class with a second classification head that is discarded at inference time.
For simplicity and faimess of comparing against single example methods, set the maximum number of randomly sampled sets to the total number of training data points Aurain in every setting. This is guaranteed to yield the same number of gradient updates as standard cross-entropy training.

---

Published as a conference paper at ICLR 2024
Training methods. Alongside OKO, consider six different baseline methods for comparing
generalization performance and seven different methods for investigating model calibration: 1.)
Standard maximum-likele -iiuuumm-iielihoodd estimation (see Eg. in Appx. [.I].......... 2.) Vanilla label smoothing (LS;
Müller et al. 2019). 3.) Focal Loss (Lin et al. 2017) ). 4.) Cross-entropy error reweighting (see Eq.
in Appx. [8.2 5.) Batch-balancing (BB; see Alg. 2 in Appx. [B3). 6.) BB L.S. 7.) BB temperature
scaling (TS; = 2.0). We consider label smoothing because it yields significantly better calibration than using hard labels for training neural nets and equivalent model calibration temperature scaling (Müller et al. 2019). We deliberately ignore temperature scaling for generalization performance analyses because does not change the arg max of a classifier's predicted probability distribution after training and therefore yields the same test accuracy as BB.
MNIST
FashionMNIST
CIFAR-10 10
CIFAR-100
Test (%)
100
90
80
45
Uniform
95
80
35
Vanila
Va L5
50
Weighted CE
Focaliine
40
15
15
80
1000
75
700
993
490
500
1853
9933
106ce
30
420
500
1000
5003
10000
70000
20
3993
10800
70303
5000
100
70
95
85
Heavy -tiled
Test accuracy
90
80
40
73
65
30
70
60
1000
1000
206
300
400
900
3000
S282 10000
20
2008 5063 10000 20000
seco
10000
20000
33200
Number of training data points
Number of training data points
Number of training data points
Number of training data points
Figure 2: Test set accuracy in % as a function of different numbers of data points used during training. Error bands depict 95% Cls and computed over five random seeds for all training settings and methods. Top: Uniform class distribution during training. Bottom: Heavy-tailed class distribution.
Generalization. For both uniform and heavy-tailed class distribution settings, OKO either outper- forms or performs on par with the best baseline approaches considered in our analyses across all four datasets (see Fig. 2 We observe the most substantial improvements over the baseline approaches for both balanced and heavy-
MNIST, heavy-tailed FNSHi and balanced CIFAR- 10 and CIFAR-100. For 10-shot MNIST OKO achieves average test set accuracy of 87.62%, with the best random seed achieving 90. 94%. This improves upon the previously reported best accuracy by 8.59% (Liu et al. 2022). For 20-shot and 50-shot MNIST, OKO improves upon the previously reported best test set accuracies by 2.85% and 1.81% respectively (Liu et al. 2022). OKO achieves the strongest average generalization performance across all datasets and class distribution settings (see Tab, 2). Improvements over the other training methods are most substantial for heavy-tailed training settings.
Table 2: Test set accuracy averaged across all training settings shown in Fig.
MNIST heavy-tailed
MashionMMIST heavy-tailed
CIFAR-I0
CIFAR-100
Training Distribation
uniform
uniform
uniform
heavy-tailed
uniform
heavy-tailed
Vanilla
34%
78.21%
81.05%
68. 16%
55.84%
30.24%
32.72%
02.68%
Vanilla + LS
91.84%
77.38%
81.10%
66.46%
55.06%
27.16%
31.20%
02.62%
Weighted CF
18%
71.45%
55.74%
33.76%
32.42%
Focal Loss (in et 2017
90.98%
76.42%
13%
69.86%
54.39%
33.89%
32.72%
05.98%
BB
92.31
81.42%
81.11%
71.24%
55.87%
44.69%
32.63%
13.67%
BB LS
91.86%
80.81%
81.
71.13%%
54.96/%
44.72%
31.26%
13.96%
OKO (ours)
93.62%
85.67%
81.49%
74.02%
57.63%
44.95%
35.11%
14.13%
Calibration. We present different qualitative and quantitative results for model calibration. Although model calibration is an orthogonal quantity to generalization performance, it is equally important for the deployment of machine learning models.
Reliability. The reliability of a model can be measured by looking at a model's accuracy as a function of its confidence. An optimally calibrated classifier is model whose predicted class is
7

---

Published as a conference paper at ICLR 2024
correct with probability (1()), where (o(2)) is the confidence of a model's prediction, i... optimal calibration occurs along the diagonal of a reliability diagram (see Fig.3). OKO's 's reliability lies along the diagonal substantially more often than to any competing method. This is quantified by lower Expected Calibration Errors (see Fig. I
T0P of OKO compared to the other methods. Its calibration is on par with BB L.S or BB 'S in some settings. In Fig. 3 we show reliability diagrams for MNIST, FashionMNIST. CIFAR-10, and CIFAR-100 averaged over all training settings using a uniform class distribution. Reliability diagrams for the heavy-tail training settings can be found in Appx. F
Uncertainty. Entropy is a measure of uncertainty and therefore can be used to quantify the confi- dence of classifier's prediction. Here, we examine the distribution of entropies of the predicted probability distributions for individual test data points as function of (in-)correct predictions. An optimally calibrated classifier has much density at entropy close log 1
Wode
Prea
ZERD N. 1500 o
NNIST
and little density at en-
tropy close to log for cor- rect predictions, and, vice versa, small density at en-
Conficecce
Wolls vasit
Vagheec
Dach-sannciogtthooo de 18 0546021-U
Rashion
Accurasy
tropy close to log 1 and much density at entropy close to log C/ for incorrect predictions, irrespective of whether classes were the tail or the mode of the train-
Confidence
CIARR110
Accurasy
ing class distribution. In
Fig. 4 we show the distri-
Confidence
bution of entropies of the models' probabilistic out- puts partitioned into correct and incorrect predictions spectively for MNIST and FashionMNIST across all training settings with heavy- tailed class distributions. We observe that label smoothing does alleviate the overconfidence problem to some extent, but is worse calibrated than OKO. More entropy visualizations can be found in Appx. F
Wodes Kedda (51ge0
WilMeate
healins
M. 21700022 ORLeERIN
CIFAR-100 Accuracy
Conficecce
Figure 3: Reliability diagrams for balanced datasets. Confidence and accuracy scores were averaged over random seeds and the number of training data points. Dashed diagonal lines indicate perfect calibration.
ECE. ECE is a widely used scoring rule to measure a classifier's calibration. complementary to reliabil-
Senlii (KGewat) Wessesee
Kart bet INStRUIN LESCNEES as TE Hell)
Uncurtaitty
MNIST
ity diagrams (see Fig. 3) in
Prodiction
that it quantifies the reliabil- ity of a model's confidence with single score, whereas reliability diagrams quali- latively demonstrate model calibration. A high ECE indicates poor calibration, whereas a classifier that achieves a low ECE gen- erally well-calibrated. Aside from CIFAR-100 where batch-balancing in combination label smoothing shows slightly lower ECEs than OKO, OKO achieves lower ECE scores than any other method across training settings (see Fig. in and Fig 10 in Appx.
Velti 1a
wesmercc ct
so 15
FazhionMNIST
Uncurtainty
kejo
Prediction
Figure 4: Here, we show the distribution of entropies of the predicted probabil- ity distributions for individual test data points across all heavy- training settings partitioned into correct and incorrect predictions respectively.
RC. Here, we demonstrate empirically that our novel entropy-based measure of datapoint calibration is useful measure of calibration. Following Def. [ and Lemma 2 in $
we quantify the average excess confidence RC (y. (())) by measuring the mean absolute difference (MAE) between (P,, Q) and (Q) for the different number of training data point settings (see Fig. 5). We find that OKO
8

---

Published as a conference paper at ICLR 2024
Table 3: MAE between entropies and enossppetropies averaged over the entire test set for different numbers of training data points. Lower better and therefore bolded.
MNIST heavy-tailed
FashionMNIST
CIFAR-10
CIFAR-100
Training Distribution
uniform
heavy-tailed
uniform
heavy-tailed
uniform
beavy-tailed
Vanilla
0.189
0.455
1,075
0,330
1.845
0.708
2.638
Vanilla 1.S
0.475
0.342
0.243
0.119
0.230
1.158
0.236
2.171
Weighted CE
0.207
0.558
0,505
0.758
0.315
0,366
0.705
0.189
Focal Loss (in 2017
0.308
0.222
0.296
0.198
BB
0.201
0.709
0.455
1.275
0,330
1.438
0.918
6.362
0.225
0.471
OKO (ours)
0.073
0.094
0.080
0.334
0.116
0.498
0.314
1,164
MNIST
FashionMNIST
CIFAR-10
CIFAR-100
705
p0/011
Den
20%
pornt
IVTA JOPn
302
402
1000
Uniform
1200
Lolve
R(( Q)
Taggie
LoWE
Alig
0.5
1.0
8.0
1.5
8.0
0.5
1.0
1.5
2.0log1101
8.0
1.0
2.0
3.0
log(100)
Heavy- tailed
H(P. Q)
6.0
0.5
1.0
1.5
0.5
1.0 H(Q)
1.5
8.0
0.5
1.0
1.5 2.0log(10)
8.0
1.0
2.0
3.0 lag(100)
H(Q)
A(Q)
A(Q))
Figure 5: For different numbers training data points, OKO achieves a substantially lower MAE for the average cross-entropy error between true and predicted class distributions and the average entropy of the predictions across both uniform and hcavy-tailed class distributions during training.
achieves the lowest MAE for all balanced training settings and is among the top-2 or top-3 training methods with the lowest MAE for the heavy-tailed training settings (see Tab.
6 CONCLUSION
In standard empirical risk minimization, a classifier minimizes the risk on individual examples; thereby ignoring more complex correlations that may emerge when considering sets of data. Our proposed odd-k-out (OKO) framework addresses this caveat - inspired by the odd-one-owt task used in the cognitive seiences (Hebart al., 2020 Muttenthaler al., 2022] 2023a). Specifically, in OKO, a classifier learns from sets of data, leveraging the odd-one-out task rather than single example classification (see Fig. [ We find that OKO yields well-calibrated model predictions, being better or equally well-calibrated as models that are either trained with label smoothing or whose logits are scaled with temperature parameter found via grid search after training (see $5). This alleviates the ubiquitous calibration problem in ML in more principled manner. In addition to being well-call call-caiiraaedd, OKO achieves better test set accuracy than all training approaches considered in our analyses (see Tab. Pp. Improvements are particularly pronounced for the heavy-tailed class distribution settings.
OKO modifies the training objective into classification problem for sets of data. We provide theoretical analyses that demonstrate why OKO yields smoother logits than standard cross-entropy, as corroborated by empirical results. OKO does not require any grid search over additional hyperparameter. While OKO is trained on sets, at test time can be applied to single examples exactly like any model trained via standard single example loss. The training complexity scales linearly in O(()) where |S] denotes the number of examples in a set and hence introduces little computational overhead during training.

---

Published as a conference paper at ICLR 2024
One caveat of OKO is that classes treated as semantically equally distant similar standard cross-entropy training. An objective function that better reflects global similarity structure may alleviate this limitation. In addition, remark that we have developed OKO only for supervised learning with labeled data. It may thus be interesting to extend OKO to self-supervised learning.
We expect OKO benefit areas that in need of reliable aleatoric uncertainty estimates but suffer from a lack of training data such as medicine, physics, or chemistry, where data collection is costly and class distributions are often heavy-tailed.
ACKNOWLEDGMENTS
LM, RV, and KRM acknowledge funding from the German Federal Ministry of Education and Research (BMBF) for the grants BIFOLD22B and BIFOLD23B. LM acknowledges support through the Google Research Collabs Programme. We thank Rodolphe Jenatton for helpful comments earlier version of the manuscript.
REFERENCES
Colin Bellinger, Roberto Corizzo, and Nathalie Japkowicz. Remix: Calibrated resampling for class imbalance in deep learning. arXiv preprint arXiv:2012.023/ 2020.
Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. arXiv preprint arXiv:221 161866, 2022.
Paula Branco, Luís Torgo, and Rita P Ribeiro. A survey of predictive modeling on imbalanced domains. ACM computing surveys (CSUR), 49(2):1-50, 2016.
Marc-André Carbonneau, Veronika Cheplygina, Eric Granger, and Ghyslain Gagnon. Multiple instance learning: A survey of problem characteristics and applications. Pattern Recognit., 77, 2018.
Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, and Jean-Philippe Vert. On mixup regulariza- tion. JMLR, 2022.
Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, and W. Philip Kegelmeyer. SMOTE: synthetic minority over-sampling technique. J. Artif. Int. Res., 16(1):321-357, jun 2002.
Chao Chen, Andy Liaw, and Leo Breiman. Using random forest to learn imbalanced data. Technical Report 666, Department of Statistics, UC Berkley, 2004.
Guillem Collell, Drazen Prelec, and Kaustubh R Patil. A simple plug-in bagging ensemble based on threshold-moving for classifying binary and multiclass imbalanced data. Neurocomputing, 275: 330-340, 2018.
Cordonnier, A. Mahendran, A. Dosovitskiy, D. Weissenborn, J. Uszkoreit, and T. Unterthiner. Differentiable patch selection for image recognition. In CVPR, 2021.
Jiequan Cui, Shu Liu, Zhuotao Tian, Zhisheng Zhong, and Jiaya Jia. Reslt: Residual learning for long-tailed recognition. IEEE Trans. Pattern Anal. Mach. Intell, 45(3):3695 2023.
Yin Cui, Menglin Jia, Tsung-Y. Yi Lin, Yang Song. and Serge Belongie. effective number of samples. In CVPR, 2019.
loss based on
Andrea Dal Pozzolo, Olivier Caelen, and Gianluca Bontempi. When is undersampling effective in unbalanced classification tasks? In ECML PKDD, 2015a.
Andrea Dal Pozzolo, Olivier Caelen, Reid A Johnson, and Gianluca Bontempi. Calibrating probability with undersampling for unbalanced classification. In IEEE Int. Symp. Comput. Intell. Inform., pp. 1659-166, 2015b.
Thomas G. Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. J. Artif. Int. Res., 2(1):263-286, jan 1995. ISSN 1076-9757.
10

---

Published as a conference paper at ICLR 2024
Chris Drummond and Robert Holte. C4.5, class imbalance, and cost sensitivity: Why under-sampling beats oversampling. PICML'03 Workshop on Learning from Imbalanced Datasets, 2003.
Fei Du, Peng Yang. Qi Jia, Fengtao Nan, Xiaoting Chen, and Yun Yang. Global and local mixture consistency cumulative learning for long- taig-taled visual recognitions. In CVPR, 2023.
Ji Feng and Zui-Hua Zhou. Deep miml network. In AAAI, 2017.
B. Fermando, H. Bilen, E. Gavves, and S. Gould. Self-supervised video representation learning with odd-one-out networks. In CVPR, 2017.
Dean P Foster and Sergiu Hart. Smooth calibration, leaky forecasts, finite recall, and nash dynamics. Games and Economic Behavior, 109:271-293, 2018.
Kazuyoshi Fukuzawa, Motonobu Itoh, Sumiko Sasanuma, Tsutomu Suzuki, Yoko Fukusako, and Tohru Masui. Internal representations and the conceptual operation of color in pure alexia with color naming defects. Brain and Language, 34(1):98-126 126,, 1988. ISSN 0093-934X.
Abhijit Guha Roy, Jie Ren, Shekoofeh Azizi, Aaron Loh, Vivek Natarajan, Basil Mustafa, Nick Pawlowski. Jan Freyberg. Yuan Liu. Zach Beaver, Nam Vo, Peggy Bui. Samantha Winter, Patricia MacWilliams Greg S. Corrado, Umesh Telang. Yun Liu, Taylan Cemgil, Alan Karthikesalingam, Balaji Lakshminarayanan, and Jim Winkens. Does your dermatology classifier know what it doesn't know? detecting the long-tail of unseen conditions. Medical Image Analysis, 75:102274, 2022.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. ICML, 2017.
Haibo He and Edwardo A. Garcia. Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering. (293):126-1228))) 2009.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image
recognition. In CVPR, 2016.
Martin N. Hebart, Charles Zheng, Francisco Pereira, and Chris I. Baker. Revealing the multidimen- sional mental representations of natural objects underlying human similarity judgements. Nature Human Behaviour, 4(11):1173-118 October 2020.
Geoffrey F. Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in a neural network. CoRR, abs/1503.02531, 2015.
Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for imbalanced classification. In CVPR, 2016.
Maximilian llse, Jakub Tomezak, and Max Welling. Attention-bass based deep multiple instance learning. In ICML, 2018
Ahmet Iscen, Andre Araujo, Boqing Gong, and Cordelia Schmid. Class-balanced distillation for long-tailed visual recognition. In BMVC, 2021.
Nathalie Japkowiez and Shaju Stephen. The class imbalance problem: A systematic study. Intell. Data Anal., 6(5):429-449 2002. ISSN 1088-467X.
Yuchang Jiang, Vivien Sainte Fare Garnot, Konrad Schindler, and Jan Dirk Wegner. Mixture of Experts with Uncertainty Voting for Imbalanced Deep Regression Problems. arXiv e-prints, art. arXiv:2305.15178. May 2023. doi: 10.48550/arxiw.23355..r 15178
Justin M. Johnson and Taghi M. Khoshgoftaar, Survey on deep learning with class imbalance. Journal of Big Data, 6(1), March 2019. doi: 011116//440037-019-99922
Sham M Kakade and Dean P Foster. Deterministic calibration and nash equilibrium. In COLT. Springer, 2004.
Bingyi Kang. Yu Li, Sa Xie, Zehuan Yuan, and Jiashi Feng. Exploring balanced feature spaces for representation learning. In ICLR, 2021.
11

---

Published as a conference paper at ICLR 2024
Archit Karandikar, Nicholas Cain, Dustin Tran, Balaji Lakshminarayanan, Jonathon Shlens, Michael C Mozer, and Becca Roelofs. Soft calibration objectives for neural networks. Advances in Neural Information Processing Systems, 11-29788-297777 2021.
Salman H. Khan, Munawar Hayat, Mohammed Bennamoun, Ferdous A. Sohel, and Roberto Togneri. Cost-sensitive learning of deep feature representations from imbalanced data. JEEE Trans. Neural Netw. Learn. Syst. 29(8):3573-3553 2018.
Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach. Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration. NeurlPS, 2019.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In NIPS, 2017.
Tsung-Y Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollar, Focal loss for dense object detection. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
Tsung-Yi Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár, Focal loss for dense object detection. IEEE Trans. Pattern Anal. Mach. Intell, 42(2):318-33 327, 2020.
Tao Liu, P. R. Kumar, Ruida Zhou, and Xi Liu. Learning from few samples: Transformation invvariant svms with composition and locality at multiple scales. In NeurIPS, volume 35, 2022.
Xu-Ying Liu, Jianxin Wu, and Zhi-Hua Zhou Exploratory undersampling for class-imbalance learning. IEEE Transactions on Systems, Man, and Cybernetics, 39(2):539-550, 2009.
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X. Yu. Large-scale long-tailed recognition in an open world. In CVPR, 2019.
Philipp Liznerski, Lukas Ruff, Robert A. Vandermeulen, Billy Joe Franks, Klaus Robert Muller, and Marius Kloft. Exposing outlier exposure: What can be learned from few, one, and zero outlier images. Transactions on Machine Learning Research, 2022. ISSN 2835-8856.
Francesco Locatello, Ben Poole, Gunnar Rätsch, Bernhard Schölkopf, Olivier Bachem, and Michael Tschannen. Weakly-supervised disentanglement without compromises. In ICML, 2020.
Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai Neil Houlsby, Dustin Tran, and Mario Lucic. Revisiting the calibration of modern neural networks. NeurIPS, 2021.
Salman Mohammadi, Anders Kirk Uhrenholt, and Björn Sand Jensen. Odd-one-out representation learning. ArXiv, abs/2012.07966 2020.
Rafael Müller, Simon Korbllihh, and Geoffrey E Hinton. When does label smoothing help? In NeurlPS, volume 32, 2019.
Lukas Muttenthaler, Charles Y Zheng, Patrick McClure, Robert A Vandermeulen, Martin N Hebart, and Francisco Pereira. VICE: Variational Interpretable Concept Embeddings. Advances Neural Information Processing Systems, 35:33661-333 -33675, 2022.
Lukas Muttenthaler, Jonas Dippel. Lorenz Linhardt, Robert A Vandermeulen, and Simon Kornblith. Human alignment of neural network representations. In ICLR, 2023a.
Lukas Muttenthaler, Lorenz Linhardt, Jonas Dippel, Robert A Vandermeulen, Katherine Hermann, Andrew K Lampinen, and Simon Kornblith. Improving neural network representations using human similarity judgments. arXiv preprint arXiv:2306.04500 2023b.
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated proba- bilities using bayesian binning. In AAAI, 2015.
Alexandru Niculescu- and Rich Caruana. Predicting good probabilities with supervised learning. In ICMI, 2005.
12

---

Published as a conference paper at ICLR 2024
Sarah Parisot, Pedro M. Esperança, Steven McDonagh, Tamas J. Madarasz, Yongxin Yang, and Zhenguo Li. Long-tail recognition via compositional knowledge transfer. In CVPR, 2022.
Pedro H. O. Pinheiro and Ronan Collobert. From image-level to pixel-level labeling with convolu- tional networks. CVPR, 2014.
John Platt al. Probabilistic outputs for support vector machines and comparisons regularized likelihood methods. Advances in large margin classifiers, 10(3):61-74, 1999.
Rocco Robilotto and Qasim Zaidi. Limits of lightness identification for real objects under natural viewing conditions. Journal of Vision, 4(9):9-9, 09 2004.
Rebecca Roelofs, Nicholas Cain, Jonathon Shlens, and Michael C. Mozer. Mitigating bias in calibration error estimation. In AISTATS, 2022.
Lukas Ruff, Robert A. Vandermeulen, Billy Joe Franks, Klaus-Rober Müller, and Marius Kloft. Rethinking Assumptions in Deep Anomaly Detection. arXiv e-prints, art. arXiv:2006.00339, May 2020. doi: 10.48550arrx..2206000333
Sunil Thulasidasan, Gopinath Chennupati, Jeff Bilmes, Tanmoy Bhattacharya, and Sarah Michalak. On Mixup Training: Improved Calibration and Predictive Uncertainty for Deep Neural Networks. 2019.
Changyao Tian, Wenhai Wang, Xizhou Zhu, Jifeng Dai, and Yu Qiao. VI-Itr: Learning class-wise visual-linguistic representation for long-tailed visual recognition. In ECCV, 2022.
Kai Ming Ting. comparative study of cost-sensitive boosting algorithms. In JCMI., 2000.
Juozas Vaicenavicius, David Widmann, Carl Andersson, Fredrik Lindsten, Jacob Roll, and Thomas Schön. Evaluating model calibration in classification. In AISTATS, 2019.
Byron C Wallace and Issa Dahabreh. Class probability estimates are unreliable for imbalanced data (and how to fix them). In ICDM, pp. 695-704, 2012.
Byron C. Wallace, Kevin Small, Carla E. Brodley, and Thomas A. Trikalinos. Class imbalance, redux. In ICDM, 2011.
Benjamin X Wang and Nathalie Japkowicz. Imbalanced data set learning with synthetic samples. In Proc. IRIS machine learning workshop, volume 19, pp. 435, 2004.
Xudong Wang, Long Lian, Zhongqi Miao, Ziwei Liu, and Stella X. Yu. Long-tailed recognition by routing diverse distribution-aware experts. In ICLR, 2021.
Yu-Xiong Wang, Deva Ramanan, and Martial Hebert. Learning to model the tail. In NIPS, 2017.
Yuzhe Yang and Zhi Xu. Rethinking the value of labels for improving class-imbalanced learning. In NeurlPS, 2020.
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass probabil- ity estimates. In KDD, pp. 694-699, 2002.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In NIPS, 2017.
Shengjia Zhao, Michael Kim, Roshni Sahoo, Tengyu Ma, and Stefano Emmon. Calibrating predictions to decisions: A novel approach multi-class calibration. NeurlPS. 2021.
Yaoyao Zhong, Weihong Deng, Mei Wang, Jiani Hu, Jianteng Peng. Xunqiang Tao, and Yaohai Huang. Unequal-training for deep face recognition with long-tailed noisy data. In CVPR, 2019.
13

---

Published as a conference paper at ICLR 2024
A OKO CLASSIFICATION HEAD
Here, we demonstrate how easily OKO can be applied to any neural network model in practice. irrespective of its architecture. OKO does not require additional set of parameters. OKO essentially just sum over the logits in a set of inputs. Below we provide JAX code for the classification head that is used for OKO. During training, logits obtained from the classification head summed across the inputs in a set. At inference time, the classification head is applied to single inputs just as any standard classification head.
import flax. linen as nn import jax.numpy numpy as inp from einops import rearrange from jax import vmap
Array jnp.ndarray
class OKOHeadd (nn. ModuMle
jum_classes: int # number of classes in the data
k: int number of odd classes in set
def setup(self) -> None:
self.clf nn. (self num_ccassses
self.scard self.k+2
card is number of odd classes 2
def set set_sun(self, x: Array) -> Array:
"""Aggregate the logits acress all examples in a set, rearrange (x, "(b scard) d -> scard d", scard=self scard) dcts (splfscf.clf, in_axes=,, out_axes=1) (x) set_ dots. sum (axis=1) set sum return set_logits
8nn. compact
def call (self, x: Array, train: bool) -> Array:
$ x Vin (b \times d)
if train:
logits self set_.setsumm (X_P)
else:
Logits self.clf(x)
return logits
Listing 1: OKO classification head implemented in JAX.
B BACKGROUND
B.1 PROBLEM SETTING
In the heavy-tailed class distribution setting, we are interested in the classification setting where classifier has access to training data D { V1) ,..., (.r.,,
C ıRd x [C] consisting inputs I; and labels from C' classes. For e E [C]. D. C D will denote those samples with label so D D= U c= De. Class imbalance occurs when [Del > |Dell for some and c'. Let e, E RC be the indicator vector at index a and softmax be the softmax function. Let pa. be the uniform empirical measure of 'D.
Cross-entropy. The cross-entropy error between the original and the predicted labels is the following risk function when averaged over all data points in the dataset D.
n
Cvanilla (D,0) -x,,))a (ey softmax (fo (X))
e log [softmax (fo())
In the class imbalanced setting optimizing Eq. 4 is known to produce classifiers that strongly favor common classes and are therefore likely to incorrectly label rare classes during test time. Here
14

---

Published as a conference paper at ICLR 2024
describe few methods designed to counteract this phenomenon, which will use competitors in our experiments.
B.2 ERROR RE- WEIGHTING
To counteract the fact that there are fewer terms in the summation in Eq. for rare classes, one may
simply weight those terms more greatly. Let fn.y (.) == j4n (R. x) )) be the empirical distribution over the class labels. In error re- weighting, the terms in Eq. aree weighted inversely to their class frequency, such that the contribution of sample in class e to the error decreases with its number of unique examples nlc.
(eieenegeee(DO)) = B(X,Y)a fley, softmax (fo
X
e
log (fftmaa((foxx:)) v.
Pa,y (Y)
11
Flg
where R is constant to bring the error term back the correct scale avoid vanishing gradient problems or a learning rate 7) that unusually large, since n. > IlC E (1,..., C).
B.3 BATCH-BALEE BALANCING
Algorithm 2 Batch- Batch-balancing
Input: D.C. C
b C is the number of classes, B is the batch size P> DD is the union of its class partitions > Each class partition contains n. ordered pairs D ||C7| C
D U D.
D. = (1f, f) C. x Ve
= (1...... C
for (1..... B} do
(~U((C))
b Sample class c Sample image and label pair from D.
(k,,ūt (D,)
end for
Output: D (ãt K
Balanced mini-batch of B image and label pairs
In normal batch construction, sample for batch is selected uniformly at random from the entire dataset D. Compensating for this by including additional copies of samples from rare classes in the training dataset, or during batch construction, is known as resampling oversampling (Chawla et al. 2002; Bellinge al. 2020). The prototypical version of this selects batch samples by first selecting class E [C]. uniformly at random, and then selecting sample from De, uniformly at random. This causes batch to contain an equal number of samples from each class on average. We term this batch-balaneing. The works (Ruff et al. 2020; Liznerski et al. 2022) use slight modification of this where the stochasticity of the labels for each batch removed so each batch contains an equal number of samples from each class.
The pseudo-code for batch- baachbbalnnciggg is described in Alg. in Appx. B.3 Error re-weighting and batch- batch-balancing are not specific to the cross-entropy loss and may be applied any loss that the empirical expectation of some loss function. They represent two different ways of remedying class imbalance: one can weigh the rare examples more heavily or one can present the rare examples more often. The following proposition shows that two methods are equivalent in expectation, although we find that batch- biich-bllancing is denoted by Pn.
always works better practice (see $5). The sampling distribution for
Proposition 1. Let B be batch selected uniformly random and B' be batch selected using batch- balancin.. Then there exists such that XE [Fre-woightedd for all 0.
weighted (B, 0)] = Eg [Evanilla (B', 8))
15

---

Published as a conference paper at ICLR 2024
Proof. Let (otqqu((1)) U(Aal). For the empirical class distribution, M,,y (Y) = I& | ys -bggl /n. So now we have
fo()))
Elyg. fo (xi4))
E (xx,
(((u))
Hn,Y (x)
[i y4 = Nq
E(yn fo (z²g)
n
E ((n))
Ki Yi = vo3l
= 19=
P Po-e((in)) (8g = j)
{(yg: fo (xzg)
K 3/ =JH
n
E ((x))((()))
[ii Bi = jH 1 =
n
C
fo (xg) Bg =] E ((a)) [e(yg)
C ((-((()))) [K(v.. fo (Eg) By = 51
(6)
Let B be the distribution over [n] according to batch-balancing. We know that U and B select
uniformly, conditioned on class label, so
Bx-u((n)) [f(y fo (Ir,) 1y = 5] = Esp-es (e(yn So (xx)) yy = -],,
and that B selects class label uniformly
Pa-Blun = =-]=
for all j [m)] Eq. 6 is equal to
C C B (((((() [R(ug. fo (xgg) Ug = = - By-s [e(ug- fo (2ig) I Ug 5] Po- = 5]
5=1
CB [e(yes so (2rgg]
= CE
C ANALYZING THE OKO LOSS LANDSCAPE
Here we analyze the optimal network output for the OKO loss and how the loss behaves around such an optimum. Such an optimization landscape analysis is notoriously difficult for non-convex optimization; hence we make some simplifying assumptions. It has been repeatedly observed that welle-rained neural networks typically "overfit" the training data. We assume that when a model has memorized its training data, its outputs will be identical for each input corresponding to the same class. In other words, its output on training data only depends on the training label: fx,)) F(y.) := Fy.- Here we will consider a matrix F of logit outputs, such that Fi,j denotes the logit for class j when the true label is i.
One issue with standard cross-entropy is that it strongly encourages the entries of F to diverge: For e the cross-entropy risk R(F") = E [-e"" log (softmax (fx)) = E [-e log (softmax (F,))]. and In other words: standard cross-entropy loss always encourages the logits of the true class to move towards oo and the logits of the wrong class towards cc.. As result, neural networks tend to be overconfident. In particular, if fa() predicts class ' then P (g r) < [softmax (f)()))
for all and i.j. BR(F) > 0 and for all + j. @R(F)
aF.,
8F.,
natural way to counteract this issue is via weight decay. Indeed, weight decay has been shown to improve calibration. However, this improvement comes at cost of generalization, and modern networks therefore typically utilize little to no weight decay (Guo et al., 2017). Thus, there is a desire to find ways to calibrate networks without using weight decay. Label smoothing is one potential solution to this since it encourages exp F, to be proportional to e,,(1 a) + a/C (Carratino et al. 2022). We include label smoothing as competitor for our method in the experimental section.
16

---

Published as a conference paper at ICLR 2024
Figure 6: This figure shows contour lines and gradient descent path f(x, y) -x - + (y 2)² Note that for fixed x or y. f is convex in the other variable. While gradient descent does indeed diverge to (x, v) + (oo, oo) the properties of slow its divergence.
Before deriving the risk functions for the hard and soft OKO losses, we must introduce further notation. Let Y. { 210), [S| i & 8}. Y, represents a potential of odd labels when y' i. For OKO we have
k42
442
Reof (F)= =
log softmax
Σ
Fvi
(7)
YEV, fm1
Yj
k442
].
Rbadd (F)
Σ Σ
log softmax
Σ Fyy
(8)
im YEY,
See Appx. ffor& derivation of these. The following proposition demonstrates that the OKO risks naturally encourage the risk not to overfit by constraining when each index of F is viewed individually.
Proposition 2. For a fixed j, both Reon (F) and Rhard (F) are convex and each admits a unique global minimum with respect to Fi.-
This acts implicit form of smoothing and helps to keep the logits from diverging during training. This is because the gradient descent path for functions like those described in Proposition 2 tend to meander rather than directly diverge. A toy example of this phenomenon
be found in Figure O Unlike label smoothing (Müller et al. 2019 Carratino et al.] 2022), however, is not encouraged to converge unique minimum. Optimizing the (hard) OKO risk still allows F to diverge if that's advantagcous - as we demonstrate in the following proposition.
Proposition& 3. There exist an initial value, F(0), such that the sequence of points given by minimizing pla)
Rhard with fixe step size gradient descent, F(0) F(1), (()) ...., yields, lima Fij + oc and
lim F(g) + for for all i and j + i.
Hence, the OKO risk strikes balance between the excessive overeonfidence caused by standard cross-entropy and the inflexible calibration of fixed minima in label smoothing (Carratino et al. 2022
17

---

Published as a conference paper at ICLR 2024
Here derive the expressions in Eq. and Eq. Bin the main text. We have that
Esseal (eoft (Sy, fo (S.))] =
P P = Esnes & (Sy, fo (Sx)) 1 =
==1
P(y'=)) i) Σ (P (LUi.... 1642] = 1-11 1 -)
(9)
1=1
YES.
[ (Sy, So (Sx)) 11' = 1/3, v2+2 Y)), (10)
noting that the parenthesis after the second summation in Eq. 9 extends to the end of Eq 10 Since y' chosen uniformly at random (y' = i) are equal for all and similarly (yg..... 1/42 are chosen uniformly at random given y/ and Y are all equal so P (13/3.... bk+2] Y V i) are equal for all Y and i, thus we can ignore these terms when optimizing over F. Letting Y' = (i, i, I....................... Yx)
in the summation we have, that ESnut [coo (Sy, fo (Sx))] is proportional to,
Esnel [Fone (Sy, (Sz)) 5/ =
vh+2] =Y]
YEV;
k+2
Bsnal
(k +
log [softmax (fo (Sx))) y = (1 (1s..... ) =Y
1=1 YEY;
i=1
k+2
T
k+2
Bs-ad
Σ
ex!
log
softmax
Σ
Fx!
i=1 YeE,
T
2+2
h++2
Σ
ex
log
softmax
Σ
Fr:
Fr:
i=1 Yez:
i==
1=1
&
1+2
A+
Σ
log
softmax
Σ
Fr:
(11)
i= GLYEV 1=1
Y3
The derivation of the hard risk is similar, however the third summation in Eq. 11 only contains the i term, for the single hard label.
C.1 PROOFS
Before proving Proposition 2 we will first introduce the following support lemma, which will be proven later.
Lemma 3. Let, N' E N be positive. Let qi of E RC, with qr1 = a,x + b,, d = aix + bg (the remaining entries of qs and of are fixed and do not depend on x) with a; > and d; > 0, and n, be sequence of N' elements in [C] \ {1). Then
N'
f(z)
Σ log (softmax (q:));
Σ
log (softmax (g/))..
(12)
is strictly convex and admits unique minimizer.
Proof of Proposition 2 This proof will be proven using surrogate indices j' in place of i,j in the proposition for Fi.; it will be useful be able use and refer indices in other expressions.
Observe that simply relabeling the network outputs does not affect the risk so, for a permutation and G defined by Gr.y (o(r)) we have that R(F) = R(G)). Because of this we will simply let = 1 for concreteness. We will begin with the case where /' = j'
18

---

Published as a conference paper at ICLR 2024
Case i' = = 1: Note that each summand in Eq. and Eq. is either constant with respect to F1.1 or has the form of the left hand sum, _, or right hand sum, L, of Eq. [2] substituting in < Fi, in the statement of Lemma 3 To finish the i' = j' case will show that both Eq. and Eq. has a summand of the form in L and one summand of the form in R:
For L: Consider = 1 and an arbitrary E W for Eq. for Eq.
we use the same values
with j since Y 1.
For A: In Eq. we can = 1, E Y be arbitrary, and j since Y3 == - j' that case. For Eq. we need only consider = 2 and some Y Y22 that contains an entry with 1.
From Lemma 3 it follows that both Reoft (F) and (F) are strictly convex and contain a unique minimum when optimizing over Fr,s.
Case i' j = 1: This case proceeds a similar fashion to the last.
For L: In Eq. 8 we have i and some E Wi, so that Y3 = 1"; for Eq. we add j =
Y 1.
For R: In Eq. we have Y E Y2 such that i' in Y. We can use the same values for and Y for Eq.
with j = 1 since Yi = 2.
Proof of Lemma
3
To show strict convexity, we will show that
is strictly positive. First, we have de
that
df
N'
Σ 0: (1 softmax (9:)1)
Σ
al (-offtmaxx (g()1)
dx
i=1
N' df (softmax (g))1
(softmax (f:n
(13)
and thus
f d
N
of (1 softmax (a))) softmax (4:) Σ dt (softmax (10)) - softmax (4()
which is clearly positive for all æ. To demonstrate the existence of a minimizer we will show that of attains both positive and negative values as function and, by the intermediate value theorem, df must equal somewhere. To see this observe that
da
N'
lim #0000
a (softmax (q:), - 1) Σ
a (softmax (qt)
Σ >
N
N'
lim Σ
ae (softmax (g:) - 1) +
Σ of (softmax (g/)) = Σ < 0, 1
t=1
which completes the proof.
Proof of Proposition 3 Let C CxC be the set of matrices F' where Fl, = Fjs for all j, and Let F(a, b) E be the matrix which contains a in the diagonal entries and b in all other entries. The chain rule tells that
Fi,j = Fe.g for all # j. + +
i OF.s
Ruard (F(a, Σ
Ruard (F)
(14)
da
F=F(a.))
19

---

Published as a conference paper at ICLR 2024
the sum of all the partial derivatives along the diagonal, and
i
Ruard (F(a, = Σ
Rhard (F)
(15)
bb
FFi
{
P= F=F((,))
the sum of all partial derivatives for the entries off the diagonal. Due to the invariance with respect 2
to labeling, as in the proof of Proposition 2 for any F E F it follows that DF., Rhard (F)
OF Rhard (F) for all i and i', and 0 aR., (F) äFF',' Because of this Rarrr (F(a, b)) will always lie in F and thus path following gradient descent starting in F will always remain in F.
0 (hard(F) for all + j. 1 + J'.
Considering Eq. 14 Eq. 15| if we show that a Rhard (F(a, b)) > 0 and 0 Ruard (F(a, b)) < d some a' 0 and V < 0. This would imply that gradient descent starting from an element of F will diverge to F (oc, -oo), which would complete the proof. We will now proceed proving Da Rhard (F b)) >
for any a, b, would follow that, for F E FF,VRRarr (F) = F(a', ,b)
0 and 5h Rhard (F b)) < O.
The risk expression applied to F(a, b) is equal to
k+2 Σ Fla. byy: )[
Ruard (( b))
log
softmax
(16)
YEY:
For concreteness we will consider the summand with and Y [2,..., k 1] fixed, which
implies Y' = k + 1] is also fixed. In this case we have that
2a + kb a + (k + 1)b
F(a,
a + (k + 1)b (k 2)6
(I: + 2)6
with & entries containing a + (k + 1)6 and C (k + 1) entries containing (A: + 2)6 (note that C' - (k: + 1) is nonnegative). Continuing with fixed and Y' have that
2+ Σ
log
softınx
F(a, b)y:
cxp (2a + bk)
=
llog
(17)
exp (2a bb) + l exp (a b(k + 1)) + (C k: 1) exp ((k: 2)b)
We will define R(a, b) to be equal to Eq. 17 Note that every summand in Eq. 16 is equal to Eq, Because of this we need only show that 3a
17
R(a b) > and oh R(a, b) to finish the proof.
Differentiating with respect to a gives
θ R(a, b) exp (2a + bk) + exp (a + b(k + 1)) (C - k 1) exp ((k + 2)b)
eexp (2a + bk) 1 kxx b(k 1))
Da
Letting
Q(a, b) exp (2a + bk) kexp (a + b(k 1)) (C k - 1) exp ((k + 2)bb
it follows that
R(a, b) =2 exp (2a bk) + kexp (a b(k + 1)) cxp (2a + bk) Q(a, b)
Da
((a,b)
We have that
exp (2a + bk) + lo kexp (a + b(k + 1))
exp (2a + bk) Q(a, b)
< 1 and
Q(a,)) b)
20

---

Published as a conference paper at ICLR 2024
8 R) 0.
0a
Differentiating with respect to we get
R(a, b) 0b
k exp (2a + bk) + k(k + 10)
exp ((k: + 2)6)
= k
exp (2a + bk)) exp (a + b(k +1) (C k 1) exp ((k: + 2)6)
Observe that
k k exp (2a + bk) k(k + 1) exp (a + 6(k 1)) + (k 2) 1) exp ((k: + 2)6)
exp (2a. + bk) + k exp (a b(k + 1)) + (C - h: 1) cxp ((1: 2)b)
0 so 06
R(a, b) < 0, which completes the proof.
D PROOF OF THEOREM
To prove this let Fo C IF be such that f Fo satisfies f())1 = 0 for all i. We have the following lemma showing that Fo can be used place of our proof.
Lemma 4. Let 01.... UM be in Rd. Then there exists vi...., I'Ms with 2/21 Ofror all such that, for all wi....y WM R. the following holds
M Σ
softmax
softmax
Σ wark
This essentially allows avoid the complications arising from that fact that there exists an uncount- able infinitude of distinct vectors, in particular f(a) with various a E I and f()) = such that (oftmax(f(a)) softmax( (a'') when + a', by simply selecting the unique representative with fi = 00
Proof of Lemma First we will show for all Rd and c that softmax (x) (r + cc where I E Idd is the ones vector. Let j [d] be an arbitrary index. We
softmax
will show that softmax
x + ct), softmax (x) Observe that
softmax (ar +c+c))
exp (I, + c)
Σ 1= exp (IT
exp (I,) exp (c)
kk-1 exp (fr) exp (c)
exp (c) exp (xy)
exp (c) Ei exp (xx)
exp (I,)
El= exp (Ix)
softmax (z),
Because the above equality is true for all indices j, it holds for the whole vector, so softmax (z)
softmax (r + cT).
21

---

Published as a conference paper at ICLR 2024
Let u/ v U1 for all d. Note that o
for all Now have that
M
M
softmax
Σ
softmax
Σ
softmax
M
)
softmax
Σ
+
Σ
Wilt,
M
softmax
Σ
where the last line follows from the equality shown at the beginning of this proof.
Using this we can prove the main theorem.
Proof of Theorem 7 From Lemma 4 the theorem statement is true iff it holds for minimizers in Fo. so we will prove the theorem for f where f(-)1 O.
Let Qe (au, 01, 02) = Qe(a) A Esaat [ (Sy, (Sz)) with satisfying f(0) [0, og). f(1) [0, a.l. and ((2) [0, a2). For the remainder for this proof will denote the entries of vectors like beginning with 0, as above, rather than 1.
To begin note that
16
Qe(a) Σ
Pe,i log (Vi(a)).
where the V, are defined in the following table (Table 4
#
21
1/2
1/3
Pas. (2 T2, F3, 21 1/2, V/3
Pr.#
1
1
1
2
(1 (1- /2
(xp(O)
exp(O) (oxp(oxppa
2
2
2
1
(1 (1- /2
exp exp(3eo)
exp(O) eep-eeppiiie 3ng
3
1
1
2
0
2
c(1 <)² /2
(xp(U)
exp(0)+exx(( +22 exp(O)
4
1
1
2
1
0
c(1 (1-c) -c)² //²/2
cxp(O) +exp! 22g + exp(U)
5
1
1
2
0
1
0
<(1 (1)=))// -)²/2
exxp0)+ (20g+aa)
6
2
2
1
0
0
1
c(1 -c)²
exp(2ag+ar)
exp(0)+exp((o))
7
2
2
1
2
0
c(1 (1-c)²// -c)²/2
exp(2ao++22)
+xx())xxp(2000 +wgg) exp(2ng
8
2
2
1
0
2
0
e1--)
exp +exp (20g
9
1
1
2
(1-
exp(U)
exp (0 (00++ +expl 2ay exp(O)
10
1
2
(1--))
exp + exp dg +ag exp(U)
11
1
2
0
è (11 (1-e)/2
exp (exp) (o to +02) explae +2ag)
12
2
2
1
2
e (1-c)/2
exp (e0))eexxxop) 2ws)
13
2
2
1
2
(1- (1-e)/2
+o2)
exp( exp dg t +
14
2
2
1
2
0
e e)
do ta +
exp exp +u, to.)
15
1
1
2
1
1
2
e /2
exp(1)
exp exp (2g +
16
2
2
1
2
2
3
exp 20z)
exp
Table Terms expectation
22

---

Published as a conference paper at ICLR 2024
From this it is clear that Qe is continuous for all c.
We will now show that for all e E (0, 1) there exists a minimizer a, E arg min, Qa by con- tradiction. For sake of contradiction suppose there exists e' for which such minimizer exists. Because Q is bounded from below we can find a sequence (a:) such that Qe (a:) + inf, (a( Because Σ , a log (Vi(a)) + oo as |ao| + oo (here do is the first entry of rather than one vector from the sequence ag incurring a slight abuse of notation) follows that the sequence (01,0);=1
no must be bounded and thus contains convergent subsequence. We will now assume that (a:) such a sequence. Note that Σ -Pr,, log (Vi(az)) would diverge were aj, or aj2 to diverge (because d, remains bounded) and, because every term -Pr,i log (Vi(a)) > O, (a;) must remain bounded otherwise Qe(ag) would diverge. Thus a, has convergent subsequence and its limit must be a minimizer by continuity, a contradiction. Therefore minimizers a, exist.
Let a" [0, - loooo)))), log())) and define
Q1 Q1:00
Pr,i log (Vi(a))
i=1
Q2
Σ
Pe, log (Vi(a))
1=3
16
Q3: :
Pe, log (Vi(a)),
with the subscript for Q left implicit to simplify notation. Observe that aj minimizes QI. which holds iff oj = O, and that minimizes Q2 with aj fixed to O. Showing that these are minima follows from simple calculus and algebra. The functions Q1 and Q2 can be shown to be strictly convex by showing that the second derivative/Hesssinn is positie/possiive-definie simply taking the derivative/ grraaiiiingg of these terms and setting them equal to zero. All instances in this proof where we assert strict convexity and find minima follow from this kind of argument.
The minima can be found by
We will now show that a. + 0 by contradiction. All limits with respect to - 0. For the sake of contradiction assume there is decreasing subsequence (G) which converges to 0 and 5 > 0
Σ log (V4 (a)) is strictly convex in its first index and is minimized when ag there exists A > 0 such that Σ log (V; (a.,)) - log (V: (a*)) Z A1, for all j (we"v ve left in the double negative to emphasize that we are subtracting the convex term). Now we have that
such that (a,, ajl 2 6. Since
(1-
Qc, (ac,) - Qa,(aa)
A -
Σ 22 (a*)
2
j=2
(1 Es) A ((es)
2
and thus, for sufficiently large i, Qc (an.) > (a*), a contradiction. We have now shown that
ar,0 + O.
We will now show that a,,1 and 0,22 must be bounded, again via contradiction. As before we can consider the case where e; converges to zero with d diverging (the proof is virtually identical for de,,2). Note that minimizer of Q. is also a minimizer of c 'Q... Now we have
(a,,) G (a,
= Q1((a))) - Qi(a") Qra((a))))))))) tc, +c7)))+(222200 Q2(an)) - - (2(2"a))++ + -oode)---'aaae "'Qa(a")
20
20
O(es)
2.- - Q2(aa)) -e-(aaaa)) + ((e)).
(18)
Observe that if ae,,1 diverges with a,,u + 0 then the first term in the last line goes to oo (see terms and 6 in Table 4 which would contradict the optimality of a,, due to Eq. [8 Thus we have that a, must remain bounded
0.
23

---

Published as a conference paper at ICLR 2024
Since ag is bounded, there exists yet another sequence e, such that a. converges. We will call this limit noting that a/- = 0. Again we have
c Qe, - = Qe,
= 3 Qi(a))) - +Q((())+++""""")" (1(()((aa)))-)) - Q2(aa) + @o(an) - (a(aa)))
-5
20
20
O(s))
2 4 Q2(ac;) - Q2(a') - -'a(aaa))
O(e,)
= (1 2)) 2 - log (V, (ac))) - log (V3 (V3 (a')) - -OGG).
(19)
Note that the interior summation of the last line converges Ei log (Vi (a')) - log (Vi (a*)) which must equal zero since Σ - log (V, (-)) continuous and otherwise the optimality of a., would be violated in Eq. 19 for sufficiently large i. Finally note that > log (V; (-)) is strictly
convex and thus a' = a". Since a, is bounded for small and because every convergent subsequence 0 causes de + a", it follows that dg a".
E CALIBRATION
Here, we provide more intuition about our new entropy- based measure of datapoint calibration. In sense, our measure is normalized scoring rule that provides localized probabilistic insight.
E.1 BACKGROUND
Rare classes make it difficult for calibration in practice, that is the predicted probabilities match the true probabilities of an event occurring, essential for making reliable decisions based on the model's predictions. Specifically, if f : X - [0. 1] is a probabilistic model for binary labels, we want (lylf(x) u) = For multi-class labels, this generalizes for each class such that for predicted probability vector p E [o, 11c. [[e,]/(xx) p] = p.
There are also various ways to measure calibration error. The most common is the expected calibration error; however, arbitrarily small perturbations to the predictor f can cause large fluctuations in ECE(F) (Kakade & Foster 2004 Foster Hart 2018). As a simple example, consider the uniform distribution over two-point space X = { 22 J. where the labels are yı = 0, 1/2 = respectively. The predictor f which simply predicts 1/2 is perfectly calibrated, so ECE(f) (ff = O. However, a more accurate estimator fx1) 1/2 and f 1/2 for any small > 0 suffers calibration error ECE(J) = 1/2 - e. Note that this discontinuity also presents a barrier to popular heuristics for estimating the ECE. However, it has been show that ECE and most binning based variants give an upper bound on the true distance to calibration (Blasiok et al., 2022). It has been shown that sample-efficient continuous, complete and sound calibration measures do exist and they all generally measure a distance to the most calibrated predictor, and many of them are similar to binned ECE. Therefore, we utilize binned ECE and brier score as two notions of calibration.
In the multiclass setting, while there is not consensus on how to measure calibration error, we use the most common way to extend calibration metrics, which widely implemented via the one-vs-all method (Zadrozny & Elkan, 2002). Recently, there were other multi-class calibration measures proposed, such as class-wise calibration (Kull et al. 2019) and decision calibration (Zhao al. 2021)
Scoring Rules and Likelihood A scoring rule provides a local measure of fit or calibration given a predictive distribution and its corresponding labels. Specifically, for a datapoint (I;, yı), let D, be the predictive distribution of a model. Then, a scoring rule is any function that outputs a scalar evaluation of the goodness of fit: S(y., ú.). Such scoring rule is called proper if Ey=o|S(3) Ø)] is maximized when ò = Q. meaning that when the predictive distribution perfectly calibrated and equal to the true label distribution, the score is maximal.
24

---

Published as a conference paper at ICLR 2024
A common proper scoring rule is the log likelihood. Recall that for distributions over [C1, p and
that cross-entropy is (p, q) = - E, pi log(g, and entropy is (p) = (p. p) = -- p. log (p.). In the classification setting the log likelihood is equivalent to the negative cross-entropy (vy y) (y. .) = ey log Indeed, we see that for any predictive distribution ý and label distribution Q. By-eyl@ltt (y. ú)] = HQQ ú) If O = Q and our label distribution is uniform, then this is equal to the maximum entropy of log( (C)) When ý is perfectly calibrated, the average negative cross- entropy will be equal to the negative entropy: Ey--g leg log(ū)) = E3 0t log(ū:) - It is easy see that this is proper rule since for any predictive distribution ÿ and label distribution Q. Ey Q)] Ey~o@Sii (S 0)] = (Q) + ((Q, 9) = K (QQll)) 2 0, where the relative entropy or KL divergence non-negative.
The definition of proper scoring rule works well when the label distribution is static and continuous, as when Q is a point mass, the KL divergence becomes (Q, .), which the case with hard labels. However, in most settings, y is dependent on and Q = (ax,))~ (ey |a]] and H (Q) is not known for each v. Furthermore, this gets even trickier when the predicted classes are non uniform, but under-representte classes require better calibration.
Cross- cosssEn vs Entropy Due to the limitations of proper scoring rules, such calibrative measures not meaningful measures of over-confidence the question of whether each datapoint is calibrated and note that the scoring rule of H (3). v) does not give inherent notion of calibration. Instead, we motivate the following definition of relative cross-entropy by noting that if y ~ G. then Syy 9) Hū) is a random variable with expectation 0.
per-datapoint level. Specifically, consider
E.2 PROOFS OF LEMMAS
Proof of Lemma 7 entropy measures,
Let i be the index corresponding to y. Then, by definitions of corresponding
RC 0) log(U;)
Σ Us log(ū,)
(0i 1)lo(()))
Σ
úg log(ū;)
(20)
1 Di
(úi 1og((())) + (1 (t) log
(21)
|C1
(1 ú.)
log
1 51
log (0:)
(22)
|C|-1)
The third line uses the principle that entropy is maximized when uniform. To see this let & Eis; Új 1 O and observe that the maximizing of the left hand side of the following equation admits the same argument as the subtrahend in Eq. 20
Σ Us (log(ū,) - log a = Σ (0,/aa log(ū,/a), J7
a
j
and the right hand side is maximized with a uniform distribution. The lemma follows since both terms in Eq. 22 are positive.
Proof of Lemma
This follows since that I is a perfectly calibrated predictor, then
Frgrgg (RC 7) = Feg-g(C(ys H())
F ADDITIONAL EXPERIMENTAL RESULTS
In this section, we expand upon the results that we presented in and show additional experimental results and visualizations for model calibration. We start by presenting reliability diagrams for the heavy-tailed class distribution settings and continue with uncertainty and expected calibration error analyses.
25

---

Published as a conference paper at ICLR 2024
Vonila
Vanilla L5 lam 0.23
Waggozd CE
Focal LoGs
Batch balancing (88) BB (a- 0.11
BB (.022.0
Odblkoout (k=1)
0.9
Accuracy
MNIST
0.7
92
06 20
0204
02 2605
0206 6
02 94 08 0.2 02 16 02 66
62
Confidence
Weighted
balanding
FashionMNIST
Accuracy
8.7-
0.5
0.1
300010
Confidence
Ventla
Vanill la- 0.33
Weighoed
Focal Beich-baleering (Ss) BB
(a10
2.00
Odd44-out (k-33
CIFAR 10
Accuracy
Confidence
Vanill farm
Weightied
Focal Betrb-bstereing (Da)
(am (cm
Oddeloout dem13
CIFAR 11FAR1100 100
Accuracy
02 04 6608 30 05 3.0 02 360810
030066.00
02 C4
06
64 1O 02 6615 02 24 08
Confidence
Figure Reliability diagrams for heavy-tailed MNIST, FashionMNIST, CIFAR-I0. and CIFAR-100. Confidence accuracy scores are averaged over five random seeds and across different number of training data points. Dashed diagonal lines indicate the best possible calibration.
F.1 RELIABILITY
Figure we present reliability diagrams for heavy-tailed MNIST, FashionMNIST, CIFAR-10 and CIFAR-100. Both confidence and accuracy scores are averaged over five random seeds and across the number of training data points, similarly to Figure in $5 Note that optimal calibration occurs along the diagonal of reliability diagram, highlighted by the blue dashed lines. For training regimes with heavy-tailed class distributions, either OKO, batch- baahnbbalnncing combination with label smoothing, batch-balancing in combination with posthoc temperature scaling achieves the best calibration the held-out test set.
F.2 UNCERTAINTY
In Figure X we show the distribution of entropies of the predicted probability distributions for individual test data points across all heavy-tailed training settings for CIFAR-10 10 and CIFAR- 100 respectively. In addition the distribution of entropies of the predicted probability distribution for heavy-tailed training settings, in Figure D points across all balanced training settings for all four datasets. We find OKO be very certain (Q)) is close to log (1) for the majority of correct predictions and to be highly uncertain H(Q) close to log (C') for the majority of incorrect predictions across all datasets. Batch- balancbg in combination with either label smoothing temperature scaling shows similar distribution of
we show similar distributions for individual test data
entropies for the incorrect predictions, but is often too uncertain for the correct predictions, indicating random guesses rather than certain predictions for significant number of predictions (see Fig. 8)
F.3 EXPECTED CALIBRATION ERROR (ECE)
Here we present ECE as a function the number of data points used during training for both uniform and heavy-tailed class distributions for all four datasets considered in analyses. We remark that for
26

---

Published as a conference paper at ICLR 2024
Varilla
Varilla (pr- 0.11
Wilghted CE
Focal LoGs
Batch- ballancnng (8:5) dB
(1m2..)
Odd-kiout Hi
Uncertainty
log (C)
CIFAR-10
THE NUSG
1.8
correct
incomret correct
cornect
correct
incemeect
correct
interee
correct
ince
Prediction
Vanilaa
Vanill + LS 6.11
Welghted CE
Focal Loss
Batch balancing (88) 6B
Got 0.31
(S 2.60
Inouu [ow
log
CIFAR-100
Uncertainty
3.5
TH
Modi
0.1
Prediction
Figure Here, we show the distribution entropies of predicted probability distributions for individual data points across all training settings partitioned into correct and incorrect predictions respectively.
Varilla
Varilla + LS ce 0.11 Welghted CE
Focal Loss
Banch batancing (88)88
Gru 0.31
(S.0==2.)
Odd-bbout (kw1)
Uncertainty
log (C)
Class distrioucion
THE
MNIST
Made
1.2
Prediction
(k-1)
FashionMNIS
Uncertainty
log
incomet: conrect
innmeett
coreet
Incanect corect
incormect correc:
Encormect correct
Incemmet
comrect
Incernect connect
Inco
correct
Prediction Focal Loss
Vonilla
Vanilla LS Ga- 0.11
Welghted CE
Batch balanding (88) (an- 0.11
(.02.
Odd out (R
CIFAR-10
Uncertainty
log (C)
THE MUse
1.8
conwet
inomect
correct
COMNEC
Pncomeet
Incoreet cornect
Pnctrne connect
Prediction Focal Loss
Vanilla + US 0.11
Weightted
Batch-balercing (nitinn Grm
(.
Gddd-b-out (km1)
log (C)
CIFAR-100
Uncertainty
3.5
TAE
Prediction
Figure Here, show the distribution entropies of the predicted probability distributions for individual data points across all training settings with uniform class distribution partitioned into correct and incorrect predictions respectively.
every method the ECE was computed on the official test set. For balanced MNIST, FashionMNIST. and CIFAR-10 as well as for heavy-tailed MNIST OKO achieves lower BCE than any other training method. For the other training settings, OKO either on par with label smoothing or achieves a
slightly larger ECE compared to label smoothing. This suggests that OKO is either better calibrated than or equally well-calibrated as label smoothing. The results are most striking in the low data settings.
27

---

Published as a conference paper at ICLR 2024
MNIST
FashionMNIST
CIFAR-10
CIFAR-100
D4D
0.2
Vania
0.2
0.25
Uniform
0.2
ECE
0.2
0.1
0.15
0.05
0.0
200
200
300
402
520
1000
5303
0.0
200
200
430
502
1000
5230
10000
0.0
400
5.0
1000
5000
10000
20:003
0.0
5380
10000
20000
30202
Heavy- tailttlleddd
ECE
0.2
0.2
0.3
0.3
0.1
0.1
0.35
0.35
0.0
0.0
Number of training data points
Number of training data points
Number of training data points Number of training data points
Figure 10: ECE as function of different numbers of training data points. Error bands depict 95% Cls and are computed five random seeds for all training settings and methods. Top: Uniform class distribution during training. Bottom: Heavy-tailed class distribution during training.
F.4 How TO SELECT K. THE NUMBER OF ODD CLASSES
In this section, we compare different values of k for generalization performance and calibration. Recall that & determines the number of examples coming from the odd classes - the classes that are different from the pair class in a set S.
Odd class examples are crucial. Removing any odd class examples from the training sets - i.c., setting & to
decreases generalization performance and worsens calibration across almost all training settings (see Fig. I1 Fig. 12 and Fig. [3). Although odd class examples are ignored the training labels, they are crucial for OKO's superior classification and calibration performance. Odd class examples appear to be particularly important for heavy-tailed training settings.
The value of i does not really matter. Concerning test accuracy, find that although odd class examples are crucial, OKŌ is fairly insensitive to the particular value of l apart from balanced CIFAR-I0 and CIFAR-I00 where achieves stronger generalization performance than larger values of A (see Fig. However, this may be due to the additional classification head that we used for predicting the odd class set rather than special advantage of l over larger values of k.
We find larger values of to result in worse ECEs for training settings with a uniform class distribution and similarly low or slightly lower ECEs for heavy- -tiled class distribution settings (see Fig. [2]. Similarly, we find the mean absolute difference (MAE) between the average cross-entropy errors. (P, Q). and the average entropies, (Q)), on the test sets for different numbers of training data points to be slightly lower for k = than for larger values of k for uniform class distribution settings and equally low or slightly larger for k = compared to larger values of for heavy-tailed class distribution settings (see Fig. 13 for visualization of this relationship and Tab. 6 for quantification thereof). Across all training settings the MAE between H (P, Q) and )) the largest and therefore the worst for O.
Table 5: MAE between entropies and cross- coss-entropies averaged over the entire test set for different numbers of training data points. Lower hetter and therefore bolded. This quantifies the relationships shown in Fig. 13
MNIST
FashionMNIST
CIFAR-IL 10
CIFAR 100
Training Distribation
uniform
heavy-tailed
uniform
heavy-tailed
uniform
heavy-tailed
uniform
heavy-tailed
Odd-A-out (A==0) Pair
0.091
0,318
0.136
0.542
0.657
1.370
2.088
3.739
Odd-k-out (A=1)
0.073
0.094
0.080
Odd out (k=2)
0.224
0.123
0.204
0.208
0.352
0.194
0.527
1.040
Odd- o-tut (lw3)
0.285
0.180
0.279
28

---

Published as a conference paper at ICLR 2024
MNIST
FashionMNIST
CIFAR-10
CIFAR-100
100
90
80
45
Test accuracy (96)
Uniform
95
70
85
50
Ost-koou (b-1)
Ost-kour (h-2)
0J0-A our (bw3)
80
303
200
300
400
546
1003
5000
240
383
400
500
1036
5002
30000
30
400
500
2000
5003
10000
20300
3000
10000
20000
30092
Test accuracy (%6
Heavy- tailed
90
60
50
50
70
70
30
Number training data points Number of training data points
Number of trainingg data points Number of training data points
Figure 11: Test set accuracy in % function of different numbers of data points used during training. Error bands depict 95% CIs and computed over five random seeds for all training settings and values of k. Top:
Uniform class distribution during training. Bottom: Heavy-tailed class distribution.
MNIST
FashionMNIST
CIFAR-10
CIFAR-100
0.25
0.3
Uniform
ECE
0.15
6.15
0.15
0.15
0.1
0.1
0.05
0.05
0.05
330
307
3000
330
5000
20303
3383
10500
30932
Heavy-tan Heavy-talled vt-taieedd
0.3
0.3
ECE
0.2
0.2
0.3
0.3
0.0
100
262
4.00
305
1000 5060
0.0
200
362
406
1,00 sede 10302
0.0
4.0
1000
5000
10000
20302
0.0
s0e0
10000
20000
36902
Number training data points
Number training data points
Number training data points
Number training data points
Figure 12: ECE as function of different numbers of training data points. Error hands depict 95% CIs and are computed over five random seeds for all training settings and values of k. Top: Uniform class distribution during trining. Bottom: failed class distribution during training.
F.5 HARD VS. SOFT LOSS OPTIMIZATION
Soft loss optimization spreads out probability mass almost uniformly. Empirically, we find that the soft loss optimization produces model predictions that tend be more uncertain compared the predictions obtained from using the hard loss (see the large entropy values for models trained with the soft loss in Fig. [6]. The soft loss optimization appears to result in output logits whose probability mass is spread out almost uniformly across classes and, thus, produces probabilistic outputs with high entropy values (often close to log C). Fig. 16 visually depicts this phenomenon. These uniformly spread out probabilistic outputs lead to worse ECEs, where differences between the hard and soft loss optimization are more substantial for MNIST and FashionMNIST than for CIFAR- 10 and CIFAR- 100 respectively (see Fig. 15). Interestingly, for CIFAR- 100 there is often barely any difference in the ECEs between the hard and soft loss optimization in the balanced class distribution setting, and the heavy-tailed distribution setting, soft targets even yield lower ECEs than hard targets.
The test set accuracy of models trained with the soft loss is substantially worse in all balanced class distribution training settings (the differences appear to be more pronounced for MNIST and
29

---

Published as a conference paper at ICLR 2024
MNIST
FashionMNIST
CIFAR-10
CIFAR-100
Por
383
Far
200
Fel.
ccB
Daan aid kima)
722
1167
Uniform
R(P. .)
1231
Fair
500
Dis
200C
8.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
8.0
0.5
1.0
1.5
2.0
8.0
1.0
2.0
3.0
log
Heavy tailed
A(P. Q)
8.0
0.5
8.0
1.5
8.0
0.5
15 2.0log[10;
8.0
1.0
2.0
3.0 log(200)
F((Q)
H(Q)
H(Q)
H(Q)
Figure 13: Average cross-entropy as a function of the average entropy for different numbers of training data points and different numbers of k. Top: Uniform class distribution during training. Bottom: Heavy-tailed class distribution during training.
CIFAR- 100 than for FasHionMNIST and CIFAR- 10 respectively), but classification performance is only slightly worse compared the hard loss in the heavy-tailed distribution settings (see Fig. 14].
MNIST
FashionMNIST
CIFAR-10
CIFAR-100
100
Test accuracy (%)
Uniform
95
85
70
Cad---cut (t-2:
50
Cat---cut (b-3) hand)
odd-k-out (k-1) sort
odd---out (b-2) sot)
odd---out (o
80
303
200
200
400
500 1000 5000
300
300
410
530
1000
5033
30
400
500
-000
5003
10000
20000
3000
10000
20000
3002
Test (96)
Heavy- teavy-tailed
90
80
60
20
75
80
70
30
5
Number training data points
Number of training data points
Number of training data points Number of training data points
Figure 14: Test set accuracy in % function of different numbers of data points used during training. Error bands depict 95% Cls and are computed over five random seeds for training settings. Top: Uniform class distribution during training. Bottom: Heavy-tailed class distribution.
Table MAF between entropies and cross-entropics averaged over the entire test set for different numbers of training data points. Lower is better and therefore bolded. This quantifics the relationships shown in Fig. T6
MNIST
FashionMNIST
CIFAR 10
CIFAR 100 heavy-tailed
Training \ Class distribution
uniform
heavy-tailed
uniform
heavy-tailed
uniform
heavy-tailed
uniform
Odd-A out (k=1: hard)
0.073
0.094
0.080
0.334
0.116
0.498
0.314
1.164
Odd-k-out (A=2; herd)
0.224
0.123
0.204
0.208
0.352
0.194
0.527
1,040
Odd out (k=3; hard)
0.285
0.180
0.279
0.160
0.376
0.153
0.682
0.769
ood-k-out (lwll; aoft)
0.893
0.759
0.761
0.627
0.417
0.243
0.331
0.281
Odd-k-out (A=2; sofL)
0.845
0.717
0.733
0.620
0.394
0.248
0.564
0,082
Odd-k-out (=:3;off)
0.772
0.667
0.668
0.585
0.301
0.268
0.626
0.107
30

---

Published as a conference paper at ICLR 2024
MNIST
FashionMNIST
CIFAR-10
CIFAR-100
0.7
0.6
0.3
Uniform
0.6
0.5
0.4
0.5
0.4
0.3
Odt-k-or to
0.3
0.2
0.2
0d5-k (em3;
0.2
0.1
0.1
0.0
220
200
200
400
302
3000
5300
0.0
230
330
422
503
1000
5300
0.0
400
500
1000
5000
10383
20000
0.0
5030
32030
20000
30222
Heavy- talyttlledd
0.5
0.3
ECE
0.3
0.3
0.1
0.0
0.0
Number of training data points
Number of training data points
Number of training data points Number of training data points
Figure 15: ECE as function of different numbers of training data points. Error bands depict 95% CIs and computed five random seeds for all training settings. Top: Uniform class distribution during training. Bottom: Heavy-tailed class distribution during training.
MNIST
FashionMNIST
CIFAR-10
CIFAR-100
perets
CRl out (hd2 and
200
Code out Inc2 hard
30
Uniform
Dak out ter catt
4th
Bada twr
A(P. Q)
(ik))
Tutkkng
Deda Jan
J000
oeplict and wre
8.0
0.5
1.0
1.5 2.0
2.5
8.0
0.5
1.0
1.5
2.0
2.5
8.0 0.5
1.0
1.5
2.
2.0log]10
8.0
1.0
2.0
3.0
l1g
Heavy- Heavy-tailed tailed
A(P. Q)
2
8.0 0.5
1.0
1.5 2.0 A()))
2.5
0.0
0.5
1.0
1.5 2.0
25
8.0
0.5
1.0
15 A(Q)
2.0log(10;
0.0
1.0
2.0
3.0 log(100)
A())
H(Q)
Figure 16: Average cross-entropy as a function of the average entropy for different numbers of training data points and different numbers of k. Top: Uniform class distribution during training. Bottom: Heavy-tailed class distribution during training.
F.5.1 WHY DO SOFT TARGETS PRODUCE WORSE ACCURATE CLASSIFIERS?
Understanding why the soft loss optimization (see Eq. 7 results in worse accurate classifiers than the hard loss optimization (see Eq. (8) requires experiments that, unfortunately, go beyond the scope of this paper. However, using the theory that we developed for understanding the properties of OKO in combination with the experimental results from the ablation experiments for comparing the hard against the soft loss (see above), we can try providing an intuition about why the soft loss produces worse accurate classifiers. We remark that this should be read conclusion because we have no clear evidence for our intuition. Recall that the soft loss (see Eq (7) in combination with Alg. results in twice mitigation of the overconfidence problem:
interpretation rather than
31

---

Published as a conference paper at ICLR 2024
(a) The output logits aggregated across all examples in set and, thus, the loss is computed for a set of inputs rather than a single input (here, an input is an image). This step happens in both the hard and the soft loss optimization.
(b) Probability mass in the target distribution is spread out across the different classes in set and, hence, transforms the majority class prediction problem - which is what the hard loss optimizes for into proportion estimation problem, which may make the model unnecessarily underconfident about the correct class.
Since the output logits aggregation step (a) is part of both the hard and the soft loss optimization, the hard loss may better strike the balance between mitigating the overconfidence problem and potentially shooting the optimization into local minima that amplify uncertainty where uncertainty/underonnff dence is actually not desirable (which could be what is happening in the second step).
G COMPUTE
We used compute time of approximately 50 hours single Nvidia A 100 GPU with 40GB VRAM for all CIFAR- 10 and CIFAR- 100 experiments using a ResNet-18 or ResNet-34 respectively and approximately 100 CPU-hours of 2.90GHz Intel Xeon Gold 6326 CPUs for MNIST and FashionM- NIST experiments using the custom convolutional neural network architecture. The computations were performed on standard, large-scale academic SLURM cluster.
32


Reviews:
[{"review_id": "oh1AFT1gf7", "reviewer": "Reviewer_se1z", "summary": "This paper introduces a new training method, which the authors call ``odd-k-out'' for training machine learning classifiers, in order to reduce the problem of over-confidence observed in large models trained on relatively small datasets (which often end up interpolating the training set).\n\nThe method essentially boils down to sampling uniformly at random two distinct classes $k_1, k_2$, and then two uniformly random examples $x_1, x_2$ from the first class ($y_1, y_2 = k_1$), and one example $x_3$ from the second class (with $y_3 = k_2$), and taking a gradient step in the direction minimizing the loss given by $e_{k_1}^T \\log(\\mathrm{softmax}(\\sum_{i \\in \\{1,2,3\\}} f_{\\theta}(x_i)))$.\n\nThe authors report improvement in terms of accuracy and importantly calibration error with respect to a number of benchmarks, and show that their method provides an approach to handle pressing issue stemming from the fact that out-of-the-box machine learning models tend to preform poorly on sub-populations that are underrepresented in the training set. They also provide a theoretical insight into how this assertion can be justified in a simplified model (Theorem 1) --- essentially saying that in specific situations, if on vanishingly small subsets of the universe the features $x_i$ determine the outcome exactly, the OKO-minimizers will only put confidence $2/3$ of this specific outcome (on aforementioned small subsets).\n\nThe introduced method seems to be fairly close to ``batch balancing + label smoothing'' --- the authors discuss briefly this method in paper and use it as a comparison point. Batch balancing here refers to sampling examples by first sampling a uniform class, and then sampling a uniform example from the class (as opposed to just sampling uniform example from the entire dataset), which is a standard method to remedy class imbalance in the training set. Label smoothing corresponds to minimizing loss $\\ell(f_\\theta, \\tilde{y}_i)$ where the desired label $\\tilde{y}_i$ has some fraction $\\alpha$ of mass on the actual class $y_i$ and $1-\\alpha$ fraction of mass evenly distributed across remaining classes --- therefore addressing the problem of over-confidence. \n\nIn the OKO method, the load balancing is done explicitly, whereas the label smoothing is somewhat implicit --- while looking at a gradient of an expression $e_{k_1}^T \\log(\\mathrm{softmax}(\\sum_{i \\in \\{1,2,3\\}} f_{\\theta}(x_i)))$ which is being minimized, we see that what happens is essentially adding some linear combinations of gradient pushing the outcome of the classifier $f_{\\theta}$ to be more confident of outcome $y_1$ on all three examples $x_i$ --- of which two has actual label $y_1$, and the third has uniformly different label --- this feels fairly close to just taking a random class $k_i$, a random example $x_i$ and shifting the weights towards higher confidence of class $k_i$ with probability $2/3$, vs higher confidence for a different (uniformly distributed) class with probability $1/3$ --- essentially label smoothing.\n\nIn contrast with label smoothing, as authors show with their Proposition 3, that in a toy example in which labels are directly determined by the feature (i.e. $x_i \\in [C]$ is uniformly random, and the corresponding label is $y_i = x_i$, then minimizing OKO-objective (over the class of all functions from $[C]$ to the probability simplex $\\Delta([C])$ leads (as it is desirable) to diverging logits: i.e. the predictions $\\tilde{f}(x)$ converge to $(0, \\ldots, 1, \\ldots 0)$ with the label $1$ on the correct label $x$.", "questions": "Most of my questions was implicitly stated in the discussion about weaknesses. I find the Theorem 1 fairly unconvincing as a desired property of the proposed training method --- it seems like informative Theorem highlighting \\emph{a property} of OKO, not necessarily an argument for using it. In light of superficial similarities with batch balancing + label smoothing, expanding a bit on similarities differences between those (and particularly scenarios where OKO seems to behaving closer to what we would expect than label smoothing) would be nice. The Proposition 3 is a great step in this direction, so potentially just highlighting it and providing more detailed discussion about it in the main body of the paper would be nice. \n\nThe Proposition 2 is said to be interpreted as \"OKO directly encouraging the risk not to overfit\" -- it is unclear to me whether this interpretation is justified. It is not clear what it means that when restricting all but one entry in the purported matrix of logits $F_{i,j}$ the OKO objective have a global minimizer. I imagine that this is supposed to be contrasted with just \"standard\" minimizing of a cross-entropy loss, in which case the logits in the toy example like this would diverge even when fixed all the remaining entries. Yet it is unclear how this property by itself is related with overfiting/overconfidence of a standard training method.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper discusses quite extensively the existing literature in the topic, deals with extremely pressing issue in the machine learning community, providing a new method to address the problem. As such it has potential of having significant impact, and the paper provides experimental evidence that their proposed method outperforms the known results in terms of calibration and accuracy on standard benchmarks for.", "weaknesses": "Given how close the newly proposed method is to label smoothing with batch balancing in essence, it might be worthwhile to discuss in much more details how the proposed method is in fact different than label smoothing, especially in main body of the paper. Highlighting a bit more the Proposition 3 which they prove in appendix could improve interpretability of their paper.\n\nOn page two, in the paragraph \"Empirical\", the authors write \"OKO is a principled approach that changes the learning objective by presenting a model with _sets of examples_ instead of individual examples, as calibration is inherently a metric of sets\". This statement seems to run into a fallacy. Indeed, calibration is a metric of sets (or, one can say, distributions over pairs of predictions and outcomes, usually given as a uniform distribution on a finite set),  and indeed the learning objective here is given by presenting a model with _sets of examples_. But those two sets have nothing to do with each other. The easiest way to see it, is that the authors suggest using as a learning objective sets of size $3$ (two in-class examples, and one out-of-class (see ``Experimental details`` page 3) --- and on a set of size $3$ any statement about calibration (even for binary classification) is meaningless --- one needs at least a couple dozens of examples to this.\n\nThe main theoretical result is Theorem 1: it considers the following toy scenario, with two classes, where the feature space is $\\{0, 1, 2\\}$, and the population distribution $F_\\varepsilon$ is given as follows. With probability $1-\\varepsilon$ we have $x_i = 0$ and $y_i$ is uniformly random class $\\{0, 1\\}$. With probability $\\varepsilon/2$ we have $x_i=1, y_i=0$ and with probability $\\varepsilon/2$ we have $x_i=2, y_i=1$. They show that as $\\varepsilon \\to 0$, the OKO-minimizers tend to something that on $x=1$ outputs the predictions $(2/3, 1/3)$. This is presented as evidence that the OKO, as desired, is not over-confident in regions that are severely underrepresented in the distribution.\n\nI can see two issues with this argument: first of all it is not immediately clear that this behavior is desirable at all, it would be great to provide more of a discussion when it is the case. Even if relatively small fraction of a population distribution has a specific feature that turns out to determine exactly the outcome, as long as this is in fact a feature of population distribution (and not an artifact of small _number_ of examples in the training distribution), it is absolutely reasonable to report this outcome with high confidence on new example that exhibit this feature. It doesn't seem to be too far-fetched either: one can easily imagine having 1% of both population distribution and a training set exhibiting a feature that determines the outcome $y_i$ --- if trained on training sets with several hundred millions of examples, this leads to millions of examples with the aforementioned feature. In a situation like this it is not only reasonable, but in fact desirable to report the determined outcome with high confidence (and it is not difficult to come up with scenarios where this could be crucial).\n\nSecond issue is what the authors do not discuss, which is the fact that this behavior proved in their theorem is not an effect of the classes $x_i=1$ and $x_i=2$ represented by small fraction of the population distribution at all --- contrary to the discussion in front of the theorem. In fact, back-of-the-envelope calculation suggest that even if probabilities for $x_i=0, x_i=1, x_i=2$ where all equal $(1/3)$, and $x_i=1$ determined $y_i=0$, $x_i=2$ determined $y_i=1$, (just as in their setup), just as the label-smoothing, would learn to classify examples with $x_i=1$ as having probability of $y_i=0$ to be some number distinctively separated from $1$ (regardless of the amount of training data). This might be even more undesirable in specific situations, and crucially this sheds a different light on how to interpret their Theorem 1: the effect they discuss (of producing a confidence for the label strictly bounded away from $1$) is not introduced by the fact that only vanishingly small fraction of the population has features that seems to determine the label $y_i$ (as suggested by the name of the paragraph ``OKO is less certain in low-data regions''), it is in fact just a consequence of an implicit label-smoothing.\n\nMinor issues regarding the presentation:\nThere is a lot of plots, stacked together in extremely small space, often on each of the multiple sub-figures in a figure, there is 8 different plots with trend lines, making most of them completely unreadable, and as such not adding much value. That is particularly true about Figure 1, Figure 3, Figure 4, Figure 5.\n\nThe statement of Theorem 1 is somewhat awkward: it consist of two separate sentences --- the first part states using symbols, that for any $\\varepsilon$ there exist a minimize for the OKO objective on a distribution $F_\\varepsilon$ --- since a statements of this form are often trivial (and the nature of local/global minimizes is the object of study), it takes a bit of time for a reader to understand its importance in this specific situation. It might be worth to expand it slightly --- as it is, the ``Furthermore, ...'' part of the theorem seems on the first glance as the only one conveying meaning.\n\nI am rather confused by the notion of \"relative cross-entropy\". This seems to be just KL-divergence. The authors say that it is ``very similar yo KL divergence but with different entropy term''. The $RC(P, Q)$ is defined as $H(P, Q) - H(Q)$ (Definition 1), the KL-divergence is $D_{KL}(P || Q) = H(P, Q) - H(P)$, hence $RC(P, Q) = D_{KL}(Q || P)$. The authors say that it is (unlike KL-divergence) not always non-negative, which doesn't seem possible.\n\nThe statement of Lemma 1 does not seem to match the explanation  preceding it, and it is not clear what it was meant. Anyway, the conclusion seems true, since the KL-divergence is indeed non-negative without any additional assumptions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x3MmxIGopD", "reviewer": "Reviewer_ALEr", "summary": "This paper proposed a modified loss function that can achieve more accurate and more calibrated classification models. The idea is to define a loss based on a set of instances (and their ground truth). Within each set, two instances are from the same class, and the other k instances are from k distinct classes. The proposed soft loss modifies the cross-entropy loss by replacing the instance-level regression function f by the sum of f functions over the set, and the instance level one-hot ground-truth group indicator by the sample proportion in the set. For the hard loss variant, the instance level one-hot ground-truth group indicator is replaced by the indicator of the most common class in the set.\n\nThe authors contend that such modifications foster improved accuracy and calibration, a claim substantiated through comprehensive empirical studies. Nonetheless, the paper does not thoroughly explain the underlying benefits of this proposed method, leaving the reader with an incomplete understanding.\n\nAdditionally, the paper presents a novel calibration metric dubbed 'relative cross-entropy' (RC). This introduction, however, appears to be executed hastily, with a significant number of details absent, which might leave the concept open to further exploration and clarification.", "questions": "1. page 1 stated that \"By construction, this paradigm ignores information that may be found in correlations between sets of data.\" I do not think \"correlation\" is the correct word here. I do not see how correlation is explicitly exploited in the newly defined loss function.  Moreover, shouldn't it be the relationship among points in the same set instead of the relationship among different sets?\n\n2. Page 3, algorithm 1: Is it guaranteed that each class is sampled at least once as the pair class? If not, then some class may not be represented in the model.\n\n3. Page 3, equation (1). The inner product is a summation over classes, and the loss function will be summed over sets. Hence, the proposed soft loss essentially boils down to an exchange of the order of summations: the traditional cross-entropy loss sum over instances (in a set) first, and then over the classes; in the proposed loss, one sums over the classes first, and then over the instances within a set. It is then intriguing as to why the improved performance? In a sense, (2) is even closer to the cross-entropy loss than (1), since in (2) only the instance level f function is replaced by the aggregate of (k+2) f functions. In the numerical studies, the soft loss is not presented at all because \"we found the hard loss to always outperform the soft loss\". I cannot help wondering if the soft loss is even better or on par with the baselines?\n\n4. Since k does not really matter, can it be zero? In fact, can we have more than 2 instances from the dominating class in a set. In this case, (2) would be very similar to a multi-instance learning method.\n\n5. Page 5 stated that \"The key observation from Theorem 1 is that, although x = 1 or x = 2 have zero entropy and are thus low-entropy regions, OKO is still uncertain about these points because the occur infrequently\". However, this is not necessarily a good thing (or not good enough). For example, the result of Theorem 1 does not say that the calibration is correct. In fact, I am not even sure how to define the calibration in this example because the limit portability distribution seems weird to me: it is distributed as 1/0 when epsilon is greater than 0 and 0/0 when epsilon = 0. Specifically, the limit of epsilon = 0 is a singular case. Can this be generalized to more general settings? In summary, Theorem 1 is about a fairly special case, and even in that case it does not explicitly show that the calibration is correct.\n\n6. I am very puzzled by the subsection titled \"Relative Cross-Entropy for Calibration\" in Section 4. This RC has nothing to do with OKO and should not be part of a section titled \"Properties of OKO\". Moreover, this subsection reads very out of context. It is unfortunate that relevant discussion is in the appendix, making it very difficult for the reader to see its relevancy to the topic being discussed in the main text. \n\n7. Page 6 stated that \"RC is no longer proper due to this zero mean.\" What does \"proper\" mean? \n\n8. Page 6 stated that \"we report results for a version of OKO with k = 1 where in addition to the pair class prediction (see Eq. 2) a model is\ntrained to classify the odd class with a second classification head that is discarded at inference time.\" How is the overall objective including the second classification head defined? A mathematic formula and/or a graph of the network structure would be helpful.\n\n9. Page 6 stated that \"For simplicity and fairness of comparing against single example methods, we set the maximum number of randomly sampled sets to the total number of training data points ntrain in every setting.\" In my opinion, it is still not a fair comparison since for the OKO method there are 3n instances out of the n sets.\n\n10. It is unclear to me what I should look for in Figure 4? Why is one method better than another and how is such an advantage shown in the figure? More specific pointers should be helpful.\n\n11. Page 9 stated that \"OKO is a theoretically grounded learning algorithm that modifies the training objective into a classification problem for sets of data. We show various consistency proofs and theoretical analyses proving that OKO yields smoother logits than standard cross-entropy, corroborated by empirical results.\" I strongly disagree with this statement. In the main text there is only one theorem, which, as I mentioned above in question 5, is not strong enough. There is no consistency results in the main text. \n\n12. In C.1 it stated \"Before proving Proposition 2 from the main text ....\"  Proposition 2 is in the appendix, not in the main text.\n\n13. It is clear to me that this paper was writing as a long, comprehensive paper. However, it was trimmed down to 9 pages in order to submit to ICLR, in a rush. For this reason, the presentation of the topics is very poor. There are too many topics in this 9 page paper, and the author did not make a convincing case advocating for the proposed method. Moreover, because of the careless reduction of topics, there are topics that read out of context (e.g. the introduction of RC), and there are topics that should have been explained more (e.g. theoretical justification of the proposed loss.) I think it may serve the readers better by submitting a comprehensive version of the paper to a journal such as JMLR, instead of rushing through a conference.", "limitations": "", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The proposed loss function seems to be interesting and numerical results show good performance.", "weaknesses": "The theoretical underpinnings presented in the paper are not robustly developed.\n\nThe organization of the manuscript lacks coherence, with various concepts introduced but not adequately interconnected or explicated.\n\nFor further elaboration on these points, please refer to the questions outlined below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pfgQNtR1R8", "reviewer": "Reviewer_S9eW", "summary": "The submission addresses the problem of multi-class learning, where the purpose is to reduce the overconfidence of the model by using a specific decomposition of the problem called odd-k-out learning. OKO learning amounts to separate a positive class (or pair class) in which two instances are randomly selected, from a set of negative classes (or odd class) for each of which one instance is selected. The authors show that this makes it possible to obtain less certain model outputs in low-density regions, and thus to restrain miscalibration. Some properties of OKO are rapidly presented, before experiments are reported and a conclusion is drawn.", "questions": "The \"set learning\" problem you mention in the introduction is not formally defined, nor is the odd-one-out scheme in Section 2. \n\nAs far as I understand, OKO consists in transforming the classification problem into a binary classification problem, as made in the \"error-correcting output coding\" decomposition strategy. Could you explain the difference between OKO and ECOC ? \n\nIn Section 3, you explain how to construct a training example for the OKO setting. I assume this operation is repeated. Could you elucidate how instance generation can be repeated in the global OKO setting ? \n\nCould you provide information on the results obtained using the soft loss, and/or insights regarding why the hard loss would give better results than the soft loss ? \n\nSection 4 is very short. Theorem 1 seems to be limited to the example discussed. The section seems to call for a discussion on the different natures of uncertainty (i.e., aleatory vs epistemic uncertainty) and on the different treatments to be applied accordingly. \n\nYou emphasize the similarity between the relative cross-entropy for calibration you use and the KL divergence. Can you elucidate the advantages of RCE for calibration over KL divergence ? \n\nYou set $k=1$ for all experiments: this seems to correspond to a very special case of OKO. Could you explain the impact of this choice ? This somehow mitigates the conclusions that can be drawn from the experimental part, as it seems difficult to generalize them. Can you elaborate ? \n\nTypos and writing : \n- I do not understand the notation in Equation (3) (\"$f_\\epsilon \\in ...\"); \n- \"the occur infrequently\" (page 5 bottom); \n- \"can be boosted by predicting the odd class using an additional classification head\" (page 6) : I do not understand this sentence.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The language is overall fine. \n\nThe experimental results seem convincing.", "weaknesses": "OKO is only rapidly presented, through how instances are constructed. The overall procedure remains unclear. \n\nThe properties of OKO are succinctly mentioned, but the theoretical reasons for which OKO outperforms classical classifiers are not crystal clear. \n\nThe case considered in the experiments seems to be a very special case, and it is difficult to see whether the conclusions drawn can be generalized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O4OEPdAxVR", "reviewer": "Reviewer_ZKiJ", "summary": "The paper proposes a new model training paradigm by minimizing the cross-entropy error for sets, rather than for individual examples. The method allows model to capture correlations across samples, and is believed to achieve better accuracy and calibration. The authors provide theoretical on calibration along with extensive experiment results to demonstrate the effectiveness of the method.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality: The set learning applied for training machine learning models is a pretty novel concept and paradigm change. \n\nQuality: The paper is well written with high quality. The authors provide detailed motivations, illustrative figures and comprehensive appendix. \n\nClarity: The paper is written with clarity and easy to follow.\n\nSignificance: I believe the paper is of great significance to both academia and industry. Set learning is a new paradigm change to how people usually train ML models. The additional benefits brought upon on calibration is important for various applications in industry.", "weaknesses": "Mainly I have some questions on the experiment.\n\n1. The authors set the maximum number of randomly sampled sets to the total number of training data points, such that the gradients updates remain the same. However, does this effectively make the proposed method sees k multiple more data points compared to the standard setting? It would be interesting to see how the experiment results look like when two algorithms are of the sample complexity. \n\n2. Is there any intuitions behind why the hard loss always outperform the soft loss?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)