Training Over-parameterized Models with Non-decomposable Objectives
Authors: Harikrishna Narasimhan
Aditya Krishna Menon
Venue: NeurIPS 2021 Poster (2021)
Keywords: Non-decomposable objectives
Class imbalance
Cost-sensitive Losses
Over-parameterized Models
Logit-adjustment
Margin
Constraints

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 cost- sensitive 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.

Training Over-parameterized Models with Non-decomposable Objectives
Harikrishna Narasimhan Google Research, Mountain View mmarasimhan@google.
Aditya Krishna Menon Google Research, New York adit edityakmenon@google..o com
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-dccomposable objectives reduce the problem into sequence of cost-sensitive learning tasks, each of which is then solved by re- re-weighting the training loss with example-specific costs. We point out that the standard approach of re- weighting the loss incorporate label costs when used to train over parameterizeed models. As remedy, we propose new cost- sensitive 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 teacher model. Through experiments datasets, we showcase the effectiveness of our approach in training ResNet models with common robust and constrained optimization objectives.
produce unsatisfactory results
benchmark image
Introduction
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 given precision or recall target [106], enforcing minimal coverage for minority classes [31], or imposing group-fairnett constraints [105]. Unlike the misclassification error, such objectives are non-decomposable, i.e., they cannot be expressed as sum of losses over individual samples. This poses non-trivial optimization challenge, which is typically addressed by reducing the problem into sequence of cost-sensitive learning tasks [12, 25, 4, 16, 71]. Such reduction-basse approaches have been successfully employed in many open-source libraries [3, 2, I] to provide drop-in replacements for standard loss functions.
In this paper, we point out that the standard approach of re- 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 parammeettte models are frequently encountered in the use of modern neural networks, and have been the subject of considerable recent study [107, 73, 66). As remedy, we provide new calibrated losses for cost-sensitive learning that are better equipped training wer-parameterized models to optimize ceoooocooeo metrics, and demonstrate their effectiveness on benchmark image classification tasks. Our main contributions are as follows:
illustrate the pitfalls of using loss re-weighting in over-parameterized settings, particularly with diagonal class weights (Section 3).
iii) we propose new logit-adjusted losses for cost-sensitive learning for both diagonal and non- diagonal gain matrices, and show that they are calibrated (Section 4).
(iii) we demonstrate that our losses provide significant gains over loss ce-weighting training ResNet models to optimize worst-case recall and to enforce coverage constraints (Section 5).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(iv) we show that the proposed approach compares favorably to post-hoe correction strategies, and can be further improved by distilling scores from teacher model (Section 6).
1.1
Related Work
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, 333. Here, the label distribution P(y) is skewed, and one seeks 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], I]. 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, 91. with the focus largely on optimizing balanced accuracy. An exhaustive survey is beyond the scope of this paper (see, e.g.. [33, 39]), but 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 improve performance on rare subgroups [82, 83, 86), as a means to ensure model fairness [24].
Amongst loss modification techniques, two strategies of particular relevance. The first is re- weighting 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 given model class (as is the case with overparameterized models). The second is margin techniques, which enforce a class desendet 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 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 separable problems. Amongst these, Lin al. [57] handle 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 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 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 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 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 training neural networks with ranking metrics 187335 8, 77]. In contrast, our focus is on handling a general family of evaluation metrics popular in multiclass classification problems.
2 Non-decomposable Objectives
Notations. Let [m] {1,.... ................................ Let Am be the (m -iddinnniio simplex with coordinates.
Let 1mm e R" denote an all Is vector of size m, and diag(u1.... um) denote a m x m diagonal matrix with diagonal elements u1,-.., Um- For vectors b E Rm a/b denotes element-wise exp(ss) denote softmax transformation of scores s E R.
division. Let softmax;(s) = ΣT explsy)
Consider a multiclass problem with an instance space X' C 1R and a label space y = |m]. Let D denote the underlying data distribution over X' x [m)) Dx denote the marginal distribution over the
2

---

