P$^2$OT: Progressive Partial Optimal Transport for Deep Imbalanced Clustering
Authors: Chuyu Zhang
Hui Ren
Xuming He
Venue: ICLR 2024 poster (2024)
Keywords: deep imbalanced clustering
optimal transport
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Deep clustering, which learns representation and semantic clustering without labels information, poses a great challenge for deep learning-based approaches. Despite significant progress in recent years, most existing methods focus on uniformly distributed datasets, significantly limiting the practical applicability of their methods. In this paper, we first introduce a more practical problem setting named deep imbalanced clustering, where the underlying classes exhibit an imbalance distribution. To tackle this problem, we propose a novel pseudo-labeling-based learning framework. Our framework formulates pseudo-label generation as a progressive partial optimal transport problem, which progressively transports each sample to imbalanced clusters under prior distribution constraints, thus generating imbalance-aware pseudo-labels and learning from high-confident samples.
In addition, we transform the initial formulation into an unbalanced optimal transport problem with augmented constraints, which can be solved efficiently by a fast matrix scaling algorithm. Experiments on various datasets, including a human-curated long-tailed CIFAR100, challenging ImageNet-R, and large-scale subsets of fine-grained iNaturalist2018 datasets, demonstrate the superiority of our method.

Published as a conference paper at ICLR 2024
P¹OT: PROGRESSIVE PARTIAL OPTIMAL TRANSPORT FOR DEEP IMBALANCED CLUSTERING
Chuyu Zhang 1.2. Hui Ren'.* Xuming He 3.3
1 "ShanghaiTede University, Shanghai, China LLingang Laboratory, Shanghai, China Shanghai Engineering Research Center of Intelligent Vision and Imaging, Shanghai, China (zhangchy2, renhui, hexm ( Shangha weegghaiiieeh......mm tech. edu.cn on
ABSTRACT
Deep clustering, which learns representation and semantic clustering without labels information, poses great challenge for deep learning- based approaches. Despite significant progress in recent years, most existing methods focus on uniformly distributed datasets, significantly limiting the practical applicability of their meth- ods. In this paper, we first introduce a more practical problem setting named deep imbalanced clustering, where the underlying classes exhibit an imbalance distribution. To tackle this problem, propose novel Seeuudo-lablligg-bbee learning framework. Our framework formulates pseudo-label generation as pro- gressive partial optimal transport problem, which progressively transports each sample to imbalanced clusters under prior distribution constraints, thus generating imbalance-awan pseudo-labels and learning from high-confident samples. In ad- dition, we transform the initial formulation into an unbalanced optimal transport problem with augmented constraints, which can be solved efficiently by fast matrix scaling algorithm. Experiments on various datasets, including human- curated long-tailed CIFAR100, challenging ImageNet-R, and large-scale subsets of fine-grained iNaturalist2018 datasets, demonstrate the superiority of our method.
INTRODUCTION
Human beings possess the innate ability to categorize similar concepts, even when encountering them for the first time. In contrast, artificial models struggle to group similar concepts without labels, although they excel primarily in scenarios where extensive semantic labeling is available. Deep clustering, which aims to learn representation and semantic clustering, is proposed to enable models achieve that, Currently, many works (Ti al.) 2019 Van Gansbeke et al., [2220] [onen al. (022) are advancing the field of deep clustering. However, they focus on developing methods on balanced datasets, limiting their application in reality, where the data distributions are imbalanced.
In this paper, we propose a practical deep imbalanced clustering problem, bridging the gap between the existing deep clustering and real-world application. Existing methods are broadly categorized into relation matching based (Dang et al.] (2021), mutual information maximization based (Ji et al. (019). and gseudo-labeling (PL)-based (Van Gansbeke al. 2020). They face significant challenges when dealing with imbalanced clustering. Relation matching and mutual information maximization act as surrogate losses for clustering and show inferior results compared to the PL method (Van Gansbeke let al. 2020: Niu et al. 2022). PL, on the other hand, tends to learn degenerate solutions (Caron ctt al. 2018 and heavily relies on the quality of the pseudo-labels. This reliance often requires an additional training stage for representation initialization and sensitive hyperparameter tuning to mitigate confirmation bias (Arazo et al., 2020 Wei et al.) 2021). especially in challenging imbalanced clustering scenarios, where imbalanced learning will seriously affect the quality of pseudo labels.
To mitigate the above weakness, we propose a novel PL-baaed progressive learning framework for deep imbalanced clustering. Our framework introduces novel Progressive Partial Optimal Transport (P²OT) algorithm, which integrates imbalance class distribution modeling and confident sample selection within a single optimization problem, enabling us to generate imbalanced pseudo labels and learn from high-confident samples in a progressive manner. Computationally, we reformulate our P²OT as a typical unbalanced OT problem with theoretical guarantee and employ the light-speed scaling algorithm (Cuturi 2013 Chizat et al. 2018) to solve it.
Both authors contributed equally. Code is available https///tthhh.cmm//hheaaa///

---

Published as a conference paper at ICLR 2024
Specifically, in our progressive PL-based learning framework, we leverage cluster estimation to generate soft pseudo-labels while imposing a set of prior constraints, including an inequality constraint governing sample weight, a Kullback-Leibler L) divergence constraint cluster size uniform distribution, and a total mass constraint. Notably, the K I. divergence- uniform distribution constraint empowers our method to avoid degenerate solutions. And our approach with K T, which represents a relaxed constraint compared to an equality constraint, facilitates the generation of imbalanced pseudo-labels. The total mass constraint allows us to selectively learn from high- confident samples by adjusting their weights through optimization, alleviating the noisy pseudo-label learning, and eliminating the sensitive and hand-crafted confidence threshold tuning. As training progresses, we incrementally raise the total mass value, facilitating gradual transition from learning easy samples to tackling more difficult ones. To solve our P2OT problem efficiently, we introduce a virtual cluster and replace the naive K J. with the weighted K constraint, thus reformulating our POT into an unbalanced optimal transport problem under transformed constraints. Then, we solve the unbalanced OT with a scaling algorithm that relies on light-speed matrix-vecton multiplications.
To validate our method, we propose a new challenging benchmark, which encompasses a diverse range of datasets, including the calman-cuuraed CIFAR 100 dataset (Krizhevsky et al., 2009), challenging fout-o--distrbuutte ImageNet-R dataset (Hendrycks et al. 2021), and large-scale subsets of fine- grained iNaturalist dataset (Van Horn al.j 2018). Experiments those challenging datasets demonstrate the superiority of our method. In summary, our contribution is as follows:
We generalize the deep clustering problem to more realistic and challenging imbalance scenarios, and establish a new benchmark.
We propose novel progressive PL-based learning framework for deep imbalance clustering. which formulates the pseudo label generation as a novel P2OT problem, enabling us to consider class imbalance distribution and progressive learning concurrently.
We reformulate the P²OT problem as an unbalanced OT problem with theoretical guarantee. and solve it with the efficient scaling algorithm.
Our method achieves the SOTA performance on most datasets compared with existing methods on our newly proposed challenging and large-scale benchmark.
RELATED WORK
Deep clustering. The goal of deep clustering (Zhou et al. 2002a Huang et al., 2022) is to learn
representation and cluster data into semantic classes simultaneously. Based on clustering methods,
current works can be grouped into three categories: relation matching, mutual information maxi- mization. and pseudo labeling. Specifically, relation matching (Chang al., 2017]] Van Gansbeke cet al. 2020 Tao et al. 2020) involves the minimization of the distance between instances considered
'similar' by representation distance, thus achieving clustering in bottom-up way. Mutual information
maximization (Ji et al. [019 Li et al. [222] [hhen et al. (021) either in the prediction or representation
space, aims at learning invariant representations, thereby achieving clustering implicitly (Ben-Shaul
et al., 2023). Pseudo labeling (PL) (Lee et al. (013). which is widely used in semi-supervised learning (SSL) (Sohn et al. 2020) Zhang et al. 2021a), assigns each instance to semantic clusters and has demonstrated exceptional performance in the domain of deep clustering (Caron et al.) 2018 Van Gansbeke et al., 2020 Asano et al.) 2020 Niu et al.] 2022). In contrast to the relatively clean pseudo-labels produced by SSL., deep clustering often generates noisier pseudo-labels, particularly in scenarios characterized by data imbalance, imposing great challenge on pseudo-label generation. In this paper, our primary focus is on PL, and we introduce a novel PaOT algorithm. This algorithm progressively generates high-quality pseudo labels by simultancously considering class imbalance distribution and sample confidence through a single convex optimization problem.
Optimal transport and its application. Optimal Transport (OT) (Villani et al., 2009 Peyré et al. 2017,Chizza Chizat et al. 2018 Khamis et al. 2023) aims to find the most efficient transportation plan while adhering to marginal distribution constraints. It has been used in a broad spectrum of machine learning tasks, including but not limited to generative model (Frogner et al.) 2015 Gulrajani et al.
2017). semi-supervised learning (Tai et al. 2021: Taherkhani et al. 2020), clustering (Asano et al.
2020 Caron et al.] 22200), and domain adaptation (Flamary al. 2016: Chang et al.] 2022: Liu
ct al. 2023] Chang et al. 2023). Of particular relevance to our work 18 its utilization in pseudo
labeling (Asano et al. 2020 Tai et al. 2021 Zhang et al. 2023). Asano et al. (2020) initially
2

---

