Training Over-parameterized Models with Non-decomposable Objectives
Year: 2022

Abstract:
Many modern machine learning applications come with complex and nuanced design goals such as minimizing the worst-case error, satisfying a given precision or recall target, or enforcing group-fairness constraints. Popular techniques for optimizing such non-decomposable objectives reduce the problem into a sequence of cost-sensitive learning tasks, each of which is then solved by re-weighting the training loss with example-specific costs. We point out that the standard approach of re-weighting the loss to incorporate label costs can produce unsatisfactory results when used to train over-parameterized models. As a remedy, we propose new costsensitive losses that extend the classical idea of logit adjustment to handle more general cost matrices. Our losses are calibrated, and can be further improved with distilled labels from a teacher model. Through experiments on benchmark image datasets, we showcase the effectiveness of our approach in training ResNet models with common robust and constrained optimization objectives.

heading: 1 Introduction
text: The misclassification error is the canonical performance measure in most treatments of classification problems [92]. While appealing in its simplicity, practical machine learning applications often come with more complex and nuanced design goals. For example, these may include minimizing the worst-case error across all classes [64], satisfying a given precision or recall target [106], enforcing minimal coverage for minority classes [31], or imposing group-fairness constraints [105]. Unlike the misclassification error, such objectives are non-decomposable, i.e., they cannot be expressed as a sum of losses over individual samples. This poses a non-trivial optimization challenge, which is typically addressed by reducing the problem into a sequence of cost-sensitive learning tasks [12, 25, 4, 16, 71]. Such reduction-based approaches have been successfully employed in many open-source libraries [3, 2, 1] to provide drop-in replacements for standard loss functions.
In this paper, we point out that the standard approach of re-weighting the training loss to incorporate label costs can produce unsatisfactory results when used with high capacity models, which are often trained to memorize the training data. Such over-parameterized models are frequently encountered in the use of modern neural networks, and have been the subject of considerable recent study [107, 73, 66]. As a remedy, we provide new calibrated losses for cost-sensitive learning that are better equipped at training over-parameterized models to optimize non-decomposable metrics, and demonstrate their effectiveness on benchmark image classification tasks. Our main contributions are as follows:
(i) we illustrate the pitfalls of using loss re-weighting in over-parameterized settings, particularly with diagonal class weights (Section 3).
(ii) we propose new logit-adjusted losses for cost-sensitive learning for both diagonal and nondiagonal gain matrices, and show that they are calibrated (Section 4).
(iii) we demonstrate that our losses provide significant gains over loss re-weighting in training ResNet models to optimize worst-case recall and to enforce coverage constraints (Section 5).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
(iv) we show that the proposed approach compares favorably to post-hoc correction strategies, and can be further improved by distilling scores from a teacher model (Section 6).