Algorithm Reductions-hased Algorithm for Maximizing Worst-case Recall (1)
Training set S, Validation set S Step-size w IR4, Class priors æ, CS-loss &o Initialize: Classifier ho, Multipliers 2 Am for t = 0 to T do
Inputs:
Update A:
x+1 X; exp (- -- Culh1)
Vi, where Ctylh] [h]
1 [S E Ei.vies (Vy=i,h =
A Σ -e-1:
G = diag(>) 1+1 / /5mm
Cost-sensitive Learning (CSL):
si+1 argming [s] Cawee (a(),s(z)) // Replaced by few steps of SGD
(+) E [e[m sf (x),
end for return hT
instances X, and π. = Ply i) i) denote the class priors. We will use p=(æ:) P(y i|æ) to denote the conditional-clas probability for instance x. Our goal to learn classifier h X (m], and will measure its performance in terms of its confusion matrix C(h]. where
Ciy [h] ( [1 (y i. h(x) -)]-
Complex learning problems. the standard setup, one is often interested in maximizing the overall classification accuracy acc(h) = Σ, C [h]. However, in many practical settings, one may care about
other metrics such as the recall for class i, rec; [h] Calhi the precision on class i, prec, = Σ, Cja
Culhi
or the proportion of predictions made on class i, i.e. the coverage, cov, [h] = Σ, Cjt- Below are common examples of real-world design goals based on these metries.
Example 1 (Maximizing worst-case recall). In class-imbalangee settings, where the classifier tends to generalize poorly on the rare classes, we may wish change the training objective directly maximize the minimum recall across all classes [12]:
Ca(h]
max min (E(m)
(I)
Example 2 (Constraining per-class coverage). Another consequence of label imbalance could be that the proportion 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 at least 95% of its prior иj [16, 71]:
m
[
m
c. Z 0.95 x J Vj E [m].
max
S.I.
n;
Other examples include constraints on recall and precision (see Table 1), the F-measure, and the area under the ROC and PR curves, well as fairness constraints like equal opportunity, which computed on group- speu--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 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 sequence of cost-sensitive objectives, which do take the form of average of training emrors [70, 12, 4, 16]. For example, the robust learning problem in (I) can be equivalently re-written as the following saddle-point optimization problem:
m
Ca(h]
max min A XEAm
Σx
(3)
where X; is a multiplier for class i. One can then find a saddle-point for (3) by jointly minimizing the weighted objective over À Am (using e.g. exponentiated-gradin updates) and maximizing

---

Problem
Gain Matrix
Losses
max; miny rec,[[A]
diag(A π
glA
2 max, acc[h) s.t. rec,
Vy
diag(1 (m A/TT)
ghA
3 max, acc, [R]] s.t. prec, [t] 2 r. Vy
diag(1m + X) - =lmA
gn gsms
4 maxe recy recy [b] s.t. cov, [b] 2 0. Vy
diag(1m/ πτ) + 1m
ghoh eSMS
5 maxp [Mc] s.t. beov,[A] 2 0.95 m Vy
diag(1m/ X) + (1m/T)A
ghys
Table I: Examples of complex learning problems, the associated gain matrices G, and the proposed losses that are applicable to the setting. We use T to denote the minimum allowed recall/precision, and beov, y [h] Di=1 x; City [b]] is the balanced coverage metric use in our experiments. Similar reductions cost- cost-sensitive learning can also be accomplished with other common evaluation metrics such as F-measure, G-mean, AUC-ROC, AUC-PR [25, 71J, and fairness criteria such as equal opportunity and equalized odds [4, 89J. See Appendix A for details.
the objective over h. Notice that for fixed X, the optimization over h is cost-sensitive (or gain-weighted) learning problem:
Cig
(4)
where G d and G. 0, + j are the rewards associated with predicting class j when the true class We will refer to G R mm as the "gain" matrix, which in this case diagonal. In practice, the cost-sensitive learning problem in (4) is usually replaced with multiple steps of gradient descent, interleaved with the updates on X. Algorithm provides an outline of this procedure.
x,
Similar to (1), the constrained learning problem in (2) can be written as an equivalent (Lagrangian) min-max problem with Lagrange multipliers X E RRT.
m
m
m Cillh] 0.95TT))
max min XER
CalA +
X j=1
77
One can find a saddle-point for this problem by jointly minimizing the Lagrangian over À E RR (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 Gj mm. + Ao Vi and G.j- >y, Vi A j. See Table 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- approach can be extended to optimize other common evaluation metrics such F-measure [25, 71].
Cost-sensitive losses. standard approach for solving the cost-sensitive learning problem in (4) is to use surrogate loss function E [m] x -R+ that takes a label y and m-dimensional score u E Rm and outputs a real value {y,, u). One would then minimize the expected loss L(s) Ez., [e(y, sxx)) over class of scoring function s x that map each instance to 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"
h"(x)) argmax,g(w) s (z).
In practice, we are provided finite sample S {(21, v1),..., (In, yn)} drawn from D, and will seek to minimize the average loss on S, given by [(s) [s] E(ewlss Ely, (())). We will also assume access to a held-out validation sample Sival (x1 v1)........... (I,ea, yroa)).
One common sanity check for "good" loss function 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 Ln (()) over all scoring functions X'-R"" coincide with the Bayes-optime prediction for x. For the cost-sensitive objective in (4), the Bayes-optimal classifier is given below [53].
Proposition 1. The optimal classifier for for general gain matrix G E Rmxm is of the form:
h" (z) E argmaxyejwr Σ = Giy P=(x) argmaxyelmr GG p(x))y
All proofs can be found in Appendix B.

---

Unweighted
0.94
0.94
Clesses
0394
Re-wee Re-weighted
Logi-adjun sege-adjusted
0.52
0.9
092
Unneighttd
Unseighhed Re Re-eeighted
Weigted
Re-weighhed
0.88
edjunted
0.88
Logit edjusted
0.88
0.86
0.66
0.6
0.54
0.6
We Weighting Class
Weighting
Weighttng seiigtiingg
Figure 1: Training ResNet-56 on a subset of CIFAR-10 10 with an unweighted, re- re-weighted (ef. (5)) and logit-adjusted (cf. (7)) cross-entropy loss. All models achieve near-zero training error.
3 The Perils of Over-parameterization
We now point out the problems in applying the algorithms described previously to models that are over-parameterized. i... 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 diagonal gain matrix G is a simple re-scaling of the standard cross-entropy loss with the diagonal weights:
exp(sy) cxp((s)
n (y, 8) = -Gy.v log
(5)
The following is natural extension of this re-weighted loss to general gain matrix G, used, for example, in constrained optimization libraries [3], and also for mitigating label noise [75]:
exp(si)
(") s) Σ Gys log
ΣS exe((x))
While this weighted loss is calibrated for G (see, e.g., [75)), it is often inadequate when training an over-parane over-parameterized model on a finite sample. This evident when is a diagonal matrix: such 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 weighted loss to train ResNet-56 models on 10000 images from CIFAR-10 with different diagonal gain matrices G. We assign a weight of the first class "airplane". and weight of I on all other classes (i.e. set G w and Gy,, 1, Vy * 1), and plot the normalized weighted accuracy Σ, Gay E, Gyy on the test set as we vary w. Compared to an unweighted cross-entropy loss, the re-weighted loss does not produce 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 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 [*)(s) = [ST Ei..)es (M s(x)) denote the average loss training sample S with eor defined in (6) for gain matrix G. Then a scoring function that achieves the minimum value of (s) over all X-RR" of the form: V(x v) E S.
softmax;(Sxx)) Σ Gz.3"
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 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 does substantially change the score learned for each example. While this does not tell us about how the model would
5

---

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 -am-lle predictions that 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- ee-ihgitging 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 sub- groups 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- seieggttingg strategies [56, 18] or deferred re- re-weighting schedules [10] have proven to work well in specialized imbalanced settings.
The work that most closely relates to our setting is Cotter al. [14], who propose a simple modifica- tion to the algorithms discussed in Section 2, with the use of two datasets: a training sample S, and a held-out validation sample S 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 [ST E(aw)es (u,,)(()),, for some cost-sensitive loss fg. The intuition here is that, even when 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, only provides partial solution for over-parameterized settings, where the model would still struggle to generalize well if lg happens to be the simple re- weiggtttd loss in (6).
Cost-sensitive Losses Based on Logit Adjustment
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 I tells us that the Bayes-optimal classifier for the resulting weighted accuracy metric is of the form h h*xx)) urgmaxye(m) Ggy Py (z). where (y(2) = P(ylz)) Intuitively, we would like the learned scoring function s(x) to mimic the Bayes-optimal scores Gyv (x) for each x. In particular, we would like the maximizer of s2())) over labels y to match the Bayes-optimal label for x.
One way to facilitate this is to adjust the scores sz)( based on the diagonal weights Gay- and to compute loss on the adjusted scores. Specifically, we shift sy(x)) 8,, (,) = sy(xx) - log(GGy)) (G and optimize the shifted scores so that their softmax transformation matches the class probabilities p(x). This would then encourage the original scorer to be monotonic in the Bayes optimal scores:
cxp(),(a)) Σ, (x)) = (x(x) =
(z) x (n(p
sy (z) x In(G (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 drawn according to p(x):
exp( log(Gyu))
ela (v. log
Σ, exp(s; log (G2)))
This loss is simple generalization of the one analyzed in Ren et al. [79], Menon et al. [63], Wang 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 eT 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 pair-wise form:
( s) log [++] Σ exp (dys (5w 8;))
(8)

---

where رgg = log(Gyy/Gg)) 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 con-diagonal, a simple logit adjustment no longer works. In this case, we propose 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 E Rmxx, and M = GD- The proposed loss then adjusts the logits to account for the diagonal entries of D and applies an outer weighting to account for M:
m
exp(s; - log(D.:)) Σ, exp(s) log(D)s))
(g.
Σ
Mys log
(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/1g1 1 1/Tm)- Another intuitive choice could be to
D (i1,(GG1,,- mmm) ), 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 For any diagonal matrix E mmmm with Dyy > O, Vy, and M = GD-1, the hybrid loss gnsh 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 diagonal matrix and a matrix with equal rows, i.e. G = diag a + 1,3 (cf. Table 1, rows 3 & 4), the Bayes-optimal classifier from Proposition 1 is of the form ht (z) = argmaxye(m OyPy(2) + By. The additive terms By in the optimal classifier can then be encoded in the loss as a shift to the softmax output, giving us the following safffmx--shiftee loss: for constant C' > 0,
( explsy (oo((sy-oog(;;)))) log(a;)) [E exp(s; - log(a;)) By/ay
SMS (y. log
(10)
Proposition 5, {SMS is calibrated for the gain matrix G = diag( (x) ) +13 when C' = L+ By/ay.
See Appendix for a practical variant this loss that avoids negative value within the log.
Experimental Comparison with Loss Re-weighting
We now showcase that the proposed losses provide substantial gains over loss re-weighting through experiments on three benchmark datasets: CIFAR-I0, 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 max, Pyy=))
min; P(y=)) to 100 for CIFAR-10 and CIFAR-100, and to 83 for TinylmageNet (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 18 models on TinyIm- ageNet, using SGD with momentum. We provide details about our hyper-paramettrs 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.
Cost-sensitive learning and baselines. We consider two learning objectives: maximizing worst-case recall, and maximizing average recall subject 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 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- 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
used for
'Code will be made available at: attpps:/eet http//gtttbu.ccooo cow//oogle www.ooooooooeorrel.oooooooooooee wowg/ggoooooooooooooooooooo researchh tree/ master/non_ce decomp
7

---

CIFAR-IO-LT
LIFAR-I00-LL
Tiny TinyImgNet-LL
Method
Avg Rec
Min Rec
Avg Rec
Min HT Rec
Avg Rec
Min HT Rec
ERM
0.750
0,563
0,441
0.082
0.321
0.009
Balanced [63]
0.790
0,664
0.478
0,210
0,353
0,086
Equalized [88]
0.754
0,541
0.461
0.147
0.325
0.033
Adaptive [10]
0.756
0,584
0.450
0.116
0.323
0.005
CSL [Re-wightt)d
0.739
0.619
0.424
0.089
0,300
0.094
CSL [Loogit-djjjusedd] 0.786
0.731
0,462
0.407
0.335
0.295
Table 2: Results of maximizing worst-case recall on CIFAR-IO and the minimum of the head and
tail recalls on CIFAR- 100 and ImageNet The last two rows contain results from Algorithm I with different losses in the CSL step. All metrics are evaluated on the test set and averaged over 5 independent trials. The highest entry in each column is shaded. The proposed logit-adjusted loss yields significantly better worst-case recall than all the baselines.
CIFAR-10-TI
LFARR-10-TI)
TinyImgNet-II
Method
Avg Rec
Min Cov
Avg Rec
Min HT Cov
Avg Rec
Min HT Cov
(igt: 0.095)
(tgt: 0.010)
(tgt: 0.005)
ERM
0.750
0.058
0.441
0.001
0.321
0.000
Balanced [63]
0.790
0.076
0.478
0.005
0.353
0.001
Equalized [88]
0.754
0.056
0.461
0.003
0.325
0,000
Adaptive [10]
0.756
0.060
0.450
0.002
0.323
0,000
CSL [Re-weighted]
0.750
0.087
0.411
0,010
0.295
0.002
CSL [Hybrid A]
0.750
0.088
0.461
0.010
0.347
0.005
CSL [Hybrid B]
0.755
0.087
0.464
0.010
0.353
0.004
Table 3: Results of maximizing average recall, while constraining the coverage for each class to be at 1 least 95% of m on CIFAR-10, and constraining the head and tail coverages to be at least 95% of 1 on CIFAR-100 and TinylmageNet The models evaluated the coverage target to 0.95 1. The last three rows contain results from Algorithm 2 (in the appendix) with different losses in the CSL step. All metrics and targets rounded off to 3 decimal places, and averaged over 5 independent trials. The highest entry and those comparable to (within 0.001) are shaded. The maximum recall among rows where the coverage is closest the target (or within 0.001 of the closest entry) is underlined. The proposed hybrid losses yield coverage values 2 target, while achieving higher average recall than the re-weighted loss.
balanced test set and hence set
the cost-sensitive loss for every update on G. and for TinylmageNet. 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 a very restrictive goal for CIFAR-100 100 and Imtge,,a,eNe,, 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 the top 90% of the classes (the "head" recall), and seek to maximize the minimum of the head and tail recalls:
max min { h
Σ YEH
rec,
1 IT|
Σ rec,|Mi SET
|7
where H. C. [m]] and T C. |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 A 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- weightingg 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.
8

---

C10-LT
CI00-LT
C100-LT
TIN-LT
Method
Per-class Recall
Per-class
Recall
Head Tail--Talee
Recall
Head- Tail
Recall
Avg
Min
Avg
Min
Avg
Min
Avg
Min
ERM
0.750
0.563
0.434
0.000
0,441
0.082
0.321
0.009
ERM PS
0.766
0.711
0.279
0.103
0.459
0.454
0.319
0.303
CSL [[Loit-adjusted]
0.786
0.731
0.389
0.107
0.462
0.407
0.335
0.295
CSL [Looit-adjusted] + PS
0.766
0.730
0.298
0.068
0.456
0.447
0.328
0.315
Table 4: Improvements with post-shifting: Results (on the test set) of maximizing the minimum recall over all classes (col 1-2) and over just the head and tail classes (col 3-4). The results are averaged over independent trials. The highest entry in each column is shaded. The proposed approach, or its variant (CSL [Logit-adjusted] PS), where the trained model is modified with a post-hoc adjustment, compares favorably to ERM PS. Our proposal often yields better average recall.
CIFAR-IO-LT
CIFAR-100-LT
Method
Avg Ree
Min Rec
Avg Rec
Min HT Rec
Distilled ERM
0.766
0.600
0.456
0.057
Distilled Balanced [63]
0.812
0.709
0.508
0.230
Distilled CSL [Re-weighted]
0.771
0.735
0.481
0.478
Distilled CSL [Logit-adjusted]
0.777
0.737
0.475
0.473
Table 5: Improvements with self dif-distillation: Performance of student model (on the test set) in maximizing worst-case recall on CIFAR-10 and the minimum of the head and tail recalls on CIFAR- 100. Both the teacher and student use ResNet-56 architecture. The results are averaged over 5 independent trials. The highest entry in each column is shaded.
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 I, where we wish to maximize the average recall, constraining the model's "balanced coverage" on each class beov, [h] Σ x; Chy[h] to be
at least 95% of . 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 TinylmageNer we consider the simpler goal of maximizing the average recall over all classes, with constraints on the model's 's average coverage over the head labels, and its average coverage over the tail labels to be both at least 95% of 1.
max h
1 Σ
[hc
s.t.
Σ DER
bcov, 2 0.95
1 m
1 T
Σ VE
bcov y [h] 2 0.95
1 m
77
[H
WE EE(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/m (//g(1//I....... 1/ m//m) (variant "A"), and with D diag(G
Gmm) (variant "B"). In Table we present the results of applying Algorithm 2 (in the appendix) to this task, with both the re- weeeeiteed 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- -000, 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 ' clear winner, although variant "B" seems to have 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).
Improvements with Post-shifting and Distillation
Having demonstrated that the proposed losses can provide significant gains over loss re- 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 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

---

base scoring model s " using ERM, (ii) construct a classifier that estimates the Bayes-optimal label for a given æ by applying gain matrix G mmmm the predicted probabilities:
h(z) E (m|m D (z)))()), where (zx) = softmax(s(z)).
The coefficients G are usually chosen maximize the given evaluation metric 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 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 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- -00-L,, the resulting classifier from this hybrid approach overfits to validation sample and worse off on the test sample.
Improvements with distillation. Another technique that has proven effective in boosting the per- formance of neural networks is knowledge distillation, wherein soft predictions from a "teacher" model p' Xm 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 distillation setup, where the training labels can be replaced
In apply- ing these losses for cost-sensitive learning, it is important that the class priors Ty used to construct the gain matrices (see Table 1) be replaced with the teacher's prior distribution =y-- - [s] E( P (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 of the teacher's labels only in the training sample, and retain the original one-hot labels in the validation sample.
with an expectation over the teacher's label distribution: Ez~Dx - (1)
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- 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 reffdistillattion 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- weighttinng is quite competitive in this case, and has a slight edge on 1IFAR-100. We attribute this surprising improvement in performance to the teacher prior distribution ti being significantly more balanced than the original class priors, and as result, the costs Guy in the optimization of the worst-case recall in Algorithm being less drastically different across classes.
7 Conclusions
We have proposed new cost-sensitive losses based on logit adjustment for training over- peeeparraeterized models with non- non-decomposable metrics. Our losses serve as replacements for and provide significant gains over standard loss re- weighting strategies used as part of the iterative reduction basod approach to optimize such metrics. We show that our proposal compares favorably to the common post-shifting baseline, and can further improved with distillation. While we considered two representative tasks in our experiments (maximizing worst-case recall and constraining coverage), the adductions-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-representte 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.
10

---

References
[1] Fairlearn Library. URI.tttss://arrrlasm..rr//
[2] Global Objectives Library. httpt///://g etit
etit, www.mm.ttccmmit..ccmmmm deattz.dde//tteee eexet/raal//eteee/a////
tf ortpearrcchhoooooooooooooootttte
[3] TensorFlow Constrained Optimization Library.
URL https://github. com/
[4] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach, reductions approach to fair classification. In International Conference Machine Learning, pages 60-69, 2018.
[5] Francis R. Bach, David Heckerman, and Eric Horvitz. Considering cost asymmetry in learning classifiers. Journal of Machine Learning Research, 7(63):1713-1741, 2006. URL attp://jmls org wwtggppap.s/v/.//cmo/ bach0aa...6.. html.
[6] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe.
Convexity, classification, and risk bounds. Journal of the American Statistical Association, (0143))::38-1155 2006.
Kay Henning Brodersen, Cheng Soon Ong, Klaas Enno Stephan, and Joachim M. Buhmann. The balanced accuracy and its posterior distribution. In 2010 20th International Conference doi: 10.1
on Pattern Recognition, pages 3121-3124, 2010.
[8] Sebastian Bruch, Masrour Zoghi, Mike Bendersky, and Mare Najork. Revisiting approximate metric optimization in the age of deep neural networks. Proceedings of the 42nd Interna- tional ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR
19), pages 1241-1244, 2019.
[9] Mateusz Buda, Atsuto Maki, and Maciej A. Mazurowski. A systematic study of the class imbalance problem in convolutional neural networks. arXiv:1710.0538) [cs, stat], October 2017.
[10] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbal- anced datasets with aabelldistribution-avaeee margin loss. Advances in Neural Information Processing Systems, 2019.
[11] Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, and W. Philip Kegelmeyer. SMOTE: Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research (JAIR), 16:321-357, 2002.
[12] Robert S Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for non-convex objectives. In Advances in Neural Information Processing Systems, pages 4705-4714, 2017.
[13] Guillem Collell, Drazen Prelec, and Kaustubh R. Patil. Reviving threshold-moving: simple plug-in bagging ensemble for binary and multiclass imbalanced data. CoRR, abs/ 1606.086988 2016.
[14] Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang. Blake Woodworth, and Seungil You. Training gellreenera classifiers for fairness metries and other data-dependent constraints. In International Conference on Machine Learning. pages 1397-1405. PMLR, 2019.
[15] Andrew Cotter, Maya Gupta, and Harikrishna Narasimhan. On making stochastic classifiers deterministic. In Advances in Neural Information Processing Systems, 2019.
[16] Andrew Cotter, Heinrich Jiang. Serena Wang. Taman Narayan, Seungil You, Karthik Sridharan, and Maya R. Gupta. Optimization with non non-differentiable constraints with applications to fairness, recall, churn, and other goals. Journal of Machine Learning Research (JMLR), 20 (172):1-59, 2019.
[17] Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel- based vector machines. Journal of machine learning research. 2(Dec):265-292, 2001.
[18] Yin Cui, Menglin Jia, Tsung-Yi Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In CVPR, 2019.
[19] M.A. Davenport, R.G. Baraniuk, and C.D. Scott. Controlling false alarms with support vector machines. In 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings, volume 5, pages V-V, 2006. doi: 10. LAL.0///CASSSP000.1661..1..

---

[20] Krzysztof Dembczyúski, Wojciech Kotlowski, Oluwasanmi Koyejo, and Nagarajan Natarajan. Consistency analysis for binary classification revisited. In International Conference on Machine Learning. pages 961-969. PMLR, 2017.
[21]
Zongyong Deng, Hao Liu, Yaoxing Wang, Chenyang Wang, Zekuan Yu, and Xuehong Sun. PML: progressive margin loss for long-tailed age classification. CoRR, abs/2103.02140, 2021.
URL https://axxiv org/abs. attaaass///// 2203. 02140.
[22] Jacek P. Dmochowski, Paul Sajda, and Lucas C. Parra. Maximum likelihood in cost-sensitive learning: Model specification, approximations, and upper bounds. Journal of Machine Learning Research, ((110)):331333333 2010.
[23] Pedro Domingos. Metacost: general method for making classifiers cost-sensitive. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '99, page 155-164, New York. NY, USA, 1999. Association for Computing Machinery. ISBN 1581131437. doi: 10. 10.1145/312129:31222 URL https: //doi. org/ 10. 1145/312129 312220.
[24] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science Conference (ITCS), pages 214-226, 2012.
[25] Elad Eban, Mariano Schain, Alan Mackey, Ariel Gordon, Ryan Rifkin, and Gal Elidan. Scalable learning of non-decomposable objectives. In Artificial Intelligence and Statistics, PMLR, 2017.
pages
[26] Charles Elkan. The foundations of cost-sensitive learning. In Proceedings of the 17th International Joint Conference on Artificial Intelligence Volume 2, IJCAI'01, page 973-978, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. ISBN 1558608125.
[27] Rizal Fathony and Zico Kolter. AP-perf: Incorporating generic performance metrics in differentiable learning. International Conference on Artificial Intelligence and Statistics, pages 4130-41444 40. PMLR, 2020.
[28] Tom Fawcett and Foster Provost. Combining data mining and machine learning for effective user profiling. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 8-13. AAAI Press, 1996.
[29] Tommaso Furlanello. Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandku- mar. Born again neural networks. In International Conference on Machine Learning, pages 1607-1616. PMLR, 2018.
[30] Tilmann Gneiting and Adrian E Raftery. Strietly proper scoring rules, prediction, and estima- tion. Journal of the American statistical Association, 102(447):359-378, 2007.
[31] Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints. In Advances Neural Information Processing Systems, pages 2415-2422 2016.
[32] Moritz Hardt, Fric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, pages 3315-3323, 2016.
[33] Haibo He and Edwardo A. Garcia. Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering, 21(9):1263-1284 2009.
[34] G. Hinton, O. Vinyals, and J. Dean. Distilling the knowledge in neural network. arXiv:1503.0253/, 2015.
[35] Chen Huang, Shuangfei Zhai, Walter Talbott, Miguel Bautista Martin, Shih- Yu Sun, Carlos Guestrin, and Josh Susskind. Addressing the loss-metric mismatch with adaptive loss alignment. In International Conference on Machine Learning, pages 2891-2900. PMLR, 2019.
[36] Arya Iranmehr, Hamed Hasnadi-Shirazi, and Nuno Vasconcelos. Cost-sensitive support vector machines. Neurocomputiing 343:50 64, 2019.
[37] Muhammad Abdullah Jamal, Matthew Brown, Ming-Hsuan Yang, Liqiang Wang, and Boqing
Gong. Rethinking class-balanced methods for long-tailed visual recognition from a domain adaptation perspective. In Proceedings of the IEFF/CVE Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
12

---

[38] Thorsten Joachims. A support vector method for multivariate performance measures. In Proceedings of the 22nd international conference on Machine learning, pages 377-384. ACM, 2005.
[39] Justin Johnson and Taghi Khoshgoftaar. Survey on deep learning with class imbalance. Journal of Big Data, 6:27, 03 2019.
[40] Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. In Eighth International Conference on Learning Representations (ICIR), 2020.
[41] Purushottam Kar, Harikrishna Narasimhan, and Prateek Jain. Online and stochastic gradient methods for non-decomposable loss functions. Advances in Neural Information Processing Systems, 2014.
[42] Purushottam Kar, Shuai Li, Harikrishna Narasimhan, Sanjay Chawla, and Fabrizio Sebastiani. Online optimization methods for the quantification problem. In Proceedings of the 22nd ACM SIGKDD international conference knowledge discovery and data mining, pages 1625-1634, 2016.
[43] Grigoris Karakoulas and John Shawe-Taylor, Optimizing classifiers for imbalanced training sets. In Proceedings of the 1 11th International Conference Neural Information Processing Systems, NIPS 98, page 253-259, Cambridge, MA, USA, 1998. MIT Press.
[44] Salman H. Khan, Munawar Hayat, Mohammed Bennamoun, Ferdous A. Sohel, and Roberto Togneri. Cost-sensitive learning of deep feature representations from imbalanced data. IEEE Transactions on Neural Networks and Learning Systems, 293))3357333 2018. doi: 10.
1 1109/NNNLS.2017.27333..
[45] Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label-imbalanced and group-sensitive classification under overparameterizztion.. CoRR. abs/2103.01550, 2021. URL
org hat///bs/22003 2105..0150.
[46] Oluwasanmi O Koyejo, Nagarajan Natarajan, Pradeep K Ravikumar, and Inderjit S Dhillon. Consistent binary classification with generalized performance metrics. In NIPS, pages 2744- 2752, 2014.
[47] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[48] Miroslav Kubat and Stan Matwin. Addressing the curse of imbalanced training sets: One-sided selection. Proceedings of the International Conference on Machine Learning (ICML), 1997.
[49] Miroslav Kubat, Robert Holte, and Stan Matwin. Learning when negative examples abound. In Maarten van Someren and Gerhard Widmer, editors, Proceedings of the European Conference on Machine Learning (ECML), volume 1224 Lecture Notes in Computer Science, pages 146-153. Springer Berlin Heidelberg, 1997. ISBN 978-3-540-62858-3.
[50] Abhishek Kumar, Harikrishna Narasimhan, and Andrew Cotter. Implicit rate-constrained optimization of non- decomposaleee objectives. In International Conference on Machine Learning (ICML), 2021.
[51] Steve Lawrence, Ian Burns, Andrew D. Back, Ah Chung Tsoi, and C. Lee Giles, Neural network classification and prior class probabilities. Neural Networks: Tricks of the Trade, This Book is an Outgrowth of 1996 NIPS Workshop, page 299-313, Berlin, Heidelberg, 1998. Springer- Verlag. ISBN 3540653112.
[52] Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 2015.
[53] Yoonkyung Lee, Yi Lin, and Grace Wahba. Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465):67-81, 2004.
[54] David D. Lewis and William A. Gale. A sequential algorithm for training text classifiers. In Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '94, page 3-12. Berlin, Heidelberg, 1994. Springer- Verlag. ISBN
[55] Yaoyong Li, Hugo Zaragoza, Ralf Herbrich, John Shawe-Taylor and Jaz Kandola. The perceptron algorithm with uneven margins. In Proceedings of the Nineteenth International
13

---

Conference on Machine Learning, ICML '02. page 379-386, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc. ISBN 1558608737.
[56] Tsung-Yr Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pages 2980-2988, 2017.
[57] Yi Lin, Yoonkyung Lee, and Grace Wahba. Support vector machines for classification in nonstandard situations. Mach. L 46(1-3))1911-002, March 2002. ISSN 0885-6125.
[58] Charles Ling and Victor Sheng. Cost-sensitive learning and the class imbalance problem. Encyclopedia of Machine Learning, 01 2010.
[59] Junru Luo, Hong Qiao, and Bo Zhang. A minimax probability machine for non-decomposable performance measures. arXiv preprint arXiv:2 00390, 2021.
[60] Marcus A. Maloof. Learning when data sets are imbalanced and when costs are unequal and unknown. In ICML. 2003 Workshop on Learning from Imbulanced Datasets, 2003.
[61] Hamed Masnadi Masnadi-Shirazi and Nuno Vasconcelos. Risk minimization, probability elicitation, and cost-sensitive SVMs. In Proceedings of the 27th International Conference on Interna- tional Conference on Machine Learning, ICML' 10. page 759-766, Madison, WI, USA, 2010. Omnipress. ISBN 9781 605589077.
[62] Aditya Menon, Harikrishna Narasimhan, Shivani Agarwal, and Sanjay Chawla. On the statisti- cal consistency of algorithms for binary classification under class imbalance. In International Conference on Machine Learning, pages 603-611, 1, 2013.
[63] Aditya Krishma Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In International Conference on Learning Representations (ICLR), 2021.
[64] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, 2019.
[65] Katharina Morik, Peter Brockhausen, and Thorsten Joachims. Combining statistical learning with a knowledge-based approach case study in intensive monitoring. In Proceedings of the Sixteenth International Conference on Machine Learning (ICML), pages 268-277, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1-55860-612-2.
[66] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference Learning Representations, 2020.
[67] Harikrishna Narasimhan.
Learning with complex loss functions and constraints. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 1646-1654, 2018
[68] Harikrishna Narasimhan, Rohit Vaish, and Shivani Agarwal. On the statistical consistency of plug-in classifiers for non-decomposable performance measures, In Advances in Neural Information Processing Systems, pages 1493-1501, 2014.
[69] Harikrishna Narasimhan, Purushottam Kar, and Prateek Jain. Optimizing non-decomposable performance measures: A tale of two classes In International Conference on Machine Learning, pages 199-208. PMLR, 2015.
[70] Harikrishna Narasimhan, Harish Ramaswamy, Aadirupa Saha, and Shivani Agarwal. Consis- tent multiclass algorithms for complex performance measures. In ICML, pages 2398 -2087, 2015.
[71] Harikrishna Narasimhan, Andrew Cotter, and Maya Gupta. Optimizing generalized rate metrics with three players. In Advances in Neural Information Processing Systems, pages 10746-10757, 2019.
[72] Nagarajan Natarajan, Oluwasanmi Koyejo, Pradeep Ravikumar, and Inderjit Dhillon. Optimal classification with multivariate losses. In International Conference on Machine Learning, pages 1530-1538. PMLR, 2016.
[73] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrizztioo in generalization of neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
14