Published as a conference paper at ICLR 2024
introduces equality constraint on cluster size, formulating pseudo-label generation optimal transport problem. Subsequently, (Tai et al. (2021) enhances the flexibility of optimal transport by incorporating relaxation on the constraint, which results in its failure in deep imbalanced clustering, and introduces label annealing strategies through an additional total mass constraint. Recently, /Zhng et al.] (2023) relaxes the equality constraint to KT. divergence constraint on cluster size, thereby addressing imbalanced data scenarios. In contrast to these approaches, which either ignore class imbalance distribution or the confidence of samples, our novel P²OT algorithm takes both into account simultaneously, allowing us to generate pseudo-labels progressively and with an awareness of class imbalance. In terms of computational efficiency, we transform our PºOT into an unbalanced optimal transport (OT) problem under specific constraints and utilize light-speed scaling algorithm.
3 PRELIMINARY
Optimal Transport (OT) is the general problem of moving one distribution of mass to another with minimal cost. Mathematically, given two probability vectors E Rmx1, V E R as well as a cost matrix C Rm defined on joint space, the objective function which OT minimizes is as follows:
min QERTXM
(Q C) F Fi (i 1)) + F2(QT1m;p)) 1m;
(I)
where Q E Ruux is the transportation plan, (,) denotes the Frobenius product, F1, F2 are constraints on the marginal distribution of Q and 1,, gax1 Imm Rmx1 are all ones vector. For example, if F1, F2 are equality constraints, i.e. Q1, Me, Q 1m v. the above OT becomes a widely-known Kantorovich's form (Kantorovich) 1942). And if F2 are KL divergence or inequality constraints, Equ. ① turns into the unbalanced OT problem (Liero et al. 2018).
In practice, to efficiently solve Kantorovich's ' form OT problem, Cuturi (2013) introduces an en- tropy term - Q) to Equ.(1) and solve the entropic regularized OT with the efficient scaling algorithm (night 2008). Subsequently. [Chizat et al.] (2018) generalizes the scaling algorithm to solve the unbalanced OT problem. Additionally, one introduce the total mass constraint to Equ.[I, and it can be solved by the efficient scaling algorithm by adding a dummy or virtual point to absorb the total mass constraint into marginal. We detail the scaling algorithm in Appendix and refer readers to (Cuturi 2013] Chizat et al. 2018) for more details.
4 METHOD
4.1
PROBLEM SETUP AND METHOD OVERVIEW
In deep imbalanced clustering, the training dataset is denoted as D = [<x)) where the cluster labels and distribution are unknown. The number of clusters is given as prior. The goal is to learn representation and semantic clusters. To achieve that, we learn representation and pseudo-label alternately, improving the data representation and the quality of cluster assignments. Specifically, given the cluster prediction, we utilize novel Progressive Partial Optimal Transport (P²OT) algorithm to generate high-quality pseudo labels. Our P2OT algorithm has two advantages: 1) generating pseudo labels in imbalanced manner; 2) reweighting confident samples through optimization. Then, given the pseudo label, we update the representation. We alternate the above two steps until convergence. In the following section, mainly detail our P²OT algorithm.
4.2 PROGRESSIVE PARTIAL OPTIMAL TRANSPORT (P²OT)
In this section, we derive the formulation of our novel P²OT algorithm and illustrate how to infer pseudo label Q by the O* algorithm. Given the model's prediction and its pseudo-label, the loss function is denoted as follows:
Σ log P, = -log 1=1
where Q,P E RNNK Q. P. is the pseudo label and prediction of sample 2;. Note that we have absorbed the normalize term y into Q for simplicity, thus Q1 k 1N.
In deep clustering, it is typical to impose some constraint on the cluster size distribution to avoid a degenerate solution, where all the samples are assigned to single cluster. As the cluster distribution is
3

---

