Selective Mixup Fine-Tuning for Optimizing Non-Decomposable Objectives
Authors: Shrinivas Ramasubramanian
Harsh Rangwani
Sho Takemori
Kunal Samanta
Yuhei Umeda
Venkatesh Babu Radhakrishnan
Venue: ICLR 2024 spotlight (2024)
Keywords: Non-Decomposable Objectives
Long-Tail Learning
Semi-Supervised Learning
Primary area: general machine learning (i.e., none of the above)
TL;DR: A selective feature mixup algorithm to optimise a Non-Decomposable objectives such as  for a classifier

Abstract: The rise in internet usage has led to the generation of massive amounts of data, resulting in the adoption of various supervised and semi-supervised machine learning algorithms, which can effectively utilize the colossal amount of data to train models. However, before deploying these models in the real world, these must be strictly evaluated on performance measures like worst-case recall and satisfy constraints such as fairness. We find that current state-of-the-art empirical techniques offer sub-optimal performance on these practical, non-decomposable performance objectives. On the other hand, the theoretical techniques necessitate training a new model from scratch for each performance objective. To bridge the gap, we propose SelMix, a selective mixup-based inexpensive fine-tuning technique for pre-trained models, to optimize for the desired objective. 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 comprehensively evaluate our technique against the existing empirical and theoretically principled methods on standard benchmark datasets for imbalanced classification. We find that proposed SelMix fine-tuning significantly improves the performance for various practical non-decomposable objectives across benchmarks.

Published as a conference paper at ICLR 2024
SELECTIVE MIXUP FINE-TUNING FOR OPTIMIZING NON-DECOMPOSABLE OBJECTIVES
Shrinivas Ramasubramanian Harsh Rangwani Sho Takemori Kunal Samanta", Yuhei Umeda', R. Venkatesh Babu² Fujitsu Research of India, Indian Institute of Science, Fujitsu Limited
ABSTRACT
The rise in internet usage has led to the generation of massive amounts of data, resulting in the adoption of various supervised and semi-supervised machine learn- ing algorithms, which can effectively utilize the colossal amount of data to train models. However, before deploying these models in the real world, these must be strictly evaluated on performance measures like worst-case recall and satisfy con- straints such as fairness. We find that current sate--of-the-aae empirical techniques offer sub-optimal performance on these practical, non-decomposable performance objectives. On the other hand, the theoretical techniques necessitate training a new model from scratch for each performance objective. To bridge the gap, we propose SelMix, selective mixup-based inexpensive fine-tuning technique for pre-trained models, to optimize for the desired objective. The core idea of our framework is to determine sampling distribution to perform mixup of features between samples from particular classes such that it optimizes the given objective. We comprehensively evaluate our technique against the existing empirical and theoretically principled methods standard benchmark datasets for imbalanced classification. We find that proposed SelMix fine-tuning significantly improves the performance for various practical non-decomposable objectives across benchmarks.
INTRODUCTION
The rise of deep networks has shown great promise by reaching near-perfect performance across computer vision tasks (He et al., 2022; Kolesnikov et al., 2020; Kirillov et al., 2023; Girdhar et al., 2023). has led to their widespread deployment for practical applications, some of which have critical consequences (Castelvecchi, 2020). Hence, these deployed models must perform robustly across the entire data distribution and not just the majority part. These failure cases are often overlooked when considering only accuracy as our primary performance metric. Therefore, more practical metrics like Recall H-Mean (Sun et al., 2006), Worst-Case (Min) Recall (Narasimhan & Menon, 2021; Mohri et al., 2019), etc., should be used for evaluation. However, optimizing these practical metrics directly for deep networks is challenging as they cannot be expressed as a simple average of a function of label and prediction pairs calculated for each sample (Narasimhan & Menon, 2021). Optimizing such metrics with constraints is termed formally as Non Decooppoope Objective Optimization.
In prior works, techniques exist to optimize such non-decomposable objectives, but their scope has mainly been restricted to linear models (Narasimhan et al., 2014; 2015a). Narasimhan & Menon (2021), recently developed consistent logit- adjusted loss functions for optimizing non-decomposable objectives for deep neural networks. After this work in supervised setup, Cost-Sensitive Seif-Training (CSST) (Rangwani et al., 2022) extends it to practical semi-supervised learning (SSL.) setup, where both unlabeled and labeled data are present. As these techniques optimize non-decomposable objectives like Min-Recall, the long-tailed (LT) imbalanced datasets serve as perfect benchmarks for these techniques. However, CSST pre- pre-training on long-tailed data leads to sub-optimal representations and hurts the mean recall of the models (Fig. 1). Further, these methods require re-training the model from scratch to optimize for each doomdccoepoabble objective, which decreases applicability. Practical methods based on empirical insights have been developed to improve the mean performance
denotes Equal Contribution. Code will be available here: Correspondence to shri ni vas ramasubr ramaan @ com, harshrg @ isc.ac. i..

---