---

[74] Shameem Puthiya Parambath, Nicolas Usunier, and Yves Grandvalet. Optimizing f-measures by cost-sensitive classification. In Advances in Neural Information Processing Systems, pages 2123-2131, 2014.
[75] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1944-1952, 2017.
[76] Foster Provost. Machine learning from imbalanced data sets 101. In Proceedings of the AAAI-2000 Workshop on Imbalanced Data Sets, 2000.
[77] Qi Qi, Youzhi Luo, Zhao Xu, Shuiwang Ji, and Tianbao Yang. Stochastic optimization of area under precision-recall curve for deep learning with provable convergence. CoRR, abs/2104.08776, 2021. URL https: /arxiv...... arg/abs/2ee 08736.
[78] Harish Ramaswamy and Shivani Agarwal. Convex calibration dimension for multiclass loss matrices. The Journal of Machine Learning Research, 17(1):397-441, 2016.
[79] Jiawei Ren, Cunjun Yu, shunan sheng, Xiao Ma. Haiyu Zhao, Shuai Yi, and hongsheng Li. Balanced meta-softmax for long-tailed visual recognition. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4175-4186. Curran Associates, Inc., 2020.
[80] Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei- Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 111(3):21-225,, 2015.
[81] Andrei A Rusu, Sergio Gomez Colmenarejo, Caglar Gülcehre, Guillaume Desjardins, James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy distillation. In ICLR (Poster), 2016.
[82] S. Sagawa, A. Raghunathan, P. W. Koh, and P. Liang. An investigation of why overparameteri- zation exacerbates spurious correlations. In International Conference on Machine Learning (ICML), 2020.
[83] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference on Learning Representations, 2019.
[84] Amartya Sanyal, Pawan Kumar, Purushottam Kar, Sanjay Chawla, and Fabrizio Sebastiani. Optimizing nonddecomposable measures with deep networks. Machine Learning, 107(8): 1597-1620, 2018.
[85]
Clayton Scott. Calibrated asymmetric surtogate losses. Electronic of Statistics, 6(none): 958 992, 2012. doi: 1...224412-EJS5661 URL https://doi. org/ 10. 1011/121/222 12114192
[86] N. Sohoni, J. Dunnmon, G. Angus, A. Gu, and C. Ré. No subclass left behind: Fine-grained robustness in coarse-grained classification problems. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
[87] Yang Song, Alexander Schwing, Raquel Urtasun, al. Training deep neural networks via direct loss minimization. In International Conference on Machine Learning, pages 2169-22 2177-2177. PMLR, 2016.
[88] J. Tan, C. Wang, Li, Q. Li, W. Ouyang, C. Yin, and J. Yan. Equalization loss for long- tailed object recognition. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 1 1659 11668, 2020.
[89] S. K. Tavker, H. G. Ramaswamy, and H. Narasimhan. Consistent plug-in classifiers for complex objectives and constraints. In Advances in Neural Information Processing Systems, 2020.
[90] Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, Yasemin Altun, and Yoram Singer. Large margin methods for structured and interdependent output variables. Journal of machine learning research, 6(9), 2005.
[91] Grant Van Horn and Pietro Perona. The devil is in the tails: Fine-grained classification in the wild. arXiv preprint 1rXiv:1709.01453 2017.
[92] Vladimir N. Vapnik. Statistical Learning Theory. Wiley-Intersciencee, 1998.
15