heading: 1.1 Related Work
text: We cover prior work on class-imbalanced learning, cost-sensitive learning, and complex metrics.
Learning under class imbalance. A common setting where metrics beyond the misclassification error have been studied is the problem of class imbalance [49, 11, 33]. Here, the label distribution P(y) is skewed, and one seeks to ensure that performance on rare classes do not overly suffer. To this end, common metrics include the average of per-class recalls (also known as the balanced accuracy) [7, 62], quadratic mean of per-class accuracies [51], and the F-score [54].
A panoply of different techniques have been explored for this problem, spurred in part by recent interest in the specific context of neural networks (where the problem is termed long-tail learning) [91, 9], with the focus largely on optimizing balanced accuracy. An exhaustive survey is beyond the scope of this paper (see, e.g,. [33, 39]), but we may roughly identify three main strands of work: data modification [48, 11, 93, 103, 108], loss modification [107, 18, 10, 88, 37, 79, 97, 63, 21, 45, 94], and prediction modification [28, 43, 76, 60, 13, 40, 110]. A related recent thread seeks to improve performance on rare subgroups [82, 83, 86], as a means to ensure model fairness [24].
Amongst loss modification techniques, two strategies are of particular relevance. The first is reweighting techniques [100, 65, 18]. As has been noted [55, 96, 61] (and as we shall subsequently verify), these may have limited effect on training samples that are perfectly separable under a given model class (as is the case with overparameterized models). The second is margin techniques, which enforce a class-dependent margin in the loss [10, 88, 79, 63, 94]. This seeks to ensure that rare classes are separated with greater confidence, to account for the higher uncertainty in their decision boundary.
Cost-sensitive learning. Cost-sensitive learning is a classical extension of standard multiclass classification, wherein errors on different classes incur different costs [26, 23, 85]. Strategies for this problem largely mirror those for class imbalance, which can be seen as imposing a particular set of costs dependent on the label frequencies [58]. In particular, loss modification techniques based on asymmetric weights [57, 98, 104, 5, 19, 22, 85, 112] and margins [61, 44, 36, 45] have been explored, with the latter proving useful on separable problems. Amongst these, Lin et al. [57] handle a general cost matrix for multiclass problems, but require the class scores to sum to 0, a constraint that might be difficult to impose with neural networks. Khan et al. [44] propose a multiclass loss similar to the logit adjustment idea used in this paper, but only handle a specific type of cost matrix (e.g., in their setup, the default cost matrix is a matrix of all 1s). The standard multiclass loss of Crammer and Singer [17] can also be extended to handle a general cost matrix [90], but unfortunately is not calibrated [78].
Complex metrics. There has been much work on extending the class imbalance literature to handle more complex metrics and to impose data-dependent constraints. These methods can again be divided into loss modifications [38, 74, 41, 69, 42, 31, 25, 4, 16, 71, 27, 59, 50] and post-hoc prediction modifications [102, 68, 46, 70, 72, 32, 20, 67, 101, 89], and differ in how they decompose the problem into simpler cost-sensitive formulations (see [71] for a unified treatment of common reduction strategies). Most of these papers experiment with simple models, with the exception of Sanyal et al. [84], who use re-weighting strategies to train shallow DNNs, Kumar et al. [50], who train CNNs on binary-labeled problems, and Eban et al. [25], who train InceptionNets to optimize an AUC-based ranking metric. There have also been other attempts at training neural networks with ranking metrics [87, 35, 8, 77]. In contrast, our focus is on handling a general family of evaluation metrics popular in multiclass classification problems.