Published as a conference paper at ICLR 2024
Figure 1: Overview of Results on CIFAR- 10 LT Seemissuperiised.. We evaluate the models from SotA Semi-supervised techniques of DASO (Oh et al., 2022), ABC (Lee et al., 2021), CSST (Rangwani ct al., 2022) and proposed SelMix on differ- ent non-dccomposable objectives. We find that SelMix produces the best performance for the con-decomposable metric and con- straints it is optimized for (blue). Further, SelMix is an inexpensive fine-tuning tech- nique compared to other expensive full pre- training- training-based based baselines.
H-Mean
Min. Recall
$1.8
.1.
82
00.66
0.676
Moan Recall
8,00
A084
$3.5
Min. Coverge
65.4
G-Mean
SelMix
CSST
ABC
DASO
Work Optinadd
of methods on long-tailed dlss--mbalanced datasets (DASO (Oh et al., 2022), ABC (Lee al., 2021), CoSSL. (Fan et al., 2022) etc.). These methods mainly generate debiased pseudo-labels for consistency regularization, leading better semi-supervised classifiers. Despite their impressive performance, these classifiers perform suboptimally for the non-decomposable objectives (Fig. 1).
In this paper, we develop SelMix, a technique that utilizes a pre-trained model for representations and optimizes it for improving the desired non-decom non-decomposable objective through fine-tuning. We fine-tune a pre-trained model that provides good representations with Selective Mixups (SelMix) between data across different classes. The core contribution of our work is to develop selective sampling distribution on class samples to selectively mixup, such that optimizes the given non non-decomposable objective (or metric) (Fig. 2). This SelMix distribution of mixup is updated periodically based on feedback from the validation set so that it steers the model in the direction of optimization of the desired metric. SelMix improves the decision boundaries of particular classes to optimize the objective, unlike standard Mixup (Zhang et al., 2018) that applies mixups uniformly across all class samples. Further, the SelMix framework can also optimize for non-linear objectives, addressing shortcoming of existing works (Rangwani et al., 2022; Narasimhan & Menon, 2021).
To evaluate the performance of SelMix, we perform experiments optimize several different non-decomposable objectives. These objectives span diverse categories of linear objectives (Min Recall, Mean Recall), non-linear objectives (Recall G-mean, Recall H-mean), and constrained objectives (Recall under Coverage Constraints). We find that the proposed SelMix fine-tuning strategy significantly improves the performance on the desired objective, outperforming both the empirical and theoretical ofate-of-thh-arr (SotA) methods in most cases (Fig. 1). In practical scenarios where the distribution of unlabeled data differs from the labeled data, we find that the adaptive design of SelMix with proposed logit-adjusted FixMatch (LA) leads to a significant 5% improvement over the state-of-the-an methods, demonstrating its robustness to data distribution. Further, our SSL framework extends easily to supervised learning and leads to improvement in desired metrics over the existing methods. We summarize our contributions below:
We evaluate existing theoretical frameworks (Rangwani al., 2022) and empirical methods (Oh et al., 2022; Wei et al., 2021b; Lee et al., 2021; Fan et al., 2022) on multiple practical non- decomposable metries. We find that empirical methods perform well on mean recall but poorly on other practical metrics (Fig. 1) and vice-versa for the theoretical method.
We propose SelMix, mixup-based fine-tuning technique that uses selective mixup over classes to mix up samples to optimize the desired non-decomposable metric objective. (Fig. 2).
We evaluate SelMix in various supervised and semi-supervised settings, including ones where the unlabeled label distribution differs from that of labeled data. We observe that SelMix with the proposed FixMatch (LA) pre- traitrannng significantly outperforms existing SotA methods (Sec. 5).
2 RELATED WORKS
Semi-Superrised Learning in Class Imbalanced Setting. Semi-Supervised Learning are algorithms that effectively utilizes unlabeled data and the limited labeled data present. A line of work has focused on using consistency regularization and pseudo-label-bee to improve performance (e.g., FixMatch (Sohn et al., 2020), MixMatch (Berthelot al., 2019b),
self- trainini on unlabeled data
2

---

Published as a conference paper at ICLR 2024
y2
Time step
c Metric Function
911
Fenmyy SelMix distribution
Confusion ustris
G: Gain Matrix
* Juverse temperature parameter
y/3
(a) Feature Representation
(b) After Mixup
(c) After SelMix
U2) ~ P
Saitix
((Ca) + =b(Ck-1))
O
C
P
1--11 Sobia
softmax(sc!!
We demonstrate the effect of the variants of mixup on feature representations (a). With Mixup, the feature representation gets equal contribution all directions of other classes (b). Unlike this, in SelMix (c), certain class mixups are selected timestep such that they optimize the desired metric. Below is an overview of how the SelMix distribution is obtained at timestep t.
Figure 2:
ReMixMatch (Berthelot et al., 2019a), ). However, when naively applied, these methods lead to biased pseudo-labels in class-imbalanced (and longetailed) settings. Various recent (Fan al., 2022; Oh et al., 2022) methods have been developed that mitigate pseudo-label bias towards the majority classes. These include an auxiliary classifier trained on balanced data (ABC (Lee al., 2021)), I)), semantic similarity- -ased classifier to de-bias pseudo-label (DASO (Oh et al., 2022)), oversampling minority pseudo-label samples (CReST (Wei et al., 2021a)). Despite their impressive accuracy, these algorithms compromise performance measures focusing on the minority classes.
Von-Decomposible Metric Optimization. Despite their impressive accuracy, there still seems to be wide gap between the performance of majority and minority classes, especially for semi-supervised algorithms. For such cases, suitable metrics like worst-case recall across classes (Mohri et al., 2019) and F-measure (Eban et al., 2017) provide much better view of the model performance. However, these metrics cannot be expressed as a sum of performance on each sample; hence, they are non- decomposable. Several approaches have been developed to optimize the non-decomposable metrics of interest (Kar et al., 2016; Narasimhan et al., 2014; 201 5a; Sanyal et al., 2018; Narasimhan & Menon, 2021). In the recent work of CSST (Rangwani al., 2022), cost-sensitive learning with logit adjustment has been generalized to a semi-supervised learning setting for deep neural networks. However, these approaches excessively focus on optimizing desired non-decomposable metries, leading to a drop in the model's average performance (mean recall).
Variants of MixUp. After MixUp, several variants of mixup have been proposed in literature like CutMix (Yun et al., 2019), PuzzleMix (Kim et al., 2020b), TransMix (Chen et al., 2022), SaliencyMix (Uddin et al., 2020), AutoMix (Zhu et al., 2020) etc. However, all these methods have focused on creating mixed-up samples, whereas in our work SelMix, we concentrate samples from which classes (y, v') are mixed up to improve the desired metric. Hence, complementary to others and can be combined with them. We also provide further discussion in App. N.
PROBLEM SETUP
Notation: For two matrices A, E Ruxn with the same size, we define an inner product (A, B) as (A, B) Tr AB = m Ey=1 Aig For general function f Rmxn - R for matrix variable X mx the directional derivative w.r.t V E mx is defined as:
Vvf(X) lim f(X + - 7-00
(1)
which implies f(X we depict the gradient (derivative) matrix w.nt X E RR as Øf E mx with each entry given as: ax -x,; For comprehensive list of variable definitions used, please refer to Table. A.
for small n. In case the function is differentiable.
(ax )3g
af
Let's examine the classification problem involving K classes, where the data points de- noted as x are drawn from the instance space X. and the labels belong to the set y de- fined as [K]. In this classification task, define classifier F as function that maps
3

---

Published as a conference paper at ICLR 2024
data points to labels. This function is constructed using neural network-based scor- ing function h, which consists of two parts: a feature extractor g that maps instances
to a feature space R and linear layer parameterized by weights W =R<* The classification decision is made by
selecting the label that corresponds to
Table I: Objectives defined by confusion matrix entries.
the highest score in the output vector: F(x) [r]] ((x)). The output of this scoring function h((x) in R&K is ex- pressed as h(x))= W g(xr), in terms of network parameters. We assume access to samples from the data distribution D for training and evaluation. We denote the prior distribution over labels as x. where π ( i) for i = 1, 1,..., K. Now, let's introduce the concept of the confusion matrix, denoted as C(a.). which is a key tool for assessing the performance of a classifier, defined as Cig [h] = Es,y y [y = i, argmaxx h(æ)) = :)]_ For brevity, we introduce the confusion matrix in terms of scoring function h. The confusion matrix characterizes how well the classifier assigns instances to their correct classes. An objective function vú is termed "decomposable" if it can be expressed
Objective
Definition
(gAM)) Meun Recall
Ciyl x EieKK Eyc|K] Cy [b]
Min. Recall
MiDACOR- EnEITT As DJEjK] Ciy [
(1lllM) H-mean
[iE(K))
Ererao Giyth 11
minAcak Eie[K] Exe[K] Cigli] ΣSE[K] As (Evejy) CG((M] -T) -1)
(VoOL) ). Mean Recall s.L.
per class coverage 2 r
function T : y x 3' R. Specifically, v6 is decomposable if it can be written as Ez.y, (P(x,, y)]. If such a function & doesn't I exist, the objective is termed "non-decomposable" In this context, we introduce the nondeecompooable objective v6, represented as tb AK*K + R, which is a function on the set of confusion matrices Cl/), and expressed as (C(()))) Our primary aim is to maximize this objective (C((h) which can be used to express various practical objectives found in prior research works (Cotter et al., 2019; Narasimban et al., 2022), examples of which are provided in Table and their real-world usage is described below.
In real-world datasets, a common challenge arises from the inherent long-tailed and imbalanced nature of the distribution of data. In such scenarios, relying solely on accuracy can lead to a deceptive assessment of the classifier. This is because model may excel in accurately classifying majority classes but fall short when dealing with minority ones. To address this issue effectively, holistic evaluation metrics like H-mean (Kennedy et al., 2010). G-mean (Wang & Yao, 2012; Lee et al., 2021), and Minimum (worst-case) recall (Narasimhan & Menon, 2021) prove to be more suitable. These metrics offer a comprehensive perspective, highlighting performance disparities between majority and minority classes that accuracy might overlook. Specifically, the G-mean of recall can be expressed in
CL *
terms of the confusion matrix (C'h)) as: (C(()) (IIεE(K) Eje[K] Chy
For the minimum
recall (N,,)), we use the continuous relaxation as used by (Narasimhan & Menon, 2021). By writing the overall objective as min-max optimization over À AK-1, have max MR (C[b))
max; minxeA=-1 ΣiE[K] A; Eye(x Cs](M] Fairness is another area where such complex objectives
are beneficial. For example, prior works (Cotter et al., 2019; Goh et al., 2016) on fairness consider optimizing the mean recall while constraining the predictive coverage (cov:/C[h]] = Σ, Cze) that is the proportion of class predictions on test data given as maxı K >; rec; [/] s.t. cov,[A] > & Vi E [K]. Optimization of the above-constrained objectives possible by using the Lagrange Multipliers (A E RR as done in Sec. of Narasimhan Menon (2021). By expressing this above expression in terms of C'hh] and through linear approximation, the constrained objective V/oons. Veons. (CTA)) can be considered as: max,, W.M, (C(h)) = max, min 20 R ΣjElK] EjElK C.l
C..lk)
ESe[K] >, [ESETR] Ciy(h) xx The X for calculating the value of elecus. (CTA)) and MR (CTh)), is periodically updated using exponentiated or projected gradient descent as done in (Narasimhan & Menon, 2021). We summarize (C[[h) for all non-decomposable objectives we consider in this paper in Table 1. Unlike existing frameworks (Narasimhan & Menon, 2021; rangwani et al., 2022) in addition to objectives that are linear functions of C(h). we can also optimize for non-linear functions like (G-mean and H-mean) for neural networks.
4

---

Published as a conference paper at ICLR 2024
4 SELECTIVE MIXUP FOR OPTIMIZING NON-DECOMPOSABLE OBJECTIVES
This section introduces the proposed SelMix (Selective Mixup) procedure for optimizing desired non-decomposable objective v. We a) first introduce a notion of selective (i.j) mixup (Zhang et al., 2018) between samples of class i and j. b) we then define the change (i.e., Gain) in desired objective produced due (i.j) mixup, e) prefer (i.J) mixups which lead large Gain in objective v, we introduce distribution PselMix from which we sample (i.j) to form training batches d) we then conclude by introducing a tractable approximation of change (i.e., gain) in metric for the network WT g. e) we summarize the SelMix procedure by providing the Algorithm for training. We provide theoretical results for the optimality of the SelMix procedure in Sec. 4.1, We elucidate each part of SelMix in detail below and provide an overview of the proposed algorithm in Fig. 2.
Feature Mixup. In this work, we aim to optimize non-decomposable objectives with a framework utilizing mixup (Zhang et al., 2018). Mixup minimizes the risk for a linear combination of samples and labels (i.e. (x. y) and (x', y²)) to achieve better generalization. Manifold Mixup (Verma et al., 2019) extends this idea to have mixups in feature space, which we use in work. However, in vanilla mixup, the samples for mixing up are chosen randomly over the classes. This may be useful in the case of accuracy but can be sub-optimal when we aim optimize for specific non-decomposable objectives (Table K.1) that may require a specific selection of classes in the mixup. Hence, this work focuses on selective mixups between classes and uses them to optimize non-decomposable objectives. Consider a K class classification dataset 1) containing sample pairs (z, y). For convenience of notation, we denote the subset of instances with a particular label y = as D; {= (x. y) D. y =
i}. For the unlabelled part of dataset D containing x, we generate these subsets D; {x' E D i = argmax, h(x);} based on the pseudo label y = argmax, h(x);; from the model h. In addition to these training data, we also assume access to D containing (z, y). Following semi- remi-supervised mixup framework (Fan et al., 2022) in our work, the mixup between a labeled and pseudo labeled pair of samples (i.e. (r, y) from D and x' from Î), the features g(x) and g(x') are mixed up, while the label is kept y. The mixup loss for our model with feature extractor g followed by a linear layer with weights W defined as:
(mixap(g(>) ((x)). y: W) = Lscc (Bg(x)) + (1 8)9(2")).
Here B Uimmn 1]. Smain [0, 1] and LScE is the softmax cross entropy loss. We define (i, j) mixups for classes i and] j to be the mixup of samples ~ D; and x' Dj and minimization of the corresponding Lmixup via SGD For analyzing the effect of (i, mixups on the model, we use the loss incurred by mixing the centroids of class samples (z, and 2;), which are defined as =s = D [x(x)] for each class k. This representative of the expected loss due to (i, mixup can be expressed as:
(t.)) Lmixup (zi, Zj, W) Vi,j E [K] [K].
Directional vectors using mixup loss. We define 8² directions as the derivative of the expected
mixup loss for each of the (i, mixup respectively w.r.t the weights W as V., = -0 /aW.
(t.j)
These directions correspond to the small change in weights W upon the minimization of ((.)) by
stochastic gradient descent. Now we want to calculate the change in the non-decomposabl objective s along these directions Va.j. Assuming the existence of directional derivatives in the span of K²
directions and fixed feature extractor g, we can write the following using Taylor Expansion (Eq. (1)):
(C[WT, g (V. = ((C(WT g)) + v., ((CWWT T g)) + O1?IIVV,,)))
(3)
In Eq. (3), since 17 a small scalar, ([, is negligible. Hence the second term in Eq. (3)
denotes the major change in objective s due minimization of the loss due to (i,5) mixup ((3)) via
SGD. We define this as Gain (Gty) or increase in desired objective eb for the (i, mixup:
ac
(t,f) E [K]
Gzy = Vv, (CTW g)), where ViJ
aw
Using this, we define the gain matrix as G [Gr,]l<s,f<< corresponding to each of the (1, mixups. We now define a general direction V, which is induced by mixing up samples from classes (i. j) respectively, according to Par (1. distribution defined over [K] x [K]. The expected weight change induced by this distribution can be given as (due linearity of derivatives): V = Ein PM (i, V..
5

---

Published as a conference paper at ICLR 2024
The change in objective induced by the (i, distribution can be similarly approximated using the Taylor Expansion for the direction V= - Pa VV.s
(C[ g + ny g)) (C[[ g)) + + PM (1, g)) N, (CC
0 (5)
To maximize change in objective (LHS), maximize the second term (RHS), the first term is constant and the third is negligible for a small step 1). On substituting Vv,, (C g]) -Gy. the second term corresponds to [[[]] - Eis GigPMiaa (i, which is expectation of gain over PMia- Thus, maximization of the objective is equivalent finding optimal PMiz to maximize expected gain E[G]. In practice to maximize objective 4h, we will first sample labels to mixup (V1)9) from optimal PMiz (described below), then will pick ø1, 22 from Dy, Dy, uniformly to form batch for training.
Selective Mixup Sampling Distribution. In our work, we introduce a novel sampling distribution PseMix for practically optimizing the gain in objective defined follows:
PS (i.j) )) = softmax(sS))
(6)
We aim to maximize E[G]. One strategy could be to only mixup samples from classes (i. j) respec- tively, corresponding to max., G.y or equivalently s - oc. However, this doesn't work in practice as we do steps of SGD based on PseMix the linear approximation in Eq. (3) becomes invalid, and later the approximation in Thm. 4.1 (See Table K.1 for empirical evidence). Hence, we select the PMix to be the scaled softmax of the gain matrix our strategy, with > 0 given PselMix. The proposed PsemMix is the distribution which is an intermediate strategy between the random exploratory uniform (s = 0) and greedy (s o0) strategies which serves good sampling function for maximizing gain. We provide theoretical results regarding the optimality of the proposed PSetMix in Sec. 4.1.
Estimation of Gain Matrix. This notion of gain, albeit accurate, is not practically tractable since v is not differentiable w.r.t W in general, as the definition of City [h] = Eg.gyD/ [1 (y = i, argmax, h(x); = f)] uses non-smooth indicator function (Sec. C.2). To proceed further with this limitation, introduce a reformulation of C' by defining the 7th row Ci(h] of the confusion matrix in terms of the 1t row [i[h] of the unconstrained matrix C(h] E Rx* as C₁[h] गे (oftmaxx(C[[]] This reformulation of the confusion matrix C' by design satisfies the necessary constraints, given as Σ, Ca, [h] = π; and Σx, Ci =1 where 0 Ctylh] < 1. We can now calculate the same objective (C(WTTg) 9)) in terms of Ć. The entries of gain matrix (G) with reformulation Ö can be analogously defined (Eq. (4)) in terms of Č:
a.mix
Gij VVv gl),, where Vi₃- = OW
vi.jj E [K] x [K].
The exact computation of Gij would be given as ( Viy) in case ac this is not defined despite introducing the c--forulltiion due to the non con-differentiabiliy of Ō w.r. W. However, with formmullation under some mild assumptions, given in Theorem (4.1). we can approximate Gi (first RHS term). We refer readers to Theorem C.3 for more mathematically precise statement. Further, we want to convey one advantage despite the proposed reformulation: we do not require the actual computation of Ć' for gain calculation in Eq. (8) (first term). As all the terms of pv( which we require, can be computed analytically in terms of C, which makes this operation aCix inexpensive. We provide the ae(C) for all va in Appendix Sec. D.
SW was defined. However,
acix
Theorem 4.1. Assume that [| |l is sufficiently small. Then, the gain for the (i. mixup (Gtz) can be approximated using the following expression:
Gij = Σ On((C)
((Vi)) 2x) +0 A.. aCi
(((,,))+llvvll (0
(8)
where 2/ = Exn is the mean of the features of the validation samples belonging to class k. used to characterize (i.j) mixups (Eq. (2)). The error term e(C,, W) does not depend on Vsg, and under reasonable assumptions we can regard this term small (we refer readers Sec. C.3).

---

Published as a conference paper at ICLR 2024
In the above theorem formulation, approximate the change in the entries of the unconstrained confusion matrix C,,[(h] [h]] with the change in logits for the classifier W 9 with weight W along the direction Vij as (Vi)) Zgg- The most non-trivial assumption of the theorem is that for each k, the random vector Vij ((x)) has small variance, where
Dral Intuitively, if g is sufficiently good feature extractor, then feature vectors g(x) (x ~ D2a are distributed near its mean, hence its linear projections ViJ g(ar) has small variance. Therefore, it is natural assumption if g is sufficiently good. Moreover, this approximation works well in practice, as demonstrated empirically in Sec. 5.
Algorithm for training through Se We provide an algorithm for training neural network through SelMix. Our algorithm shares high-level framework as used by (Narasimhan et al., 2015b; 2022). The idea is to perform training ey- cles, in which one estimates the gain matrix G through a validation set (D(val) and uses it to train the neural network for a few Stochastic Gradient Descent (SGD) steps. As our expressions of gain are based on lin- car classifier, we primarily fine-tune the linear classifier. The backbone is fine-tuned at lower learning rate 1y for slightly better empirical re- sults (Sec. 5). Formally, we introduce the time- dependent notations for gain (G)()), the classi-
Algorithm 1 Training through SelMix
For 1 to T do Compute P = softmax(=+ using Thm. 4.1 for n SGD steps
Y1. Y2 ((t) X, ~ (((DD))) ). X2 ~ ((Dyg)
fier 1) the SelMix distribution p(() SelMix weight-
A A = SGD Updateeh (1) Criup. (X1, X2!)
direction change (() due to the minimization of CTY.. As SelMix is a fine-tuning procedure,
end for return (T)
we assume a feature extractor g and its linear classification layer, pre-trained with an algorithm like FixMatch, to be provided as input. Another important step in our algorithm is the update of the pseudo-labels of the unlaheled set, (+)) The pseudo-labels are updated with predictions from the h(0), The algorithm is summarized in Alg. 1 and detailed in App. Alg. 2, and an overview provided in Fig. 2. In our practical implementation, we mask out entries of the gain matrix with negative gain before performing the softmax operation (Eq. (6)). We further compare the SelMix framework to others (Rangwani et al., 2022; Narasimhan & Menon, 2021), in the App. E.
4.1 THEORETICAL ANALYSIS OF SELMIX
Convergence Analysis. For each iteration = 1,..., T, Algorithm updates the parameter W of our network h- = W g as follows: (a) It selects a mixup pair (i,j) from the distribution P!t))
SelMix (b) and updates the parameter W by ((+1) W + m7. V1),, where (1()) /////V/// //VV("))) Here, we consider the normalized directional vector (1() instead of Vi We denote by TE,-1 [-] the conditional expectation conditioned on randomness with respect to mixup pairs up to time step L - 1. In the convergence analysis, we make the following assumptions for the analysis. We assume that the objective v as function of W is concave, differentiable and the gradient is 7-Lipschitz, where y > 0 (Wright, 2015; Narasimhan et al., 2022). We assume that there exists a constant e > 0 independent @v(W())
of satisfying the following condition E,-1 [+0]]]
SW II. that is, (1()) vector has sufficient alignment with the gradient vector to maximize the objective & in expectation. Here,
Be(Wi))
> cll
SW
we regard ve as a function of W in (y(((())
aw Moreover, we assume that in the optimization process, [| does not diverge, i.e., we assume that for any > 1, we have || [|[(()] || < R with constant R > O. In practice, this can be satisfied by adding (e-reuularization of W to the optimization. We define constant Ra > 0 Rg = ||| R, where W = argmaxw (W). Using the above mild assumptions, we have the following result (we provide a proof in Sec. C.1):
with an appropriate choice Theorem 4.2. For any > 1, we have (((") EE [((W(()]] < -(--
of the learning rate πe.
Theorem 4.2 states that the proposed Algorithm 1 leads convergence to the optimal metric value
(WW') E
[ is reasonable directional vector for optimization of vb.
Validity of the mixup sampling distribution. By formalizing the optimization process as an online learning problem (a similar setting to that of Hedge (Freund & Schapire, 1997)), we state that our sampling method is valid. For conciseness, we only provide an informal statement here and refer to Sec. C.4 for more precise formulation. We suppose that mixup pair (i.j) is sampled by
7

---

Published as a conference paper at ICLR 2024
Table 2: Comparison of metric values with various Semi-supervised Long-Tailen methods on CIFAR- 10/100 LT under Pt = Pa setup. The best results are indicated in bold.
CHFAR-1B
100,
1505, M2 (000)
CHEAR-100
U/
FL
=
10, Ng
190, M2 300)
Meen Rec.
Rec.
HM
Mean Roc /Min Cow.
Roc.
Rec.
HM
Mean /Min
DARP (KiP ot 2000a;
83.3as
66-4cn
61.9pr
K2.6ara
KS 20000000
50.5e11
48.2g11
S5.4g4
16. B.0000g
CReST (Weel et di, 203183
82.3
68.2.z2
S18
51.0
52. 11.073 con
58.2
<0.74m
48.3 48.3
54.1am
58.2
CluST+ (Wec
202166
83.las
T1.3
62.2pr
62.6
53. be 2t1007660
$7.8
42.3a57
48.2
$3.8
57.8csal 4:00
ALec er 2001)
85.3
345
54
55. 11.000000.000
59. T2.
38.4as
M0.aa
55.0
59: Tax 10889
cassi dean et at. 2022))
81.0u.0
300
M133
52 Bux 20077
57.9
537a.
57 Mux
DASO (ON 2022)
84.3.m
726-2:
$3.5
83.
60.6-
40.
49.1.c7
55.9
60.6va00
20029)
FiMMushLL) (Oun)
76.7
58.5.a0
45.5
38....00.0055
63.4
29
88.3g1
88.7 N0.066
59,8
57.8g
538
56.7
59.6 A1LI99
a distribution p(O) on [K] x [K] for 1 = ,,...,T. We call a sequence of sampling distributions
P = (p()) a policy, and call a policy P non-adaptive if p(t) is the same for all S t S T. For example, if p(t) is the uniform distribution for any t, then P is non-adaptive. Then, in Sec. C.4, we shall prove the following statement regarding the optimality of SeiMi:
Theorem 4.3 (Informal). The SelMix policy P seiMi is approximately better than any non non-adaptive policy P na (P)- in terms of the average gain T is sufficiently large.
5 EXPERIMENTS
We demonstrate the effectiveness of SelMix in optimizing various Non-Decomposath objectives across different labeled and unlabeled data distributions. Following conventions for Long-Tail (LT) classification, N; and M, represent the number of samples in the ht class for the labeled and unlabeled sets, respectively. The label distribution is exponential in nature, and the imbalance factor p characterizes it. We define it as Pt = NN/NK K. Ps. = M In our experiments, we consider the LT semi-supervised version for CIFAR-10, 10, 100, Imagenet- 100, and STL-10 datasets as done by (Fan et al., 2022; Oh et al., 2022; Kim et al., 2020a; Lee et al., 2021; Rangwani et al., 2022). For the experiments on the long-tailed supervised dataset, we consider the Long-Tailes Tailed versions of CIFAR-10, 100, and ImageNet-lk. The parameters for the datasets are available in Tab. G.I.
Our classifier comprises a feature extractor g : X' + RRd and a linear layer with weight W (see Sec. 3). In semi-supervised learning, we use the pre-trained Wide ResNet-28- 2 (Zagoruyko & Komodakis, 2016) with FixMatch (Sohn et al., 2020), replacing the loss function with the logit adjusted (LA) cross-entropy loss (Menon et al., 2020) for debiased pseudo-labels. Fine-tuning with SelMix (Alg. 1) includes cosine learning rate and SGD optimizer. In supervised learning, we pre-train models with MiSLAS on ResNett33 for CIFAR- 10, CIFAR- and ResNet-50 for ImageNet-Ik. 1k. We freeze batch norm layers and fine-tune the feature extractor with a low learning rate to maintain stable mean feature statisties 2g, as per our theoretical findings. Further details and hyperparameterss are provided in appendix Table G.I.
Training Details:
Evaluation Setup. We evaluate our work against baselines CReST, CReST+ (Wei et al., 202 DASO (Oh et al., 2022), DARP (Kim et al., 2020a), and ABC (Lee et al., 2021) in semi-supervised long-tailed learning. We assess the methods based on two sets of metric objectives: a) Unconstrained objectives, including G-mean, H-mean, Mean (Arithmetic Mean), and worst-case (Min.) Recall. b) Constrained objectives. involving maximizing recalls under coverage constraints. The constraint requires coverage 2 0.95 for all classes. For CIFAR-100, we optimize Min Head-Tail Recall/Min Head-Tail coverage instead of Min Recall/Coerraee due to its small size. The tail corresponds to the least frequent 10 classes, and the head the rest 90 classes. For detailed metric objectives and definitions, refer to Table G.3. We present results as mean and standard deviation across three seeds.
K
Matched Label Distributions. We report results for Pt Pa. signifying matched labeled and unlabeled class label distributions. SelMix outperforms FixMatch (LA), achieving 5% Min Recall boost for CIFAR- 10 and a 9.8% improvement in Min HT Recall for CIFAR- 100. SelMix also excels in mean recall, akin to accuracy. Its strategy starts with tail class enhancement, transitioning to uniform mixups (App. J). We delve into optimizing coverage-constrained objectives (cov;[h) [h] > 0.95 Initially, we emphasize mean recall with coverage constraints, supported by CSST. However, SelMix, a versatile method, accommodates objectives like H-mean with coverage (App. 1). Table 2 reveals that most SotA methods miss minimum coverage values, except CSST and SelMix. SelMix outperforms CSST in mean recall while meeting constraints, as confirmed in our detailed analysis (App. K.I).
Unknown Label Distributions. We address the practical scenario where the labeled data's 's label distribution differs from that of the unlabeled data (7) # 7y). We assess two cases: a) Mismatched Distributions. We evaluate various techniques CIFAR-10 with two mismatched unlabeled dis-
8

---

Published as a conference paper at ICLR 2024
H: H-Mean
H-Mean
Min.
Min flacel
Min. Recal
Mean Rocal
Recal
odd
Min Conoaag
Coverage
G.Maan
G-Mean
10,
A= 100
SelMic (Durs)
CSST
ABC
DASO
FirMatch
Waak
Figure 3: Comparison of metric for semi-supervised CIFAR- 10 LT under pt # and STL-10
Pr. = NA assumption. For CIFAR-IO-LT (semi-supervised) involve Pt 100, Pv 1, (uniform) and Pt = 100, Pa 100 (inverted). SelMix achieves significant gains over other baselines.
Table 3: Comparison results in supervised case for CIFAR-I0, 10, LT (p 100). We use the pre-trained model of MiSLAS (Zhong et al., 2021) in stage- and fine-tune using SelMix.
CIFAR-10
[n no- 196)
CIFAR-100
(A 10)
Moen Roc
Min Boa.
1IM
GM
Mon
Con
Mean Rec.
Min H-- Roc.
IM
GM
Monn Roo Miln Cao
Misas (Staes E1 G2hong stol., 20213 wi Staes (Ching ui., 2023)
72 Peor
45.6
70.3as
39.5.aa
0.0ccc
50.5 Svaaaa000000 daa
71.5
81.0 6-
00.07 pooc
40.0
30.
41.3
42.3-s
Table 4: Results for scaling SelMix to large datasets ImageNet-Ik LT and ImageNet100 LT.
ImageNatt18-LT (u- 10)
InsigeNetl-LIT
Mean Rec.
Min Rec.
Mean Rec. Cov.
Mean Rec.
Min HTT Rec.
Mean Rec./Mnn Cov.
CSST (Rerpwani al., 2032)
1
12.1
MISI AS (Stgs (Zhong et 2001)
Piomunch (LA))
69.9
99.900002
Suaee
52.4
52.40000058
SelMix
73.5
73.100.09
$2.8
$2.50,0009
tributions: balanced (Pu. 1) and inverse ( (o0)). ). SelMix consistently outperforms all methods, especially in min. Recall and
objectives (Fig. 3). b) Real World Unknown Label Distributions. STL-10 provides an additional 100k samples with an unknown label distribution, emulating scenarios where data is abundant but labels are scarce. SelMix, with no distributional assumptions, outperforms SotA methods like CSST and CRest (which assume matched distribution) in min-recall by substantial 12.7% margin (Fig. 3). Detailed results can be found in App. H.
Results on SelMix in Supervised Learning. To further demonstrate the generality of SelMix, we test it for optimizing non- decomposable objectives via fine-tuning recent SotA work MisLaS (Zhong et al., 2021) for supervised learning. In comparison to fine-tuning stage-2 of MisLaS. SelMix-based fine-tuming achieves better performance across all objectives as in Table 3, for both CIFAR 10.
Analysis of SelMix. We demonstrate SelMix's scalability on large-scale datasets like Imagenet- Ik LT and Imagenet- 100 LT and its ability to improve the objective compared to the baseline Tab. 4, with minimal additional compute cost (~ 2 min.) (see Table L..),, through Thm. C.8, we show the advantage of SelMix over uniform random sampling and the limitations of purely greedy policy (ref. Table K. for empirical evidence). We observe improved feature extractor learning by comparing a trainable backbone to a frozen one (Tab. K.4). Additionally, our work can be combined with other mixup variants like (Kim et al., 2020b; Yun et al., 2019), leading to performance enhancements (Tab. K.5) demonstrating the diverse applicability for the proposed SelMix method. We refer readers the Appendix for details on complexity (Sec. B, L), analysis (Sec. K), and limitations (Sec. M).
6 CONCLUSION AND DISCUSSION
We study the optimization of practical but complex metrics like the G-mean and H-mean of Recalls, along with objectives with fairness constraints in the case of neural networks. We find that SotA techniques achieve sub-optimal performance in terms of these practical metrics, notably on worst-case recall. These metrics and constraints are non-decomposable objectives, for which we propose Selec- tive Mixup (SelMix) based fine-tuning algorithm for optimizing them. The algorithm selects samples from particular classes to a mixup to improve tractable approximation of the non-decomposable objective. Our method, SelMix, can improve on the majority of objectives in comparison to both theoretical and empirical SotA methods, bridging the gap between theory and practice. We expect the SelMix fine-tuning technique to be used for improving existing models by improving on worst-case and fairness metrics inexpensively.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors would like thank Yasunari Hikima for providing useful comments on preliminary version of this paper. We thank the KIAC Centre for its financial support. Harsh Rangwani is supported by the Prime Minister's Research Fellowship program.
REFERENCES
Peter Auer, Nicolo Cesa-Bianch, Yoav Freund, and Robert E. Schapire. The non-stochastic multi- armed bandit problem. SIAM Journal of Computing, 32(1): 2002. 20
David Berthelot, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel. Remixmatch: Semi-supervised learning with distribution alignment and augmentation anchoring. CoRR, abs/191 11119991999979 1.09785, 2019 9a.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raffel. Mixmatch: A holistic approach to semi-supervised learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019b. 2
Davide Castelvecchi. Is facial recognition too biased to be let loose? Nature, 58777834)347-355, 2020.
Jie-Neng Chen, Shuyang Sun, Ju He, Philip HS Torr, Alan Yuille, and Song Bai. Transmix: Attend to mix for vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12135-12144, 2022. 3
Andrew Cotter, Heinrich Jiang, Maya R Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. J. Mach. Learn. Res., 20(172)) 2019.
Elad Eban, Mariano Schain, Alan Mackey, Ariel Gordon, Ryan Rifkin, and Gal Elidan. Scalable learning of non-decomposable objectives. Artificial intelligence and statistics, pp. 832-840. PMLR, 2017. 3
Yue Fan, Dengxin Dai, Anna Kukleva, and Bernt Schicle. Cossl: Co-lcarning of representation and classifier for imbalanced semi-supervised learning. The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2022. 2, 5, 8, 23
Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application boosting. Journal of computer and system sciences, 55(1):119-139, 1997. 20, 21
Rohit Girdhar, Alaaeldin El-Nouby, Zhuang Liu, Mannat Singh, Kalyan Vasudev Alwala, Armand Joulin, and Ishan Misra. Imagebind: One embedding space to bind them all. arXiv preprint arXiv:2305.05666 2023.
Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints, Advances in Neural Information Processing Systems, 29, 2016. 4
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16000-16009, 2022.
Inwoo Hwang, Sangiun Lee, Yunhyeok Kwak, Seong Joon Oh, Damien Teney, Jin-Hwa Kim, and Byoung-Tak Zhang. Selecmix: Debiased learning by contradicting pair sampling. Advances in Neural Information Processing Systems, 35:14345-14335 2022. 30
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, pp. 1625-1634, 2016.
10

---

Published as a conference paper at ICLR 2024
Kenneth Kennedy, Brian Mac Namee, and Sarah Jane Delany. Learning without default: A study of one-class classification and 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. 4
Jachyung Kim, Youngbum Hur. Sejun Park, Eunho Yang, Sung Ju Hwang. and Jinwoo Shin. Distri- bution aligning refinery of pseudo-label for imbalanced semi-supervised learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020a. Curran Associates Inc. ISBN 9781713829546. 8
Jang-Hyun Kim, Wonho Choo, and Hyun Oh Song. Puzzle mix: statistics for optimal mixup. In International Conference Machine Learning, pp. 5275-5285.
Exploiting saliency and local
PMLR, 2020b. 3, 9, 29
Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yes Lo, et al. Segment anything. arXiv preprint arXiv:2304.02644, 2023.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In European conference on computer vision, pp. pp. 491-507. Springer, 2020.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009. Technical report, University of Toronto. 25
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020. 20
Hyuck Lee, Seungjae Shin, and Heeyoung Kim. Abe: Auxiliary balanced classifier for class- imbalanced semi-supervised learning. Advances in Neural Information Processing Systems, 34: 7082-7094, 2021. 2, 3, 4,
Jing Li, Yuangang Pan, Yueming Lyu, Yinghua Yao, Yulei Sui, and Ivor W Tsang. Earning extra performance from restrictive feedbacks. IEEE Transactions Pattern Analysis and Machine Intelligence, 2023. 30
Aditya Krishna 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, 2020. 8
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- lional Conference on Machine Learning, pp. 461154625... PMLR, 2019. 1,3
Harikrishna Narasimhan and Aditya K Menon. Training over peremtaameter models with non- decomposable objectives. Advances in Neural Information Processing Systems, 34, 2021. 1, 1, 3, 7.32
Harikrishna Narasimhan, Rohit Vaish, and Shivani Agarwal. On the statistical consistency of plug- in classifiers for non-decomposable performance measures. Advances neural information processing systems, 27, 2014. 1,
Harikrishna Narasimhan, Purushottam Kar, and Prateek Jain, Optimizing non-decomposable perfor- mance measures: A tale of two classes. In International Conference Machine Learning, pp. 199-208. PMLR, 2015a. 1,
Harikrishna Narasimhan, Harish Ramaswamy, Aadirupa Saha, and Shivani Agarwal. Consistent multiclass algorithms for complex performance measures. In International Conference on Machine Learning, pp. 2398-2407. PMLR, 2015b. 7
Harikrishna Narasimhan, Harish G Ramaswamy, Shiv Kumar Tavker, Drona Khurana, Pranecth Netrapalli, and Shivani Agarwal. Consistent multiclass algorithms for complex metrics and constraints. arXiv preprint arXiv:2210009695, 2022. 4,7

---

Published as a conference paper at ICLR 2024
Youngtaek Oh, Dong-Jin Jin Kim, and In So Kweon. Daso: Distribution-avern semantics-oriented pseudo-label for imbalanced superviie learning. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, pp. 9786-9796, 2022. 2, 3. 2.
SaanennTTan, Ragja Palakkadavath, Thanh Nguyen- Tang, Sunil Gupta, and Svetha Venkatesh. Improving domain generalization with interpolation robustness. In NeurlPS 2022 Workshop Distribution Shifts:
Connecting Methods and Applications, 2022. 30
Harsh Rangwani, Shrinivas Ramasubramanian Sho Takemori. Kato Takashi, Yuhei Umeda, and Venkatesh Babu Radhakrishnan. Cost-sensitive self celf-training for optimizing non decomposable metrics. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. 1, 2, 3, 4, 7, 8, 9, 14, 15, 23, 24, 28
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-255 2015. 25
Amartya Sanyal, Pawan Kumar, Purushottam Kar, Sanjay Chawla, and Fabrizio Sebastiani. Opti- mizing non-decomposable measures with deep networks. Machine Learning, 107(8):597-11220 2018. 3
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Advances in Neural Information Processing Systems, 33:596-608, 2020. 2, 8
Yanmin Sun, Mohamed S Kamel, and Yang Wang. Boosting for learning multiple classes with imbalanced class distribution. In Sixth international conference on data mining (ICDM'06 pp. 592-602. IEBE, 2006.
Damien Teney, Jindong Wang, and Ehsan Abbasnejad. Selective mixup helps with distribution shifts, but not (only) because of mixup. arXiv preprini N.XVv:2305.16117. 2023. 30
AFM Uddin, Mst Monira, Wheemyung Shin, TaeChoong Chung, Sung-Ho Bae, et al. Salien- cymix: A saliency guided data augmentation strategy for better regularization. arXiv preprint arXiv:2006.01791, 2020. 3
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez-Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6438-6447 PMLR, 2019. 5
Shuo Wang and Xin Yao. Multiclass imbalance problems: Analysis and potential solutions. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), (2(4):1119-113) 2012.
Chen Wei, Kihyuk Sohn, Clayton Mellina, Alan Yuille, and Fan Yang. Crest: A ceaaa-nnba self-training framework for imbalanced supe-supe learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10857-10866, June 2021a.
Chen Wei, Kihyuk Sohn, Clayton Mellina, Alan Yuille, and Fan Yang. Crest: A class-rebalancing self-training framework for imbalanced semi-supervised learning. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 10857-10866, 2021b. 2, 2
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1):949-980, 2014. 30
Stephen J Wright. Coordinate descent algorithms. Mathematical programming, 151(1):3-344 2015. 7, 15, 16
Huaxiu Yao, Yu Wang. Sai Li, Linjun Zhang, Weixin Liang, James Zou, and Chelsea Finn. Improving out-of-distribution robustness via selective augmentation. In International Conference on Machine Learning, pp. 25407-25437. PMLR, 2022. 30
12

---

Published as a conference paper at ICLR 2024
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceedings of the IEEE/CVF international conference computer vision, pp. 6023-6032, 2019. 3, 9, 9, 29
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. CoRR, abs/ 146, 2016.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018. 2, 23
L Zhang, Z Deng, K. Kawaguchi, A Ghorbani, and J Zou. How does mixup help with robustness and generalization? In International Conference on Learning Representations, 2021. 23, 30
Zhisheng Zhong, Jiequan Cui, Shu Liu, and Jiaya Jia. Improving calibration for long-tailed recogni- tion. In IEEE Conference Computer Vision and Patlern Recognition (CVPR), pp. 16489-16498, 2021. 9, 23
Jianchao Zhu, Liangliang Shi, Junchi Yan, and Hongyuan Zha. Automix: Mixup networks for sample interpolation cooperative barycenter learning. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Purt X 16, pp. 633-649. Springer, 2020.
13

---

Published as a conference paper at ICLR 2024
APPENDIX
A NOTATION
We provide summary of notations in Table A.I.
Table A.1: Table of Notations used in Paper.
K
Number of classes
= [K]
Label space
Instance
Label
Learning rate
Instance space
Feature space a neural network based scoring function Confusion matrix for the classifier h the n 1-dimensional probability simplex a function defined on the set of confusion matrices (+b(C(h)) is the metric of h)
h: X + R
[h)
A n-1 R"
3 A K2 RK*K) R
prior for class i E [K] a feature extractor (backbone)
9: X + Rdd
f: RRd AK-1
the final classifier such that h argmax, fa o
W E B 2
the weight of the final layer the centroid of features of class samples given as De [g(x)]
Emixup (I', 33 96: W)
the loss for mixup between labeled sample (Ia, yi) and unlabeled sample Ty
Cmix (9))
the expected loss due to (i.j) mixup
G ViJ
gain upon performing (f, mixup
the directional vector (matrix) defined by the (i,j) mixup
(A, B) (where A, B E mm))
Tr AB
V VAX (where A e R)
the directional derivative of function x with the directional vector (matrix) A
the inverse temperature parameter for softmax
Č
Unconstrained extension for confusion matrix
D;
Subset of data with label i Subset of data with pseudo-label a distribution on [K] x [K]
D
P (P
a policy sequence of distributions Pt)
G(P)
the expected average gain of
NE
the number of samples in the k-th labeled class
the number of samples in the k-th unlabeled class the class imbalanced factor of the labeled dataset (maxişijgK N./Ng) the class imbalanced factor 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 matrix
Pt
Pu
H
||A||E
B COMPUTATIONAL COMPLEXITY
We discuss the computational complexity SelMix and that of an existing method (Rangwani al., 2022) for non-decomposable metric optimization in terms of the class number K. We note that to the best our knowledge, CSST (Rangwani et al., 2022) the only existing method for non-decomposable metric optimization in the SSL setting.
14

---

Published as a conference paper at ICLR 2024
Proposition B.1. The following statements hold:
1. In each iteration in Algorithm 1, computational complexity for P SelMis given as O(K))
2. In each iteration of CSST (Rangwani al., 2022), it needs procedure that takes ((K3) 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 size of the validation dataset.
Proof. Computational complexity for the confusion matrix given as O(K3) since there are K2 entries and for each entry, evaluating (x)) takes ((K) time for each validation data æ. For each 1 < h < K, computational complexity for 2 is O(K). We compute (softmax(2z) & which takes ((K²) time. The (m, ()-h entry of the matrix Paj is given as -1/5m (бu - softmax, (O), where S m v d, 1 S 1 S K, and Ç = 32, + (1 8)2j E IR4, Therefore, once we compute {softmax (softmax(++) K. computational complexity for {vghsissK is O(K"). For each S 1 K, we put 11 Σ av(c(t))
aCn zg. Then computational complexity for {uiliisk is O(K?). Since G. - EE (T) un is a sum of K dot products of d-dimensional vectors, once we compute (w/h. computational complexity for {Gl hSsigk is O(K*). Thus, computational complexity for p SelMix is given OKK3).
In each iteration CSST needs computation a confusion matrix at validation dataset. Since there K2 entries and for each entry, (xx) takes O O(K) K)) time for each validation data x; computational complexity for the confusion matrix is given as O(K3). Thus, we have our assertion.
C ADDITIONAL THEORETICAL RESULTS AND PROOFS OMITTED IN THE PAPER
C.I CONVERGENCE ANALYSIS
We provide convergence analysis of Algorithm For each iteration 1,..., T, Algorithm updates parameter W follows:
1. It selects a mixup pair (i.j) from the distribution P!0 SelMix
2. and updates parameter W by ((++1) ( + nJe (0) where (1) V.J /
Here, we consider the normalized directional vector ( instead of (t) and || || denotes the Euclidean norm. We denote by E,-1 [-] the conditional expectation conditioned on randomness with respect to mixup pairs up to time step 1.
Assumption C.1. The function &i (as a function of W) is concave, diffcrentiable, the gradient ow W'll where > 0. There exists constant > 0
du
is 7-Lipschitz, i.e., || Be independent satisfying
8v ow < W|
ay
(W((
E_1 [
>
(WO()
where (w((()))- (w((())
aW that is, (10) vector has sufficient alignment with the gradient. More- over, we make the following technical assumption. We assume that in the optimization process, [| does not diverge, i.e., we assume that for any 2 1, we have
[ || R
with constant R O. In practice, this be satisfied by adding l eerrgularizzation of W to the optimization. We define a constant Ro > 0 as Rs = || + R, where W = argmax w (W). We note that similar boundedness condition using level set is assumed by (Wright, 2015).
Theorem C.2. Under the above assumptions and notations, we have the following result. For any ( 1, we have
Rx
sup (W) - E (o(W())] < W
2(t-1)
15

---

Published as a conference paper at ICLR 2024
with appropriate choice of the learning rate ne-
Proof. By the Taylor's theorem, for each iteration t, there exists 8 E [0. 1] such that (WW+1)) = ( + (g) V(,, where & W + srj V(1), We decompose n Vi)(E) V(0)
as (V)(E) Ve)(W()) V( + nH VV(W10) -V(0.
First, provide lower bound of the first term. Since Veh Lipschitz, we have V ( < > W Mp- Thus, by the Cauchy-Schwardh we have 7/2 (V)(E)
((((O))) ((() 2 -yyh. Next, we consider the second term. By the assumption on the co-
sine similarity (9), we have
Ve(W(o) E--1 [ 2 on [b(W()))
where e is a constant independent of t. Here we note that when taking the expectation E,-1 P. can regard W()) as non-random variable. Thus, we have
(W(()))) E (w(()) + no Ve(E). ((0)
E
((W()) mm en [[V)
By letting 7/2 2 E (
[[]] we that
2 a) [IVe(w()))) (wW(+))) E [(omm)) + 47
E
We define Φi supw (W) E (W()))) By the above argument, we have
e² 47 E [Ive(w()))
6 S 0:
(10)
Then, we can prove the statement by a similar argument to Theorem I in (Wright, 2015) as follows. Let W* argmarw By the concavity of sb and the definition of Ro, we have
((W") - ((W())) & (V - w = ())
Therefore, we have
a. S R
By this inequality and (10), we have
Φ 01+1 2 Ao?
where A = o² 4yng
Thus, noting that 01+1 Φi holds by (10), we have
Φ: de+l
Φ1- Φ++1
A.
Φ++1
Φ1
010++1
Therefore, it follows that
1 1
> (1-
1)A (1-1)A
Φt
Φ1
This completes the proof.
C.2 A FORMAL STATEMENT OF THEOREM 4.1 AND REMARKS ON NON-DIFFERENTIABILIY
We provide more formal statement of Theorem 4.1 (Theorem C.3) and provide its proof.
Theorem C.3. For matrix A E Raxm, we denote by ||A]| the Frobenius norm of A. We fix the iteration of the gradient descent and assume that the weight W takes the value W(O) and C takes the value (1))
16

---

Published as a conference paper at ICLR 2024
We assume that the following inequality holds all le E [K] and E [K] uniformly W E No. where No is an open neighbourhood of W
Ex [softmax| (WT g(x)))] softmax; (Ca))
We also assume that on No. C can be regarded as smooth function of W and the Frobenius norm of the Hessian is bounded on No- Furthermore, we assume that the following small variance assumplion with & > 0 for all k:
K
Σ
Uee Vv
[(WT g((x))m) SE.
1711
Then if |/WW || is sufficiently small, there exist a positive constant > 0 depending only on K with c = O(poly(p))))))) and a positive constant è' >> 0 such that the following inequality holds:
K
bbb
Oup ac (++))+c(IIAW))
Gij
Σ
(AW)
2 S
aCk
k=
Here AW = V/J and Ck is a column vector such that the k-th row of Ò is given as Ck and we consider Jacobi matrices at C (()) and the corresponding value of C.
We provide some remarks.
Independence of the choices of Č. Although the matrix C is not uniquely determined since the softmax function is not one-to-one, the approximation (the first term of the RHS of (8) is unique as the derivative of all these are unique. We explain this more in detail. In the approximation ag ac We note that gradient of the softmax function formula, only need jacobian 0v/0C JC 3C
Sa ( - ( (f), where can also be written as a function of the softmax function (i.e., a5m (E softmax;(() for & E EK L, m S K). Therefore, the first term of the RHS of eq (8) is uniquely determined even is not uniquely determined.
Non-smoothness of the indicator functions. In Theorem C.3, we assume that C and C as smooth functions W, however strictly speaking this assumption does not hold since the indicator functions are not differentiable. Thus, in the definition of Gij. we used surrogate functions of the indictor functions. In the following, we provide more detailed explanation. In Eq. (4), we define the gain Gūj by directional derivative of (C)) with respect to weight W. However, strictly speaking, since the definition of the confusion matrix involves the indicator function, (CC) is not differentiable function of W. Moreover, even if gradients are defined, they vanish because of the definition of the indicator function. In the assumption of Theorem C.3 (a formal version of Theorem 4.1), we assume C is a smooth function of W and it implies C' is a differentiable function of W. This assumption can be satisfied if replace the indicator function by surrogate functions of the indicator functions in the definition of the confusion matrix C. More precisely, we replace the definition of Cit [7] T T. [1(((==) = j)} by n. EgEEp [s, (f)))). Here h(x) argmax; fx(x)) as before, P. is the class conditional distribution P(zly = i) and sy is surrogate function of p + 1 (argmax, P. = j) satisfying 0 < 8y 1 for any 1 S < K. A and Σø= (p) 1 for any p E AK-1- To compute Gij. can directly use the definition of Eq. (4) 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 Ò and the approximation formula Theorem 4.1 (Theorem C.3). An advantage of introducing Ö and the approximation formula is that the RHS of the approximation formula Σx. axCC) ((Mi)) =x)
aCe;
does not depend on the choice of the surrogate function if we use formulas provided in Sec. D with the original -ifieefffrent definition of C (error terms such as in Theorem C.3 do depend on the surrogate function). Since the optimal choice of the surrogate function is unknown, this gives reliable approximation.
C.3 PROOF OF THEOREM C.3
Proof. In this proof, to simplify notation, we denote softmax(2) by d(2) for E R In this proof, fix the iteration of the gradient descent and assume that the weight W takes the value ( and Č
17

---

Published as a conference paper at ICLR 2024
takes the value ((O) We assume in open neighborhood of W have smooth correspondence W C. and that if the value of W changes from Wo Wo AW, then C changes from Co to T. AČ. To prove the theorem, we introduce the following three lemmas. We note that by the assumption of the theorem and Lemma C.5, the assumption (13) of Lemma C.6 can be satisfied with
f (=+ E).
where e" > O is constant depending only on K with c" = (ppoly(K) (K)). Then by Lemma C.6, there exist constants 61 c1 ()) and C = (2))) depending on only K with cı, 02 = O(poly (K) such that the following inequality holds for all k:
aC
(ACx - (AW) 2x)
cIE c2(1IAč211 + ((W)) 2x 2x1
(11)
oCk C.
Then, have the following:
Oab
Obb (AW) 24
Orb 0C
K
Oib 8C
AC
AC
Σ
(AW) 2R
ac
aOk
8C 0C
dC 00
k=1
k=1
Ob
8C
Ob ac
ACx Σ
(AW) z6
ac
80k
8C 0Ck
K
Σ
ac
(ACx - (AW) 21)
aC
|F
1=1 aCk
Here, by fixing an order on [K] x [K], we regard
0y BC and AČ as a -i-dimensional row vector, K² x KK--marrxx, and -dmdeennio column vector, respectively. Moreover, we consider Jacobi
ac' ac
matrices at C ((U), Then, the assertion of the theorem from this inequality, (11), Lemma C.4. O
Lemma C.4. Under assumptions and notations in the proof of Theorem C.3, there exists constant
c > 0 such that
Oub
Aō < c|AWI
Gis
ac
C-
Proof. By the assumption of the mapping W + C and the Taylor's theorem, there exists C)
such that
ae
AC
AW
S <allAWI..
(12)
ow
W-
F
By definition of Gij. we have the following:
Oy Gig
Oy
8% AČ ac
Ač
AW
ac
aw
Ou ac
AW
ac AW
ac
0b IAWI2
c1
ac
Here we consider Jacobi matrices at W = Wo and corresponding values. The last inequality follows from the fact that the matrix norm || ||| is sub-multiplicative and Eq. (12).
n
Lemma C.5. Under assumptions and notations in the proof of Theorem C.3, there exist positive constant e = c(K) depending only on K with e = O(poly(K)) (K) such that:
K
[T g(xx))] (W 2x)1 < Σ v ((WTg(Zx))))) VI
for any 1 S k.l S K.
18

---

Published as a conference paper at ICLR 2024
Proof. This can be proved by applying the Taylor's theorem to or. We fix k, and apply the Taylor's theorem to the function Ç + (5) at W 2* = W [g(xx)] Then there exists &o E R such that
doi of
(E - T xx) + 1 - - -T Tx HH(E - W zx),
0i(E) = o:( zx) +
2
E-WTT
where HR delta), it is easy to see that there exists constant c/ depending only on I and K such that || < di and c/ O(poly(K)) By letting { = W g(xx) in the above equation and taking the expectation of the both sides, we obtain the assertion of the lemma with c = 1/2 maxigik] 4.
0 mz
By noting that do
(1) (m) (5) (here 6tm is the Kronecker's
x
E=Eo
35m
Lemma C.6. Under assumptions and notations in the proof of Theorem C.3, we assume there exists & > such that the following inequality holds for all lc and 1 for any W an open neighhorhood of (( and corresponding C:
(o( -i))) S.1. S
(13)
Furthermore, we assume that (AAW) 2 is sufficiently small for all k. Then there exist constants G1 = (K) and C2 (2) depending on only K with c1, C2 Oppoly (K)) such that
ac
(Acx-(WW) 2x) F
Sai + C2 + ((AW) z6 11.)
OCk 01=
Here, ÜR (resp. ACr)) is a column vector such that the k-th row vector of Ò (resp. Δ is given as CR (resp. AC&). Moreover, when defining Jacobi matrices, we regard C' as a K22 -veeor and consider a K2 K Jacobi matrix o0e 6. al C* = =
((0)
Proof. Since (13) holds all W in an open neighborhood of W(O) and corresponding Č we apply the Taylor's theorem to the function & + (IEE at & = (W(")) and & = ()()) Then by (13) and the same argument in the proof of Lemma C.5, we have
do a
doi
A
pkk
AC Sel+G((AAN + I
E=
0g
c= 2003
where μı (W( 2k. Apk = (AW) zk. Noting that (00) )m is given as SmIo)(E) (om)(()))((((()))))) (E)o (13) and the assumption that | ||r is sufficiently small, see that there exists constant e o2 > 0 depending only on K with ci. ds = O(poly(K)) such that the following inequality holds:
0a D
(Anx
s cGs + +6 11A)21
(14)
((0(0)
Next, consider entries of the K²-vector
ac 802 -
(ACx ApR).. Here as previously men-
tioned by fixing an order on [K] x [K], we regard ac ač,
as a K2 x K -mmatixx For (ks, 1) E [K] [K], (ACx Apus) is given as
by the definition of the mapping Č + C, (k, entry of ac 80s
(= (ACx Aμи).. By (14), we see that there exist constants of di depending only on K and c² 0/ O(poly((K) (K)) such that
T 05
ac
AC. - (AW) 2x
)
< scfes + ((AW) (x
aCk -
F
Since constants c', c/ may depend on (ks, 1) by taking e = maX(k.1) of and C2 = max(1,) cy we have the assertion of the lemma.
n
19

---

Published as a conference paper at ICLR 2024
C.4 VALIDITY OF THE MIXUP SAMPLING DISTRIBUTION
In this section, Motivated by Algorithm 1, we consider the following online learning problem and prove validity of our method. For each time step 1 = 1,..., T, an agent selects pairs (i(0), ())()) E [K] x [K], where random variables ((0)) follows a distribution PD()) on [K] x [K]] We call a sequence of distributions (P()))= a policy. For (i. E [K] x [K] and 1 S S T, we assume that random variable G is defined. We regard G.) the gain in the metric when performing
(i,j) j-miuup iteration in Algorithm We assume that G/y) is random variable due randomness of the validation dataset, 11, X2, and the policy. Furthermore, we assume that when selecting (i(t), ((0),, the agent observes random variables G for (i.j) [K] [K] but cannot observe the true gain defined by
(P) of a policy P (p()))= defined as ((0)tes} where (f()) follows the distribution (P() and the expectation taken with respect to the randomness of the policy, validation dataset, X1, X2. This problem setting is similar to that of Hedge (Freund & Schapire, 1997) (i.e., online convex optimization). 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 gains before performing an action. We note that even in this setting, methods such as argmax with respect to G.yy may not perform well due to randomness of ( and errors in the approximation (Refer Sec. 5 for evidence).
[ tj
The average gain G (TT((P
a (P) = + ((()
We call policy P = (P( non-adaptive (or stationary) if p(t) is the same for all t= I,.... T, i.e, there exists a distribution p(o) on [K] x [K] such that p(1) = pp()) for all L = 1,... T. A typical example of non-adaptive policies is the uniform mixup, i.e., p(t) is the uniform distribution
on [K] x [K]. Another example is p(t) = )(p00) for fixed (i(0), ((0)) E [K] x [K] (i.c.,
the agent performs the fixed (i(0), (()) ) in each iteration). Similarly to Hedge (Freund & Schapire, 1997) and EXP3 (Auer et al., 2002), we define Paaai = (P(t)
(PiMMii) T by
((t) SaMMi =
((sssjk)))) where is the inverse temperature parameter. The following theorem states that P SelMix is better than any non non-ad adaptive policy in terms of the average expected
softmax ((s Σ G.T7)
gain if is large:
Theorem C.7. We assume that G! is normalized so that |G S 1. Then, for any non-adaptive ij
policy p()) (P(O)) TT we have (T)) (P (PeeMMis 2 log K
+
2 C
(T) (P())))
all
Proof of Theorem C.7. This can be proved by standard argument of the proof of the mirror descent method (see e.g. (Lattimore & Szepesvári, 2020), chapter 28).
Denote by A C R the probability simplex of dimension - Let (ip, jo) E K x 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(U) (TO)s. where ma is the one-hot vector A defined as (To)as = if (i.j) (io. and 0 otherwise for 1 < j < K. Let F be the negative entropy function, i.c. F(p)
Σ 1i Piy log For E A and G R K*K we define (p, G) Ex PtyGiy. Then, SalMix defined above is given as the solution of the following:
K
it is easy to see that (()) pl!))
pd (t) argmin - sp, (()) + D(p. "-1))
(15)
Here denotes the KL-divergence and we define p(o) = (1/K2) Iijjsk = argmin F(p).
Since the optimization problem (15) is a convex optimization problem, by the first order optimality condition, we have
(To )1)(((0)) 1
(( - DT.u. ((1) - D(p()), (tp(0)p(t-1))) -(t--11}}
20

---

Published as a conference paper at ICLR 2024
By summing the both sides and taking expectation, we have
T
TG T (p!()) -7 (P SelMix)
1 S 8
D(Fu.D!") D(
Σ 1=1
D(p 10001)10111))
1 ((
Here the second inequality follows from the non-negativity of the KL-divergence. Since pl)) argmin, F()), by the first-order optimality condition, we have D(TO. I F(TT) ())
Noting that F(TO) S O, we have the following
TG m
(P(0) TTO")) PelMix) S -F()(0))
log K
8
This completes the proof.
C.5 A VARIANT OF THEOREM C.7
In the case when SelMix defined similarly to Hedge (Freund Schapire, 1997), i.e., P(1) softmax((s Et=1 )1s) then by the standard analysis, can prove the following.
SelMix
Theorem C.8. We assume that G normalized that | < 1. Then, with an appropriate
choice of the parameter 8, for any non-adaptive policy p(0) = (P(O)) YT we have ((e)) 2 K / 2 (T)) (P!))..
(P SelMis)
First we introduce the following lemma, which is due to (Freund & Schapire, 1997). Although, one can prove the following result by a standard argument, we provide proof for the sake of completeness.
Lemma C.9 (c.f. (Freund Schapire, 1997)). We assume that G [0, for all t and 1 S i,j S
K. For (i,j)= E [K]
X [K], we define Sr = - [G For policy P (PoT. we define
Sp
Dd -=1
E
(0) Ge Then, we have the following inequality:
2 log K +
max [[]]]]]]
3ij S (exp(s) - 1)3 PaciMix
Proof. This lemma can be proved by a standard argument, but for the sake of completeness, we provide proof. We put A = [K] x [K], ar = (2(*), (())) and in the proof we simply denote PeeMMi by P. For a E A and 1 S t < T + 1, we define wa,t as follows. We define Wa,1 1/K2 for all
a E and Wo,t+1 = Wa.t exp(sG!)). We also define W, W, EaEEA Wa,t. Then, the distribution P. given as the probability (Wa.s/ /Wt) A by definition. Noting that exp(sx) S + (exp(s) 1)x for x E [0, 1], we have the following inequality:
W
Σ
Wa.t+1
Σ aEA
Wa,t exp(sG(())
aEAA
Wa (1 + exp(s 1)G(
nE.4
Thus, we have
W Σ (1 + exp(s +xpp(1 1)
a
= W (1 (1+ +1+ (exp(s) - 1),p, G(t)
where Ep, [t] denotes the expectation with respect to By repeatedly apply the inequality above, we obtain:
Wr+1 < II (1 + (exp(s) - 1)Ep, [c..] ))
t=1
21

---

Published as a conference paper at ICLR 2024
Let A be any pair. By this inequality and Wr+1 2 Wa,T+1 R- exp(s Et= )o the following:
have
T
T
exp(s
S III
1
(exp(s)
1)lEp, c(t
K2
t=1
t=1
By taking log of both sides and log(1 x)
S v;
have
T Σ
T
log K +
G <
log (I+ (exp(s) 1)EP, [G
1=1
1=1
T
< (exp(s) -1)
Σ Bp,
Gas
G(()
By taking the expectation with respect to the randomness of G. we obtain the following:
-2 log K + sS. < (exp(s) - 1)Sp.
Since a E [K] x [K] is arbitrary, we have the assertion of the lemma.
We can prove Theorem C.7 by Lemma C.9 as follows:
Proof of Theorem C.7. Let (i",j*) be the best fixed Mixup pair hindsight, i.e. (i",5") argmax argmax (L.))[[K)((]] Sij- Since any non-adaptive (or stationary) policy is no better than ((- (+), to prove the theorem, is enough prove the following:
S. S Sp + 2 K.
(16)
Here in this proof, we simply denote SoIMix by P. To prove (16), we define the pseudo regret Rt by Rr Se Sp. Then by Lemma C.9, have
Rr < (exp(s) - - S) + 2og K
exp(s)
We put = loog( + a)) with > 0. Then we have
Rr (a log(1 3))3 2 log K
a
We note that the following inequality holds for a 0:
logg11 + a)
1
7
Then follows that:
2log K
log K
R1 S uu.
< aT +
5
a
Here the second inequality follows from 3, < T. We take a = 2/ log K
Then we have
Ry I 2/Tlog K. Thus, we have the assertion of the theorem.
D UNCONSTRAINED DERIVATIVES OF METRIC
For any general metric (C(h)) the derivative w.r.t the unconstrained confusion matrix Chh) is ex- pressible purely in terms of the entries of the confusion matrix. This is because C(h] = softmax (C(h) The derivative using the chain rule is expressed follows,
(V()))
8Cu [h]
Σ k
(17)
[h1
@Ciy
22

---

Published as a conference paper at ICLR 2024
We observe that in Eq. 17 the partial derivative Bv(CA)) is purely function of entries of C(h) [Cu(h]
since (C(AA) itself is a function of entries of Clh]. The second term is the partial derivative of our confusion matrix w.r. the unconstrained confusion matrix. Since C and C are related by the
@Ca[[A] also following relation (h) = softmax softmax(C:(h))); By virtue of the aforementioned map ac,, [h]
happens to be expressible terms of C(M]:
0g Culli
k i
(18)
C (
CG
i k,1=)
CllM Let us consider the metric mean recall va (C Σ C The derivative of (/A (C(M)
w.r.t the unconstrained confusion matrix Ö can be expressed in terms of the entries of the confusion matrix. This is useful property of this partial derivative since need not infer the inverse map from C' - C' inorder to evaluate the partial derivative in terms of C. It can be expressed follows:
C. (m
((JAM(CCT)) [A,
m +
(19)
Ca K-n
Cai K-
77 71
Hence we can conclude that for metric defined function of the entries of the confusion matrix, the derivative w.r.t the unconstrained confusion matrix (C) is easily expressible using the entries of the confusion matrix (C).
E COMPARISON OF SELMIX WITH OTHER FRAMEWORKS
In our work, we optimize the non-decomposable objective function by using Mixup (Zhang et al., 2018). In recent works, Mixup training has been shown to be effective specifically for real-world sce- narios where the long-tailed imbalance is present in the dataset (Zhong et al., 2021: :: Fan et al., 2022). Further, mixup has been demonstrated have a data-dependent regularization effect (Zhang et al., 2021). Hence, this provides us the motivation to consider optimization of the con-pecomposable objec- tives which important for long-tailed imbalanced datasets, in terms of directions induced by Mix- ups. However, this mixup-induced data-dependent regularization is not present for works (Narasimhan & Menon, 2021; Rangwani al., 2022), which use consistent loss functions without mixup. Hence, this explains the superior generalization demonstrated by SelMix (mixup based) on non-decomposable objective optimization for long-tail tailed datasets.
F UPDATING THE LAGRANGE MULTIPLIERS
F.1 MIN. RECALL AND MIN OF HEAD AND TAIL RECALL
Consider the objective of optimizing the worst-case(Min.) recall, MR (C(h))
C.(b] minxEλK Eie(K] ARRec;[h] minxe Eie(K] E A as in Table G.3. the
Lagrange multipliers are sampled from - dimensional simplex and X; = 1 recall of 7tt class is the lowest and the remaining lagrange multiplers zero. Hence, good approximation of the lagrange multipliers at a given time step can be expressed as:
1000
(20)
ΣjEKK e wRee (1)
This has some nice properties such as the Lagrange multipliers being a soft and momentum-free approximation of their hard counterpart. This enables SelMix to compute a sampling distribution Peela that neither over-corrects nor undercorrects based on the feedback from the validation set. For sufficiently high this approximates the objective the min recall.
23

---

Published as a conference paper at ICLR 2024
F.2 MEAN RECALL UNDER COVERAGE CONSTRAINTS
For the objective where we wish to optimize for the mean recall, subject to the constraint that all the classes have coverage above K. where if is the ideal case for balanced validation
set. We shall relax this constraint and a 0.95, V-c.s. (C[h)) xRn EiE(K] Rec,[h]
EjE[k] A (Cov,[ x) min K Lielk] Eye( Ca Σ yjEKK] X [EEEK] Ciylit] K For practical purposes, we look at related constrained optimization problem,
C. [k]
8--M ComS.
(Clh))
min R
Σ SE[K]
Rec,|[[]
Σ No (Cov,11) SEIK]
Amaz +
K
then A; increases, and vice-versa for the converse case. Also, if Fi s.t. (Covi[A] - R < then this implies that Am + 0+ and
Such that if (Cov;[h) x)
Ama+=1 + 1-, which forces h to
Arme
satisfy the constraint (Cov,]h) [h] # the lagrangian multipliers is as follows:
O. Based this, momentum free formulation for updating
A; = max (0. Amax
(1
-
Here, Amez is the maximum value that the Lagrange multiplier can take. A large value of Amaz forces model focus more on the coverage constraints that be biased towards mean recall optimization. is hyperparameter that is usually kept small, say 0.01 so, which acts as sort of tolerance factor to keep the constraint violation in check.
G EXPERIMENTAL DETAILS
The baselines (Table 2) are evaluated with the SotA base pre-training method FixMatch + LA using DASO codebase (Oh et al., 2022), whereas CSST (Rangwani et al., 2022) is done through their official codebase.
G.1 HYPERPARAMETER TABLE
The detailed values of all hyperparameters specific to each dataset has been mentioned Table G.I.
Table G.1: Table of Hyperparameters for Semi-Supervised datasets.
CIFAR-10 (All distributions)
CIFAR-100
Parameter
STL-10
Imagenet- 100(p: P.. 10)
(Pl
10, Pu
10)
Gain scaling (8)
10.0
10.0
2.0
10.0
40
20
20
20
Anaa
100
100
100
100
0.01
0.01
0.01
0.01
0.95
0.95
0.95
0.95
Batch Size
64
64
64
64
Learning Rate(f)
3e-4
3e-4
3e-4
0.1
Learning Rate(g)
3e-5
3e-5
3e-5
0.01
Optimizer
SGD
SGD
SGD
SGD
Scheduler
Cosine
Cosine
Cosine
Cosine
Total SGD Steps
10k
10k
10k
10k
Resolution
32 X 32
32 X 32
32 X 32
224 224
Arch.
WRN-28-2
WRN-28-2
WRN-28-2
WRN-28-2
24

---

Published as a conference paper at ICLR 2024
Table G.2: Table of Hyperparameters for Supervised Datasets.
CIFAR-10
CIFAR-100
Parameter
Imagenet- 1 LTT
(p 100)
(p 100)
Gain scaling (s)
10.0
10.0
10.0
Min. Rec
50
25
100
Amax
100
100
100
0.01
0,01
0.001
0.95
0.95
0.95
Batch Size
128
128
256
Learning Rate(
3e-3
3e-3
0.1
Learning Rate(g)
3e-4
3e-4
0.01
Optimizer
SGD
SGD
SGD
Scheduler
Cosine
Cosine
Cosine
Total SGD Steps Resolution
2k
2k
2.5k
32 X ResNet-32
32 X ResNet-32
224 224
Arch.
ResNet-50
G.2 EXPERIMENTAL DETAILS FOR SUPERVISED LEARNING
We show our results on 3 datasets: CIFAR-10 LT (p = 100), CIFAR- 100 LT (p= 100) (Krizhevsky Hinton, 2009) and Imagenet-Ik 1k (Russakovsky et al., 2015) LT. For our pre-trained model, we use the model trained by stage-1 of MiSLAS(ZZong et al., 2021), which uses mixuppbasse pre-training as improves calibration. For CIFAR- 10, LTT (p = 100) we use ResNet-32 while for Imagenet- 1 LT, we use ResNet-50. The detailed list of hyperparameters have been provided in Tab. G.2. Unlike semi-supervised finennunin, we do not require to refresh the pseudo-labels for the unlabelled samples 1 since we already have the true labels. The backbone is trained at learning rate TO of the linear classifier learning rate. The batch norm is frozen across all the layers. The detailed algorithm can be found in Alg. and is very similar to its semi-supervised variant. We report the performance obtained at the end of fine-tuning.
Algorithm 2 Training through SelMix
Input: Data (D, Dval), iterations T, classifier (1)), metric function vi
for t = 1 to T do
(1) (t)-1) C(t) (( (( [C]h(']]
(:(() = -1 F. Vi,j (4)
ac
G ΣR., aCu
Qv(C()) (V/10)) zzk Vi,j
((t)
SalMix = softmax(s (t) ()))) // Compute Sampling distribution and update pseudo-labes label
for SGD steps do
(())
Y1, Y2 SeiMix
X1 ((v;), X2 ~ ((22)) sample butches of
10 SGD-Update Lmiixup (X1, Y1,Y,, X2))
end for end for
Output: (T)
H RESULTS FOR CASE WITH UNKNOWN LABELED DISTRIBUTION
In this section, we provide full-scale comparison of all the methods of the case when the labeled distribution does not match the unlabeled data distribution, simulating the scenario when label distribution is unknown. The main paper presents the summary plots for these results in Fig. 3. The Table H.I, we present results for the case when for CIFAR-10 10 once the unlabeled data follow an inverse label distribution i.e. (pt 100, Pu. T0o) and the case when the unlabeled data is distributed
25

---

Published as a conference paper at ICLR 2024
Table G.3: The Expression of ceoDpeoomposale Objectives we consider in our paper.
Metric
Definition
Mean Recall (U-MM)
Cull R Eiem Exer Cu
G mean (s:GM)
Gild (Ther Dicry) Cill)) CirlM)
H-mean (U(lM)
K (Ear1s) 2ingo Cu.4 -1 CulA
Min. Recall (1.0e))
minxean Ex(()) de Cull Eiuiie Cula
minguariee, iit >ir Em G4
Guly
Min of Head and Tail class recall (PW)")
# DiET FoJiK Cirl
G.ll
Mean Recall per class coverage 2 & (wrom)))
Oull minAERt 7 A Eie(s) E.j Gr(A) EVERKY As (EvE Cylh] =2)
min ArteRgo R Eigin Supmin Col97 +dr (Zienl
Culy
Ar (EIEINTEE TRI 0.00
Mcan Recall s.t. minimum head and tail class coverage 2: ft (s-AM (H
Sulhi
H mean S.L. per class coverage 2 (HM)
minxers K (Enetay Eseng m -1
+ EsSoiK) As (Eeeue Cyll - (2)
Aeeeen (ErEIk) +dr (Enejy ou 090
Eugn Ax (Eeekk]ee C.ll
H-mean s.t. minimum head and tail class coverage (M
(Nooesom))
uniformly across all classes (pr 100, Pu. 1). In both cases, we find that SelMix can produce significant improvement across metries. Further, we also compare our method in the practical setup where unlabeled data distribution is unknown. This situation is perfectly emulated by the STL-10 dataset, which also contains an unlabeled set of 100k images. Table H.2 presents results for different approaches on the STL-10 case. We observe that SelMix produces superior results compared to baselines and is robust to the mismatch in distribution between labeled and unlabeled data.
Table H.1: Comparison
metric objectives for CIFAR-10 LT under pt * Py assumption. Our experiments involve Pu = 100, Pt = (uniform) and Pr. = 100, = T0o (inverted). SelMix achieves significant gains over other SSL-LT methods across all the metries.
CIEAR-10
100, Pa
1500. Ms
CIFAR-10
100, A. 1,N 1500, M. 3000)
Mean
Min
Mean /Mc Cov.
Mean
Min
HM
GM
Mean Rec/Min
FisMatch
28.
70005
00059
DARP
70.7
60.7274
85.3gm
54
71.3.0>
40.3
68.6111
0.040.54
85.7
68.7113
$4.5134
15.7
CReST+
72.8um
45.2gz>
68.4a13
70.6est
72.8asa/
0.047
86.4
71.7as
85.6a33
W6.las
4ean 00078
DASO
79.2unz
64.6115
7am
78.6
79.2 0.072
88.62n4
78 78:221
88.4130
88.5axa
58, Gasa 00089
ABC
80.5.c
63.1us
79,8103
50.7
80.8 / 0.073 idva
88.6.04
74.8
38.2
88.61e3
38.0 0.00 aed
CASSI
78.6
66.3g75
77.2ar
77.8
78 0.0R0
88. Tame
76. 1270
88.2
88.5gin
88. 7ass 0084
CSST
77.5-15
76,524
76.8151
77.5 / 0,091 Ltd
87.6.00
78, 1:x3
$6.1
87.1
$7.6 0000 ated
FisMarchlLA)
75.5.15
45.1
71.1235
73.32s5
75.5 0,046.243
90. Jana
75.8221
$9.5231
89.7
50. lasa/ 0.033tte
w/Sellli (Ours)
81.3.5
74,3
81.0
50.9
81.7 ao. / 0,091 .33
91.4
$4.7
91.3
91.3
91.4 0J99
I OPTIMIZATION OF H-MEAN WITH COVERAGE CONSTRAINTS
We consider the objective of optimizing H-mean subject to the constraint that all classes must have a coverage 2 a For CIFAR-10, when the unlabeled data distribution matches the labeled data distribution, uniform or inverted, SelMix is able to satisfy the coverage constraints. A similar observation could be made for CIFAR- 100, where the constraint is to have the minimum 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 complex objectives like optimizing H-mean with constraints. This shows the superiority of the proposed SelMix framework.
26

---

Published as a conference paper at ICLR 2024
Table H.2:
Comparison across methods when label distribution Pa is unknown. We use the STL-10 dataset for comparison in such case.
STL-10
(m = 10, NA, No 450, Σ, M, 100K)
Mean Rec.
Min Rec.
HM
GM
HM/Min Cov.
Mean Rec./Min Cov.
FixMatch
72.7+ur
43.2+
67.7+15
71.6=13
67.7+1s / 0.048
72.7 0atpaa/00.444 00.48
DARP
76.5gm3
54.7219
74.0a05
75.3
74.0ans / 0.055
76.5 16.554s300008::: /.005
CReST
10.1
48. 48.2+22
67.1=u
67.8=11
67.1 / 000066:2-3
70. / 0.0666
DASO
78. Lns
55.8137
76.6211
77.22ma
76.6111
/0.083.1
78. 78.12os/0.0831// 00.08311ed
ABC
77.5+04
55.4+67
74.7+15
76.3+09
74.7+15 / 0,079+724
77.5+a4 0.079+774
CSST
79.2+ts
50.8+29
78.3=26
78.9+21
78.3+2s / 0,081 +4:-3
79.2 0,08 ::t0-3
FixMatch(LA)
78.9
56.4219
76.5=1
77.8=0s
76.5
0,066=5e3
78.9 0.066
w/SelMix (Ours)
80.9
68.5118
79.1212
80.1
19.1 0.088
80.9
0.088 111
Table L1: Comparison of methods for optimization of H-mean with coverage constraints.
CIFAR-10
CIFAR-10 Ps
CIFAR-10
CIFAR-100 Au
STL-10 At
100, Au
Th
100,
Pi
N₁
M,,
Ni- = 1500, M4;
= 3000
N2 1500, MG = 3000
Ng 150, = 300
Nj 450, M,M, 100k
HM
Min Cov.
HM
Min Cow.
HM
Min Cov.
HM
Min H-T Cov.
HM
Min Cov.
DARP
78. 0.066g2
81.9gm
0.070axs
83. Sanx
0.0672x-
48.7211
0.00400g>
74.0grs
0.058
CR:ST
65.8115
0.040.53
81.0.00
0,073:553
84.6131
0,075
48.3162
0.0083
67.1131
0,066.24
78.11s1
0.072-333
83.5.00
0.083
0.089:w2
0.0063:344
76.6211
0,083
ARC
79.62ss
0.073
84.6
0.006
58 Rant
0
50.1a1
0.0089
74.7211
0:079gte
CSST
76.5240
76.9
0.09
86 7ast
0.092aw>
47.7
0.0098
78.3
0.081 Zene
FixMarch (I.))
78, 78.3
76.7
0.056
89.3em
0
45.8gn
0.0053
74.6217
0.066
w/SelMix (Ours)
81,01es
0,095
85.1.oo
0.095
91.3uat
0,096
53.81es
0,0098
79.1
0,088
400
(a) Initial Stage (1- = 0 SGD steps)
(b) Intermediate Stage (1 = 5k SGD steps)
(c) Final Stage (L = 10k SGD steps)
Figure J.1: Evolution of gain matrix for mean recall optimized run for CIFAR-IO LT (pr = pw).
J EVOLUTION OF GAIN MATRIX WITH TRAINING
From the above collection of gain matrices, which are taken from different time steps of the training phase, we observe that (Imax(G (G) 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 disproportionate amount of gain associated with them. A downstream consequence of this is that the sampling function Psemi 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 particular timestep.
K ANALYSIS
We subset of Min. Recall, Mean Recall and Mean Recall with constraints for analysis. a) Sclability and Computation. To demonstrate scalability of our method we show results on ImageNeet00-LLT for semi and ImageNet-LTT for fully supervised settings. Similar to other datasets,
27

---

Published as a conference paper at ICLR 2024
190
(a) Initial Stage (t- = 0 SGD steps)
(b) Intermediate Stage (t = 3k SGD steps)
(c) Final Stage (t = 10k SGD steps)
Figure J.2: Evolution of gain matrix for min. recall optimized run for CIFAR-IO LT (pt. = -p)-
Table K.I: Results for sampling policies for PMix Table K.2: Comparison of finetuning the feature (CIFAR-10 LT, semi-supervised) 100.
extractor vs only the linear classification layer
(CIFAR- LT, semi-supervised) p 100
Method
Mean Recall
Min
Min
Mean Recall
Uniform Policy
Coverage
0.072
Recall
70.5
83.3
Method
Mean Recall
Coverage
Recull
Recall
Greedy Policy
83.6
0.093
78.2
81.8
83.5
0,089
77.3
84.1
SelMix Policy
84.9
0.094
79.1
84.1
Fiinetunigg g
85,4
0.095
79.1
84.5
we find in Table 4 SelMix is able to improve over SotA methods across objectives. Further, SelMix has the same time complexity as CSST (Rangwani et al., 2022) baseline. (Refer Sec. I. & Sec. B).
b) Comparison of Sampling Policies. We compare the sampling policies (PMr): the uniform mixup policy, the greedy policy of selecting the max gain mixup and the SelMix policy (Table K.I). We find that other policies in comparison to SelMix are unstable and lead to inferior results. We compare furtherthe performance of a range of sampling distribution by varying the inverse distribution temperature in PselMix We find that intermediate values of 10 work better in practice (Fig. K.1).
Fine- Tuning In Table K.2 we observe that fine-tuning g leads to improved results in comparison to keeping it frozen. We further show in App. L. that fine-tuning with SelMix is computationally cheap compared to CSST for optimizing a particular non-decomposable objective.
K.1 DETAILED PERFORMANCE ANALYSIS OF SELMIX MODELS
As in SelMix, we have provided results for fine-tuned models for optimizing specific metrics on CIFAR-IO 10 (pi = P.) in Table 2. In this section, we analyze all these specific models on all other sets of metrics. We tabulate our results in Table K.3. It can be 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 the models produced are balanced and fair in general. As a rule of thumb, we would like the users to utilize models trained for constrained objectives as they perform better than others cumulatively.
Table K.3:
Values of all metric values for individually optimized runs for CIFAR-10 LT (pr = Pr)
Observed Metric
Optimized On
Mean Rec.
Min. Rec.
HM
GM
Mean Rec Cov.
HM/Min Cov.
Moan Ree.
85.4
77.6
85.0
85.1
85.480.089
85,000
Rec.
84.1
$4.2/0.091
$4.1/0.091
HM
85.3
77.7
85.1
85.2
85.3/0.091
85.1/00091
GM
85.3
77.5
85.1
85.3
85.3/0.091
85.1/0.00
Moan Rec. /Min. Cov.
85.7
84.7
84.8
85.781.995
84.7/0.095
HM/Min Cow.
85.1
76.2
84.8
84.9
18.009
84.800.955
K.2 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 Mixhhtch Algorithm (Table K.4). However, our method SelMix
28

---

Published as a conference paper at ICLR 2024
Mean Recall Inverse temperature parameter (5)
85.4
85.2
Towards uniform
Towards greedy sampling
sampling (4 + 0)
84.8
84.6
84.4
84.0
Inverse temperature
Figure K.1: We show ablation on the inverse temperature parameter (s) v/s the performance on the mean recall, For a mean recall optimized run very small yields sampling function close to uniform sampling, whereas a very large ends up close to greedy sampling strategy.
is able to improve both the FixMatch and the FixMatch (LA) variant. We advise users to use the FixMatch (LA) algorithm for better results.
Table K.4: Comparison of the FixMatch and FixMatch (LA) methods with SelMix.
Mean Recall
Min
Min Recall
Mean Recall
Method
Coverage
Fix.Match
76.8
0.037
36.7
76.8
w/ SelMix
84.7
0.094
78.8
82.7
Fix.atcc (LA)
82.6
0.065
63.6
82.6
w/ SelMix
85.4
0.095
79.1
84.1
K.3 VARIANTS OF MIXUP
As SelMix is distribution which class samples (i,j) to be mixed up, it can be easily be combined with different variants of 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 K.5 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 SelMix with the different variants of Mixup like CutMix. PuzzleMix, etc., which re-design the procedure of mixing up images.
L COMPUTATIONAL REQUIREMENTS
The experiments were done on Nvidia A5000 GPU (24 GB). While the fine-tuning was done single A5000, the pre-training was done using PyTorch data parallel on 4XA5000. The pre-training was done until significant change in metries was observed and the fine-tuning steps of SGD with a validation step every 50 steps. A major advantage of SelMix over CSST is that the process of training model optimized for specific objective requires end end training
done for 10k
29

---

Published as a conference paper at ICLR 2024
Table K.5: Comparison SelMix when applied to various Mixup variants.
Mean Recall
Min Recall
Method
FixMatthh
55.9 -9.7
w/ SelMix (CutMix)
75.3 84.8
w/ SelMix (PuzzleMix)
85.1
75.2
w/ SelMix (Features-Ours)
85.4
79.1
Table L.1: Comparison of time taken across datasets, for the calculation of Gain using SelMix (Alg. was done on GPU (NVIDIA RTX A5000).
Dataset
CIFAR- 10 LT (p = 100) CIFAR-100 LT 100)
Imagenet- Ik LT
0.02 sec.
1.3 sec.
124 sec.
which is computationally expensive(~110 hrs on CIFAR datasets). Our finetuning method takes a fraction (~Ihr on CIFAR datasets) of what it requires in computing time compared to CSST. An analysis for computing the Gain through Alg. 1, is provided in Table L.1. We observe that even for the ImageNet- Ik dataset, the gain calculation doesn't require large amount of GPU time. Further, an efficient parallel implementation across classes can further reduce time significantly.
M LIMITATION OF OUR WORK
In our current work, we mostly focus on our algorithm's correctness and empirical validity of SelMix across datasets. Another direction that could be further pursued is improving the algorithm's performance by efficiently parallelizing the operations across GPU cores, as the operations for each class are independent of each other. The other direction for future work could be characterization of the classifier obtained through SelMix, using generalization bound. Existing work (Zhang al., 2021) on the mixup method for accuracy optimization showed that learning with the vicinal risk minimization using mixup leads to better generalization error bound than the empirical risk minimization. would interesting future work to show similar result for SelMix.
N ADDITIONAL RELATED WORKS
Selective Mixup for Robustness. The paper SelecMix (Hwang et al., 2022) creates samples for robust learning in the presence of bias by mixing up samples with conflicting features, with samples with bias-aligned features. The paper demonstrates that learning on these samples leads improved out- of-distribution accuracy, even in the presence of label noise. This paper selects the samples to mixup based on the similarity the labels, to improve mixup performance on regression tasks. Existing works (Hwang et al., 2022; Yao al., 2022; Palakkadavath et al., 2022) show that mixups help train classifiers with better domain generalization. Teney et al. (2023) show that resampling-best based techniques often come close in performance to mixup-based methods when utilizing the implicit sampling technique used in these methods. It has been shown that mixup improves the feature extractor and can also be used train more robust classifiers (Hwang et al., 2022). Palakkadavath et al. (2022) show that it is possible to generalize better to unknown domains by making the model's feature extractor invariant both variation in the domain and any interpolation of sample with similar semantics but different domains.
Black- Box Optimization. We further note that there are some recent works (Li et al., 2023; Wierstra et al., 2014) which aim to fine-tune a model based on local target data for an specific objective, however these methods operate in black-box setup whereas SelMix works white-box setup with full access to model and its gradients.
30


Reviews:
[{"review_id": "PSzPObPUbS", "reviewer": "Reviewer_misU", "summary": "This paper aims to fine-tune a pre-trained model using an additional objective, especially a non-decomposable objective. In particular, the authors propose a mixup-based technique that can determine a sampling distribution over classes for performing objective-oriented mix-up. Empirical results demonstrate the efficacy of the proposed method.", "questions": "1.\tWhat is the difference between \"Non-Decomposable Objective\" and \"Non-Differentiable Objective\"?\n2.\tThe first-order Taylor approximation is adopted in this paper for calculating the Gain matrix, which cannot guarantee convergence for complex objectives, although it is simple and efficient. \n3.\tIt seems we can fitting a surrogate model to approximate the Non-Decomposable Objective, which can then be used for gradient-based model fine-tuning. It would be interesting to discuss the advantages of the first-order Taylor approximation compared to fitting a surrogate model.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed method, SelMix, is simple and reasonable, with a theoretical guarantee.  \n2. Sufficient empirical results are provided.", "weaknesses": "1. Literature review is not sufficient, and some sentences are over-claimed. Fine-tuning a pretrained network for non-decomposable objectives and even non-differential objectives has been extensively developed recently. Please refer to a recent paper [1] and the references therein for more details. Particularly, the objective derived $\\mathbb{E}[G]=\\sum_{i, j} G_{i, j} \\mathcal{P}_{M i x}(i, \\jmath)$ shares the same motivation as the natural evolution strategies [2] adopted in [1].\n2. There are many grammar errors, needed to double check. For example, \"existing frameworks theoretical frameworks\", \"Semi-Supervised Learning is are algorithms\", $f: \\mathbb{R}^{m \\times n} \\rightarrow n$, $\\rho_l=N_1 / N_K, \\rho_l=M_1 / M_K$.  \n3. Some theorems are not formal and have overly strong assumptions. For instance, $z_k$ in Theorem 4.1 appears suddenly without intuitive explanation. There is no detailed explanation in the proof in the Appendix. “a reasonable directional vector for optimization” is not professional.   \n\n[1] Li, Jing, et al. \"Earning Extra Performance from Restrictive Feedbacks.\" IEEE Transactions on Pattern Analysis and Machine Intelligence (2023).  \n[2] Wierstra, Daan, et al. \"Natural evolution strategies.\" The Journal of Machine Learning Research 15.1 (2014): 949-980.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hCTjBd5Kbz", "reviewer": "Reviewer_iMBB", "summary": "For applications with critical consequences, accuracy is not a suitable performance metric, and other metrics such as recall h-mean and worst-case recall should be used. However, such metrics are non-decomposable, which means that they cannot be expressed as a simple average of a function of label and prediction pairs calculated for each sample. Prior techniques to optimize non-decomposable objectives such as CSST lead to sub-optimal representations. Other methods to improve the performance on long-tailed class-imbalanced datasets such as DASO, ABC, and CoSSL perform suboptimally for the non-decomposable objectives. This paper proposes SelMix -- a technique that utilizes a pre-trained model for representations and optimizes it for improving the desired non-decomposable objective through fine-tuning.", "questions": "The description of SelMix in Algorithm 1 is a bit confusing. Algorithm 1 says the classifier h is updated, but in Section 4.1 it says the parameter W is updated. I’m assuming the former is a consequence of the latter. If this is the case, wouldn’t it be better to replace h with W in Algorithm 1? Obfuscating the actual operation with the function SGD-Update() also makes it difficult to see the exact algorithm.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "In the experimental results for matched label distributions shown in Table 2, the proposed method shows shows superior performance compared to existing methods; DARP, CReST, CReST+, ABC, CoSSL, DASO, and CSST for all metrics; mean recall, min recall, H-mean, G-mean, and min coverage. The results for unknown label distributions in Figure 3 also shows that the proposed method outperforms existing methods on all metrics. The same is true for large datasets such as ImageNet-1k LT, shown in Table 4.", "weaknesses": "The fact that the proposed method requires only fine-tuning of a pre-trained model should result in a huge advantage in training time compared to existing methods, but this is not highlighted in the main results section of the paper. The only mention of computational requirements is in Appendix L, where only the time to calculate the Gain is shown. It would be interesting to see a more comprehensive comparison of the training time of the proposed method vs. all the existing methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gQGHui4Gqe", "reviewer": "Reviewer_LrpR", "summary": "The paper introduces a novel approach called Selective Mixup (SelMix), which leverages an optimized sampling distribution of elements to mix based on a specific objective. This sampling distribution is designed to consider the gain in the objective function achieved by mixing centroids of class samples. Throughout the training process, the sampling distribution is dynamically updated to adapt to changes in class centroids. The paper also includes a rigorous theoretical analysis, establishing the approach's convergence rate and the validity of the sampling distribution. To validate its effectiveness, the method is empirically evaluated across various long-tailed benchmark datasets in both supervised and semi-supervised scenarios, by fine-tuning pretrained models using SelMix.", "questions": "- What is the *prior distribution* on labels $\\pi_i$ ? How do you define this in practice ?\n- What is the *unconstrained confusion matrix* $\\tilde{C}$ ? It is never clearly defined in the paper, but is important to define the gain.\n- I would like to see at least some comparison of SelMix using \"vanilla\" FixMatch to fairly compare with state of the art.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- **Theoretical Analysis and Convergence Rate:** The paper's presents a rigorous theoretical analysis, particularly the establishment of a convergence rate. This analysis adds credibility and reliability to the proposed SelMix.\n- **Strong Experimental Results:** The paper showcases strong experimental results compared to other state-of-the-art approaches. The empirical evaluation is performed across different long-tailed benchmark datasets in both supervised and semi-supervised settings, and for different objectives.\n- **Efficiency of the proposed approach:** As discussed in Appendix L, the paper is much more computationally efficient than previous methods, since it relies on fine-tuning a pretrained model.", "weaknesses": "- **On a Fair Comparison with Other Methods:** The paper uses FixMatch + Logits Adjusted (LA) loss as a baseline, while other approaches are evaluated using the vanilla FixMatch. This discrepancy in the comparison may not provide a fair assessment of the true impact of SelMix. As can be seen in Table H.2 and H.1, FixMatch + LA shows already significant improvements over vanilla FixMatch. This makes it challenging to evaluate whether SelMix's improvements reported in the benchmarks are due to the approach or its combination with a more advanced baseline. A fair comparison would involve evaluating SelMix with vanilla FixMatch to better understand its relative performance, or comparing to other state-of-the-art methods when using FixMatch + LA.\n- **Lack of Discussion about other related \"Selective Mixup\":** Several recent paper have discussed using *selected pairs* of examples to mix, between specific classes or different domains [1,2,3,4,5]. Even though the approach presented is applied in a different context and quite novel compared to these papers, I think a discussion about the relation to these methods is important since the paper is currently part of a popular topic. \n\n[1]: Yao H. et al., C-mixup: Improving generalization in regression. In NeurIPS 2022  \n[2]: Yao H. et al., Improving out-of-distribution robustness via selective augmentation. In ICML 2022  \n[3]: Hwang I. et al., Selecmix: Debiased learning by contradicting-pair sampling. In NeurIPS 2022  \n[4]: Palakkadavath R. et al., Improving domain generalization with interpolation robustness. In NeurIPS 2022 Workshop on Distribution Shifts: Connecting Methods and Applications  \n[5]: Teney D. et al., Selective mixup helps with distribution shifts, but not (only) because of mixup. In arXiv:2305.16817, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZDfF0V0TWT", "reviewer": "Reviewer_4axA", "summary": "The authors propose SelMix which utilizes a pre-trained model for representations and optimizes it for improving the desired non-decomposable objective through fine-tuning. They developed a selective sampling distribution on class samples to selectively mix up, optimizing the given non-decomposable objective. The distribution is also updated periodically based on feedback from the validation set. The efficacy of SelMis is evaluated across a wide range of linear or non-linear objectives under both supervised and semi-supervised settings.", "questions": "Please see weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The key novelty lies in the idea of selective mixup. The selective procedure ensures that at each timestep the the objective is optimized.\n\n2. The theoretical analyses present in the paper are sufficient. They provide the convergence analysis and show the validity of the sampling procedure. \n\n3. The experimental results are comprehensive, which consist of strong empirical results under different supervision settings and different distributions.", "weaknesses": "1. The authors use the first-order Taylor expansion on Eq. 5. I am curious about the performance if the second-order terms are involved, i.e., calculating the third term of Eq. 5. Also, the first-order gradient can be also approximated by f(x+ h) + f(x-h) -f(x) / 2h. Would it give better performance than the current one-sided approximation?\n\n2. Can authors provide some ablation studies on the hyper-parameters, such as the imbalanced ratio and the number of samples for feedback?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)