---

[93] B.C. Wallace, K.Small, C.E. Brodley, and T.A. Trikalinos. Class imbalance, redux. In Proc. ICDM, 2011,
[94] Jiaqi Wang, Wenwei Zhang, Yuhang Zang, Yuhang Cao, Jiangmiao Pang, Tao Gong, Kai Chen, Ziwei Liu, Chen Change Loy, and Dahua Lin. Seesaw loss for long-tailed instance segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2021.
[95] Robert C Williamson, Elodie Vernet, and Mark D Reid. Composite multiclass losses. Journal of Machine Learning Research, 17:1-52, 2016.
[96] Shan-Hung Wu, Keng-Pei Lin, Chung-Min Chen, and Ming-Syan Chen. Asymmetric support vector machines: Low halse-positive learning under the user tolerance. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '08, page 749-757, New York, NY, USA, 2008 Association for Computing Machinery. ISBN 9781605581934
[97] Tong Wu, Qingqiu Huang, Ziwei Liu, Yu Wang, and Dahua Lin. Distribution- loss for multi-label classification in long-tailed datasets. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision ECCV 2020, pages 162-178, Cham, 2020. Springer International Publishing. ISBN 978-3-030-58844-88
[98] Xiaoyun Wu and Rohini Srihari. New v-support vector machines and their sequential minimal optimization. In AAAI, pages 924-831, 01 2003.
[99] Qizhe Xie, Minh- ThangTThag Luong, Eduard Hovy, and Quoe V Le. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 10687-10698, 2020.
[100] Yu Xie and Charles F, Manski. The logit model and response- based samples. Sociological Methods & Research, 17(3):283-302. 1989.
[101] Bowei Yan, Sanmi Koyejo, Kai Zhong, and Pradeep Ravikumar. Binary classification with karmic, threshold-quee wutpooooddguussccccvveeeae metrics. In International Conference on Machine Learning, pages 5531-5540. PMLR, 2018.
[102] Nan Ye, Kian Ming Chai, Wee Sun Lee, and Hai Leong Chieu. Optimizing f-measures: a tale of two approaches. In Proceedings of the 29th International Conference on Machine Learning. pages 289-296. Omnipress. 2012.
[103] Xi Yin, Xiang Yu, Kihyuk Sohn, Xiaoming Liu, and Manmohan Chandraker. Feature transfer learning for face recognition with under-represented data. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
[104] B. Zadrozny, J. Langford, and N. Abe. Cost-sensitive learning by proporoopttt example weighting. In Third IEFE International Conference on Data Mining, pages 435-442, 2003. doi: 10. 10 1091109//MMMMM 2003..10.111110 1250950.
[105] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna Gummadi. Fairness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pages 962-970, 2017.
[106] Ao Zhang, Nan Li, Jian Pu, Jun Wang. Junchi Yan, and Hongyuan Zha. Tau-fpl: Tolerance- constrained learning in linear time. In Sheila A. Mcllraith and Kilian Q. Weinberger, editors, Proceedings of the Phirty-Secoon AAAI Conference on Artificial Intelligence, (AAAI-18), pages 4398-4405. AAAI Press, 2018.
[107] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Under- standing deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICIR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.nee 2017.
[108] Junjie Zhang, Linggiao Liu, Peng Wang, and Chunhua Shen. To balance or not to balance: A simple-yet-effeective approach for learning with long-tailed distributions, 2019.
[109] Shaoyu Zhang, Chen Chen, Xiyuan Hu, and Silong Peng. Balanced knowledge distillation for long-tailed learning. CoRR, abs/2104. 10510, 2021. URL hattp:://arxiii www.g////a/////////////////////e 10510.
[110] Songyang Zhang, Zeming Li, Shipeng Yan, Xuming He, and Jian Sun. Distribution alignment: A unified framework for long-tail visual recognition. In CVPR, 2021.
16