heading: 2 Non-decomposable Objectives
text: Notations. Let [m] = {1, . . . ,m}. Let m be the (m 1)-dimensional simplex with m coordinates. Let 1m 2 Rm denote an all 1s vector of size m, and diag(u1, . . . , um) denote a m ⇥m diagonal matrix with diagonal elements u1, . . . , um. For vectors a,b 2 Rm, a/b denotes element-wise division. Let softmaxi(s) =
exp(si)Pm j=1 exp(sj) denote a softmax transformation of scores s 2 Rm.
Consider a multiclass problem with an instance space X ✓ Rd and a label space Y = [m]. Let D denote the underlying data distribution over X ⇥ [m], DX denote the marginal distribution over the
Algorithm 1 Reductions-based Algorithm for Maximizing Worst-case Recall (1) Inputs: Training set S, Validation set Sval, Step-size ! 2 R+, Class priors ⇡, CS-loss `G Initialize: Classifier h0, Multipliers 0 2 m for t = 0 to T 1 do
Update : t+1i = t i exp ⇣ ! bCii[ht] ⇡i ⌘ , 8i,where bCij [h] = 1|Sval| P (x,y)2Sval 1(y = i, h(x) = j)
t+1i = t+1iPm
j=1 t+1 j
, 8i
G = diag( t+11 /⇡1, . . . , t+1m /⇡m)
Cost-sensitive Learning (CSL): st+1 2 argmins 1 |S| P (x,y)2S `G(y, s(x)) // Replaced by few steps of SGD
ht+1(x) 2 argmaxi2[m] s t+1 i (x), 8x
end for return hT
instances X , and ⇡i = P(y = i) denote the class priors. We will use pi(x) = P(y = i|x) to denote the conditional-class probability for instance x. Our goal is to learn a classifier h : X![m], and will measure its performance in terms of its confusion matrix C[h], where
Cij [h] = E(x,y)⇠D [1 (y = i, h(x) = j)] .
Complex learning problems. In the standard setup, one is often interested in maximizing the overall classification accuracy acc[h] = P i Cii[h]. However, in many practical settings, one may care about other metrics such as the recall for class i, reci[h] = Cii[h] ⇡i , the precision on class i, preci[h] = Cii[h]P j Cji ,
or the proportion of predictions made on class i, i.e. the coverage, covi[h] = P
j Cji. Below are common examples of real-world design goals based on these metrics.
Example 1 (Maximizing worst-case recall). In class-imbalanced settings, where the classifier tends to generalize poorly on the rare classes, we may wish to change the training objective to directly maximize the minimum recall across all classes [12]:
max h min i2[m]
Cii[h]
⇡i . (1)
Example 2 (Constraining per-class coverage). Another consequence of label imbalance could be that the proportion of predictions that the classifier makes for the tail classes is lower than the actual prevalence of that class. The following learning problem seeks to maximize the average recall while explicitly constraining the classifier’s coverage for class j to be at least 95% of its prior ⇡j [16, 71]:
max h
1
m
mX
i=1
Cii[h]
⇡i s.t.
mX
i=1
Cij [h] 0.95⇥ ⇡j , 8j 2 [m]. (2)
Other examples include constraints on recall and precision (see Table 1), the F-measure, and the area under the ROC and PR curves, as well as fairness constraints like equal opportunity, which are computed on group-specific versions of the confusion matrix [25, 71, 15, 32, 4].
Reduction to cost-sensitive learning. All the problems described above are non-decomposable, in the sense that, they cannot be written as minimization of a sum of errors on individual examples, and hence cannot be tackled using common off-the-shelf learning algorithms. The dominant approach for solving such problems is to formulate a sequence of cost-sensitive objectives, which do take the form of an average of training errors [70, 12, 4, 16]. For example, the robust learning problem in (1) can be equivalently re-written as the following saddle-point optimization problem:
max h min 2 m
mX
i=1
i Cii[h]
⇡i , (3)
where i is a multiplier for class i. One can then find a saddle-point for (3) by jointly minimizing the weighted objective over 2 m (using e.g. exponentiated-gradient updates) and maximizing
the objective over h. Notice that for a fixed , the optimization over h is a cost-sensitive (or a gain-weighted) learning problem:
max h
X
i,j
GijCij [h], (4)
where Gii = i⇡i and Gij = 0, 8i 6= j are the rewards associated with predicting class j when the true class is i. We will refer to G 2 Rm⇥m as the “gain” matrix, which in this case is diagonal. In practice, the cost-sensitive learning problem in (4) is usually replaced with multiple steps of gradient descent, interleaved with the updates on . Algorithm 1 provides an outline of this procedure.
Similar to (1), the constrained learning problem in (2) can be written as an equivalent (Lagrangian) min-max problem with Lagrange multipliers 2 Rm+ :
max h min 2Rm+
1
m
mX
i=1
1
⇡i Cii[h] +
mX
j=1
j ⇣ mX
i=1
Cij [h] 0.95⇡j ⌘ .
One can find a saddle-point for this problem by jointly minimizing the Lagrangian over 2 Rm+ (using e.g. gradient updates) and maximizing it over h, with the maximization over h taking the form of a cost-sensitive learning problem. In this case, the gain matrix G is non-diagonal and is given by Gii =
1 m⇡i + i, 8i and Gij = j , 8i 6= j. See Table 1 for the form of the gain matrix for other common constraints. In Appendix A, we provide an outline of this procedure (Algorithm 2), and also elaborate on how this reduction-based approach can be extended to optimize other common evaluation metrics such F-measure [25, 71].
Cost-sensitive losses. A standard approach for solving the cost-sensitive learning problem in (4) is to use a surrogate loss function ` : [m] ⇥ Rm!R+ that takes a label y and a m-dimensional score u 2 Rm, and outputs a real value `(y,u). One would then minimize the expected loss L(s) = Ex,y [`(y, s(x))] over a class of scoring function s : X!Rm that map each instance to an m-dimensional score. The final classifier h⇤ can then be obtained from the learned scoring function s⇤ by taking an argmax of its predicted scores, i.e. by constructing h⇤(x) 2 argmaxi2[m] s⇤i (x).
In practice, we are provided a finite sample S = {(x1, y1), . . . , (xn, yn)} drawn from D, and will seek to minimize the average loss on S, given by bL(s) = 1
|S| P (x,y)2S `(y, s(x)). We will also
assume access to a held-out validation sample Sval = {(x1, y1), . . . , (xnval , ynval)}.
One common sanity check for a “good” loss function is to confirm that it is classification calibrated (or Fisher consistent) for the learning problem of interest [6]. Loosely speaking, a surrogate loss ` is classification calibrated if the minimizers of the conditional risk Ey|x(`(y, s(x))) over all scoring functions s : X!Rm coincide with the Bayes-optimal prediction for x. For the cost-sensitive objective in (4), the Bayes-optimal classifier is given below [53]. Proposition 1. The optimal classifier for (4) for a general gain matrix G 2 Rm⇥m is of the form:
h⇤(x) 2 argmaxy2[m] Pm i=1 Giy pi(x) = argmaxy2[m](G >p(x))y.
All proofs can be found in Appendix B.