Published as a conference paper at ICLR 2024
long-tailed and unknown, we adopt KLL divergence constraint and only assume the prior distribution uniform. Therefore, with two marginal distribution constraints, we can formulate the pseudo-label generation problem unbalanced OT problem:
min (Q, log P) AKI(Q T 1N. QEIT
1x)
(3)
S.L. 11 (Q= R X
1 = N 1n}
(4)
where (.)r is the Frobenius product, and À is a scalar factor. In Equ. B.. the first term is exactly L. the KL term constraint on cluster size, and the equality term ensures each sample is equally important. However, the unbalanced OT algorithm treats each sample equally, which may generate noisy pseudo labels, due to the initial representation being poor, resulting in confirmation bias. Inspired by curriculum learning, which first learns from easy samples and gradually learns hard samples, we select only a fraction of high-confident samples to learn initially and increase the fraction gradually. However, instead of manually selecting confident samples through thresholding, formulate the selection process as a total mass constraint in Equ. This approach allows us to reweight each sample through joint optimization with the pseudo-label generation, eliminating the need for sensitive hyperparameter tuning. Therefore, the formulation of our novel P²OT is as follows:
min QQ log P) + AKL(Q IN. K 1x)
(5)
QEII
s.t. II = Q R NxK
Q1x S
1N. 1, = p}
(6)
N
where p is the fraction of selected mass and will increase gradually, and KL is the unnormalized divergence measure, enabling us to handle imbalance distribution. The resulted Q1k is the weight for samples. Intuitively, the OOOT subsumes a set of prior distribution constraints, achieving imbalanced pseudo-label generation and confident sample "selection" in a single optimization problem.
Increasing strategy of p. In our formulation, the ramp-up strategy for the parameter P plays an important role in model performance. Instead of starting with 0 and incrementally increasing to 1, we introduce an initial value Pa to mitigate potential issues associated with the model learning from very limited samples in the initial stages. And we utilize the sigmoid ramp-up function, technique commonly employed in semi-supervised learning (Samuli Laine 2017 Tarvainen & Valpola, 2017). Therefore, the increasing strategy of p is expressed as follows:
p= Po + (1 Po) 501-1/T)
where T represents the total number of iterations, and t represents the current iteration. We analyze and compare alternate design choices (e.g. linear ramp-up function) in our ablation study. Further- more, believe that a more sensible approach to setting P involves adaptively increasing it based on the model's learning progress rather than relying on fixed parameterization tied to the number of iterations. We leave the advanced design of p for future work.
4.3 EFFICIENT SOLVER FOR P²OT
In this section, reformulate our P²OT into unbalanced OT problem and solve with an efficient scaling algorithm. Our approach involves introducing a virtual cluster onto the marginal (Caffarelli & McCann 2010 Chapel et al., 2020). This virtual cluster serves the purpose of absorbing the I P unselected mass, enabling us to transform the total mass constraint into the marginal constraint. Additionally, we replace the K T. constraint with a weighted K... constraint to ensure strict adherence to the total mass constraint. As a result, we can reformulate Equ.(5) into a form akin to Equ. (T) and prove their solutions can be interconverted. Subsequently, we resolve this reformulated problem using efficient scaling algorithm. As shown in See 5.3] compared to the generalized scaling solver proposed by (Chizat et al. 2018), our solver is two times faster.
Specifically, we denote the assignment of samples on the virtual cluster E. Then, we extend & to Q and denote the extended Q as Q which satisfies the following constraints:
= [Q. E N (x(++1) E N
Q1K+1 = 1lx
(8)
Due to 1 TQ1=== = p. we known that,
Q =1 Q + INe = 1 T/e 1-p.
4

---

Published as a conference paper at ICLR 2024
Therefore,
Q Q 1N 1N
Q T 1n 1-p
(10)
5
The equation is due to 1E 1' p. We denote C |- log P, Onl and replace Q with Q. thus the Equ.(5) can be rewritten as follows:
min (Q.) QE
X 1x,
(11)
s.t. + [Q R (
Q1k+1 - 1N). ==
P
1
(12)
However, the Equ. I1 is not equivalent to Equ. due to the KL constraint not guarantee Equ. 10) is strictly satisfied, i.e. 1N = 1- p. To solve this problem, we replace the L constraint
with weighted K L,, which enables us control the constraint strength for each class. The formula of weighted K is denoted as follows:
K+1 K I, = Σ
1 B.
XI 10 1 log
(13)
==1
Therefore, the (5 can be rewritten as follows:
min (2, C)2 + 1ILQQIN,,,.. B.
(14)
QE
e 1K ].
(K+11 = Q R4
Q1K+1 1N3. B
AK+1 - +oc.
(15)
Intuitively, to assure Equ.qIo) is strictly satisfied, we set AK+1 + +00. This places substantial penalty on the virtual cluster, compelling the algorithm to assign a size of - to the virtual cluster.
Proposition 1 C 1- log P, Ov), and A.K X, Ax+1 too, the optimal transport plan Q of Eqq.IT. can be expressed as:
== ,0",
(16)
where Q* is optimal transport plan of Equ. 5 and 8* is the last column of Q*
The proof is in Appendix B Consequently, we focus on solving Equ. 14 to obtain the optimal Q*
Proposition 2 Adding entropy regularization -(H((Q) Equ. 14 we can solve it by efficient scaling algorithm. We denote M = as follows:
X a N 1N. The optimal Q is denoted
x+e
Q = didg(a)Mdiag(())
(17)
where a, b are scaling coefficient vectors and can be derived by the following recursion formula:
3
Mb -
jo
(18)
M
a
where o denotes Hadamard power, i.e., element-wise power. The recursion will stop until b converges.
The proof is in Appendix C and the pseudo-code is shown in Alg The efficiency analysis is in the 5.3 In practice, rather than solving the P2OT for the entire dataset, we implement a mini-batch approach and store historical predictions memory buffer stabilize optimization.
EXPERIMENTS
EXPERIMENTAL SETUP
Datasets. To evaluate our method, we have established a realistic and challenging benchmark, including CIFAR100 (Krizhevsky al. 2209). ImageNet-R (abbreviated ImgNet-R) (Hendrycks) jet al.) 202T) and iNaturalist0118 (Van Horn et al., 2018) datasets. To quantify the level of class imbalance, we introduce the imbalance ratio denoted as R, calculated the ratio of Nmaz Nuins
5

---

Published as a conference paper at ICLR 2024
Algorithm 1: Scaling Algorithm for POOT
Input:
Cost matrix
log P. e, A. P. N, K. a large value
C <- log P. Ox],
À x (A.,, X,4]
3 + $ k
p
a + IlN
1K+1: M - expl(C/ee) f A
Atc
while not converge do
Mb 1f
b
end
Q 4 diag a) (d)ag(() return Q[,: K]
where Nmar represents the largest number of images in a class, and N represents the smallest. For CIFARI00, 100, as in (Cao et al. (201)), we artificially construct long-tailed CIFARI00 dataset with an imbalance ratio of 100. For ImgNet-R, which has renditions of 200 classes resulting in 30k images and is inherently imbalanced, we split 20 images per class as the test set, leaving the remaining data as the training set (R = 13). Note that the data distribution of ImgNet-R different from the ImageNet, which is commonly used for training unsupervised pre- pre-trained models, posing great challenge to its clustering. Consequently, ImgNet-R serves as a valuable resource for assessing the robustness of various methods. Furthermore, we incorporate the iNaturalist2018 8 dataset, natural long-taile dataset frequently used in supervised long-tailed learning (Cao et al., 2019 Zhang et al., (021b). This dataset encompasses 8, 142 classes, posing significant challenges for clustering. To mitigate this complexity, we extract subsets of 100, 500, and 1000 classes, creating the iNature 100 (R = 67), iNature500 (R = 111), and iNature 1000 (R = 111) datasets, respectively. iNature (00ture1001 is the subset of iNature500, and iNature500 is the subset of iNature 1000. The distribution of datasets is in Appendix We perform evaluations on both the imbalanced training set and the corresponding balanced test set. Note that we do not conduct experiments on ImageNet datasets because the unsupervised pretrained models have trained on the whole balanced ImageNet.
Evaluation Metric. We evaluate our method using the clustering accuracy (ACC) metric averaged over classes, normalized mutual information (NMI), and Fi-score. We also provide the adjusted Rand index (ARI) metrics, which is not a suitable metric for imbalanced datasets, in Appendix H To provide a more detailed analysis, we rank the classes by size in descending order and divide the dataset into Head, Medium, and Tail categories, maintaining ratio of 3:4:3 across all datasets. Then, we evaluate performance on the Head, Medium, and Tail, respectively.
Building upon the advancements in transformer (Dosovitskiy et al. 2020) and unsupervised pre-trained models (He et al. 2022). we conduct experiments on the ViT-B16 B1. which is pre-trained with DINO (Caron al. 2021). To provide a comprehensive evaluation, we re- e--imlleeen most methods from the existing literature, including the typical IIC (Ji et al.) 2019),
Implementation Details.
PICA (Huang et al. (2020), CC (Li et al. 20211) SCAN (Van Gansbeke et al. 2020), strong two-stage based SCAN* # (Van Gansbeke et al.) (020) and SPICE (Niu et al.) 2022). and the recently proposed DivClust (Metaxas al.] (023). In addition, we also implement BCL (Zhou et al.) (022b), which is specifically designed for representation learning with long-tailed data. It is important to note that all of these methods are trained using the same backbone, data augmentation, and training configurations to ensure a fair comparison. Specifically, we train 50 epochs and adopt the Adam optimizer with the learning rate decay from 5e-4 to 5e-6 for all datasets. The batch size is 512. Further details [F] For hyperparameters, we set À as 1, as 0. and initial p as 0.1. The stop criterion of Alg is when the change of b less than 1e-6, or the iteration reaches 1000. We utilize the loss on training sets for clustering head and model selection. For evaluation, we conduct experiments with each method three times and report the mean results.
can be found in Appendix
5.2
MAIN RESULTS
In [ we provide comprehensive comparison of our method with existing approaches on various imbalanced training sets. The results for iNature 1000 and balanced test sets can be found in Appendix H On the relatively small-scale CIFAR 100 dataset, our method outperforms the previous by achieving an increase of 0.9 in ACC, 0.3 in NMI, and 0.6 in Fl score. On the ImgNet-R R datasets, our method demonstrates its effectiveness with significant improvements of 2.4

---

Published as a conference paper at ICLR 2024
Table Comparison with SOTA methods different imbalanced training sets, shown in boldface, and the next best results are indicated with an underscore.
The best results are
CIFART00
ImgNet-R NMI
iNature100
iNature500
Method
ACC
NMI
F1
ACC
F1
ACC
NMI
F1
ACC
NMI
Fi
DINO
36.6
68.9
31.0
20.5
39.6
22.2
40.1
67.8
34.2
29.8
67.0
24.0
BCL
35.7
66.0
29.9
20.7
40.0
22.4
41.9
67.2
35.4
28.1
64.7
IIC
27.3as1
65.0-18
23.0:26
18.7
39.6.1.1
15.9
28.5=16
63.9=10
22.2+12
13.1aa8
58.4a0.5
7.1
PICA
29.8.ns
59.9202
24.0ga2
12.6,0.
34.0zno
12.1
34.8.24
54.8206
23.8a12
16.320a
55.9
11.3an.1
SCAN
37.2-09
69.4-o4
31.4.07
21.8
42.6.0.5
21.7.0s
38.7.uu
66.3-05
28.4.00
29.0
66.7.e.
21.6.0.
SCAN
30.2.na 68.5_2a
25.4
23.6
44.1
22.8
39.5.m4
68.5
30.7
19.0
65.9
12.540.
CC
29.0=aa 60.7-06
24.6s05
12.1
30.5
11.2a0s
28.2.24
56.1-12
20.6
16.5
55.5+60
12.3
DivClust
31.820a
64.0_o4
26, 10.
14.8
33.920.
13.8
33.7
59.3
23.3
17.2
56,4
12.5
P'TT
38.2.us
69.6
32.0.cm 20.
25.9
45.7
27.3
44.2.1
67.0
36.9
32.2
67.2
25.2
CIFAR10O, R-100
ImgNettRR R-13
INature100, R-67
INstureSoo, R-111
30
50
25
10
Head
Medium
Tail
Head
Medium
Tal
Head
Medium
Tail
Head
Medium
Tail
SCAN
SCAN"
PICA
CC
DivClust
PlOT
Figure 1: Head, Medium, and Tail comparison on several datasets.
PICA
SCAN
DivClust
pOTT
Figure 2: The T-SNE analysis on iNature 100 training set.
in ACC, 1.6 in NMI, and 4.5 in Fl score, highlighting its robustness in out-of-distribution scenarios. When applied to the fine-grained iNature datasets, our approach consistently delivers substantial performance gains across each subset in terms of ACC and F1 scores. Specifically, on ACC, we achieve improvements of 5.9 on iNature 100 and 3,4 on 5Nature500. On the F1 score, we obtain improvements 1.5 and 1. on the two datasets, respectively. improvement 500 but 1.5 decrease on iNature 100. It's worth noting that our method is an efficient one-stage approach, unlike SCAN* which is a two-stage ascudo-labeling- -bsedd method. Additionally, another pscudo-labeling labeling-based method, SPICE, exhibits degenerate solution in the imbalance scenario (see Appendix FF. Those results indicate the naive pseudo-labeling methods encounter great challenge and demonstrate superiority in handling imbalance scenarios.
terms of NMI, we observe 0.6
In addition, we provide a detailed analysis of the results for the Head, Medium, and Tail classes, offering
comprehensive understanding of method's performance across different class sizes. As depicted in Fig. [ our improvements are predominantly driven by the Medium and Tail classes, especially in challenging scenarios like ImgNet-R and iNature500, although our results show some reductions in performance for the Head classes. These results highlight the effectiveness of our P'OT algorithm in generating imbalance-aware pseudo-labels, making particularly advantagcous for the Medium and Tail classes. Furthermore, in Fig we present T-SNE (Van der Maaten & Hinton 2008) comparison of features before the clustering head. The T-SNE results illustrate our method learns more distinct clusters, particularly benefiting Medium and Tail classes.
5.3 ABLATION STUDY
Component Analysis. To assess the KL constraint and the progressive we conduct ablation experiments to analyze their individual contributions. As shown in Tab compare our full POTT method with three ablated versions: OT. POT and UOT. OT (Asano et al. 2020) imposes equality constraint cluster size and without the progressive p component, POT signifies the replacement of
7

---

Published as a conference paper at ICLR 2024
Table 2: Analysis of different formulations. SLA is proposed by Tai et 2021 in semi-supervised learning. OT (Asaoo et al. 2020), POT and UOT are variants of our POOT. POT substitutes the K L constraint with the equality constraint. UOT removes the progressive p.
CIFARIOO
ImgNet-R
iNature500
Formulation
Head
Medium
Tail
ACC
Head
Medium
Tail
ACC
Head
Medium
Tail
ACC
SL.A
3.26
1.00
6.33
OT
35.0
30.2
18.7
28.2
24.4
19.3
10.7
18.2
27.1
27.5
16.4
24.1
POT
39.6
42.9
14.5
33.4
25.5
23.3
17.6
22.2
31.7
32.7
19.7
28.5
UOT
43.4
42.5
19.6
35.9
27.7
23.9
14.6
22.2
32.2
29.0
18.3
26.7
POT
45.1
45.5
21.6
38.2
31.5
29.3
16.1
25.9
36.3
37.0
21.6
32.2
POT
UOT
P²OT
10
11
9 R 0 088.88888888888888 2888
O AARNNASS 9838848888
0 28 Prediction
Prediction
Figure 3: Confusion matrix on the balanced CIFARI00 test set. The two red rectangles represent the Medium and Tail classes.
CIFAR100
ImgNett-
INature500
(96)
10
30
10
30
40
10
20
40
precision
recall
weiighted_precissin
weighted recall
Figure 4: Precision, Recall analysis on train dataset with different training epoch. The weighted precision and recall derived by reweighting each sample by P²OT algorithm.
the KL term in the original P²OT formulation with a typical uniform constraint. UOT denotes the removal of the progressive component from the original P*OT formulation. Furthermore, we also compare with SLA (Tai al., 2021), which relaxes the equality constraint POT by utilizing an upper bound. However, due to this relaxation, samples are erroneously assigned to single cluster the early stages, rendering its failure for clustering imbalanced data. detail their formulation and further analysis in Appendix [ The results show POT and UOT both significantly surpass the OT, indicating that both of our components yield satisfactory effects. Compared to POT, we achieve improvements of 5.8, 3.8, and 3.6 CIFAR100, ImgNet-R, and 50ature500, respectively. Our improvement is mainly from Head and Tail classes, demonstrating that our P2OT with L constraint generate imbalanced pseudo labels. Compared UOT, realize gains of 2.3. 3.8, and 5.4 CIFAR100, ImgNet-R, and iN0ture500, respectively. Furthermore, as depicted in Fig the confusion matrix for the CIFARI remarkable results underscore the effectiveness of each component in our P²OT.
also validates our improvement on Medium and Tail classes. These
Pseudo Label Quality Analysis. To provide deeper understanding, conduct an analysis of the pseudo-label quality generated by our P"OT. We evaluate precision and recall metrics to assess the pseudo-label quality for the entire training set. Notably, our P*OT algorithm conducts selection through reweighting, rather than hard selection. Consequently, we reweight each sample and present the weighted precision and recall results. As depicted in Fig/4] weighted precision and recall consistently outperform precision and recall across different epochs. In the early stages, weighted precision and recall exhibit more rapid improvements compared precision and recall. However,
8

---

Published as a conference paper at ICLR 2024
Table Analysis of po and different ramp up function. Fixed denotes p as a constant value.
Sigmoid
Linear
Fixed
Po
0.00
0.05
0.1
0.15
0.2
0
0.1
0.2
0.1
0.2
CIFAR100
32.9
37.9
38.2
36.3
37.6
35.0
36.6
36.8
37.4
37.1
ImgNet-R
26.5
27.2
25.9
26.0
26.6
25.8
28.5
23.0
25.5
24.7
5N0ture500
32.6
31.7
32.2
32.8
32.9
31.9
32.0
30.5
29.9
30.3
Ours
Ours
1.50
1.25
5
10
40
0.1 0.2 0.3
0.5.0.6. 0.7
0.80.9
Number of Points (K)
Figure 5: Time cost comparison of our solver with Generalized Scaling Algorithm (GSA).
they eventually plateau around 10 epochs (p 0.15), converging gradually with precision and recall. The decline observed in weighted precision and recall over time suggests that our current ramp-up for p may not be necessary. We believe that the ramp-up
function may not be optimal, and raising strategy for p should be adaptive to the model's ' learning progress. In this paper, we have adopted typical sigmoid ramp-up strategy, and leave more advanced designs for future work.
Analysis of p. In our POTT algorithm, the choice of initial po and the specific ramp-up strategy important hyperparameters. In this section, we systematically investigate the impact of varying Po values and alternative ramp-up strategy. The term "Linear" signifies that p is increased to from Po using linear function, while "Fixed" indicates that p remains constant as Pa- The results in Tab provide several important insights: 1) Our method exhibits consistent performance across various Po values when using the sigmoid ramp-up function, highlighting its robustness on datasets like ImgNet-R and 500ture500; 2) The linear ramp-up strategy, although slightly less effective than sigmoid, still demonstrates the importance gradually increasing P during the early training stage; 3) The fixed p approach results in suboptimal performance, underscoring the necessity of having dynamically increasing p. These findings suggest that good starting value for Po around 0.1, and it should be progressively increased during training.
Efficiency Analysis. To demonstrate the efficiency of our solver, we perform a comparison between our solver and the Generalized Scaling Algorithm (GSA) proposed by (Chizat et al.) 2018). The pseudo-code of GSA is in Appendix K This comparison is conducted on iNaure 1000 using identical conditions (NVIDIA TITAN RTX, 0.1, 1), without employing any acceleration strategies for both. To ensure the comprehensiveness of our time cost analysis, we conduct experiments by average the time costs
varying both the number of data points and the o value. Subsequently, for different numbers data points across different o values and vice versa. The results presented the time cost of both methods increases near lincarly with the number of points; 2) as P approaches 1, the time cost of GSA increases rapidly due to the tightening inequality constraint, whereas our time cost decreases; as shown in the left figure, our solver is 2x faster than GSA. Those results demonstrate the efficiency of our solver.
in reveaal several insights:
CONCLUSION
In this paper, we introduce more practical problem called "deep imbalanced clustering," which aims learn representations and semantic clusters from imbalanced data. To address this challenging problem, we propose novel progressive PL-based learning framework, which formulates the pseudo- label generation as a progressive partial optimal transport (P²OT) algorithm. The P2OT enables us to generate high-quality pseudo-labed in an imbalance-awan and progressive manner, thereby significantly improving model learning and clustering performance. To efficiently solve the P'OT algorithm, we introduce virtual cluster and a weighted KL constraint. Subsequently, by imposing certain constraints, we transform our problem into an unbalanced optimal transport problem, which can be efficiently solved using scaling algorithm. Finally, extensive results the human-curatee long-tailed CIFAR 100 dataset, challenging ImageNet-R datasets, and several large-scale fine-grained iNature datasets validate the superiority of our method.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported by National Science Foundation of China under grant 62350610269, Shanghai Frontiers Science Center of Human-centere Artificial Intelligence, and MoE Key Lab of Intelligent Perception and Human-Machine Collaboration (ShanghaiTech University). We thank Wanxing Chang for her valuable and inspiring comments.
REFERENCES
Eric Arazo, Diego Ortego, Paul Albert, Noel D'Conoo, and Kevin McGuinness. Pseudo-laheling and confirmation bias in deep semi-supervised learning. In 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2020.
Yuki M. Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultaneous clustering and representation learning. In International Conference on Learning Representations (ICLR), 2020.
Ido Ben-Shaul, Ravid Shwartz-Ziv, Tomer Galanti, Shai Dekel, and Yann LeCun. Reverse engineering self-supervised learning. arXiv preprint arXiv:2305. 2023.
Luis A Caffarelli and Robert McCann. Free boundaries in optimal transport and monge-ampere obstacle problems. Annals of mathematics, pp- 673-730, 2010.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with dibrlldistribution-awaa margin loss. Advances in neural information processing systems, 32, 2019.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsuper- vised learning of visual features. In Proceedings of the European conference computer vision (ECCV), pp. 132-149, 2018.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in Neural Information Processing Systemx, 33:9912-9924, 2020.
Mathilde Caron, Hugo Touvron. Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties self-supervised vision transformers. Proceedings of the IEEE/CVF international conference computer vision, pp. 9650-9660, 2021.
Jianlong Chang, Lingfeng Wang, Gaofeng Meng. Shiming Xiang, and Chunhong Pan. Deep adaptive image clustering. In Proceedings of the IEEE international conference computer vision, pp. 5879-5887, 2017.
Wanxing Chang, Ye Shi, Hoang Tuan, and Jingya Wang. Unified optimal transport framework for universal domain adaptation. Advances in Neural Information Processing Systems, 35:29512- 29524, 2022.
Wanxing Chang, Ye Shi, and Jingya Wang. Csot: Curriculum and structure-aware optimal transport for learning with noisy labels. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Laetitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial optimal tranport with applications on positive-unlabeled learning. Advances in Neural Information Processing Systems, 33:2903-2913 2020.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2563-266 2609,, 2018.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
10

