SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Shrinivas Ramasubramanian∗ 1 Harsh Rangwani∗ 2 Sho Takemori∗ 3 Kunal Samanta 2
Yuhei Umeda 3 R. Venkatesh Babu 2

Abstract& Menon, 2021). Optimising such metrics is termed as
Non-Decomposable Metrics (NDM) optimization.

Natural data often has class imbalance. This canmake it difficult for machine learning models tolearn to classify minority classes accurately. Industrial machine-learning applications often have
objectives beyond just accuracy. For example,
models may be required to meet certain fairness
criteria, such as not being biased against theclasses with fewer samples. These objectives areoften non-decomposable in nature. SelMix is afine-tuning technique that can be used to improve
the performance of machine learning models on
imbalanced data. The core idea of our framework
is to determine a sampling distribution to perform
a mixup of features between samples from particular classes such that it optimizes the given
objective. We evaluate our technique against theexisting empirical methods on standard benchmark datasets for imbalanced classification.

In prior works, there exist techniques to optimize such
NDM, but their scope has mainly been restricted to linear models (Narasimhan et al., 2014; 2015a). Narasimhan& Menon (2021) in their recent work developed consistent logit-adjusted loss functions for optimizing NDM fordeep neural networks. After this work in supervised setup,
CSST (Rangwani et al., 2022) extends it to practical semisupervised learning (SSL) setup, where both unlabeled andlabeled data are present. Optimizing NDM presents a challenge when learning from long-tailed datasets.
In this paper, we develop a technique that utilizes the existing pre-trained classifier for representations and finetunes it for the desired NDM. The core contribution of ourwork is to develop a selective mixup sampling distribution
for selecting which classes to mix up so that it optimizes thegiven non-decomposable objective (Figure 1). This distribution of mixup is updated periodically based on feedback
from a validation set, such that it steers the model in the desired direction for optimizing the non-decomposable objective. SelMix improves the decision boundaries between particular classes to optimize the non-decomposable objective,
unlike Mixup technique (Zhang et al., 2018) that applies it
uniformly across all class samples. SelMix framework canalso optimize neural networks for non-linear objectives,addressing a shortcoming of existing works (Rangwani et al.,2022; Narasimhan & Menon, 2021).

1. Introduction
The rise of deep networks has shown great promise byreaching near-perfect performance, particularly on tasks
like visual recognition (He et al., 2022; Kolesnikov et al.,2020). It has led to their widespread deployment for practical applications, some of which also have critical consequences (Castelvecchi, 2020). Due to this, developedmodels must perform robustly across the entire distribution
rather than only the majority part. These failure cases areoften overlooked when we consider only accuracy as ourprimary metric for quantifying the model’s performance.
Therefore, more practical metrics like Recall H-Mean (Sunet al., 2006), Worst-Case (Min) Recall (Narasimhan &Menon, 2021; Mohri et al., 2019), etc., should be used forevaluation. Optimizing these metrics directly for deep networks is challenging as they cannot be expressed as a simple
average of metrics calculated for each sample (Narasimhan*

To evaluate the performance of SelMix, we perform experiments to optimize six different NDM by fine-tuninga pre-trained classifier using MiSLAS(Zhong et al., 2021)
stage-1. These objectives span linear and non-linear functions of the confusion matrix. We also consider constrained
optimization objectives. A list of objectives considered isavailable in Appendix J.3

2. Problem Setup

1

In our framework, we have a K-class classification problem where the data (x) comes from an instance space X
with labels in Y := [K]. The classifier h is a mappingwhere h : X → Y. The classifier is composed of a feature extractor g : X → Rd which is followed by a linear softmax classification layer f : Rd → ∆K−1 , where

Equal contribution Fujitsu Research of India Private Limited,
Bengaluru, India 2 Vision and AI Lab, Indian Institute of Science,
Bengaluru, India 3 Fujitsu Limited, Kanagawa, Japan. Correspondence to: Shrinivas <shrinivas.ramasubramanian@fujitsu.com>.
Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics∆K−1 ⊂ RK is the K − 1 dimensional probability simplex.
For a data sample X, the label prediction from classifier h is:
h(x) = argmaxj∈[K] f (g(x))j . For learning the classifier
h we assume access to samples from data distribution D. We
denote the prior over labels as πi , which is πi = P(y = i).
The confusion matrix for a classifier h is given as:
Cij [h] = E(x,y)∼D [1(y = i, h(x) = j)].

(1)

The confusion matrix C ∈ ∆K×K−1 and is used for characterizing the performance of a classifier. We now defineψ where ψ : ∆K×K−1 →− R to be the non-decomposable
objective we want to optimize (or maximize). The ψ(C[h])can be used for expressing a lot of practical objectives
used in prior works (Cotter et al., 2019; Narasimhan
et al., 2022). We elucidate some of them below, which
we use in our current work. The detailed list of definitions of the variables used can be refered from Table.
A.1. The worst-case recall is better suited than accuracy toevaluate classifiers on long-tailed datasets (Narasimhan &Menon, 2021) and defined as the minimum of recalls acrossMRclasses ψ
P (C[h]) = min1≤i≤K reci [h], where reci [h] =Cii [h]/ j∈[K] Cij [h]. Similarly, the G-mean ψ GM of recalls and H-mean ψ HM of recalls are defined as the geometric and the harmonic mean of recalls across classes,
respectively. Fairness is another area where such complex
metrics are particularly useful. Following (Cotter et al.,2019; Goh et al., 2016),
PK we consider the maximization of1
the mean recall K
i=1 reci [h] subject to covi [h] ≥ α/Kwith a constant α > 0.P
Here, covi [h] is the predictive coverage, i.e., covi [h] = j∈[K] Cij [h]. By using Lagrange
multiplier λ, the coverage constrained objective can be reAMduced to the max-min problem maxh minλ ψcons(ψ) (See
Table D.1 and (Narasimhan & Menon, 2021)).

Figure 1. We demonstrate the effect of the variants of Mixup on
feature representations of samples (a). With standard Mixup, thefeature representation gets equal contribution in all directions ofother classes (b). For SelMix (c), Mixups for specific classes are
selected such that they optimize the desired metric.

Di is defined as the set of samples with class label i i.e.,{(x, y) : y = i}. Although our main focus is supervised
learning, in the semi-supervised setting, we consider anunlabeled sample x′ with a pseudo label y ′ and replace Dj
e j with pseudo label j. Even in theby the set of samples Dsemi-supervised setting, the set Di remains to be the set ofsamples (x, y) with true label i. In our method, we assumeaccess to a held-out validation dataset Dval . For analyzing
the effect of (i, j) mixups on the model, we use the loss
incurred by mixing the centroids of class samples given aszk = Ex∼Dkval [g(x)] for each class k. This loss which isrepresentative of the expected loss due to (i, j) mixup is:
L̄i,j
MU = LMU (zi , i, zj ; f ) ∀i, j ∈ [K] × [K].

(2)

In our work, we mainly focus on analysis of linear classifierf having weight ν as we primarily train that for optimizing
the NDM. We use the gradient of the above representativeloss to characterize the change in linear classifier weights(∆W ) due to (i, j) mixup, given as νij = −η∇L̄ij
MU-CE .
These νi,j directions characterize the average weight change
due to (i, j) mixup.

3. Selective Mixup for Optimizing NDM
In this work, we aim to optimize the NDM using
the mixup (Zhang et al., 2018) framework. Manifold
Mixup (Verma et al., 2019) extends this idea to have mixups in feature space, which we use in our work. However,in mixup, the samples for mixing up are chosen randomly.
This may be useful in general but can be sub-optimal when
we aim to optimize for specific NDM (Table O.1). Hence,in this work, we focus on selective mixups and use themfor optimizing the non-decomposable objective. The loss
for mixup (LMU (g(x), y, g(x′ ); f )) between samples (x, y)and (x′ , y ′ ) having features g(x) and g(x′ ) is given as:

Our framework is based on the idea of optimizing the linear approximation of non-decomposable objective ψ(C)in terms of directional derivative, in the directions ofchange in weights (νij ) due to (i, j) mixups. This differsfrom earlier Cost Sensitive Learning (CSL) frameworks
for non-decomposable objective optimization (Narasimhan& Menon, 2021; Cotter et al., 2019; Narasimhan et al.,2015b;a), as they consider linear approximation w.r.t. theentries of confusion matrix. Hence, our work gives a new
orthogonal direction to the problem of non-decomposable
objective optimization. We define gain G matrix as the
expected rate of increase in metric ψ(C) upon performing(i, j) mixup and performing a step of stochastic gradientdescent. It is given as the directional derivative of ψ(C)w.r.t the parameters along the direction of update of weights

LMU = LCE (f (βg(x) + (1 − β)g(x′ )), y).
Here LCE is the cross entropy loss, h is f ◦ g and β ∼Unif(βmin , 1), βmin ∈ [0, 1) . The above design choices
follow the ideas of mixup for semi-supervised learning as
used in Fan et al. (2022). We define (i, j) mixups to be themixup of samples (x, y) ∼ Di and (x′ , y ′ ) ∼ Dj , where2

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

for a given L̄ij
MU :Gij = ∇νij ψ(C)where νij = −η∇L̄ij
MU .

to perform training cycles, in each of which you estimate thegain matrix G through a validation set and use it for training
the neural network for a few Stochastic Gradient Descent(SGD) steps. As our expressions of gain are based on linear
classifier, we only train linear classifier fully and fine-tune
the backbone slightly for better empirical results (Sec. 4).
For expressing the algorithm formally, we introduce the(t)time-dependent notations for gain (Gij ), the classifier h(t) ,(3)

We now define a distribution PMix (i, j) over the labels i’sand pseudo-labels j’s of the samples that shall be mixed
up. As we aim to maximize the average gain E(i,j) [Gij ],one greedy strategy could be to only mixup (i, j) pairs
corresponding to maxi,j Gij . However that strategy doesn’t
work as we do n mixups and in that the linear approximation
becomes invalid (Refer Table O.2 for evidence). Hence, we
select the PMix to be the scaled softmax of the gain matrix as
our strategy, with s > 0 given as (PSelMix ): PSelMix (i, j) =softmax(sGij ). We provide theoretical results regarding
the optimality of the proposed PSelMix in Sec. F.

(t)

the SelMix distribution PSelMix , weight-direction change(t)νij . At each iteration t = 1, . . . , T , we compute the SelMix(t)distribution PSelMix = softmax(sG(t) ) using Thm.3.1. We(t)randomly sample class labels Y1 and Y2 by Y1 , Y2 ∼ PSelMix ,and sample (X1 , Y1 ) and (X2 , Y2 ) uniformly random from
DY1 and DY2 respectively. Then, we update the classifier h(t) by using the CE and the mixup sample, i.e.,h(t+1) := SGD-Update(h(t) , ∇LMU (g(X1 ), Y1 , g(X2 ))).
In each iteration t, we repeat this SGD update n times.

We now move to the second crucial practical component
required for the algorithm: the tractable gain estimation(Gij ) for each (i, j) mixup. However, while trying to optimize the non-decomposable objective, it’s required thatthe confusion
P matrix C[h]Pshould satisfy the following constraints: j Ci,j = πi , i,j Ci,j = 1 with 0 ≤ Ci,j ≤ 1.
For implicitly enforcing these constraints we make use of
the re-parameterization (Achiam et al., 2017) trick to define
the row of confusion matrix (Ci ) in terms of the row of
unconstrained matrix C̃ ∈ RK×K . We define Ci := [πi ·softmax(C̃i )]. The gain can be analagously defined (Eq. 3)
in terms of C̃: Gij = ∇νij ψ(C̃) where νij = −η∇L̄ij
MU .

4. Experimental Analysis
4.1. Experimental Setup
We follow the convention for long-tailed classification
where the classes are indexed 1...K with the number ofsamples per class decreasing as the class index increases.
The data distribution is exponentially decreasing in nature.
The number of samples in class i are denoted as Ni . The
severity of imbalance is quantified by ρ = N1 /NK .
We show the efficacy of SelMix for optimizing a wide variety of NDM for CIFAR 10,100 LT (ρ = 100) and Imagnenet1k LT datasets . Our classifier h is composed of a feature
extractor g : X → Rd followed by a linear softmax classification layer f : Rd → ∆K−1 , as mentioned in Sec. 2. As
our initial classifier we use ResNet (He et al., 2016) pretrained using the first stage of MiSLAS (Zhong et al., 2021).
We perform fine-tuning of the model through SelMix (Alg.
1) that generates a distinct sampling function to perform
mixup that specifically optimised the desired objective. The
appendix mentions additional details and hyper-parameters
values in Table J.1.
Evaluation Setup. We compare the methods on two broad
sets of metric objectives: a) Unconstrained objectives
which includes G-mean, H-mean, Mean (Arithmetic Mean),
and worst-case (Min.) Recall b) Constrained objectives
include maximizing the recalls under coverage constraints.
The constraint for all classes is that coverage should begreater than 0.95
K . As followed in the literature (Narasimhan& Menon, 2021) for CIFAR-100 LT, Imagenet-100 LT, andImagenet-1k LT due to very few samples in the tail classes,
instead of Min Recall/Coverage, we optimize the Min HeadTail Recall/Min Head-Tail coverage, respectively. The tailcorresponds to the least frequent 10% of the classes, and thehead corresponds to the rest. For a more detailed overview
of the metric objectives and their definition (Table J.3).