---

[111] Zhi-Hus Hua Zhou and Xu- Ying Liu. Training cost-sensitive neural networks with methods address- ing the class imbalance problem. IEEE Transactions on Knowledge and Data Engineering (TKDE), 18(1), 2006.
[112] Zhi-Hua Zhou and Xu- Yunging Liu. On multi-class cost-sensitive learning, Computational Intelligence, 26(3):232-257, 2010.
17


Reviews:
[{"review_id": "RD571kV49xC", "reviewer": "Reviewer_t7Bj", "summary": "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). ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "In a classification problem with $m$ classes, each classifier $h:\\mathcal{X}\\to [m]$ has an associated confusion matrix $C[h]$ that describes how often it predicts a $j$ when the true label is a $i$. The \"non-decomposeable\" objectives described in the title of the paper are losses that can be expressed in a saddle point fashion in terms of $C[h]$, like for example:\n$$(\\star) \\max_{h\\in mathcal{H}} \\min_{\\lambda\\in S}\\sum_{i,j}G_{ij}(\\lambda)C_{ij}[h] ,$$\nwhere the matrix $G$ depends linearly on $\\lambda$. Such metrics are quite natural and include e.g. the minimum recall over classes for a given $h$.\n\nThe present submission notices that, for a fixed $\\lambda$, $(\\star)$ is a cost-sensitive classification problem that can be solved by standard techniques. Therefore, a solution to the saddle point problem $(\\star)$ could obtained via a sequence of these cost-sensitive problems alternated with updates to $\\lambda$. However, this strategy may perform poorly for finite samples. Intuitively, when the base learner tends to interpolate data, then the cost-sensitivity constraint is irrelevant, as training loss will be zero anyway. \n\nThis paper presents an alternative approach whereby the cost-sensitive learning problems are replaced by certain learning problems. The salient feature of the latter is that the losses used are calibrated: that is, a classifier that achieves minimum population surrogate loss is the optimal one corresponding to an \"ideal\" iteration of the saddle point problem. Calibration is not quite a practical result, since in practice it is rarely the case that the population surrogate loss is exactly minimized. Still, this property lends some credibility to the procedure developed here. Moreover, the method performs well in experiments with CIFAR-10, CIFAR-100 and TinyImageNet. The authors also consider the effect of post shifting and distillation on the final result. \n\nThis submission is quite well written. Mathematical statements and proofs are mostly well explained, and the authors give very precise descriptions of their experiments. As I explained above, calibration is not a decisive result proving their approach works, but it is nonetheless an interesting result. To this reader, the experimental results are convincing ; however, I would have liked to have access to code, and larger experiments would make a more compelling case. Overall, my evaluation of the paper is positive, although I also feel I am not a specialist on the topics of the submission. \n\nAn additional (minor) comment is that the proof of Prop. 2 does not seem to work if there are repeated feature vectors with distinct labels in the dataset $S$.\n\n\n \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "OyxezosLSWh", "reviewer": "Reviewer_e3jE", "summary": "The paper proposes to use logit adjustments for class imbalanced training settings with over-parameterized models.\nThey introduce logit adjustments with general gain matrices (in constrast to only diagonal gain matrices).\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is well written, and nicely introduced.\nThe work is very interesting, however, it seems like the contribution of the work is limited considering the related works.\n\nThere are two very similar works (which have been cited by the paper). https://arxiv.org/pdf/2007.10740.pdf https://arxiv.org/pdf/2007.07314.pdf\nRen et al. (https://arxiv.org/pdf/2007.10740.pdf) also use logit adjustment on the same task, while they use a ResNet-34 instead of the here used ResNet-56.\nIt is not clear to me, why ResNet-56 is much more overparameterized than ResNet-34. I see that it is larger, but it is not that much larger.\nThe operation on overparameterized models seems to be the main contribution of this paper, it does not convince me that the proposed setting is overparameterized and (that at the same time) in the work by Ren et al. it is not overparameterized.\n\nI acknowledge that this work is a generalization of those previous works. \nHowever, the empirical distinction of your work to the previous works is not strong.\nAs Menon et al. and Ren et al. train on the same task, I would strongly encourage you to include these baselines (as well as some of their baselines) into your paper. \n\nMore clearly distinguishing between prior work and your contributions and using prior works as baselines would improve my score.\n\nMinor:\nl. 143 function -> functions\n\nComment on Confidence:\nI carefully checked the math in the main paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The empirical evaluation lacks baselines and the scope of contribution is limited.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.25"}, "extra_text": {}}, {"review_id": "Ow67ZqSzIq", "reviewer": "Reviewer_qkBf", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "First of all, I have to claim that the paper is beyond my expertise and I'm not familiar with the literature. I asked to have the paper unassigned but it didn't work out. I'm not confident about my review.\n\nClarity & Significance: \n\nThe paper is not so clear for me (perhaps it is just because I'm not an expert). \n\nI'm not quite familiar with the terminology \"calibrated\", does it mean \"Fisher consistency\" or something related? I mean, optimizing a certain surrogate loss can achieve the Bayes optimal classifier given infinite samples with a hypothesis of all measurable functions. It should be defined rigorously. \n\nThe paper also presents some propositions. Only proposition 1 is quoted from existing work. I'm not quite sure about the others. Any of them is the main theory of this paper? They are the same and natural/simple to me according to the presentation. If there is some technical contribution, please highlight it.\n\nFurther, the discussion of the literature, especially the related ones is not sufficient. For instance, the authors claim that Eqn. 7 is a simple generalization of existing work. But in which sense? Making them \"calibrated\" or something else? I didn't see the significance and necessity.\n\nAs for the experiments, the results of the methods differ a lot under two different measures. The proposed method does not perform as well as the baseline in terms of the avg. acc. Then which one do we really care about and any deeper analysis? Lastly, the experimental settings are typical? It seems quite arbitrary to define a classification task. It would be better to consider some widely adopted settings and compare to a larger family of existing methods.\n\n\nOriginality & Quality: \n\nI cannot tell the originality of the paper as I do not know the literature at all. I give a temporal weak reject and update my score based on the authors' feedback and discussion with other reviewers. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The clarity of the paper can be improved. See details above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "BJwOkGSUS9Z", "reviewer": "Reviewer_svfi", "summary": "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall, I like the idea of modifying the logits instead of reweighting the samples or classes, as it has been shown in previous literature that sample reweighting does not work as intended in the over-parameterized models. The author shows that the proposed logit modification can align the over-parameterized models with the original metrics better. I also like the consistency property of the proposed loss.\nI have questions that I would like the author to address. \n1. Since the author mentioned that the proposed method works for complex metrics, could the author explain how generic the model is. Could the model handle other types of non-decomposable metrics? For example, the F-score or the MCC score, or ranking-based scores. If someone wants to apply the proposed model on a particular non-decomposable metric, how much modification is needed?\n2. Related to the first question, how to construct the G matrix for a particular metric?\n3. The logit adjustment technique presented in the paper is the inner step of the full training algorithm, but it was not so clear from the main paper. I suggest the author provide more explanation in the main paper rather than putting it in the appendix.\n4. Some related papers are missing from the reference: e.g., Fathony & Kolter (2020) and Luo et. al. (2021)\n\nFathony, R. & Kolter, Z.. (2020). AP-Perf: Incorporating Generic Performance Metrics in Differentiable Learning. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in PMLR 108:4130-4140\n\nLuo, Junru, Hong Qiao, and Bo Zhang. \"A Minimax Probability Machine for Non-Decomposable Performance Measures.\" arXiv preprint arXiv:2103.00396 (2021).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes new calibrated cost-sensitive losses for training over-parameterized models.  The reviewers were unanimous in their opinion that the paper is above the acceptance threshold.  The approach is well supported theoretically, and covers an interesting family of non-decomposable losses.  The authors have promised to release code at the time of publication in response to a reviewer comment.
Decision: Accept (Poster)