---

Published as a conference paper at ICLR 2024
Zhiyuan Dang, Cheng Deng, Xu Yang, Kun Wei, and Heng Huang. Nearest neighbor matching for deep clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 13693-13702, June 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
R Flamary, N Courty, D Tuia, and A Rakotomamonjy. Optimal transport for domain adaptation. IEEE Trans. Pattern Anal. Mach. Intell, 1:1-40, 2016.
Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learning with wasserstein loss. Advances in neural information processing systems, 28, 2015.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in neural information processing systems, 30,
2017.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 16000-16009, 2022.
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, Dawn Song, Jacob Steinhardt, and Justin Gilmer. The many faces of robustness: critical analysis of out-of-distribution generalization. ICCV, 2021.
Jiabo Huang, Shaogang Gong, and Xiatian Zhu. Deep semantic clustering by partition confidence maximisation. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
Zhizhong Huang, Jie Chen, Junping Zhang, and Hongming Shan. Learning representation for clustering via prototype scattering and positive sampling. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
Xu Ji, Joao Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp.
2019.
Ziyu Jiang, Tianlong Chen, Bobak J Mortazavi, and Zhangyang Wang. Self-damaging contrastive learning. In International Conference on Machine Learning, pp. 4927-4939, PMLR, 2021.
L. Kantorovich. On the transfer of masses (in russian). Doklady Akademii Nauk, 37:227-229, 1942.
Abdelwahed Khamis, Russell Tsuchida, Mohamed Tarek, Vivien Rolland, and Lars Petersson. Earth movers in the big data era: A review of optimal transport in machine learning. arXiv preprint arXiv:2305.05080 2023.
Philip A Knight. The sinkhorn knopp algorithm: convergence and applications. SIAM Journal on Matrix Analysis and Applications, 30(1):261-211 2008.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Dong-Hyun Lee al. Pseudo-label: The simple and efficient cemi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, pp. 896. Atlanta, 2013.
Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng. Joey Tianyi Zhou, and Xi Peng. Contrastive clustering. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 8547-8555, 2021.
Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropy-transper problems and new hellinger-kante kantorovich distance between positive measures. Inventiones mathematicae, 211(3): 969-1117,, 2018
11