We want to convey that despite the re-parameterization we
do not require the actual computation of C̃. As all the termsC̃)
which we require, can be computed analytically inof ∂ψ(∂ C̃lkterms of C, which makes this operation inexpensive (see Sec.
B). Further, this also allows us to have a tractable formulafor gain circumeventing the non-differentiability introducedby constraints of confusion matrix C. (see Sec. H) We now
provide an approximation for gain through the following.
Here for conciseness, we provide an informal statement of
the approximation formula. We refer to Theorem G.1 for amore mathematically precise statement.
Theorem 3.1. The Gain for the i, j mixup (Gij ) can bePC̃)(νij )⊤
approximated as Gij ≈ k,l ∂ψ(l · zk . where∂ C̃klzk = Ex∼Dkval [g(x)] is the mean of the feature of the samples from validation set belonging to class k.
The above formula is an approximation based on the correlation of change in logits for the classifier f with weight
W , with the change in the unconstrained version of theconfusion matrix. Changes in the confusion matrix entries
are necessary to be correlated with changes in logit vectors.
This approximation formula holds under natural conditions(Theorem G.1). Moreover, this approximation works wellin practice, as demonstrated empirically in Sec. 4.
We now provide an algorithm for training h through SelMix(We refer to Alg. 1 for psuedo code). The high-level idea is3

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Mean Rec.

Min Rec.

GM

HM

Mean Rec. / Min Cov.

Mean Rec.

Min H-T Rec.

HM

GM

Mean Rec. / Min HT Cov.

70.1
76.3
79.7
74.9
81.9
83.3

40.2
60.9
71.1
45.2
72.5
79.2

66.9
75.4
79.5
72.7
81.6
82.8

63.7
74.5
79.2
70.3
81.3
82.6

70.1/0.041
76.3/0.066
79.7/0.091
74.9/0.046
81.9/0.077
83.2/0.095

41.7
42.6
41.9
40.2
47.0
48.3

10.5
10.2
36.2
1.1
15.2
41.3

31.2
33.2
26.4
0.0
39.9
42.3

19.0
19.3
12.2
0.0
30.9
38.2

41.7/0.0029
42.6/0.0047
41.9/0.0990
40.2/0.0020
47.0/0.0055
47.8/0.0095

CIFAR-100

ERM
LDAM w/ DRWCSLMiSLAS (stage 1)
w/ (stage 2)
w/ SelMix

CIFAR-10

Table 1. Comparison of metric values with various Long-Tailed methods on CIFAR-10/100 LT under ρ = 100 setup. The best results areindicated in bold. We consistently observe a boost in the performance compared to the initial pre-trained model of MiSLAS (stage 1)

4.2. Comparison
CIFAR datasets: Here, we consider the CIFAR-10 and
CIFAR-100 LT (ρ = 100) datasets. We observe a significant improvement in the corresponding metric for which
the model was fine-tuned when using the proposed SelMix
method in all cases, compared to the FixMatch (LA) pretrained model. For the Min. Recall metric, we observe anapproximately 75% improvement for CIFAR-10 LT and acorresponding 48% improvement in Min. HT Recall for
CIFAR-100 LT over the baseline method. SelMix also outperforms the 2nd stage of MiSLAS across all metrics, including mean recall (∼ accuracy). We find that, for optimizing
a given metric, PSelMix initially mixes up samples from tailclasses with head classes while using the tail class sample’slabel to increase performance on them. Then, it graduallytransitions towards uniform mixups later ( Appendix L).

age constraints without suffering on the mean recall. Thisis unlike Stage-2 MiSLAS trained model which does notsatisfy the coverage constraint.
4.3. Extension to Semi-Supervised Learning
We show results for the case of a semi-supervised setup
where the samples are taken from the labeled and unlabeleddatasets based on their labels and pseudo-labels, respectively. We compare against existing SoTA methods in imbalanced semi-supervised learning such as DASO (Oh et al.,2022), CoSSL (Fan et al., 2022), and ABC (Lee et al., 2021).
We show that and our method not only achieves superior
performance for the desired metric but also achieves superior accuracy (∼ Mean Rec.) under a diverse set of data
distributions, even under cases where the labeled and unlabeled data distribution are mismatched. For the metric of
Min Recall, a 5% improvement is observed for CIFAR-10,
and a corresponding 9.8% improvement in Min HT Recall
for CIFAR-100 over existing SoTA methods (Table O.5).
The STL-10 dataset comes with an additional 100k samples,with unknown label distribution. This setting emulates thepractical scenario where a lot of data is being collected
but labels are absent due to high annotation costs. Due tono distributional assumption, SelMix outperforms SoTA
methods for the min-recall metric by 12.7% (Table O.3).
We use a WideResNet 28-2 pre-trained using FixMatch(Sohn et al., 2020) where the supervised loss is replaced by
the logit adjusted loss for superior consistency regularization
despite the label distribution mismatch between labeled andunlabeled data. Training details are available in Table J.2.

Consider the optimization of metrics with coverage constraints (i.e., covi [h] ≥ 0.95
K ). We optimize the model’smean recall with coverage constraint, as CSL(Narasimhan& Menon, 2021) supports it. However, as SelMix is generic,it also supports optimizing non-linear metrics like H-mean
with coverage, which we show in the Appendix K. Table 1
shows that most heuristic SotA methods lead to sub-optimalmin. coverage values, and only CSL and SelMix approximately satisfy the coverage constraints. SelMix achieves
better mean recall than CSL, providing a better tradeoff interms of performance and satisfiability of constraints.
Table 2. Comparison of SelMix’s performance on Imagnet-1k LT.
We show the scalability of SelMix to large scale datasets with veryminimal cost of fine-tuning the pre-trained model

MethodCSL
MiSLAS (stage 1)
w/ (stage 2)
w/ SelMix

Mean
Recall
48.5
45.5
52.2
52.8

Min
Recall
40.2
4.1
29.7
45.1

5. Conclusion and Discussion

Mean Rec.
/ Min HT Cov.
38.5/0.00099
45.5/0.00004
52.2/0.00062
52.5/0.00099

We study the optimization of complex practical metrics likethe G-mean and H-mean of Recalls, along with objectives
with fairness constraints in the case of neural networks. We
find that most existing techniques achieve sub-optimal performance in terms of these practical metrics, notably on
worst-case recall. These metrics and constraints are NDM,
for which we propose a Selective Mixup (SelMix) basedfine-tuning algorithm for optimizing them. The algorithm
selects samples from particular classes to mixup to improvea linear approximation of the non-decomposable objective.
Our method SelMix is able to improve on the majority ofobjectives in comparison to the baselines, bridging the gap
between theory and practice. We expect SelMix fine-tuning
technique to be used for improving existing models by improving on worst-case and fairness metrics inexpensively.

Imagenet1k LT We show that our method SelMix, scales
well to large-scale datasets as well. Here we do not consider
the Harmonic mean of recall and Geometric mean of recall
since due to the scarcity of samples for the tail classes (5samples per class), their recall values are very small pushing the overall values too low (≈ 0) making them not very
informative about the overall performance of the classifier.
Here again, we observe that SelMix significantly improves
over the baseline and also comfortably satisfies the cover4

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

References

Kim, J.-H., Choo, W., and Song, H. O. Puzzle mix: Exploiting saliency and local statistics for optimal mixup.
In International Conference on Machine Learning, pp.
5275–5285. PMLR, 2020b.

Achiam, J., Held, D., Tamar, A., and Abbeel, P. Constrained
policy optimization. In International conference on machine learning, pp. 22–31. PMLR, 2017.
Auer, P., Cesa-Bianch, N., Freund, Y., and E. Schapire, R.
The non-stochastic multi-armed bandit problem. SIAM
Journal of Computing, 32(1):48–77, 2002.

Kolesnikov, A., Beyer, L., Zhai, X., Puigcerver, J., Yung,J., Gelly, S., and Houlsby, N. Big transfer (bit): Generalvisual representation learning. In European conferenceon computer vision, pp. 491–507. Springer, 2020.

Castelvecchi, D. Is facial recognition too biased to be letloose? Nature, 587(7834):347–350, 2020.

Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020.

Cotter, A., Jiang, H., Gupta, M. R., Wang, S., Narayan,T., You, S., and Sridharan, K. Optimization with nondifferentiable constraints with applications to fairness,recall, churn, and other goals. J. Mach. Learn. Res., 20(172):1–59, 2019.

Lee, H., Shin, S., and Kim, H. Abc: Auxiliary balanced
classifier for class-imbalanced semi-supervised learning.
Advances in Neural Information Processing Systems, 34:
7082–7094, 2021.
Menon, A. K., Jayasumana, S., Rawat, A. S., Jain, H., Veit,
A., and Kumar, S. Long-tail learning via logit adjustment.
In International Conference on Learning Representations,
2020.

Fan, Y., Dai, D., Kukleva, A., and Schiele, B. Cossl: Colearning of representation and classifier for imbalanced
semi-supervised learning. In The IEEE Conference on
Computer Vision and Pattern Recognition (CVPR), 2022.

Mohri, M., Sivek, G., and Suresh, A. T. Agnostic federated learning. In International Conference on Machine
Learning, pp. 4615–4625. PMLR, 2019.

Freund, Y. and Schapire, R. E. A decision-theoretic generalization of on-line learning and an application to boosting.
Journal of computer and system sciences, 55(1):119–139,
1997.

Narasimhan, H. and Menon, A. K. Training overparameterized models with non-decomposable objectives.
Advances in Neural Information Processing Systems, 34,
2021.

Goh, G., Cotter, A., Gupta, M., and Friedlander, M. P. Satisfying real-world goals with dataset constraints. Advancesin Neural Information Processing Systems, 29, 2016.

Narasimhan, H., Vaish, R., and Agarwal, S. On the statisticalconsistency of plug-in classifiers for non-decomposable
performance measures. Advances in neural information
processing systems, 27, 2014.

He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE
conference on computer vision and pattern recognition,
pp. 770–778, 2016.

Narasimhan, H., Kar, P., and Jain, P. Optimizing nondecomposable performance measures: A tale of twoclasses. In International Conference on Machine Learning, pp. 199–208. PMLR, 2015a.

He, K., Chen, X., Xie, S., Li, Y., Dollár, P., and Girshick,
R. Masked autoencoders are scalable vision learners. In
Proceedings of the IEEE/CVF Conference on Computer
Vision and Pattern Recognition, pp. 16000–16009, 2022.

Narasimhan, H., Ramaswamy, H., Saha, A., and Agarwal,
S. Consistent multiclass algorithms for complex performance measures. In International Conference on Machine Learning, pp. 2398–2407. PMLR, 2015b.

Kennedy, K., Mac Namee, B., and Delany, S. J. Learning without default: A study of one-class classificationand the low-default portfolio problem. In Artificial Intelligence and Cognitive Science: 20th Irish Conference,
AICS 2009, Dublin, Ireland, August 19-21, 2009, Revised
Selected Papers 20, pp. 174–187. Springer, 2010.

Narasimhan, H., Ramaswamy, H. G., Tavker, S. K., Khurana, D., Netrapalli, P., and Agarwal, S. Consistent multiclass algorithms for complex metrics and constraints.
arXiv preprint arXiv:2210.09695, 2022.

Kim, J., Hur, Y., Park, S., Yang, E., Hwang, S. J., and Shin,
J. Distribution aligning refinery of pseudo-label for imbalanced semi-supervised learning. In Proceedings ofthe 34th International Conference on Neural Information Processing Systems, NIPS’20, Red Hook, NY, USA,
2020a. Curran Associates Inc. ISBN 9781713829546.

Oh, Y., Kim, D.-J., and Kweon, I. S. Daso: Distributionaware semantics-oriented pseudo-label for imbalanced
semi-supervised learning.
In Proceedings of theIEEE/CVF Conference on Computer Vision and Pattern
Recognition, pp. 9786–9796, 2022.
5

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Rangwani, H., Ramasubramanian, S., Takemori, S., Takashi,K., Umeda, Y., and Radhakrishnan, V. B. Cost-sensitive
self-training for optimizing non-decomposable metrics.
In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K.
(eds.), Advances in Neural Information Processing Systems, 2022.
Sohn, K., Berthelot, D., Carlini, N., Zhang, Z., Zhang, H.,
Raffel, C. A., Cubuk, E. D., Kurakin, A., and Li, C.-L.
Fixmatch: Simplifying semi-supervised learning withconsistency and confidence. Advances in Neural Information Processing Systems, 33:596–608, 2020.
Sun, Y., Kamel, M. S., and Wang, Y. Boosting for learning
multiple classes with imbalanced class distribution. In
Sixth international conference on data mining (ICDM’06),
pp. 592–602. IEEE, 2006.
Verma, V., Lamb, A., Beckham, C., Najafi, A., Mitliagkas,
I., Lopez-Paz, D., and Bengio, Y. Manifold mixup: Better
representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6438–6447.
PMLR, 2019.
Wang, S. and Yao, X. Multiclass imbalance problems: Analysis and potential solutions. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 42(4):1119–1130, 2012.
Wei, C., Sohn, K., Mellina, C., Yuille, A., and Yang, F.
Crest: A class-rebalancing self-training framework for
imbalanced semi-supervised learning. In Proceedings ofthe IEEE/CVF conference on computer vision and patternrecognition, pp. 10857–10866, 2021.
Yun, S., Han, D., Oh, S. J., Chun, S., Choe, J., and Yoo,
Y. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceedings of theIEEE/CVF international conference on computer vision,
pp. 6023–6032, 2019.
Zagoruyko, S. and Komodakis, N. Wide residual networks.
CoRR, abs/1605.07146, 2016.
Zhang, H., Cisse, M., Dauphin, Y. N., and Lopez-Paz, D.
mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018.
Zhong, Z., Cui, J., Liu, S., and Jia, J. Improving calibration for long-tailed recognition. In IEEE Conference on
Computer Vision and Pattern Recognition (CVPR), pp.
16489–16498, 2021.

6

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Appendix
A. Notation
Table A.1. Table of Notations used in PaperK
Y := [K]xyX
h:X →YC[h]∆n−1 ⊂ Rn
ψ : ∆K 2 −1 (⊂ RK×K ) → R
πig : X → Rd
f : Rd → ∆K−1
W ∈ RK×dzk
LMU (xi , yi , xj ; h)
i,j

LMU
Gij
νeij
∇A ψ (where A ∈ RK×d )
s
C̃
Di
D̃i
P
P = (P t )Tt=1
G(P)
Nk
Mk
ρl
ρu
H
T
∥A∥F

Number of classes
Label space
Instance
Label
Instance spacea classifier
Confusion matrix for the classifier h
the n − 1-dimensional probability simplex
a function defined on the set of confusion matrices (ψ(C[h]) is the metricof h)prior for class i ∈ [K]a feature extractor
the final classifier such that h = argmaxi fi ◦ g
the weight of the final layer
the centroid of class samples given as Ex∼Dkval [g(x)]the loss for mixup between labeled sample (xi , yi ) and unlabeld sample
xj
the expected loss due to (i, j) mixup
gain upon performing (i, j) mixup
the change in linear classifier weights ν due to (i, j) mixupP∂ψ
the directional derivative defined as k,l Akl ∂W
kl
the inverse temperature parameter for the softmax
Unconstrained extension for confusion matrix C
Subset of data with label i
Subset of data with pseudo-label ia distribution on [K] × [K]a policy (a sequence of distributions P t )the expected average gain of P
the number of samples in the k-th labeled classthe number of samples in the k-th unlabeled classthe class imbalanced factor of the labeled dataset (max1≤i,j≤K Ni /Nj )the class imbalanced factor of the unlabeled dataset
The set of first 90% classes that contains the majority of samples
The set of last 10% classes that contains the minority of samples
the Frobenius norm of a matrix

B. Non-differentiability and the Unconstrained Confusion Matrix
In Eq. (3), we define the gain Gij by a directional derivative of ψ(C) with respect to weight W . However, strictly
speaking, since the definition of the confusion matrix C involves the indicator function, ψ(C) is not a differentiable
function of W . Moreover, even if gradients are defined, they vanish because of the definition of the indicator function.
e is a smooth function of W and it
In the assumption of Theorem G.1 (a formal version of Theorem 3.1), we assume C
implies C is a differentiable function of W . This assumption can be satisfied if we replace the indicator function bysurrogate functions of the indicator functions in the definition of the confusion matrix C. More precisely, we replace thedefinition of Cij [h] = πi Ex∼Pi [1(h(x) = j)] by πi Ex∼Pi [sj (f (x))]. Here h(x) = argmaxk fk (x) as before, Pi is theclass conditional distribution P (x|y = i) and sj is a surrogate function of p 7→ 1(argmaxi pi = j) satisfying 0 ≤ sj (p) ≤ 1
7

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

PKfor any 1 ≤ j ≤ K, p ∈ ∆K−1 and j=1 sj (p) = 1 for any p ∈ ∆K−1 . To compute Gij , one can directly use the definitionof Eq. (3) with the smoothed confusion matrix using surrogate functions of the indicator function. However, an optimal
choice of the surrogate function is unknown. Therefore, in this paper, we introduce an unconstrained confusion matrix C̃
e and the approximation formulaand the approximation formula Theorem 3.1 (Theorem G.1). An advantage of introducing CP ∂ψ(C̃)⊤is that the RHS of the approximation formula k,l ∂ C̃(νij )l · zk does not depend on the choice of the surrogateklfunction if we use formulas provided in Sec. H with the original (non-differentiable) definition of C. 1 . Since the optimal
choice of the surrogate function is unknown, this gives a reliable approximation.

C. Computational Complexity
We discuss the computational complexity of SelMix and that of an existing method (Rangwani et al., 2022) for NDM
optimization in terms of the class number K. We note that to the best of our knowledge, CSST (Rangwani et al., 2022) isthe only existing method for NDM optimization in the SSL setting.
Proposition C.1. The following statements hold:(t)

1. In each iteration t in Algorithm 1, computational complexity for PSelMix is given as O(K 3 ).
2. In each iteration of CSST (Rangwani et al., 2022), it needs procedure that takes O(K 3 ) time.
Here, the Big-O notation hides sizes of parameters of the network other than K (i.e., the number of rows of W ) and the sizeof the validation dataset.
Proof. 1. Computational complexity for the confusion matrix is given as O(K 3 ) since there are K 2 entries and for eachentry, evaluating h(t) (x) takes O(K) time for each validation data x. For each 1 ≤ k ≤ K, computational complexity
for zk is O(K). We compute {softmax(zk )}1≤k≤K , which takes O(K 2 ) time. The (m, l)-th entry of the matrix νij isgiven as −ηζm (δil − softmaxi (ζ)), where 1 ≤ m ≤ d, 1 ≤ l ≤ K, and ζ = βzi + (1 − β)zj ∈ Rd . Therefore, once
we compute {softmax(zk )}1≤k≤K , computational complexity for {νij }1≤i,j≤K is O(K 3 ). For each 1 ≤ l ≤ K, we put
(t)
PK
PK
(t)
(t)
)
vl = k=1 ∂ψ(Czk . Then computational complexity for {vl }1≤l≤K is O(K 2 ). Since Gij = l=1 (νij )⊤l · vl is a
∂ C̃
kl

(t)

sum of K dot products of d-dimensional vectors, once we compute {vl }l , computational complexity for {Gij }1≤i,j≤K is(t)

O(K 3 ). Thus, computational complexity for PSelMix is given as O(K 3 ).

2. In each iteration t, CSST needs computation of a confusion matrix at validation dataset. Since there are K 2 entries andfor each entry, h(t) (x) takes O(K) time for each validation data x, computational complexity for the confusion matrix is
given as O(K 3 ). Thus, we have our assertion.

D. Non-Decomposable Metrics
In this section, we provide more detailed introduction to NDM. Real-world datasets are long-tailed and imbalanced. Insuch cases, the mean recall can be deceptive as the model might be very good for majority classes while performing below
par for minority classes. In such cases, the metrics of H-mean (the harmonic mean of recalls across classes) (Kennedy
et al., 2010), G-mean (the geometric mean of recalls across classes) (Wang & Yao, 2012; Lee et al., 2021) and Minimum (worst-case) recall (the minimum of recalls across classes) (Narasimhan & Menon, 2021) across classes is better
suited for holistic evaluation. These metrics show a significant deviation from mean performance in case of performancedisparity between the majority and minority classes. The G-mean of recall can be defined in terms of the confusion
Q K1
P Cii [h]. For the minimum recall (ψ MR ) we use the continuous relaxmatrix (C[h]) as ψ GM (C[h]) =i∈[K]j∈[K] Cij [h]ation as used by (Narasimhan & Menon, 2021), by writing the objective as min-max optimization over λ ∈ ∆K−1 :P. Fairness is another area where such complex metrics aremaxh ψ MR (C[h]) = maxh minλ∈∆K−1 i∈[K] λi P Cii [h]j∈[K] Cij [h]particularly useful. For example, prior works (Cotter et al.,2019;
Goh et al., 2016) consider optimizing the mean recall
P
while constraining the predictive coverage (covi [C[h]] = j Cji ) that is the proportion of class i predictions on test dataPK1αgiven as maxh K
i=1 reci [h] s.t. covi [h] ≥ K ∀i ∈ [K]. Optimization of above-constrained objectives is possible by1

Constants such as c, c′ in Theorem G.1 do depend on the surrogate function

8

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Table D.1. Metrics defined using the entries of confusion matrix C.

MetricMean Recall (ψ AM )1
KMin. Recall (ψ MR )G-mean (ψ GM )H-mean (ψ HM )AMMean Recall s.t. per class coverage ≥ τ (ψcons.
)P

Definition
P Cii [h]j∈[K] Cij [h]P Cii [h]i∈[K] λi j∈[K] Cij [h]i∈[K]minλ∈∆K−1
Q

P

1

K
P Cii [h]j∈[K] Cij [h]PP−1j∈[K] Cij [h]Ki∈[K]Cii [h]PPPαP Cii [h]minλ∈RK
λ
C
[h]
−
+
i∈[K]
j∈[K] ji∈[K] ijK
Cij [h]
+

i∈[K]

j∈[K]

using the Lagrange Multipliers (λ ∈ RK≥0 ) as done in Sec. 2 of Narasimhan & Menon (2021). By expressing this above
expression in terms of C[h] and through linear approximation, the constrained objectiveψcons. (C[h]) can be considered
as:

P
P
P
P
α
1
AM
C
[h]
−
λ
maxh ψcons.
(C[h]) = maxh minλ∈RK
C
[h]
+
C
[h]/
.
i∈[K] ijj∈[K] jj∈[K] iji∈[K] iiK
≥0 K

The λ for calculating value of ψcons. (C[h]) and ψ MR (C[h]), is periodically updated using exponentiated or projectedgradient descent as done in (Narasimhan & Menon, 2021). We summarize ψ(C[h]) for all NDM we consider in this paperin Table D.1. We will consider maximization of all such objectives expressed through ψ(C[h]). In comparison to existing
frameworks (Narasimhan & Menon, 2021; Rangwani et al., 2022) in addition to linear metrics, we can also optimize fornon-linear metrics like (G-mean and H-mean) for neural networks. , such as optimizing minimum Recall (Narasimhan &Menon, 2021; Cotter et al., 2019), H-mean of Recall and even the lagrangian relaxations of constrained objectives like mean
recall under coverage constraints. We follow the convention that increasing ψ leads to the desired performance. Givena K
class classification problem, our objective is to optimize a NDM ψ(C), where ψ : ∆K×K−1 →− R, which is a function of
the entries of the confusion matrix C[h], for a classifier h ∈ H. Here H is the set of all possible classifiers. Some of the
NDM we wish to optimise for have been tabulated below. Many of these metrics encourage the classifier to produce more
equitable results on long-tailed data. We assume a feature extractor g : χ → Rd which is followed by a linear layer classifierf parameterised by weights W ∈ Rd×K which is followed by a softmax layer.

E. Algorithm
In this section, we provide more detailed description of our algorithm in Algorithm 1.

Algorithm 1 Training through SelMix
Input: Data (D, Dval ), iterations T , classifier h(0) , metric function ψ
for t = 1 to T doh(t) = h(t−1) , C (t) = E(x,y)∼Dval [C[h(t) ]](t)

νij = −η∇L̄ij(3)
MU-CE ∀ i, jP ∂ψ(C (t) ) (t) ⊤(t)(νij )l · zk ∀ i, j
Gij = k,l ∂ C̃(t)kl

PSelMix = softmax(G(t) )for n SGD steps do(t)
Y1 , Y2 ∼ PSelMix
X1 ∼ U(DY1 ) , X2 ∼ U(DY2 ) // sample batches of datah(t) := SGD-Update(h(t) , ∇LMU-CE (X1 , Y1 , X2 ))end forend for
Output: h(T )9SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

F. Theoretical Analysis
In this section motivated by Algorithm 1, we consider the following online learning problem and prove validity of our
method. For each time step t = 1, . . . , T , an agent selects pairs (i(t) , j (t) ) ∈ [K] × [K], where random variables (i(t) , j (t) )follows a distribution P t on [K] × [K]. We call a sequence of distributions (P t )Tt=1 a policy. For (i, j) ∈ [K] × [K] and(t)(t)
1 ≤ t ≤ T , we assume that a random variable Gij is defined. We regard Gij as the gain in the metric when performing(t)(i, j)-mixup at iteration t in Algorithm 1. We assume that Gij is a random variable due to randomness of the validation
dataset, X1 , X2 , and the policy. Furthermore, we assume that when selectingh(i(t) ,ij (t) ), the agent observes random variables
(t)

(t)

(T )

Gij for (i, j) ∈ [K] × [K] but cannot observe the true gain defined by E Gij . The average gain G (P) of a policy
h
i
PT
(T )
(t)
P = (P t )Tt=1 is defined as G (P) = T1 t=1 E Gij , where (i(t) , j (t) ) follows the distribution P t and the expectation
is taken with respect to the randomness of the policy, validation dataset, X1 , X2 . This problem setting is similar to thatof Hedge (Freund & Schapire, 1997) and EXP3 (Auer et al., 2002). However, in the problem setting of Hedge, the agent
observes gains (or losses) after performing an action but in our problem setting, the agent have random estimations of the(t)gains before performing an action. We note that even in this setting, methods such as argmax with respect to Gij may not(t)

perform well due to randomness of Gij and errors in the approximation.
We call a policy P = (P t )Tt=1 non-adaptive (or stationary) if P t is the same for all t = 1, . . . , T , i.e, if there exists a
distribution P 0 on [K] × [K] such that P t = P 0 for all t = 1, . . . , T . A typical example of non-adaptive policies is theuniform mixup, i.e., P t is the uniform distribution on [K] × [K]. Another typical example is P t = δ(i(0) ,j (0) ) for a fixed(i(0) , j (0) ) ∈ [K] × [K] (i.e., the agent performs the fixed (i(0) , j (0) ))-mixup in each iteration). Similarly to Hedge (Freund& Schapire, 1997) and EXP3 (Auer et al., 2002), we consider softmax policy with respect to the cumulative sum of gains.
Similary to Hedge (Freund & Schapire, 1997), the following theorem states that the SelMix policy is better than any
non-adaptive policy in terms of the average expected gain if T is sufficiently large:
Pt−1 (τ )ttTheorem F.1. We define P SelMix = (PSelMix)Tt=1 by PSelMix= softmax((s τ =1 Gij )1≤i,j≤K ), where s > 0 is the inverse
(t)