heading: 3 The Perils of Over-parameterization
text: We now point out the problems in applying the algorithms described previously to models that are over-parameterized, i.e., which contain enough parameters to perfectly fit the labels in the training set. We will focus particularly on the loss used for cost-sensitive learning steps in Algorithms 1–2.
Limitations of loss re-weighting. One of the most common loss function for a diagonal gain matrix G is a simple re-scaling of the standard cross-entropy loss with the diagonal weights:
`wt(y, s) = Gy,y log ✓ exp(sy)P j exp(sj) ◆ . (5)
The following is a natural extension of this re-weighted loss to a general gain matrix G, used, for example, in constrained optimization libraries [3], and also for mitigating label noise [75]:
`wt(y, s) = mX
i=1
Gy,i log ✓ exp(si)P j exp(sj) ◆ . (6)
While this weighted loss is calibrated for G (see, e.g., [75]), it is often inadequate when training an over-parameterized model on a finite sample. This is evident when G is a diagonal matrix: such a model will usually memorize the training labels and achieve zero training loss for every class, irrespective of what we choose for the outer weighting. In such separable settings, it is unclear how the outer weighting will impact the model’s out-of-sample performance on different classes.
For clarity, we provide a simple illustration in Figure 1, where we use a re-weighted loss to train ResNet-56 models on 10000 images from CIFAR-10 with different diagonal gain matrices G. We assign a weight of ! to the first class “airplane”, and a weight of 1 on all other classes (i.e. set G1,1 = ! and Gy,y = 1, 8y 6= 1), and plot the normalized weighted accuracy P y GyyCyy[h]/ P y Gyy on the test set as we vary !. Compared to an unweighted cross-entropy loss, the re-weighted loss does not produce a significant change to the test metric, whereas the logit-adjusted loss (which we will discuss in Section 4) yields substantially better values. Probing closer into the test accuracy for each class, we see that the re-weighted loss yields slightly better accuracies for class 1, but is significantly worse-off on the other classes, suggesting that re-weighting has the effect of excessively focusing on the class with the higher weight at the cost of the other classes. Sagawa et al. [83] also make a similar observation when using importance weights to improve worst-group generalization, while Cui et al. [18], Cao et al. [10] observe that up-weighting the minority classes can lead to unstable optimization.
When G is not diagonal, the minimum training loss may not be zero. Nonetheless, the following proposition sheds some light on the scores learned by a model that achieves minimum training loss.
Proposition 2. Suppose the instances x in S are all unique. Let bLwt(s) = 1 |S| P (x,y)2S ` wt(y, s(x)) denote the average loss on training sample S with `wt defined as in (6) for a gain matrix G. Then a scoring function bs that achieves the minimum value of bLwt(s) over all s : X!Rm is of the form: softmaxi(bs(x)) = Gy,iP
j Gy,j , 8(x, y) 2 S.
Notice that the model output is invariant to re-scaling of the rows in G, i.e., one can multiply each row of the gain matrix G by a different scalar, and the values memorized by the model for each training example will remain unchanged. On the other hand, re-scaling a column of G does substantially change the score learned for each example. While this does not tell us about how the model would
behave on unseen new examples, our experience has been that loss re-weighting is usually effective when used to control the amount of out-of-sample predictions that a model makes for a certain class (by suitably scaling the column for that class in G), but does not work well when used to emphasize greater accuracy on a particular class. Consequently, we find that loss re-weighting usually fares better with metrics like coverage that depend only on the model predictions and not on the true labels, than with metrics like recall which depend on both the predictions and labels.
Existing remedies for better generalization. The literature offers some remedy to improve model generalization with non-standard objectives. Sagawa et al. [83] improve performance on rare subgroups by regularizing the losses based on the size of each group, but their solution applies to a specific learning problem. Other remedies such as smarter re-weighting strategies [56, 18] or deferred re-weighting schedules [10] have proven to work well in specialized imbalanced settings.
The work that most closely relates to our setting is Cotter et al. [14], who propose a simple modification to the algorithms discussed in Section 2, with the use of two datasets: a training sample S, and a held-out validation sample Sval. They suggest using the validation sample to perform updates on the multipliers and in turn the gain matrix G, and the training sample to solve the resulting cost-sensitive learning problem in (4). The latter would typically involve optimizing the empirical risk on the training set 1
|S| P (x,y)2S `G(y, s(x)), for some cost-sensitive loss `G. The intuition here is that,
even when a model achieves very low training error, the estimate of G will accurately reflect the model’s performance on held-out examples. While this modification improves our estimate of G, it only provides a partial solution for over-parameterized settings, where the model would still struggle to generalize well if `G happens to be the simple re-weighted loss in (6).

heading: 4 Cost-sensitive Losses Based on Logit Adjustment
text: We present new cost-sensitive losses that seek to avoid the problems mentioned above. We build on recent work on logit adjustment, shown previously to be effective in long tail settings [79, 63, 94].
Diagonal gain matrix. When the gain matrix G is diagonal, Proposition 1 tells us that the Bayes-optimal classifier for the resulting weighted accuracy metric is of the form h⇤(x) 2 argmaxy2[m] Gyy py(x), where py(x) = P(y|x). Intuitively, we would like the learned scoring function s(x) to mimic the Bayes-optimal scores Gyy py(x) for each x. In particular, we would like the maximizer of sy(x) over labels y to match the Bayes-optimal label for x.
One way to facilitate this is to adjust the scores sy(x) based on the diagonal weights Gyy, and to compute a loss on the adjusted scores. Specifically, we shift sy(x) to s̄y(x) = sy(x) log(Gyy), and optimize the shifted scores so that their softmax transformation matches the class probabilities p(x). This would then encourage the original scorer s to be monotonic in the Bayes optimal scores:
exp(s̄y(x))P j exp(s̄j(x)) = py(x) () s̄y(x) / ln(py(x)) () sy(x) / ln(Gyy py(x)).
In practice, p(x) is not directly available to us, and so we employ the following logit-adjusted cross-entropy loss that implements this idea with labels y drawn according to p(x):
`LA(y, s) = log ✓ exp(sy log(Gyy))P j exp(sj log(Gjj)) ◆ . (7)
This loss is a simple generalization of the one analyzed in Ren et al. [79], Menon et al. [63], Wang et al. [94], in which the logits are adjusted based on the class priors to optimize the balanced error rate. Such approaches have historical precedent in the class imbalance literature [76, 111, 13]. Proposition 3. The logit-adjusted loss `LA is calibrated for a diagonal gain matrix G.
Unlike the weighted loss in (5), changing the diagonal entries of G in (7) changes the operating point of the learned scoring function. In separable settings, this would mean that the diagonal weights will determine the operating point at which the model achieves zero training error, and tend to push the separator towards classes that have higher weights, thus helping improve model generalization. An alternate explanation posed by Menon et al. [63] re-writes the loss in a pair-wise form:
`LA(y, s) = log ✓ 1 + X
j 6=y
exp yj (sy sj)
◆ , (8)
where yj = log(Gyy/Gjj) can be seen as the relative margin between class y and class j. This tells us that the loss encourages a larger separation between classes that have different weights. In Appendix C, we elaborate on this margin interpretation and point out that this loss can in fact be seen as a soft-approximation to the more traditional margin-based loss of Crammer and Singer [17].
General gain matrix. When the gain matrix G is non-diagonal, a simple logit adjustment no longer works. In this case, we propose a hybrid approach that combines logit adjustment with an outer weighting. To this end, we prescribe factorizing the gain matrix into a product G = MD for some diagonal matrix D 2 Rm⇥m, and M = GD 1. The proposed loss then adjusts the logits to account for the diagonal entries of D and applies an outer weighting to account for M:
`hyb(y, s) = mX
i=1
Myi log ✓ exp(si log(Dii))P j exp(sj log(Djj)) ◆ . (9)
In practice, D can be chosen to reflect the relative importance of the classes and include information such as the class priors, which cannot be effectively incorporated as part of the outer weighting. One simple choice could be D = diag(1/⇡1, . . . , 1/⇡m). Another intuitive choice could be to D = diag(G11, . . . , Gmm), so that the residual matrix M = GD 1 that serves as the outer weighting has 1s in all its diagonal entries, and thus equal weights on the diagonal loss terms. Proposition 4. For any diagonal matrix D 2 Rm⇥m with Dyy > 0, 8y, and M = GD 1, the hybrid loss `hyb is calibrated for G.
In some special cases, we may be able to avoid the outer-weighting: e.g., when the gain matrix is the sum of a diagonal matrix and a matrix with equal rows, i.e. G = diag(↵) + 1 > (cf. Table 1, rows 3 & 4), the Bayes-optimal classifier from Proposition 1 is of the form h⇤(x) = argmaxy2[m] ↵ypy(x)+ y. The additive terms y in the optimal classifier can then be encoded in the loss as a shift to the softmax output, giving us the following softmax-shifted loss: for constant C > 0,
`SMS(y, s) = log C exp(sy log(↵y))P j exp(sj log(↵j))
y/↵y
! . (10)
Proposition 5. `SMS is calibrated for the gain matrix G = diag(↵)+1 > when C = 1+ P
y y/↵y .
See Appendix D for a practical variant this loss that avoids a negative value within the log.