---

Published as a conference paper at ICLR 2024
Hong Liu, Jeff Z HaoChen, Adrien Gaidon, and Tengyu Ma. Self-superviset learning is robust to dataset imbalance. 2022.
Yang Liu, Zhipeng Zhou, and Baigui Sun. Cot: Unsupervised domain adaptation with clustering and optimal transport. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 19998-20007, June 2023.
loannis Maniadis Metaxas, Georgios Tzimiropoulos, and Ioannis Patras. Divelust: Controlling diversity in deep clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3418-3428, 2023.
Chuang Niu, Hongming Shan, and Ge Wang. Spice: Semantic pseudo-labeling for image clustering. IEEE Transactions on Image Processing, 31:7264-7278, 2022.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport. Center for Research in Economics and Statistics Working Papers, (2017-86), 2017.
Meitar Ronen, Shahaf E. Finder, and Oren Freifeld. Deepdpm:
Deep clustering with unknown number of clusters. In Conference on Computer Vision and Pattern Recognition, 2022.
Timo Aila Samuli Laine. Temporal ensembling for sam-ssuper learning. International Confer- ence on Learning Representations (ICLR), 30, 2017.
Yuming Shen, Ziyi Shen, Menghan Wang. Jie Qin, Philip Torr, and Ling Shao. You never cluster alone. Advances in Neural Information Processing Systems, 14-27734-277466 2021.
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 cemi-supervised learning with consistency and confidence. Advances in Neural Information Processing Systems, 33:596-608, 2020.
Fariborz Taherkhani, Ali Dabouei, Sobhan Soleymani, Jeremy Dawson, and Nasser M Nasrabadi. Transporting labels via hierarchical optimal transport for semi-supervised learning. In Computer Vision ECConn-ECVVAA 2020: 16th European Conference, Glasgow, UK, August 23-28 2020, Proceedings, Part IV 16, pp. 509-526. Springer, 2020.
Kai Sheng Tai, Peter D Bailis, and Gregory Valiant. Sinkhorn label allocation: Semi-supervised classification via annealed self-training. In International Conference Muchine Learning, pp. 10065-10075. PMLR, 2021.
Yaling Tao, Kentaro Takagi, and Kouta Nakata. Clustering-friendly representation learning via
instance discrimination and feature decorrelation. In International Conference Learning Representations, 2020.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-aweraged consistency targets improve supi-supe deep learning results. Advances in neural information processing systems, 30, 2017
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Mare Proesmans, and Luc Van Gool. Scan: Learning classify images without labels. In Proceedings of the European Conference on Computer Vision, 2020.
Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The inaturalist species classification and detection dataset. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8769-8776 2018.
Cédric Villani al. Optimal transport: old and new, volume 338. Springer, 2009.
Chen Wei, Kihyuk Sohn, Clayton Mellina, Alan Yuille, and Fan Yang. Crest: A daaa-aebbl self-training framework for imbalanced sumi-super learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 10857-10866, June 2021.
12

---

Published as a conference paper at ICLR 2024
Bowen Zhang, Yidong Wang. Wenxin Hou, Hao Wu, Jindong Wang. Manabu Okumura, and Takahiro Shinozaki. Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling. Advances in Neural Information Processing Systems, 14.18408-18419, 2021a.
Chuyu Zhang, Ruijie Xu, and Xuming He. Novel class discovery for long-tailed recognition. Transactions on Machine Learning Research, 2023.
Songyang Zhang, Zeming Li, Shipeng Yan, Xuming He, and Jian Sun. Distribution alignment: A unified framework for long-tail visual recognition. In Proceedings the IEEE/CVF conference on computer vision and pattern recognition, pp. 2361-2370, 2021b.
Sheng Zhou, Hongjia Xu, Zhuonan Zheng, Jiawei Chen, Jiajun Bu, Jia Wu, Xin Wang. Wenwu Zhu, Martin Ester, et al. comprehensive survey on deep clustering: Taxonomy, challenges, and future directions. arXiv preprint arXiv:220.007559, 2022a.
Zhihan Zhou, Jiangehao Yao, Yan-Feng Wang, Bo Han, and Ya Zhang. Contrastive learning with boosted memorization. In International Conference on Machine Learning, pp. 27367-27377.
PMLR, 2022b.
13

---