(t)

temperature parameter. We assume that Gij is normalized so that Gij ∈ [0, 1]. Then, with an appropriate choice of theinverse temperature parameter s, for any non-adaptive policy P 0 = (P 0 )Tt=1 , we have (Proof in Appendix G.2)√
2 log K(T )(T )G (P SelMix ) + √≥ G (P 0 ).
T

Next, we consider a variant of the policy and introduce analysis of it.
Pt
(t)
(t)
(τ )
Theorem F.2. We define PSelMix = softmax((s τ =1 Gij )ij ) and define a policy P SelMix = (PSelMix )t . Then for anys > 0 and for any non-adaptive policy P (0) = (P (0) )Tt=1 , we haveG(T )(P SelMix ) +2 log K(T )≥ G (P (0) ).
sT

G. Proofs for Mathematical Results in Paper
G.1. A Formal Statement of Theorem 3.1 and its Proof
We provide a more formal statement of Theorem 3.1 (Theorem G.1) and provide its proof.
Theorem G.1. For a matrix A ∈ Rn×m , we denote by ∥A∥F the Frobenius norm of A. We fix the iteration of the gradiente takes the value C
e (0) .
descent and assume that the weight W takes the value W (0) and C

We assume that the following inequality holds for all k ∈ [K] and l ∈ [K] uniformly W ∈ N0 , where N0 is an open
neighbourhood of W (0) :ek )| ≤ ε.
|E softmaxl (W ⊤ g(xk )) − softmaxl (Ce can be regarded as a smooth function of W and the Frobenius norm of the Hessian is bounded
We also assume that on N0 , C
on N0 . Furthermore, we assume that the following small variance assumption with εe > 0 for all k:
K
X

m=1



V (W ⊤ g(xk ))m ≤ εe.
10

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Then if ∥∆W ∥F is sufficiently small, there exist a positive constant c > 0 depending only on K with c = O(poly(K)) anda positive constant c′ > 0 such that the following inequality holds:
Gij −

K
X
∂ψ

e
k=1 ∂ Ck(∆W )⊤ zk ≤ c

∂ψ
∂C

F

e 2F ).
(ε + εe) + c′ (∥∆W ∥2F + ∥∆C∥t
ek is a column vector such that the k-th row of C
e is given as C
ek , and we consider Jacobi matrices at
Here ∆W = ν̃ij
and C
e=C
e (0) and the corresponding value of C.
C

Proof. In this proof, to simplify notation, we denote softmax(z) by σ(z) for z ∈ RK . In this proof, we fix the iteration ofe takes the value C
e (0) . We assume in an
the gradient descent and assume that the weight W takes the value W (0) and C(0)eopen neighborhood of W , we have a smooth correspondence W 7→ C and that if the value of W changes from W0 toe changes from C
e0 to Ce0 + ∆C.
e To prove the theorem, we introduce the following three lemmas. We
W0 + ∆W , then C
note that by the assumption of the theorem and Lemma G.3, the assumption (6) of Lemma G.4 can be satisfied with
ε1 = c′′ (ε + εe),where c′′ > 0 is a constant depending only on K with c′′ = O(poly(K)). Then by Lemma G.4, there exist constants
c1 = c1 (K) and c2 = c2 (K) depending on only K with c1 , c2 = O(poly(K)) such that the following inequality holds for
all k:
∂Cek − (∆W )⊤ zk
ek ∥2F + ∥(∆W )⊤ zk ∥2F ).
∆C≤ c1 ε1 + c2 (∥∆C
(4)
ek Ce =Ce(0)
∂C
k

F

k

Then, we have the following:KK∂ψ ∂C e X ∂ψ ∂C∂ψ e X ∂ψ∆C −∆C −(∆W )⊤ zk =(∆W )⊤ zkeekeek∂C ∂ C∂C ∂ C
∂C
∂
C
k=1
k=1
K

=

K

X ∂ψ ∂C∂ψ X ∂C e∆C k −(∆W )⊤ zkeek∂C∂C ∂ C
∂ Ck
k=1

≤

∂ψ
∂C

F

k=1

K
X
∂C 

e

k=1 ∂ Ck

ek − (∆W )⊤ zk
∆C



F

∂C
2
2
2
e
Here, by fixing an order on [K] × [K], we regard ∂∂ψe , ∂Ce and ∆C as a K -dimensional row vector, a K × K -matrix,
C
2
e
e (0)

and a K -dimensional column vector, respectively. Moreover, we consider Jacobi matrices at C = C
of the theorem from this inequality, (4), Lemma G.2.

. Then, the assertion

Lemma G.2. Under assumptions and notations in the proof of Theorem G.1, there exists a constant c > 0 such that
Gij −

∂ψ
e ≤ c∥∆W ∥2 .
∆C
F
e
(0)
e
e
∂ C C=Ce and the Taylor’s theorem, there exists c1 > 0 such that
Proof. By the assumption of the mapping W 7→ C
!
e
∂
C
e−
∆C
∆W
≤ c1 ∥∆W ∥2F .
∂W
W =W0

F

By definition of Gij , we have the following:
Gij −

∂ψ
e C=
e C
e(0)
∂C

e =
∆C

=

∂ψ e
∂ψ
∆W −
∆C
e
∂W
∂C

e
∂ψ e
∂ψ ∂ C
∆W −
∆C
e ∂W
e
∂C
∂C

≤ c1
11

∂ψ
e
∂C

2

F

∥∆W ∥F .

(5)

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Here we consider Jacobi matrices at W = W0 and corresponding values. The last inequality follows from the fact that thematrix norm ∥ · ∥F is sub-multiplicative and Eq. (5).
Lemma G.3. Under assumptions and notations in the proof of Theorem G.1, there exist a positive constant c = c(K)depending only on K with c = O(poly(K)) such that:
K
X




V (W ⊤ g(xk ))m ,|E σl (W ⊤ g(xk )) − σl (W ⊤ zk )| ≤ c
m=1

for any 1 ≤ k, l ≤ K.
Proof. This can be proved by applying the Taylor’s theorem to σl . We fix k, l and apply the Taylor’s theorem to the function
ξ 7→ σl (ξ) at ξ = W ⊤ zk = W ⊤ E [g(xk )]. Then there exists ξ0 ∈ RK such thatσl (ξ) = σl (W ⊤ zk ) +2

where Hk = ∂∂ξσ2l

ξ=ξ0

∂σl
1
(ξ − W ⊤ zk ) + (ξ − W ⊤ zk )⊤ Hk (ξ − W ⊤ zk ),∂ξ ξ=W ⊤ zk
2∂σl
= δlm σl (ξ) − σl (ξ)σm (ξ) (here δlm is the Kronecker’s delta), it is easy to. By noting that ∂ξmsee that there exists a constant c′l depending only on l and K such that ∥H∥F < c′l and c′l = O(poly(K)). By letting
ξ = W ⊤ g(xk ) in the above equation and taking the expectation of the both sides, we obtain the assertion of the lemma withc = 12 maxl≤[K] c′l .
Lemma G.4. Under assumptions and notations in the proof of Theorem G.1, we assume there exists ε1 > 0 such that theefollowing inequality holds for all k and l for any W in an open neighborhood of W (0) and corresponding C:ek ) ≤ ε1 .
σl (W ⊤ zk ) − σl (C(6)

Furthermore, we assume that ∥(∆W )⊤ zk ∥F is sufficiently small for all k. Then there exist constants c1 = c1 (K) andc2 = c2 (K) depending on only K with c1 , c2 = O(poly(K)) such that∂Cek − (∆W )⊤ zk∆C
ek Ce =Ce(0)
∂C
k

k

F

ek ∥2 + ∥(∆W )⊤ zk ∥2 ).
≤ c1 ε1 + c2 (∥∆CFFek ) is a column vector such that the k-th row vector of C
e is given as Cek ).
ek (resp. ∆Ce (resp. ∆C)ek (resp. ∆CHere, C∂C
2
2
Moreover, when defining Jacobi matrices, we regard C as a K -vector and consider a K × K Jacobi matrix ∂ Ce(0)kek = Ce (0) .
at C
k

ek =C
e
C
k

e we apply the Taylor’s theorem to the
Proof. Since (6) holds all W in an open neighborhood of W (0) and corresponding C,
(0)
(0) ⊤
e . Then by (6) and the same argument in the proof of Lemma G.3, wefunction ξ 7→ σl (ξ) at ξ = (W ) zk and ξ = C
k
have
∂σl
∂σl
ek ∥2 ),
ek ≤ ε1 + c′2 (∥∆µk ∥2F + ∥∆C
∆µk −
∆C
F
∂ξ ξ=µk∂ξ ξ=Ce(0)klwhere µk = (W ) zk , ∆µk = (∆W ) zk . Noting that ( ∂σ∂ξ )m is given as δml σl (ξ) − σm (ξ)σl (ξ), (6) and theassumption that ∥µk ∥F is sufficiently small, we see that there exists a constant c′1 , c′2 > 0 depending only on K withc′1 , c′2 = O(poly(K)) such that the following inequality holds:

(0) ⊤

⊤



∂σl
ek ∥2F ).
ek ≤ c′1 ε1 + c′2 (∥∆µk ∥2F + ∥∆C∆µk − ∆C∂ξ ξ=Ce(0)(7)

kNext, we consider entries of the K 2 -vector ∂∂C
e
C

k

ek =C
e(0)
C
k

ek − ∆µk ). Here as previously mentioned by fixing an order(∆C2eon [K] × [K], we regard ∂∂Ce as a K × K-matrix. For (k, l) ∈ [K] × [K], by the definition of the mapping C 7→ C,Ck12

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics(k, l)-th entry of ∂∂C
e
C

k

ek =C
e(0)
C
k

ek − ∆µk ) is given as πk ∂σl
(∆C
∂ξ

(0)

e
ξ=C
k

ek − ∆µk ). By (7), we see that there exist(∆Cconstants c′′1 , c′′2 depending only on K and c′′1 , c′′2 = O(poly(K)) such that∂Cek − (∆W )⊤ zk∆C
ek Ce =Ce(0)
∂C
k

k

F

ek ∥2F + ∥(∆W )⊤ zk ∥2F ).
≤ c′′1 ε1 + c′′2 (∥∆C

Since constants c′′1 , c′′2 may depend on (k, l) by taking c1 = max(k,l) c′′1 and c2 = max(i,l) c′′2 , we have the assertion of thelemma.

G.2. Proof of Theorem F.1
First we introduce the following lemma, which is (essentially) due to (Freund & Schapire, 1997). Although, one can prove
the following result by a standard argument, since our problem setting is different, we provide a proof for the sake ofcompleteness.
(t)Lemma G.5 (c.f. (Freund & Schapire, 1997)). We assume that Gi,j ∈ [0, 1] for all t and 1 ≤ i, j ≤ K. For (i, j) ∈
h
h
i
i
PT
PT
(t)
(t)
[K] × [K], we define S i,j = t=1 E Gi,j . For a policy P = (Pt )Tt=1 , we define S P := t=1 E Git ,jt . Then, we
have the following inequality:−2 log K + s

max(i,j)∈[K]×[K]S i,j ≤ (exp(s) − 1)S P SelMix .

Proof. This lemma can be proved by a standard argument, but for the sake of completeness, we provide a proof. We put
A = [K] × [K], at = (i(t) , j (t) ) and in the proof we simply denote P SelMix by P. For a ∈ A and 1 ≤ t ≤ T + 1, we defineP(t)wa,t as follows. We define wa,1 = 1/K 2 for all a ∈ A and wa,t+1 = wa,t exp(sGa ). We also define Wt = a∈A wa,t .
Then, the distribution Pt is given as the probability (wa,t /Wt )a∈A by definition. Noting that exp(sx) ≤ 1 + (exp(s) − 1)x
for x ∈ [0, 1], we have the following inequality:
XX
wa,t exp(sG(t)wa,t+1 =Wt+1 =
a )
a∈A

a∈A

≤
Thus, we haveWt+1 ≤

X

wa,t (1 + exp(s − 1)G(t)a ).

Xwa,t (1 + exp(s − 1)G(t)
a )

a∈A

a∈A

i

h
,
= Wt 1 + (exp(s) − 1)EPt G(t)atwhere EPt [·] denotes the expectation with respect to at . By repeatedly apply the inequality above, we obtain:
WT +1 ≤

T 
Y

t=1

i
h
.
1 + (exp(s) − 1)EPt G(t)at

Let a ∈ A be any pair. By this inequality and WT +1 ≥ wa,T +1 = K12 exp(sPT(t)
t=1 Ga ), we have the following:

T 
T
i
h
Y
X
1
(t)
.
1 + (exp(s) − 1)EPt G(t)
G
)
≤
exp(s
at
a
2
K
t=1
t=1

By taking log of both sides and log(1 + x) ≤ x, we have
−2 log K + s

T
X
t=1

G(t)
a ≤

T
X
t=1


i
h
log 1 + (exp(s) − 1)EPt G(t)at

≤ (exp(s) − 1)
13

T
X
t=1

i
h
EPt G(t)at .

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics(t)

By taking the expectation with respect to the randomness of Gi,j , we obtain the following:−2 log K + sS a ≤ (exp(s) − 1)S P .
Since a ∈ [K] × [K] is arbitrary, we have the assertion of the lemma.
We can prove Theorem F.1 by Lemma G.5 as follows:
Proof of Theorem F.1. Let (i∗ , j ∗ ) be the best fixed Mixup pair hindsight, i.e., (i∗ , j ∗ ) = argmax(i,j)∈[K]×[K] S i,j . Since
any non-adaptive (or stationary) policy is no better than δ(i∗ ,j ∗ ) , to prove the theorem, it is enough to prove the following:p
S i∗ ,j ∗ ≤ S P + 2 T log K.
(8)Here in this proof, we simply denote P SelMix by P. To prove (8), we define the pseudo regret RT by RT = S i∗ ,j ∗ − S P .
Then by Lemma G.5, we have(exp(s) − 1 − s)S i∗ ,j ∗ + 2 log K
RT ≤.
exp(s) − 1

We put s = log(1 + α) with α > 0. Then we haveRT ≤(α − log(1 + α))S i∗ ,j ∗ + 2 log K.
α

We note that the following inequality holds for α > 0:
α − log(1 + α)
1
≤ α
α
2
Then it follows that:

2 log K12 log K1
αS i∗ ,j ∗ +≤ αT +
.
2
α
2
α
q
√
Here the second inequality follows from S i∗ ,j ∗ ≤ T . We take α = 2 logT K . Then we have RT ≤ 2 T log K. Thus, wehave the assertion of the theorem.
RT ≤G.3. Proof of Theorem F.2
Proof. This can be proved by standard argument of the proof of the mirror descent method (see e.g. (Lattimore & Szepesvári,2020), chapter 28).
Denote by ∆ ⊂ RK×K the probability simplex of dimension K 2 −1. Let (i0 , j0 ) ∈ K ×K be the best fixed mixup hindsight.
Since any non-adaptive policy is no better than the best fixed mixup in terms of G, we may assume that P (0) = (π0 )t ,where π0 is the one-hot vector in ∆ defined as (π0 )ij = 1 if (i, j) = (i0 , j0 ) and 0 otherwise for 1 ≤ i, j ≤ K. Let F be thePKPKnegative entropy function, i.e., F (p) = i,j=1 pij log pij . For p ∈ ∆ and G ∈ RK×K , we define ⟨p, G⟩ = i,j=1 pij Gij .
(t)Then, it is easy to see that p(t) = PSelMix defined above is given as the solution of the following:p(t) = argminp∈∆ −s⟨p, G(t) ⟩ + D(p, p(t−1) ).

(9)Here D denotes the KL-divergence and we define p(0) = (1/K 2 )1≤i,j≤K = argminp∈∆ F (p). Since the optimization
problem (9) is a convex optimization problem, by the first order optimality condition, we haveo1n⟨π0 − p(t) , G(t) ⟩ ≤D(π0 , p(t−1) ) − D(π0 , p(t) ) − D(p(t) , p(t−1) ) .
s
By summing the both sides and taking expectation, we have
)
(
T
X
1
(T )
(T )
(0)
(t) (t−1)(0)(T )D(p , p)D(π0 , p ) − D(π0 , p ) −T G (P ) − T G (P SelMix ) ≤
s
t=1
≤

1
D(π0 , p(0) ).
s
14

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Here the second inequality follows from the non-negativity of the KL-divergence. Since p(0) = argminp F (p), by the
first-order optimality condition, we have D(π0 , p(0) ) ≤ F (π0 ) − F (p(0) ). Noting that F (π0 ) ≤ 0, we have the following
TG

(T )

(P (0) ) − T G(T )(P SelMix ) ≤−F (p(0) )log K 2=.
ssThis completes the proof.

H. Unconstrained Derivatives of metric
For any general metric ψ(C[h]) the derivative w.r.t the uncostrained confusion matrix C̃[h] is expressible purely in terms of
the entries of the confusion matrix. The derivative using chain rule is expressed as follows,∂ψ(C[h]) X ∂ψ(C[h]) ∂Ckl [h]=·∂Ckl [h] ∂ C̃ij [h]∂ C̃ij [h]
k,l

(10)

We observe that in Eq. 10 the partial derivative ∂ψ(C[h])∂Ckl [h] is purely a function of entries of C[h] since ψ(C[h]) itself is afunction of entries of C[h]. The second term is the partial derivative of our confusion matrix w.r.t the unconstrained confusion
matrix. Since C and C̃ are related by the following relation Cij [h] = softmax(C̃i [h])j . By virtue of the aforementionedkl [h]
also happens to be expressible in terms of C[h]:map ∂C∂ C̃ [h]
ij






0,
Cil [h]·Cij [h]∂Ckl [h]
,
= −
πival
2
∂ C̃ij [h] C [h] − Cij [h] ,ij(π val )2k ̸= ii = k, l ̸= j

(11)

i = k, l = ji

1
Let us consider the metric mean recall ψ AM (C[h]) = K

Pi

PCii [h] . The derivative of ψ AM (C[h]) w.r.t the unconstrained
j Cij [h]confusion matrix C̃ can be expressed in terms of the entries of the confusion matrix. This is a useful property of this partial
derivative since we need not infer the inverse map from C → C̃ inorder to evaluate the partial derivative in terms of C̃. It
can be expressed follows:
Cij [h]·Cii [h]AMm ̸= n∂ψ (C[h]) − K(πival )2 ,= Cii [h]
(12)
2
C
[h]
ii

∂ C̃ij [h]
m=n
val −
val 2 ,
K·(πi )

K·πi

Hence we can conclude that for a metric defined as a function of the entries of the confusion matrix, the derivative w.r.t theunconstrained confusion matrix (C̃) is easily expressible using the entries of the confusion matrix (C).

I. Updating the Lagrange multipliers
I.1. Min. Recall and Min of Head and Tail Recall
PPPP
minλ∈∆K−1 i∈[K] λi Reci [h] =minλ∈∆K−1 i∈[K] λi P Cii [h]Consider the objective ψ MR (C[h]) =Cij [h] , as inj∈[K]

Table D.1. the lagrange multipliers are sampled from a K − 1 dimensional simplex and λi = 1 if recall of ith class is thelowest and the remaining lagrange multiplers are zero. Hence, a good approximation of the lagrange multipliers at a given
time step t can be expressed as:
λti = Pe−ωReci [h]−ωRecj [h]j∈[K] e(13)This has some nice properties such as the Lagrange multipliers being a soft and momentum free approximation of their hardcounter part. For sufficiently high ω this approximates the objective to the min recall.
15

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

I.2. Mean recall under Coverage constraints

P
P
P
α
AM
P Cii [h]+For the objective ψcons.
(C[h]) = minλ∈RK
j∈[K] λj Covj [h] − K = minλ∈RK
i∈[K] Reci [h]+
i∈[K]
+
+
j∈[K] Cij [h]PPαj∈[K] λji∈[K] Cij [h] − K . For practical purposes, we look at a related constrained optimization problem,AMψcons.
(C[h]) = min1

λmax + 1
λ∈RK
+




X

Reci [h] +

i∈[K]

X

λj

j∈[K]




α 
Covj [h] −
K



α
α
Such that if Covi [h] − K< 0, then λi increases, and vice-versa for the converse case. Also, if ∃i s.t. Covi [h] − K
< 0,

λmax
1
α
+
−
then this implies that λmax +1 → 0 and λmax+1 → 1 , which forces h to satisfy the constraint Covi [h] − K > 0. Basedon this, a momentum free formulation for updating the lagrangian multipliers is as follows:

λi = max 0, Λmax 1 − eCovi [h]− αKτHere, λmax is the maximum value that the Lagrange multiplier can take. A large value of λmax forces the model to focus
more on the coverage constraints that to be biased towards mean recall optimization. τ is a hyperparameter that is usually
kept small, say 0.01 or so, which acts as sort of a tolerance factor to keep the constraint violation in check.

J. Experimental details
J.1. Hyperparameter Table
The detailed values of all hyperparameters specific to each dataset has been mentioned in Table J.1 and Table J.2.
Table J.1. Table depicting Hyperparameters across our experiments for the supervised classification task.

Parameter
Gain scaling (s)ωMin. Recλmax
ταBatch Size
Learning Rate(f )Learning Rate(g)Optimizer
Scheduler
Total SGD Steps
Resolution
Arch.

CIFAR-10(ρ = 100)
10.0
50
100
0.01
0.95
128
3e-3
3e-4
SGD
Cosine2k
32 X 32
ResNet-32

CIFAR-100(ρ = 100)
10.0
25
100
0.01
0.95
128
3e-3
3e-4
SGD
Cosine2k
32 X 32
ResNet-32

Imagenet-1k LT
10.0
100
100
0.001
0.95
256
0.1
0.01
SGD
Cosine2.5k
224 X 224
ResNet-50

J.2. Computational Requirements
The experiments were done on Nvidia A5000 GPU(24 GB). While the fine-tuning was done on a single A5000, thepre-training was done using Pytorch data parallel on 4XA5000. The pre-training was done until no significant change inmetrics was observed and the fine-tuning was done for 10k steps of SGD with a validation step every 50 steps. A majoradvantage of SelMix over CSST is that the process of training a model optimized for a specific objective requires end to end
training which is computationally expensive(∼10 hrs on CIFAR datasets). Our finetuning method takes a fraction (∼1hr) ofwhat it requires in computing time compared to CSST.
16

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Table J.2. Table of Hyperparameters for Semi-Supervised datasets.

Parameter
Gain scaling (s)ωMin. Recλmax
ταBatch Size
Learning Rate(f )Learning Rate(g)Optimizer
Scheduler
Total SGD Steps
Resolution
Arch.

CIFAR-10(All distributions)
10.0
40
100
0.01
0.95
64
3e-4
3e-5
SGD
Cosine10k
32 X 32
WRN-28-2(a) Initial Stage (t = 0 SGD steps)

CIFAR-100(ρl = 10, ρu = 10)
10.0
20
100
0.01
0.95
64
3e-4
3e-5
SGD
Cosine10k
32 X 32
WRN-28-2

STL-10

Imagenet-100(ρl = ρu = 10)

2.0
20
100
0.01
0.95
64
3e-4
3e-5
SGD
Cosine10k
32 X 32
WRN-28-2

10.0
20
100
0.01
0.95
64
0.1
0.01
SGD
Cosine10k
224 X 224
WRN-28-2(b) Intermediate Stage (t = 5k SGD
steps)(c) Final Stage (t = 10k SGD steps)

Figure L.1. Evolution of gain matrix for mean recall optimized run for CIFAR-10 LT (ρl = ρu )K. Optimization of H-mean with Coverage Constraints for Semi-Supervised Learningα
We consider the objective of optimizing H-mean subject to the constraint that all classes must have a coverage ≥ K. For
CIFAR-10, when the unlabeled data distribution matches the labeled data distribution, uniform or inverted, SelMix is able tosatisfy the coverage constraints. A similar observation could be made for CIFAR-100, where the constraint is to have theminimum head and tail class coverage above 0.95
K . For STL-10, SelMix fails to satisfy the constraint because the validation
dataset is minimal (500 samples compared to 5000 in CIFAR). We want to convey here that as CSST is only able to optimize
for linear metrics like min. recall its performance is inferior on complex objectives like optimizing H-mean with constraints.
This shows the superiority of the proposed SelMix framework.

17

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Table J.3. The Expression of Non-Decomposable Objectives we consider in our paper.
MetricDefinition
1
K

Mean Recall (ψ AM )PQ

G-mean (ψ GM )

i∈[K]

P

H-mean (ψ HM )K

Min. Recall (ψ M R )minλ∈∆K−1

MR
Min of Head and Tail class recall (ψHT)

P Cii [h]j∈[K] Cij [h]

i∈[K]

P

P Cii [h]j∈[K] Cij [h]j∈[K] Cij [h]i∈[K]Cii [h]P k1i∈[K] λi

−1

P Cii [h]j∈[K] Cij [h]λH P
P Cii [h]min(λH ,λT )∈∆1 |H|i∈Hj∈[K] Cij [h]P
Cii [h]λT
P+ |T | i∈T
Cij [h]j∈[K]

αAM
Mean Recall s.t. per class coverage ≥ K(ψcons.
)Mean Recall s.t. minimum of headαAM(ψcons.(HT))
and tail class coverage ≥ K
αHM(ψcons.
)H-mean s.t. per class coverage ≥ K

H-mean s.t. minimum of headαHM(ψcons.(HT))
and tail class coverage ≥ K

1minλ∈RK
+ K

P

i∈[K]

1
min(λH ,λT )∈R2≥0 K

Kminλ∈RK+P

min(λH ,λT )∈R2≥0 K

PP
P Cii [h]+ j∈[K] λjj∈[K] Cij [h]Pαi∈[K] Cij [h] − KPCij [h]0.95
P Cii [h]+ λHi∈[K],j∈H |H| − KPj∈[K] Cij [h]Cij [h]0.95+λTi∈[K],j∈T |T | − K
i∈[K]

P

j∈[K] Cij [h]i∈[K]Cii [h]

P

P
i∈[K]

+λT

−1

j∈[K] Cij [h]Cii [h]

P

+

P

−1

i∈[K],j∈T

j∈[K] λj

+ λH

P

P

Cij [h]0.95|T | − K

αi∈[K] Cij [h] − Ki∈[K],j∈HCij [h]0.95|H| − K

Table K.1. Comparison of methods for optimization of H-mean with coverage constraints.
CIFAR-101ρl = 100, ρu = 100
N1 = 1500, M1 = 30

CIFAR-10
ρl = ρu = 100
N1 = 1500, M1 = 3000

CIFAR-10
ρl = 100, ρu = 1
N1 = 1500, M1 = 3000HM

Min Cov.

HM

Min Cov.

HM

Min Cov.

HM

Min H-T Cov.

STL-10ρl = 10,Pρu = NAN1 = 450, i Mi = 100k
HM

Min Cov.

DARP
CReST
DASO
ABC

78.1±0.965.8±1.578.1±0.1
79.6±0.3

0.065±3e-30.040±5e-30.072±3e-30.073±5e-381.9±0.5
81.0±0.7
83.5±0.3
84.6±0.5

0.070±3e-30.073±5e-30.083±1e-30.086±3e-383.5±0.884.6±0.2
88.4±0.588.2±0.7

0.067±3e-30.075±7e-40.089±1e-30.086±1e-348.7±1.3
48.3±0.2
49.1±0.750.1±1.2

0.0040±2e-30.0083±2e-40.0063±3e-40.0089±2e-474.0±0.567.1±1.1
76.6±1.174.7±1.5

0.058±2e-30.066±2e-30.083±3e-30.079±7e-3

CSST
FixMatch (LA)w/SelMix (Ours)

76.5±4.978.3±0.8
81.0±0.8

0.081±6e-30.064±1e-30.095±1e-376.9±0.276.7±0.1
85.1±0.1

0.093±3e-40.056±3e-30.095±1e-3

86.7±0.789.3±0.2
91.3±0.7

0.092±1e-30.086±1e-30.096±1e-347.7±0.845.5±2.1
53.8±0.5

0.0098±2e-40.0053±1e-40.0098±1e-478.3±2.674.6±1.779.1±1.2

0.081±6e-30.066±5e-30.088±1e-318

CIFAR-100
ρl = ρu = 10
N1 = 150, M1 = 300

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

L. Evolution of Gain Matrix with Training(a) Initial Stage (t = 0 SGD steps)(b) Intermediate Stage (t = 3k SGD
steps)(c) Final Stage (t = 10k SGD steps)

Figure L.2. Evolution of gain matrix for min. recall optimized run for CIFAR-10 LT (ρu = ρl ).

From the above collection of gain matrices, which are taken from different time steps of the training phase, we observe thatthe range (|max(G(t) ) − min(G(t) )|) of the gain matrix decreases with increase in SGD steps t, and settles on a negligible
value by the time training is finished. This could be attributed to the fact that as the training progresses, the marginal
improvement of the gain matrix decreases.
Another phenomenon we observe is that initially, during training, only a few mixups (particularly tail class ones) have adisproportionate amount of gain associated with them. A downstream consequence of this is that the sampling function
PSelMix prefers only a few (i, j) mixups. Whereas, as the training continues, it becomes more exploratory rather than greedily
exploiting the mixups that give the maximum gain at a particular timestep.

M. Detailed Analysis of SelMix Models
In this section, we analyze all these specific models on all other sets of metrics. We tabulate our results in Table M.1. It canbe observed that when the model is trained for the particular metric for the diagonal entries, it performs the best on it. Also,
we generally find that all models trained through SelMix reasonably perform on other metrics. This demonstrates that themodels produced are balanced and fair in general. As a rule of thumb, we would like the users to utilize models trained forconstrained objectives as they perform better than others cumulatively.

Table M.1. Values of all metric values for individually optimized runs for CIFAR-10 LT Semi-Supervised (ρl = ρu )Observed Metric
Optimized On
Mean Rec.
Min. Rec.
HM
GM
Mean Rec./Min. Cov.
HM/Min Cov.

Mean Rec.

Min. Rec.

HM

GM

Mean Rec./Min Cov.

HM/Min Cov.

85.4
84.2
85.3
85.3
85.7
85.1

77.6
79.1
77.7
77.5
75.9
76.2

85.0
84.1
85.1
85.1
84.7
84.8

85.1
84.2
85.2
85.3
84.8
84.9

85.4/0.089
84.2/0.091
85.3/0.091
85.3/0.091
85.7/0.095
85.1/0.095

85.0/0.089
84.1/0.091
85.1/0.091
85.1/0.091
84.7/0.095
84.8/0.095

N. Comparison between FixMatch and FixMatch (LA)We find that using logit-adjusted loss helps in training feature extractors, which perform much superior in comparison to
the vanilla FixMatch Algorithm (Table N.1). However, our method SelMix is able to improve both the FixMatch and the
FixMatch (LA) variant. We advise users to use the FixMatch (LA) algorithm for better results.
19

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Table N.1. Comparison of the FixMatch and FixMatch (LA) methods with SelMix.

MethodFixMatchw/ SelMix
FixMatch (LA)w/ SelMix

Mean
Recall
76.8
84.7
82.6
85.4

Min
Coverage
0.037
0.094
0.065
0.095

Min
Recall
36.7
78.8
63.6
79.1

Mean
Recall
76.8
82.7
82.6
84.1

O. Variants of Mixup
As SelMix is a distribution on which class samples i, j to be mixed up, it can be easily be combined with different variantsof mixup (Yun et al., 2019; Kim et al., 2020b). To demonstrate this, we replace the feature mixup that we perform in
SelMix, with CutMix and PuzzleMix. Table O.1 contains results for various combinations for optimizing the Mean Recall
and Min Recall across cases. We observe that SelMix can optimize the desired metric, even with CutMix and PuzzleMix.
However, the feature mixup we performed originally in SelMix works best in comparison to other variants. This establishes
the complementarity of SelMix with the different variants of Mixup like CutMix, PuzzleMix, etc., which re-design theprocedure of mixing up images.
Table O.1. Comparison of SelMix when applied to various Mixup variants.

MethodFixMatchw/ SelMix (CutMix)
w/ SelMix (PuzzleMix)
w/ SelMix (Features-Ours)

Mean
Recall
79.7±0.684.8±0.285.1±0.385.4±0.1

Min
Recall
55.9±1.975.3±0.175.2±0.1
79.1±0.1

O.1. Extention to Semi-Supervised Learning
We show the efficacy of SelMix for optimizing a wide variety of Non-Decomposable metrics across different distributions
for the labeled and unlabeled data. This includes cases where the underlying label distribution for labeled and unlabeled data
are matched, mismatched, and even unknown for the latter. Following a similar convention to long-tail (LT) classification
problems, we index the classes from 1...K where the distribution of labeled samples follows an exponentially decaying
function. Ni and Mi denotes the number of samples in the ith class of the labeled and unlabeled set respectively. The
underlying label distribution of these samples is characterized by their imbalance factor ρ. Corresponding to this imbalancefactor, the label distribution is defined using a factor γ as follows:1

Ni = N1 · γli−1 , Mi = M1 · γui−1 where γ = ρ− K−1
Since the labeled and unlabeled data need not have the same distribution in our experiments, their corresponding imbalancefactors shall be denoted by ρl and ρu , respectively. For CIFAR-10, we set N1 = 1500 with an imbalance factor ρl =N1
NK = 100. We consider three settings for the unlabeled data where the nature of the underlying label distribution is either
1matched (M1 = 3000, ρu = 100), uniform (M1 = 3000, ρu = 1) or inverted (M1 = 30, ρu = 100). For STL-10 we use
N1 = 450 with an imbalance ρl = 10. The underlying labels of STL-10 for the unlabeled set (100k images) is not knownρu = NA, Mi = NA.

Table O.2. Results for sampling policies for PMix (CIFAR-10 LT, semi-supervised) ρ = 100.

MethodUniform Policy
Greedy Policy
SelMix Policy

Mean
Recall
83.3
83.6
84.9

Min
Coverage
0.072
0.093
0.094
20

Min
Recall
70.5
78.2
79.1

Mean
Recall
83.3
81.8
84.1

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

Table O.3. Comparison on metric objectives for CIFAR-10 LT under ρl ̸= ρu assumption. Our experiments involve ρu = 100, ρl = 1
1(uniform) and ρu = 100, ρl = 100(inverted). SelMix achieves significant gains over other SSL-LT methods across all the metrics.
CIFAR-101, N1 = 1500, M1 = 30)(ρl = 100, ρu = 100

CIFAR-10(ρl = 100, ρu = 1, N1 = 1500, M1 = 3000)

Mean Rec.

Min Rec.

HM

GM

Mean Rec./Min Cov.

Mean Rec.

Min Rec.

HM

GM

Mean Rec./Min Cov.

DARP
CReST
CReST+DASO
ABC

79.7±0.871.3±0.972.8±0.879.2±0.280.8±0.460.7±2.440.3±345.2±2.564.5±1.8
65.1±0.878.1±0.965.8±1.568.4±1.3
78.1±0.1
79.6±0.3

78.9±0.968.6±1.270.6±1.1
78.6±0.880.7±0.679.7±0.8/0.065±2e-3
71.3±0.9/0.040±5e-372.8±0.8/0.047±3e-379.2±0.2/0.072±3e-380.8±0.4/0.073±5e-384.8±0.785.7±0.3
86.4±0.2
88.6±0.488.6±0.466.9±3.1
68.7±1.771.7±1.978.2±1.674.8±2.983.5±0.884.6±0.1485.6±0.2
88.4±0.588.2±0.785.2±0.785.1±0.1
86.1±0.1
88.5±0.488.6±0.3

84.8±0.7/0.067±3e-385.7±0.3/0.075±7e-4
86.4±0.2/0.078±1e-388.6±0.4/0.089±1e-388.6±0.4/0.086±4e-3

CSST
FixMatch (LA)w/SelMix (Ours)

77.5±1.579.4±0.781.3±0.572.1±0.2
61.1±1.274.3±1.276.5±4.978.3±0.8
81.0±0.876.8±5.2
78.7±1.1
81.1±0.577.5±1.5/0.091±3e-379.4±0.7/0.064±1e-381.7±0.8/0.091±3e-387.6±0.789.8±0.3
91.4±1.2

78.1±0.375.9±1.6
84.7±0.786.1±0.789.3±0.2
91.1±1.1

87.1±0.2
89.6±0.1
91.3±1.2

88.7±0.1/0.093±5e-489.8±0.3/0.086±1e-3
91.4±1.2/0.096±9e-4

Table O.4. Comparison across methods when label distribution ρu is unknown. We use the STL-10 dataset for comparison.
STL-10(ρl = 10, ρu = NA, N1 = 450,Pi Mi = 100k)

Mean Rec.

Min Rec.

HM

GM

DARP
CReST
DASO
ABC

76.5±0.370.1±0.3
78.1±0.577.5±0.454.7±1.948.2±2.255.8±3.755.4±6.7

74.0±0.567.1±1.1
76.6±1.174.7±1.575.3±0.467.8±1.177.2±0.276.3±0.9

Mean Rec./Min Cov.
76.5±0.3/0.058±2e-370.1±0.3/0.066±2e-3
78.1±0.5/0.083±3e-377.5±0.4/0.079±7e-3

CSST
FixMatch(LA)w/SelMix (Ours)

79.2±1.577.9±1.180.9±0.550.8±2.952.2±4.1
68.5±1.878.3±2.674.6±1.779.1±1.278.9±2.1
76.1±1.480.1±0.479.2±1.5/0.081±6e-377.9±1.1/0.066±5e-380.9±0.5/0.088±1e-3

Training Details. Our classifier h is composed of a feature extractor g : X → Rd followed by a linear softmax classification
layer f : Rd → ∆K−1 , as mentioned in Sec. 2. As our classifier, we use the Wide ResNet-28-2 (Zagoruyko & Komodakis,2016) pretrained using FixMatch (Sohn et al., 2020) with the cross-entropy loss replaced by the logit adjusted (LA) crossentropy loss (Menon et al., 2020). This replacement helps generate pseudo-labels debiased from the long-tail imbalance ofthe training set (Appendix N). This results in better consistency regularization, hence a better feature extractor g, especiallyin cases where there is a mismatch of label distribution of labeled and unlabeled data. We perform fine-tuning of the modelthrough SelMix (Alg. 1) using cosine learning rate and SGD optimizer, we freeze the batchnorm layers and fine-tune thefeature extractor with low learning rate. This is done to ensure that the mean feature statistics zk don’t change much during
the process, as per our theoretical results. The appendix mentions additional details and hyperparameter values in Table J.1.
Evaluation Setup. For evaluation, we compare the results of our work to the state-of-the-art empirical baselines of CReST,
CreST+ (Wei et al., 2021), DASO (Oh et al., 2022), DARP (Kim et al., 2020a) and ABC (Lee et al., 2021) in semi-supervised
long-tailed learning. We consider the public codebase of DASO (Oh et al., 2022) for all these baselines and report the resultscorresponding to the SotA base pre-training method of FixMatch + LA. We also compare with CSST (Rangwani et al., 2022),
which is a theoretically principled method by obtaining the implementation from authors. We compare the methods on two
broad sets of metric objectives: a) Unconstrained objectives which includes G-mean, H-mean, Mean (Arithmetic Mean),
and worst-case (Min.) Recall b) Constrained objectives include maximizing the recalls under coverage constraints. The
constraint for all classes is that coverage should be greater than 0.95
K . As followed in the literature (Narasimhan & Menon,2021) for CIFAR-100 due to its small size, instead of Min Recall/Coverage, we optimize the Min Head-Tail Recall/Min
Head-Tail coverage, respectively. The tail corresponds to the least frequent ten classes, and the head corresponds to the other90 classes. For a more detailed overview of the metric objectives and their definition, refer to Table J.3. We report mean andstd. deviation of results across 3 seeds.
O.2. Results on Matched Label Distributions
In this section, we report results for the typical case of ρl = ρu , i.e., matched unlabeled and labeled distributions of classlabels. We report the metrics for Mean, G-mean, H-mean, and worst-case (Min) recall for all baselines in Table O.5. For
reporting results for CSST and SelMix, we report the results after training them for the specified metric. We observe
significant improvement in the corresponding metric when FixMatch (LA) model is fine-tuned with the proposed SelMix
method in all cases. For the metric of Min Recall, a 5% improvement is observed for CIFAR-10, and a corresponding 9.8% improvement in Min HT Recall for CIFAR-100 over SotA methods which aim for optimizing accuracy. We also find21