heading: 5 Experimental Comparison with Loss Re-weighting
text: We now showcase that the proposed losses provide substantial gains over loss re-weighting through experiments on three benchmark datasets: CIFAR-10, CIFAR-100 [47], and TinyImageNet [52, 80] (a subset of the ImageNet dataset with 200 classes). Similar to [18, 10, 63], we use long-tail versions of these datasets by downsampling examples with an exponential decay in the per-class sizes. We set the imbalance ratio maxi P(y=i)mini P(y=i) to 100 for CIFAR-10 and CIFAR-100, and to 83 for TinyImageNet (the slightly smaller ratio is to ensure that the smallest class is of a reasonable size). In each case, we use a balanced validation sample of 5000 held-out images, and a balanced test set of the same size.
We trained ResNet-56 models on CIFAR-10 and CIFAR-100, and ResNet-18 models on TinyImageNet, using SGD with momentum. We provide details about our hyper-parameters choices in Appendix E. On CIFAR-10 and CIFAR-100, the ResNet-56 architectures have sufficient parameters to perfectly fit the training labels, as evident from the training set metrics reported in Appendix E.1.1
Cost-sensitive learning and baselines. We consider two learning objectives: maximizing worst-case recall, and maximizing average recall subject to coverage constraints. As outlined in Algorithms 1–2, we employ the “two dataset” approach of Cotter et al. [14] (discussed in Section 3) to solve these problems, with the validation set used for updates on the gain matrix G, and the training set used for the cost-sensitive learning (CSL) step. Since our goal here is to demonstrate that the the proposed losses fair better at solving the CSL step than loss re-weighting, we use a large validation sample to get good estimates of the gain matrix G. For the CIFAR datasets, we perform 32 SGD steps on
1Code will be made available at: https://github.com/google-research/google-research/tree/ master/non_decomp
the cost-sensitive loss for every update on G, and for TinyImageNet, we perform 100 SGD steps for every update on G. In each case, we compare the results with empirical risk minimization (ERM) with the standard cross-entropy loss, and as representative methods that seek to maximize the average per-class recall (i.e. balanced accuracy), we include the balanced logit-adjusted loss of Menon et al. [63] in which the adjustments are based on the class priors alone (Balanced), the equalized loss of Tan et al. [88] (Equalized), and the adaptive margin loss of Cao et al. [10] (Adaptive).
Maximizing worst-case recall. In our first task, we maximize the worst-case recall over all 10 classes on CIFAR-10 (cf. (1)). Given the larger number of classes, this can be a very restrictive goal for CIFAR-100 and TinyImageNet, leading to poor overall performance. So for these datasets, we will consider a simpler goal, where we measure the average recall on the bottom 10% of the smallest-sized classes (the “tail” recall), and the average recall on the top 90% of the classes (the “head” recall), and seek to maximize the minimum of the head and tail recalls:
max h min n 1 |H| X
y2H
recy[h], 1
|T |
X
y2T
recy[h] o ,
where H ⇢ [m] and T ⇢ [m] denote the set of head and tail labels respectively. The gain matrix G for these problems is diagonal. In Table 2, we present results of maximizing the worst-case recall metrics using Algorithm 1, with both the re-weighted loss in (5) and the proposed logit-adjusted loss for a diagonal G in (7) used in the CSL step. Compared to loss re-weighting, the prescribed loss provides huge gains in the worst-case recalls. In fact, on the CIFAR datasets, loss re-weighting fairs significantly worse than using the simple logit adjustment with class priors prescribed by Menon et al. [63], which performs the best on the average recall metric that it seeks to maximize. Our approach improves substantially over this baseline on the worst-case recall, at the cost of a moderate decrease in the average recall.
Constraining coverage. The next task we consider for CIFAR-10 seeks to ensure that when evaluated on a balanced dataset, the model makes the same proportion of predictions for each class. This leads us to the optimization problem shown in row 5 of Table 1, where we wish to maximize the average recall, constraining the model’s “balanced coverage” on each class bcovy[h] = Pm i=1 1 ⇡i Ciy[h] to be at least 95% of 1m , where m is the number of classes. Because the validation and test samples are already balanced, the model’s coverage on these datasets is the same as its balanced coverage. For CIFAR-100 and TinyImageNet, we consider the simpler goal of maximizing the average recall over all classes, with constraints on the model’s average coverage over the head labels, and its average coverage over the tail labels to be both at least 95% of 1m :
max h
1
m
X
y2[m]
recy[h] s.t. 1
|H|
X
y2H
bcovy[h] 0.95 1
m ,
1
|T |
X
y2T
bcovy[h] 0.95 1
m .
The gain matrix G for these problems (as shown in Table 1) is non-diagonal, and does not have a special structure that we can exploit. We will therefore use the hybrid loss function that we provide in (9) for a general G, and try out both variants suggested: with the diagonal matrix D = diag(1/⇡1, . . . , 1/⇡m) (variant “A”), and with D = diag(G11, . . . , Gmm) (variant “B”). In Table 3, we present the results of applying Algorithm 2 (in the appendix) to this task, with both the re-weighted loss and the proposed losses used in the CSL step. In this case, loss re-weighting is able to match the coverage target as closely as the proposed losses on CIFAR-10 and CIFAR-100, but fares poorly on the average recall on two of the three datasets. The proposed losses are often considerably better on this metric, while yielding coverage values that are closest to the target. Between the two hybrid variants, there isn’t a clear winner, although variant “B” seems to have a slight edge. The reason we are not able to match the target in CIFAR-10 as closely as we do in the other two datasets is because of the larger number of constraints (10) that need to be satisfied (we only have 2 constraints to be satisfied for CIFAR-100 and TinyImageNet).