Published as a conference paper at ICLR 2024
A EFFICIENT SCALING ALGORITHM FOR SOLVING OPTIMAL TRANSPORT
In this section, we detail how to solve the optimal transport by an efficient scaling algorithm. Let's recall the definition of optimal transport, given probability vectors μa m R as well as a cost matrix C E g defined on joint space, the objective function which OT minimizes follows:
min QERT X
(). + Fi(Q1n: (1) F2(Q"1m.2)) 1m.
(S19)
where Q E -I is the transportation plan, (,) denotes the Frobenius product, Fi, F2 are constraints on the marginal distribution of Q, which are convex, lower semicontinuous and lower bounded functions, and 1, E R=*1 1m E R=*l are all ones vector. To solve it efficiently, motivated by Cuturi (013)), we first introduce an entropy constraint, -Q) Therefore, the first term of
Equ. (S19) follows:
<Q C>p- = < Q C/c + log Q >F
(S20)
Q
= Q. log
>F
(S21)
exp( C/c)
=c (c)()
(S22)
The entropic optimal transport can be reformulated as follows:
min
ex. + (QQ,, μ)) + F2 (mm
(S23)
QER m X
Then, this problem can be approximately solved by an efficient scaling Alg where the proximal operator is as follows:
KL prox Ffc (z, (1) aargmnn F(x, (1) cXL(
(S24)
Intuitively, it is the iterative projection on affine subspaces for the KL divergence. We refer readers to (Chizat al. 2018) for more derivation. Consequently, for OT problems with any proper constraint, we can transform it into the form of Equ.(ST9) and derive the corresponding proximal operator, we can solve it with Alg 2 efficiently.
Algorithm 2: Scaling Algorithm for Optimal Transport
Input: Cost matrix C, e, m, n, M,
M Mexxp(-Ci) C/e)
1n while not converge do
prox RT.
(Mb, (MB(
paje (M a, w)/ (M²)
end
return diag(a) Mdiag
B PROOF OF PROPOSITION
In this section, prove the Proposition I Assume the optimal transportation plan of Equ. is
Q+, which can be decomposed [Q", {"], and the optimal transportation plan of Equ. is Q
Step We first prove E+ IN 1 p. To prove that, we expand the second KL term and rewrite it as follows:
K Σ 1 1N
Q 1Nls
T 1N
KL 1,,
+ *
IN log 1- p
(S25)
B
1=1
T P. 1x) AK+I T log
=XKI
IN.
(S26)
K
1- p
14

---

Published as a conference paper at ICLR 2024
Due to AK+1 + +00, if f Ly is not equal to 1- p, the cost of Equ. (4) will be +oo. In such case, can find more optimal Qt, which satisfies _ 1N 1 p. and its cost is finite, contradicting our assumption. Therefore, 1* 1 p. and KL(Q- 1N,
(QL 1N, 1N, k1x).
Step 2. We then prove Q', Q* are in the same constraint set. Due to
Q' Q'1k+11 [Q',"']]'""" = Q'1x + = 1N,
(S27)
and 5* 2 0, we know Q- 1x - 1x. Furthermore,
Q (²'xxx + E*) 1I +1 1,
(S28)
and 5x gT Tx N5 - p. we derive that
1 = 1 1 1N = 1 (1
(S29)
In summary, Q E (Ô- E BR Q^ S IN, 1 Q-11 =p}, which is the same lI in Equ. 5
Step 3. Finally, we prove Q' = Q-. According to Proposition 1
C |- log pN We plug
into Equ. and the cost of Q' is as follows:
()+ RI(Â* I,, (")* log P. (N])) + AKI(Q IN
P
1k)
(S30)
K
QQ' log P) AKL(Q 1N, P 1x)
(S31)
K
=C1
(S32)
And in Equ. (5. the cost for Q" is as follows:
(Q log P)r + AKT(Q* IN,
P 1x) C2 K
(S33)
From step 2. we know that Q*, Q are in the same set. Consequently, the form of Equ. S30 is the same as Equ. (S3), and in set II, (Q.-log log P)
XKL(Q 1N, f (1x) is convex function.
C1 = C2, due to is a convex function, Q = Q"
If C1 > C2. we can construct a transportation plan Q = [Q", <+] for Equ. 14). which cost is C2. achieving smaller cost than Q*, The results contradict the initial assumption that Q+ is the optimal transport plan. Therefore, C can not be larger than C2.
If C < C2 we can construct transportation plan Q' for Equ. which cost is C1 achieving smaller cost than Q The results contradict the initial assumption that Q* is the optimal transport plan. Therefore, C₁ can not be smaller than C2.
QQ'iie i.c. Q' = [Q",E*) We can derive Q* by omitting the last In conclusion, C1 C2 and Q* =Q,, column of Q'. Therefore, Proposition is proved.
C PROOF OF PROPOSITION 2
From the Appendix A we know the key to proving Proposition 2 is derive the proximal operator for F1, Fy. Without losing generality, we rewrite the entropic version of Equ. (14) in more simple and general form, which is detailed as follows:
min eK L(Q, exp( C/e)) + +KL(Q 1,, QEo
1N, 1,,
(S34)
+ = (Q NRRNKK QQ = =)
(S35)
In Eq4.(S3) the equality constraint means that F, is an indicator function, formulated as:
a
F Fx = + x., otherwise
(S36)
15

---

Published as a conference paper at ICLR 2024
Therefore, can plug in the above Fi Equ. (224), and derive the proximal operator for F1 is For the weighted KL constraint, the proximal operator is as follows:
KL prox F2/e (z, ()- argmin X (x 3, A) (x,
(S37)
x;
argmin
X,x; log
A + Br + Ex; log
ex; + Z;
(S38)
B
2i
X;
argmin
X log
X,x; + cx; log Zi
eX
(S39)
B
argmin
(A + c)x, logx, (A; log 3: + X; + e elog z; + c)x; (S40)
The first line to the second is that expand the unnormalized KT. The second line the third is that we omit the variable unrelated to x. The third line to the fourth line is that we reorganize the equation. Now, we consider a function as follows:
g(x) az log x bz
(S41)
Its first derivative is denoted as:
g' (x) a + log b Therefore, argmin,g(x) exp( b-q aa) According to this conclusion, know that:
(S42)
A log B: + clog
A
exp
Z
xits
(S43)
X +
And the vectorized version is as follows::
A
x= 2
(S44)
X+E
Finally, we plug in the two proximal operators into Alg
The iteration of a, b is as follows:
prox
KL. Fi/c
(Mb, <M/(Mb)=
(S45)
M.b
B oo
b prox F2/e
KL (M a, (MM a) = B (MM a) (12)-)/(Maa
a) -
(S46)
M a
Consequently, Proposition 2 is proved.
D MORE DISCUSSION ON UNIFORM CONSTRAINT
In deep clustering, the uniform constraint is widely used to avoid degenerate solutions. Among them, KL constraint is common feature in many clustering baselines, such as SCAN (Van Gansbeke et al. 2020), PICA (Huang et al., 2020). CC et 2021), and DivClust(Metaxar et 2023). These methods employ an additional entropy regularization loss term on cluster size to prevent degenerate solutions, which is equivalent to the KL constraint. Different from above, Huang et al. 2022) achieves uniform constraints by maximizing the inter-clusters distance between prototypical representations. By contrast, our method incorporates KL constraint in pseudo-label generation, constituting a novel OT problem. As demonstrated in our approach significantly outperforms these baselines.
E DATASETS DETAILS
Fig S6 displays the class distribution of ImgNet-R and several training datasets from iNaturalist 8. As evident from the figure, the class distribution in several iNature datasets is highly imbalanced. While ImgNet-R exhibits a lower degree of imbalance, its data distribution still presents significant challenge for clustering tasks.
F MORE IMPLEMENTATION DETAILS
In this section, we illustrate the implementation details of other methods.
16

---

Published as a conference paper at ICLR 2024
ImgNet-R
INature1 00
1000
300
Num of images
600
Num
150
200
25
100
125
150
175
200
20
80
Class Index
Class Index
INature500
INature1000
1000
1000
Num of images
Images
600
600
400
200
200
100
200
300
400
500
0
200
400
600
800
1000
Class index
Class index
Figure S6: The class distribution of different datasets.
F.1 DEEP CLUSTERING
In our study, we employed various methods, all utilizing the same datasets and finetuning the last block of ViT-B16. All methods are trained for 50 epochs due to convergence observation.
For our OT method, we use batch size of 512. To stabilize the mini-batch P*OT, We incorporate memory buffer queue of size 5120 for history prediction after the first epoch to stabilize optimization. During training, we apply two transformations to the same sample and cross-utilize the two pseudo- labels as supervision, thereby encouraging the model to maintain equivariance. We employ clustering heads the CIFAR 100 dataset and clustering head on others. The clustering heads designed with the sample cluster number as ground truth. Since the sum of sample weights in the pseudo label Q is p. we adjust the loss on training sets for the clustering head and model selection as C/p.
For IIC, we adopt their method (loss function) from GitHub They aim maximizing the mutual information of class assignments between different transformations of the same sample. In all experiments, we use a batch size of 512. We follow their over-clustering strategy, i.c.. using two heads, one matching the ground-truth cluster number and the other set at 200 for CIFAR 100 and iNature 100, 400 for ImgNet-R, and 700 for iNature500. We do not use over-clustering for iNature due to resource and efficiency considerations. Models from the last epoch are selected.
For PICA. we adopt their method (loss function) from GitHub Their basic idea is minimize cluster-wise Assignment Statistics Vector(ASVV cosine similarity. In our implementation, the batch size, over-clustering strategy, and model selection are the same as IIC above.
For SCAN, we adopt their code from GitHub For clustering, their basic idea is to make use of the information of nearest neighbors from pretrained model embeddings. We use a batch size of 512. Following their implementation, ImgNet-R. We use 1 head for iNature 1000 due to resource and efficiency considerations. While the authors select models based loss test sets, argue that this strategy may not be suitable as test sets are unavailable during training. For the fine-tuning stage of SCAN, they use high-confident samples to obtain pseudo labels. Following their implementation,
use 10 heads for CIFAR 100, iNature 100, iNature500, and
the confidence threshold
17

---

Published as a conference paper at ICLR 2024
of 0.99 CIFAR. On other datasets, we use the confidence threshold of 0.7 because the model is unable to select confident samples we use 0.99.
For CC, adopt their code from GitHub They perform both instance- and cluster-level contrastive learning. Following their implementation, we use a batch size of 128, and the models of the last epochs are selected.
For DivClust, we adopt their code from GitHub Their basic idea to enlarge the diversity of multiple clusterings. Following their implementation, use batch size of 256, with 20 clusterings for CIFAR 100, ImgNet-R, iNature 100, and iNature50.. We use clusterings for iNature 1000 due to resource and efficiency considerations. The models of the last epoch along with the best heads selected.
Table S4: SPICE accuracy on different datasets.
Dataset
CIFAR100
ImgNet-R
iNature100
iNature500
iNature1000
Imbalance ratio
100
67
111
111
SPICE
6.74
2.58
10.29
2.15
0.74
We also tried to implement SPICE from Gn imbalanced datasets. Given a pre-trained backbone, they employ two-stage training process: initially training the clustering head while keeping the backbone fixed, and subsequently training both the backbone and clustering head jointly. For the first stage, they select an equal number confident samples for each cluster and generate pseudo-labed to train the clustering head. However, imbalanced datasets, this strategy can easily lead degraded results as presented in Tab[S4] For example, for the medium and tail classes, the selected confident samples will easily include many samples from head classes, causing clustering head degradation. For the second stage, they utilize neighbor information to generate reliable pseudo-labels for further training. However, the degradation of the clustering head, which occurs result of the first stage's limitations, poses hurdle in the selection of reliable samples for the second stage, thus preventing the training of the second stage. For comparison with SPICE on the balanced training set, please refer to Sec
F.2 REPRESENTATION LEARNING WITH LONG-TAILED DATA
In the literature, (Zhou et al. 20226 Liu et al. 2022 Jiang et al. 2021) aims to learn unbiased representation with long-tit tailed data. For fair comparison, we adopt the pre-trained ViT-B16, finetune the last block of the ViT-B16 with their methods by 500 epochs, and perform K-means on representation space to evaluate the clustering ability. However, we exclude reporting results from (Liu et al., 2022, Jiang et al. 2021) for the following reasons: 1) (Jiang et al., (021) prunes the ResNet, making it challenging to transfer to ViT; 2) (Liu et al. (2022) has not yet open open-sourced the code for kernel density estimation, which is crucial for its success.
G ARI METRIC
Additionally, we report the results the Adjusted Rand Index (ARI) metric. Interestingly, on the imbalanced training set (Fig S5). methods like IIC and SCAN' tend to exhibit a bias toward head classes (Fig S7) and achieve very high ARI scores, even though they perform inferiorly compared to our method in terms of ACC and NMI. However, as shown in Fig S6] on the balanced test set, the performance of IIC and SCAN* relatively poor compared our method. This inconsistency in performance across different class distributions highlights that ARI can be sensitive to the distribution of data and may not be suitable metric in imbalance scenarios.
H MORE COMPARISON
iNature1000 dataset. As shown in ST the large-scale iNature 1000 dataset, our method achieves comparable results with Strong SCAN. Specifically, we achieve improvements of 0.5 in ACC and 0.3 in score, while there a slight decrease 0.6 in the NMI metric. It's important to note that aseudo-labeeing--eee methods face significant challenges in large-scale scenarios, as
18

---

Published as a conference paper at ICLR 2024
Training set distributtion
SCAN" prediction distribution
600
Num of ima
200
20
40
60
80
100
20
40
66
80
100
prediction distribution
prodiction distribution
Num of images
600-
100
Class index
Class index
Figure S7: Prediction distribution comparison of IIC, SCAN* and P²OT on CIFARI00.
Table S5: ARI Comparison with SOTA methods on imbalanced training datasets.
Dataset
CIFAR100 100
ImgNet-R
iNature 100
iNature500
iNature
Imbalance ratio
13
67
111
111
IIC
43.3
13.2
33.616.2
19.2
20.2
PICA
24.640.2
5.2
12.6.0.5
7.1
5.4
SCAN
34.7
13.5
18.2
13.6
14.3
SCAN"
50.0
15,8
21.040.4
27.6
28.0
CC
29.8
6.040.3
13.9
13.6
11.9
DivClust
29.0+1.1
7.140.2
14.2+t0.5
11.0
10.8
P²OT
36.9+1.3
16.0+0.7
23.140.5
14.3
12.6+0.2
Table S6: ARI Comparison with SOTA methods on balanced test datasets.
Dataset
CIFAR100 100
ImgNet-R 13
iNature 67
iNature500
iNature
Imbalance ratio
111
111
IIC
21.5+1.
11.640.9
16.9+1.7
7.7+0.4
4.4
PICA
19.9+0.5
5.240.00
17.643.4
6.440.3
3.640.2
SCAN
28.2+0.2
12.0+0.5
25.0+1.7
17.0=0.3
14.0+0.3
SCAN
21.7+18
13.940.1
27.7+0.6
11.1=0.6
5,840.2
CC
19.1
4.340.3
15.1+0.4
6.8+0.5
4.3
DivClust
21.3 21.3
5.5
19.2
8.0
4.5
P²OT
28.8+0.8
13.4008
29.7+1.7
18.9-0.4
14.2+0.7
generating high-quality pseudo-labels becomes increasingly difficult. Despite this challenge, our method demonstrates competitive performance in such challenging setting.
Results on the balanced test sets. As presented in Tab we conduct comprehensive comparison of our method with existing approaches on balanced test sets, validating their ability an inductive setting. On the relatively small-scale CIFAR 100 dataset, our method outperforms the previous state-of-the-art (SCAN) by margins of 1.4, respectively. demonstrates its effectiveness with notable improvement of 2.2, highlighting its robustness in out- of-distribution scenarios. On the fine-grained iNature datasets, our performance gains are substantial across each subset. Particularly. observe improvements of 5.2 iNature 100, 3.2 on iNature500, and 1.2 on iNature 1000. Note that SPCIE degrades in the imbalance scenario (see Appendix (F). and SCAN* performs worse than SCAN in some cases, indicating the ineffectiveness of naive
the ImgNet-R datasets, our method
19

---

Published as a conference paper at ICLR 2024
Table S7: Comparison with SOTA methods on NNature1000 training
iNature 1000
Method
ACC
NMI
F1
IIC
7.8
56.940.4
4.2+0.2
PICA
12.4
55.010.1
8.5
SCAN
26.240.2
68.0
19.6
SCAN#
10.5
63.910.5
6.410.2
CC
12.1+0.4
55.2+0.4
9.1+0.4
DivClust
13.0+0.2
56.040.3
9.5+0.2
POT
26.7
67.4+0.4
19,9.0.4
Table S8: ACC Comparison with SOTA methods on balanced test sets. SCAN* denotes performing another self-labeling training stage based on SCAN.
(Van Gansbeke et al.
2020
Dataset Imbalance ratio
CIFARI00
ImgNet-R
iNature500 1Nature100
INature1000
100
13
67
111
111
IIC
29.4=3.0
21.4+1.7
35.1
19.8
13.3_1.0
PICA
30.3
16.6+0.1
43.5
31.440.3
28.3
SCAN
37.5-0.3
23.8
44.0+0.9
39.0+0.1
36.5-0.3
SCAN*
30.5_o.6
25.2+0.1
44.8+0.7
24.3
14.5_0.2
CC
29.1 11.33
14.7
38.2+1.4
29.7
26.6
DivClust
31.8 31.8_0.6
16.840.3
42.4
31.6400.
26.9_o.1
P²OT
38.9
27.5
50.0
42.2
37.7
Table S9: NMI Comparison with SOTA methods on balanced test sets.
Dataset
CIFARI00 100
ImgNet-R
iNature 67
iNature500 111
iNature 1000
Imbalance ratio
13
111
56.0+
53,9
75.4+1.4
73.9
71.2+
PICA
54.5
51.940.1
78.2+1.5
79.7
80.0+..2
SCAN
63.0
57.0
80.8
83.4
84.2+
SCAN#
57.642.0
57.1
81.940.6
77.0
72.8
CC
54.2
48.5
76.3
78.3
78.7 10.2
DivClust
58.1
50.4
78.7
79.2
78.8+0.2
PPOT
63.1 10.8
58.0
83.010.9
84.3
84.410.2
Table S10: Fl Comparison with SOTA methods balanced test sets.
Dataset
CIFAR100 100
ImgNet-R
iNature 67
iNature500
iNature1000
Imbalance ratio
13
111
111
IIC
21.0+3.6
17.7+1.
25.7+22
10.6
5.0+0.7
PICA
28.2+0.6
16.6+0.2
38.7+3.5
28.3
26.0+
SCAN
34.9+0.4
23,8+0.9
36.5+1.1
33.3
31.8+0.4
SCAN
19.8+0.8
23.5+0.2
36,8+1.3
14.4-0.4
5.8+0.2
CC
25.6+1.3
14.2+0.4
32.4+0.6
26.5+14
23.9+0.8
DivClust
28.9
16.410.3
36.111.4
27.810.6
24.3
P2OT 35.9
28.1+1.3
44.242.1
37.2-1.4
33.0
self-labeling training. These strong results demonstrate the superiority of our method in fine-grained and large-scale scenarios.
The NMI and Fl result comparisons of our method with existing approaches presented in Tab S9 and Tab SIo For NMI, our method achieves comparable results with previous state-of-ther (SCAN) on the CIFARI00 100 and iNature 1000 datasets. On ImgNet-R, INature100, and 5Nature500, our method outperforms state-of ofetherrrt by ~ 1%. For F1, our method surpasses the previous method by large margin, demonstrating the effectiveness of our method in handling imbalance learning.
20

---

Published as a conference paper at ICLR 2024
Table S11: Comparision with SPICE on balanced training set
Fine Tune
Confidence Ratio
Time Cost(h)
CIFARTO0
Method
Backbone
ACC
NMI
ARI
SPICE,
ViT-B16
False
3.6
31.9
57.7
22.5
SPICE,
VIT-B16
True
6.7
60.9
69.2
46.3
SPICE
ViT-B16
False
>0
3.6
Fail
Fail
Fail
SPICE
VIT-B16
True
>0.6
6.7
Fail
Fail
Fail
SPICE
ViT-B16
True
0.5
21.6
68.0
77.7
54.8
Ours
ViT-B16
False
2.9
61.9
72.1
48.8
I COMPARISON AND ANALYSIS ON BALANCED TRAINING DATASET
To compare and analyze our method with baselines on balanced datasets, we conduct experiments using the balanced CIFAR100 dataset demonstrated in TTb Overall, have achieved superior performance on imbalanced datasets, and on balanced datasets, we have achieved satisfactory results. However, in balanced settings, we believe that it is bit unfair compare our proposed method to methods developed in balanced scenarios, which usually take advantage of the uniform prior.
Note that, imagenet-r and |Naturelist2018 subsets are inherently imbalanced, do not conduct experiments on them.
For all methods, we employ the ImageNet- IK pre-trained ViT-B16 backbone. Fine tune refers to the first training stage of SPICE, which trains the model on the target dataset using self-supervised learning, like MoCo. SPICE, corresponds the second stage of training, which fixes the backbone and learns the clustering head by selecting top-K samples for each class, heavily relying on the uniform distribution assumption. SPICE refers the final joint training stage, which selects an equal number of reliable samples for each class based on confidence ratio and applies FixMatch-like training. SPICE, the confidence ratio varies across different datasets. Time cost denotes the accumulated time cost in hours on A100 GPUs.
The observed results in the table reveal several key findings: I) Without self-supervised training on the target dataset, SPICE, yields inferior results; 2) SPICE tends to struggle without self-supervised training and demonstrates sensitivity to hyperparameters; 3) SPICE incurs a prolonged training time; 4) Our method achieves comparable results with SPICE, and inferior results than SPICE.
On imbalanced datasets, as demonstrated in Tab S4 SPICE encounters difficulties in clustering tail classes due to the noisy top-K selection, resulting in lack of reliable samples for these classes. In contrast, our method attains outstanding performance on imbalanced datasets without the need for further hyperparameter tuning.
In summary, the strength SPICE lies in its ability to leverage the balanced prior and achieve superior results in balanced scenarios. However, SPICE exhibits weaknesses: training, taking 21.6 hours and 7.45 times our training cost; 2) It requires meticulous tuning of multiple hyperparameters for different scenarios and may fail without suitable hyperparameters, while our method circumvents the need for tedious hyperparameter tuning: 3) It achieves unsatisfactory results on imbalanced datasets due to its strong balanced assumption.
necessitates multi-stage
In contrast, the advantage of our method lies in its robustness to dataset distribution, delivering satisfactory results on balanced datasets and superior performance on imbalanced datasets.
J FURTHER ANALYSIS OF POT, UOT AND SLA
In this section, provide comprehensive explanation of the formulations of POT, UOT, and SLA (Tai et al. 202I), followed by an analysis of their limitations the context of deep imbalanced scenarios. POT replaces the K constraint with equality constraint, and its formulation is as
21

---

Published as a conference paper at ICLR 2024
Algorithm 3: Generalized Scaling Algorithm for POOT
Input:
Cost matrix log c, A, P. K
C < log P
k TK,
N IN:
b - 1x. s e CCccc, 8 x
while not converge do
a - min( sMb 1)
b MM
Mb
end
return (ddag()):)
follows:
min (Q, log P)r QEIl
(S47)
s.t. [- E R
N
Q1k S
N N
Q f 1x. Q = ppp
(S48)
K
This formulation overlooks the class imbalance distribution, thus making it hard to generate accurate pseudo-labels in imbalance scenarios.
On the other hand, UOT eliminates the progressive and its corresponding formulation is denoted as follows:
Qeil min QQ, 1 log P) X 1N. K 1k)
(S49)
s.t. II (Q E Q1K
N 1s}
(S50)
UOT has the capability to generate imbalanced pseudo-labels, but it lacks the ability effectively reduce the impact of noisy samples, which can adversely affect the model's learning process.
SL.A (Tai et al. 2021), represented by Equ. SS5 relaxes the equality constraint using an upper bound b. However, during the early training stages when is smaller than the value in bl k1,, SLA tends to assign all the mass to single cluster, leading to a degenerate representation.
min Q log P) QEIl
(S51)
s.t. I= N Q1x & 1 IN S blk 1 = p}
(S52)
K GENERALIZED SCALING ALGORITHM FOR POT
We provide the pseudo-code for the Generalized Scaling Algorithm (GSA) proposed by (Chizat et al. 2018 in Alg 3
22


Reviews:
[{"review_id": "a2v9PkDSg6", "reviewer": "Reviewer_H8zS", "summary": "This paper aims to address deep clustering in an imbalanced scenario. In particular, the authors resort to partial optimal transport to gradually select imbalance-aware high-confidence samples based on pseudo-labels. The selected high-confidence samples are then considered as ground truth labelled data for supervised training. The proposed method has been evaluated in human-curated datasets and achieves superior results over baselines.", "questions": "1. A very popular real imbalanced dataset is REUTERS-10K[1], which is more challenging than the constructed dataset. How does the proposed method perform on REUTERS-10K?  \n2. In Eq. 3, the KL constraint is defined for the uniform distribution. Why it can be called an unbalanced OT problem?  \n3. The proposed method is defined for the whole dataset. How can it be implemented for a mini-batch scenario? In the mini-batch scenario, samples from minority clusters may not exist.  \n4. Figure 2 shows that the embedding of P2OT is well-separated compared to that of other baselines. Can the authors explain why the embedding is much better than others, given that it is only slightly higher than SCAN in terms of NMI?  \n5. Figure 4 shows that the performance degenerates after 10 epochs. Can you explain the reason behind this?  \n\n[1] Xie, Junyuan, Ross Girshick, and Ali Farhadi. \"Unsupervised deep embedding for clustering analysis.\" International conference on machine learning. PMLR, 2016", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1.\tThe proposed algorithm is overall reasonable. \n2.\tSufficient empirical results are conducted. \n3.\tThe performance over SOTA clustering baselines are impressive.", "weaknesses": "1. Some claims in this paper are confusing and need improvement. For instance, (i) \"the KL divergence-based uniform distribution constraint empowers our method to avoid degenerate solutions and generate imbalanced pseudo-labels\", \"demonstrating that KL constraint enables our P2OT to generate imbalanced pseudo labels.\" Why can the KL constraint generate imbalanced pseudo-labels, given that it is defined for a uniform distribution?\n2. I don't think Eq. 5-Eq. 6 are necessary. You can consider introducing Eq. 8 directly after Eq. 3 by introducing a virtual cluster. If I am wrong, please point it out.\n3. The technical contributions are overclaimed. It appears that the most important aspect of the proposed method lies in the KL constraints. If these KL constraints are added to other clustering baselines, the superiority of the proposed method will be marginal. Additionally, gradually increasing the number of high-confidence samples has been widely adopted in other clustering papers such as SPCIE. It is true that the proposed method can avoid manual selection, but it still introduces an additional hyperparameter in Eq. 7, i.e., $\\rho_0$. More importantly, it does not demonstrate the superiority over the baselines.\"", "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": "b85IY5BvNi", "reviewer": "Reviewer_xbkw", "summary": "This paper addresses the challenge of deep clustering under imbalanced data. The paper proposes a novel pseudo-labeling-based learning framework. This framework formulates pseudo-label generation as a progressive partial optimal transport problem, allowing it to generate imbalance-aware pseudo-labels and learn from high-confidence samples. The approach transforms the problem into an unbalanced optimal transport problem with augmented constraints, making it efficiently solvable. Experimental results on various datasets, including long-tailed CIFAR100, ImageNet-R, and iNaturalist2018 subsets, demonstrate the effectiveness of the method.", "questions": "1. Change 'confidence sample selection' to 'confident sample selection'\n2. Which dataset is used for DINO pretraining? Is the backbone fixed during training?\n3. It is unclear about the use of historical predictions.\n4. What is visualized in Figure 2? We usually visualize the features before the classifier instead of class predictions. If the results are consistent for the features, we can conclude: more distinct clusters.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies an interesting problem, deep clustering under imbalanced data. It proposed a progressive partial optimal transport algorithm to address this problem, and extensive experiments have been conducted to evaluate its effectiveness.", "weaknesses": "1. Great computational cost. In Figure 5, it takes 1 second to estimate the pseudo-labels when K=40. It is impossible in practice with a larger number of clusters, eg, imagenet, and mini-batch training.\n2. Missing comparisons on balanced datasets. The true data distribution is unknown in real-world applications. This paper only investigates the settings of imbalanced data or tests on balanced data. It is not well aligned with most literature of deep clustering.\n3. This paper does not learn representations, which may be confusing and needs to be clarified. In addition, this paper uses a large pre-trained model and lacks a simple baseline with representation learning models. For example, BYOL or DNIO pre-trained on ImageNet can be used to extract the representations for subsequent K-means clustering. In such settings, we do not need to determine whether the data is imbalanced, as each sample belongs to a single class or a large number of clusters can be pre-defined.\n4. A good evaluation metric should be important for imbalanced deep clustering. Under the imbalanced setting, no samples may be assigned to tail classes during Hungarian matching. As we can see in Figure S7, the predictions of the proposed method are more uniform than baselines. There are more samples assigned to tail classes, though this is not true in training data. It confirms that a uniform clustering result is beneficial for evaluation. I suggest that kNN evaluation in representation learning can be adopted for imbalanced clustering, without the need of Hungarian matching. Due to the uniform constraints, more discussion should be paid to Huang et al., 2022.\n\nAlthough I have raised many questions, I think this paper is interesting, and I will keep/increase my score if the authors have addressed my concerns.", "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": "43y1DekyeR", "reviewer": "Reviewer_qtAk", "summary": "This paper studied a more general clustering problem, deep imbalanced clustering. From the perspective of pseudo label generation, the authors propose a progressive partial optimal transport method to combat the imbalanced challenges in data. The technical way to incorporate the imbalanced distribution into the optimal-transport framework and align with the classical solver is appealing, and a range of experiments demonstrate the performance of the proposed method.", "questions": "1) The performance of P^2OT and SPICE on the balanced datasets.\n\n2) How is the performance comparison between the proposed deep imbalanced clustering and some self-supervised long-tailed learning methods in terms of the representation quality?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The technical point is good, which leverages a virtual cluster to incorporate the spirit of sample selection in optimal transport is novel. The authors applied a mass increasing process in the constraint of unbalanced OT to progressively leverage more confident samples for representation learning and avoids the degeneration due to the skew distribution.\n\n2) The reformulation with entropy regularization and the weighted the KL divergence makes the classical Sinkhorn-knop algorithm appliable and stably optimize the target towards the progressive imbalance constraint. The authors carefully deal with the reformulation to make the algorithm can sufficiently incorporate the desire for sample selection.\n\n3) The authors conduct a range of experiments on the representative datasets like small dataset CIFAR100-LT, the mid-scale ImageNet-R, and large-scale iNaturalist. The experimental results and the visualization consistently support the author's claim, and the ablation study provided the insight on how the components work and how useful they are.", "weaknesses": "Although the proposed method is overall novel, there are still some concerns that should be considered.\n1) The technical choice about Eq.(13) is unique. The other choice like introducing a hard equality constraint about the mass of the virtual cluster and applying the lagrange multiplier can be also possible. The main concern here is that the authors introduce two hyperparameters for weighted KL: one is for the target clusters, i.e., \\lambda, and the other is the large value for the virtual cluster.  How is the performance of directly constraining the equality about 1-\\rou with lagrange multiplier compared with Eq.(13).\n\n2) It is not clear why the authors have not compared with the clustering with self-labeling by Asano from the perspective of OT. For SPICE, the performance reported in the appendix is also not convincing. How is the performance comparison of SPICE and P^2OT on the balanced datasets. It will be provide more comprehensive comparison here on both imbalanced datasets and balanced datasets to show their pros and cons.\n\n3) In the perspective of representation learning, some related works should be included with the proper discussion, e.g., about the self-supervised long-tailed learning, like SDCLR [1], BCL [2] and re-weighted regularization, as they also target to representation learning of imbalanced data without label information. Some proper comparison will be better.\n\n[1] Jiang, Z., Chen, T., Mortazavi, B.J. and Wang, Z., 2021, July. Self-damaging contrastive learning. In International Conference on Machine Learning (pp. 4927-4939). PMLR.\n[2] Zhou, Z., Yao, J., Wang, Y.F., Han, B. and Zhang, Y., 2022, June. Contrastive learning with boosted memorization. In International Conference on Machine Learning (pp. 27367-27377). PMLR.\n[3] Liu, H., HaoChen, J.Z., Gaidon, A. and Ma, T., 2021. Self-supervised learning is more robust to dataset imbalance. In International Conference on Learning Representation, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)