SelMix: Selective Mixup Fine Tuning for Optimizing Non-Decomposable Metrics

a significant improvement over SotA in the H-mean of Recall for CIFAR-100, showing the reduction in the performancedisparity of the model between the head and tail classes. Further, even for the standard metric of mean recall (∼ accuracy),
SelMix achieves improved performance compared to baselines. We find that for optimizing the PSelMix , initially mixes up
samples from tail classes to increase performance on them and then gradually moves towards uniform mixups in the laterpart (Appendix L).
We now move towards focusing on the optimization of metrics while satisfying the coverage constraints (i.e., covi [h] ≥ 0.95
K ).
We first focus on optimizing the model’s mean recall with coverage constraint, as CSST supports it. However, as SelMix
is generic, it also supports optimizing metrics like H-mean with coverage, which we show in the Appendix K. In Table
O.5, we find that most heuristic SotA methods lead to sub-optimal min. coverage values, and only CSST and SelMix
approximately satisfy the coverage constraints (underlined). Further, SelMix produces better mean recall performance
than CSST, providing a better tradeoff in terms of performance and satisfiability of constraints. The models obtained after
improving on such constrained objectives often perform well across all metrics and lead to more balanced and fair models .
We find that this observation holds true even in the detailed analysis of SelMix models across metrics presented in Appendix
M.
Optimising constrained NDO: In our setup, metrics such as Minimum Recall and fairness metrics such as Mean Recall s.t.
0.95
per-class coverage ≥ 0.95
K and H-mean s.t. per-class coverage ≥ K observe the most significant gains in performance, for
CIFAR-10 SelMix and CSST are the only methods that satisfy the coverage constraint while optimising mean recall andH-mean. This is due to the inherent design of these methods capable of optimising such constrained Non-Decomposable
objectives and SelMix improves over CSST w.r.t the underlying objective with a significant margin. This is true for
CIFAR-100 too where we optimise for Mean Recall and H-mean subject to the constraint of the minimum of head class andtail class coverages being ≥ 0.95
K . Here too, other methods which are often designed w.r.t overall accuracy fail to satisy
the coverage constraints and SelMix that not only satisfies them but also has either competitive or superior Mean Recalland H-mean. SelMix shows the biggest performance gain in optimising for Min. Recall for CIFAR-10 and Min. of Headclass and Tail class recall for CIFAR-100. This is because when a certain class suffers in recall, the sampling function P t
dynamically adjusts to oversample from those classes from the labeled set, which in-turn increses its recall.
Table O.5. We compare the results for CIFAR-10 and CIFAR-100 when the labeled and unlabeled data distribution matches, this is theclassical imbalanced semi-supervised learning case. CIFAR-10 is kept at an imbalance ratio ρ = 100 while CIFAR-100 is kept at ρ = 10
CIFAR-10
Fixmatch + LA
w/ DARPw/ CReST
w/CReST+
w/DASO
w/ABC
FixMatch + w/CSST
w/SelMix (Ours)(ρl = ρu = 100, N1 = 1500, M1 = 3000)