heading: 6 Improvements with Post-shifting and Distillation
text: Having demonstrated that the proposed losses can provide significant gains over loss re-weighting, we explore ways to further improve their performance.
Does post-shifting provide further gains? Post-hoc correction strategies have generally shown to be very effective in optimizing evaluation metrics [68, 46, 101, 89, 63], often matching the performance of more direct methods that modify the training loss. They are implemented in two steps: (i) train a
base scoring model s : X!Rm using ERM, (ii) construct a classifier that estimates the Bayes-optimal label for a given x by applying a gain matrix G 2 Rm⇥m to the predicted probabilities:
h(x) 2 argmaxy2[m] Pm i=1 Giy⌘i(x), where ⌘(x) = softmax(s(x)).
The coefficients G are usually chosen to maximize the given evaluation metric on a held-out validation set, using either a simple grid search (when the number of classes is small) or more sophisticated optimization tools [70, 89]. Table 4 shows the results of post-shifting the ERM-trained model for the tasking of maximizing worst-case recall (see Appendix E for details of how we fit the post-shift coefficients). While post-shifting provides huge improvements over ERM, our proposed approach of employing an iterative training procedure (Algorithm 1) with a modified logit-adjusted loss for the CSL step does often have a slight edge over the simpler post-shifting approach on the worst-case recall. Moreover, our proposal often yields a higher average recall, e.g., on the more difficult problem of maximizing the worst-case recall over all 100 classes in CIFAR-100-LT. Interestingly, applying the post-hoc adjustment procedure to a model trained using our iterative approach (CSL [Logit-adjusted] + PS) does not always yield further gains. For example, while maximizing the worst-case recall over all 100 classes on CIFAR-100-LT, the resulting classifier from this hybrid approach overfits to validation sample and is worse off on the test sample.
Improvements with distillation. Another technique that has proven effective in boosting the performance of neural networks is knowledge distillation, wherein soft predictions from a “teacher” model pt : X! m are used as labels to train a “student” model [34, 81, 29, 99, 109]. All the losses discussed so far can be easily applied to a distillation setup, where the training labels can be replaced with an expectation over the teacher’s label distribution: Ex⇠DX hPm y=1 p t y(x)`(y, s(x)) i . In applying these losses for cost-sensitive learning, it is important that the class priors ⇡y used to construct the gain matrices (see Table 1) be replaced with the teacher’s prior distribution ⇡ty = 1 |S| P (x,y)2S p t y(x). This is particularly important when the teacher is trained on a dataset with a different prior distribution, or its outputs are re-calibrated to yield soft predictions. We make use of the teacher’s labels only in the training sample, and retain the original one-hot labels in the validation sample.
We re-run the worst-case recall experiments on CIFAR-10 and CIFAR-100 from Section 5 with distillation, and compare a distilled version of our approach with the distilled ERM, a distilled version of the class-prior-adjusted loss of Menon et al. [63] (which performed the best in Table 2 among all methods that sought to maximize average recall), and a distilled version of loss re-weighting. In each case, we employ self-distillation and use the same ResNet-56 architecture for both the teacher and the student. As shown in Table 5, distillation provides improvements across the board. Interestingly, loss re-weighting is quite competitive in this case, and has a slight edge on CIFAR-100. We attribute this surprising improvement in performance to the teacher prior distribution ⇡ty being significantly more balanced than the original class priors, and as a result, the costs Gyy in the optimization of the worst-case recall in Algorithm 1 being less drastically different across classes.

heading: 7 Conclusions
text: We have proposed new cost-sensitive losses based on logit adjustment for training over-parameterized models with non-decomposable metrics. Our losses serve as replacements for and provide significant gains over standard loss re-weighting strategies used as a part of the iterative reduction-based approach to optimize such metrics. We show that our proposal compares favorably to the common post-shifting baseline, and can be further improved with distillation. While we considered two representative tasks in our experiments (maximizing worst-case recall and constraining coverage), the reductions-based approach that we employ and the losses that we propose apply to general evaluation metrics such as the F-measure, the AUC-PR, and common fairness goals [25, 4, 67].
A limitation of our losses is that while they are calibrated, these guarantees only hold in the large sample limit. In the future, we wish to probe further into why our loses improve generalization even in finite sample settings, and to develop a more formal understanding of their margin properties. We would also like to further investigate into why post-hoc adjustment approaches work well in practice. More broadly, when applied to objectives with fairness constraints, the techniques presented here could be used to improve performance of complex neural networks on under-represented samples. Carefully studying their empirical behaviour in such settings, to ensure they do not introduce unforeseen additional biases, is an important direction for future study.

Review summaries:
This paper proposed new cost-sensitive losses for training over-parameterized models. The losses are "calibrated" (see details in the main review). The experiments show the proposed method has gained in terms of a certain metric.

The author proposed a new approach for optimizing non-decomposable metrics that focuses on over-parameterized models (i.e., deep learning models). Rather than performing reduction and reweighting as in the traditional models for non-decomposable metrics, the proposed model modifies the logits of the over-parameterized models. The author also shows that the logit modifications are calibrated with respect to the original metric. Finally, the author shows the effectiveness of the proposed models on CIFAR and TIN datasets. 

The paper considers multiclass classification with "non-decomposeable" objectives: that is, objectives that are not the sum of individual terms over sample points. The focus is on problems that can be reformulated in terms of a single saddle point structure. These are often recast as a sequence of cost-sensitive problems, but this strategy can be bad when the learning method applied at each step tends to achieve zero error. The authors show that considering instead a sequence of problems with non-standard losses losses leads to significantly better empirical results. A partial justification for the non-standard losses is that they are calibrated (so their optima correspond to optimal classifiers).