CIFAR-100(ρl = ρu = 10, N1 = 150, M1 = 300)

Mean Rec.

Min Rec.

HM

GM

HM/Min Cov.

Mean Rec./Min Cov.

Mean Rec.

Min H-T Rec.

HM

GM

HM/Min H-T Cov.

Mean Rec./Min H-T Cov.

82.6±1.1
83.3±0.482.1±0.6
83.1±0.3
84.1±0.385.1±0.581.1±0.285.4±0.1

63.6±6.3
66.4±3.1
68.2±3.2
71.3±1.572.6±2.1
74.1±0.671.7±0.2
79.1±0.1

81.1±1.581.9±0.5
81.0±0.782.2±0.2
83.5±0.3
84.6±0.576.9±0.285.1±0.1

81.8±1.3
82.6±0.481.6±0.782.6±0.3
83.8±0.3
84.9±0.677.7±0.785.3±0.1

82.6±1.1/0.065±8e-3
83.3±0.4/0.070±3e-382.1±0.6/0.073±5e-383.1±0.3/0.076±2e-384.1±0.3/0.083±1e-385.1±0.5/0.086±3e-381.1±0.2/0.090±2e-484.9±0.2/0.094±3e-482.6±1.1/0.065±8e-3
83.3±0.4/0.070±3e-382.1±0.6/0.073±5e-383.1±0.3/0.076±2e-384.1±0.3/0.083±1e-385.1±0.5/0.086±3e-381.1±0.2/0.090±2e-485.7±0.2/0.095±1e-358.8±0.1
60.1±0.258.2±0.2
57.8±0.860.6±0.259.7±0.2
57.2±0.259.8±0.236.2±1.1
39.6±1.1
40.7±0.742.1±0.740.9±0.4
46.4±0.6
48.4±0.3
57.8±0.5

45.0±0.548.7±1.3
48.3±0.2
48.2±0.649.1±0.750.1±1.247.7±0.853.8±0.553.2±0.155.4±0.554.1±0.153.8±0.955.9±0.1
55.6±0.453.5±0.456.7±0.4

45.0±0.5/0.0055±2e-448.7±1.3/0.0040±2e-3
48.3±0.2/0.0083±2e-448.2±0.6/0.0088±1e-449.1±0.7/0.0063±3e-450.1±1.2/0.0089±1e-347.7±0.8/0.0096±4e-353.8±0.5/0.0098±5e-558.8±0.1/0.0055±2e-460.1±0.2/0.0040±2e-358.2±0.2/0.0083±2e-457.8±0.8/0.0088±1e-460.6±0.2/0.0063±3e-459.7±0.2/0.0089±1e-357.2±0.2/0.0096±4e-359.6±0.2 / 0.0097±1e-422