AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation
Authors: Boyu Han
Qianqian Xu
Zhiyong Yang
Shilong Bao
Peisong Wen
Yangbangyan Jiang
Qingming Huang
Venue: NeurIPS 2024 poster (2024)
Keywords: Semantic Segmentation
Primary area: machine_vision

Abstract: The Area Under the ROC Curve (AUC) is a well-known metric for evaluating instance-level long-tail learning problems. In the past two decades, many AUC optimization methods have been proposed to improve model performance under long-tail distributions. In this paper, we explore AUC optimization methods in the context of pixel-level long-tail semantic segmentation, a much more complicated scenario. This task introduces two major challenges for AUC optimization techniques. On one hand, AUC optimization in a pixel-level task involves complex coupling across loss terms, with structured inner-image and pairwise inter-image dependencies, complicating theoretical analysis. On the other hand, we find that mini-batch estimation of AUC loss in this case requires a larger batch size, resulting in an unaffordable space complexity. To address these issues, we develop a pixel-level AUC loss function and conduct a dependency-graph-based theoretical analysis of the algorithm's generalization ability. Additionally, we design a Tail-Classes Memory Bank (T-Memory Bank) to manage the significant memory demand. Finally, comprehensive experiments across various benchmarks confirm the effectiveness of our proposed AUCSeg method. The code is available at https://github.com/boyuh/AUCSeg.

AUCSeg: AUC-oriented Pixel-level Long-tail
Semantic Segmentation
Boyu Han 1.2
Qianqian Xu Zhiyong Yang² Shilong Bao
Peisong Wen 1.2
Yangbangyan Jiang'
Qingming Huang 2,44
Key Lab. of Intelligent Information Processing. Institute of Computing Technology, CAS 2 School of Computer Science and Tech., University of Chinese Academy of Sciences Peng Cheng Laboratory
Key Laboratory of Big Data Mining and Knowledge Management, CAS fhanboyu23z, auqiaaqian, wenpei sonpeiisong202)@icc ac. cn, fyangzhiyong21, baoshilong, jaagggg.aannnnnnnnn langyangbangyan, gnhuang) &ucas ac
Abstract
The Area Under the ROC Curve (AUC) is well-known metric for evaluating instance-level long-tail learning problems. the past two decades, many AUC optimization methods have been proposed improve model performance under long-tail distributions. In this paper, we explore AUC optimization methods in the context of pixel-level long-tail semantic segmentation, a much more complicated scenario. This task introduces two major challenges for AUC optimization tech- niques. On one hand, AUC optimization in a pixel-level task involves complex coupling across loss terms, with structured inner-image and pairwise inter-image dependencies, complicating theoretical analysis. On the other hand, find that mini-batch estimation of AUC loss in this case requires a larger batch size, re- sulting in an unaffordable space complexity. To address these issues, we develop a pixel-level AUC loss function and conduct a dependency-gnge grapp-bbase theoret- ical analysis of the algorithm's generalization ability. Additionally, we design a Tuil-Classe Memory Bank (T--Memory Bank) to manage the significant memory demand. Finally, comprehensive experiments across various benchmarks con- firm the effectiveness of our proposed AUCSeg method. The code is available at https//gittub.combbyyl//AAA
Introduction
Semantic segmentation aims to categorize each pixel within an image into specific class, which a fundamental task in image processing and computer vision [33, 75]. Over the past decades, substantial efforts [58, 23, 43, 96] have advanced the field of semantic segmentation. The mainstream paradigm is to develop innovative network architectures that encode more discriminative features for dense pixel-level classifications. Typical backbones include CNN-based [58, 14, 80] and newly emerging Transformer-basee methods [108, 83, 65, 15, 32], which have achieved the state-of-the-an (SOTA) performance. Beyond this direction, researchers [24, 66, 48, 41] have recently realized the Pixel-level Long-tail issue in Semantic Segmentation (PLSS), as shown at the top of Figure 1. Similar the flaws of traditional long-tail problems, the major classes will dominate the model learning process, causing the model to overlook the segmentation of minority classes in an image. Several remedies have been proposed alleviate this [49, 61, 10, 56, 104, 92, 78]. For example, [77] introduces category-wiss variation technique inversely proportional to distribution to achieve balanced segmentation; [66] introduces sequence-based based generative adversarial network for imbal- anced medical image segmentation, and [41] develops a re-weighting scheme for semi-supervised segmentation.
"Corresponding authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Currently, mainstream studies fall into two camps. One is to develop carefully designed backbones for long-tail distributions but leave the effect of loss functions unconsidered. The other is to conduct empirical studies on the loss functions without exploring their theoretical impact on the generalization performance. question then arises naturally:
Can we find theoretically grounded loss function for PLSS top of SOTA backbones?
This paper provides an affirmative answer from the AUC perspective and proposes novel framework called AUC-oriented Pixel- level Long-tail Semantic Segmentation (AUC- Seg). Specifically, AUC indicates the likelihood that a positive sample scores higher than neg- ative one, which has been proven to be insen- sitive to data distribution [86, 101]. Applying AUC to instance-level long-tail classifications has shown promising progress in the machine learning community [86, 100, 88, 68]. Moti- vated by its success, this paper starts an early trial to study AUC optimization for PLSS. The primary concern is to study its effectiveness for PLSS from a theoretical perspective. The key challenge is that the standard techniques for gen- eralization analysis [62, 8, 21] require the loss function to be expressed as a sum of indepen- dent terms. Unfortunately, the proposed loss function does not satisfy this assumption due to the dual effect of structured inner-image de- pendency and pairwise inter-image dependency. This complicated structure poses a big challenge to understanding its generalization behavior. To address this, we decompose the loss function into inner-image and inter-image terms. On top of this reformulation, we deploy the dependency
log toytoppaaol Numboryy
Phead Cleaso
NNadde Claxate
Classo
100
miaii (86))
(Itead desol
AUC22g (Dum)
Oep
Label
Figure 1: Statistic information of pixel number for each class in the Cityscapes training set and the performance of previous methods (DeepLab V3+, HRNet and STDC) compared to our method (AUC- Seg). Our method aims to improve overall perfor- mance, particularly for tail classes. The dashed lines represent mIoU values for each class, while the solid lines represent the average mloU for the head, middle, and tail classes.
graph [103] to decouple the interdependency. Finally, we reach bound of Ō (Tvlog (TNK) /N
where 7 behaves like an indicator for imbalance degree, and denotes the number of pixels in each image. This suggests optimizing AUC loss could ensure a promising performance under PLSS.
Back to the practical AUC learning process, we realize that the stochastic gradient optimization (SGD) for structured pixel-level tasks imposes a greater computational burden compared to instance- level long-tail problems. Specifically, the SGD algorithm of AUC requires at least one sample from each class in each mini-batch [99, 85J. In light of this, the primary choice is to adopt the so-called stratified sampling on all images [70, 60, 86] for mini-batch generation (See Equation (7)). Unfortunately, as shown in Figure 3(a) and (b). this is hard to implement under PLSS because pixel-level labels are densely coupled in each image. Meanwhile, as shown in Proposition 1, we also argue that directly using random sampling include all classes would require extremely large batch size. This leads to unaffordable GPU memory demands for optimization, as described in the experiments in Appendix G.6.
To alleviate this, a novel Tail-class Memory Bank (T-Memory Bank) is carefully designed. The main idea is to identify those missing pixel-level classes in each randomly generated mini-batch and then complete these absences using stored historical class information from the T-Memory Bank. This enables efficient optimization of AUCSeg with a light memory usage, enhancing the scalability of our proposed method, as shown in Figure 1. Finally, comprehensive empirical studies consistently speak to the efficacy of our proposed AUCSeg.
Our main contributions are summarized as follows:
This paper starts the first attempt to explore the potential of AUC optimization in pixel-Ievel long-tail problems.
2

---

We theoretically demonstrate the generalization performance of AUCSeg in semantic segmentation.
To our knowledge, this area remains underexplored in the machine-learning community.
We introduce a Tail-class Memory Bank to reduce the optimization burden for pixel-level AUC learning.
Related Work
2.1 Semantic Segmentation
Semantic segmentation is subtask of computer vision, which has seen significant development since the inception of FCN [58]. The most common framework for semantic segmentation networks the encoder-decoder. For the encoder, researchers typically use general models such as ResNet [37] and ResNeXt [84]. As the segmentation tasks become more challenging, some specialized networks have emerged, such HRNet [75], ICNet [105], and multimodal networks [76, 42]. For the decoder, series of studies focus on strengthening edge features [23, 107], capturing global context [43, 31, 45], and enhancing the receptive field [96, 67, 12, 13]. Recently, the transformer has shown immense potential, surpassing previous methods. series of methods related to Vision Transformer [108, 83, 65, 15, 74] proposed. SegNeXt [32], which is the current state-of-the-ard (SOTA) method, possesses the same powerful feature extraction capabilities as the Vision Transformer and the same low computational requirements CNN. Apart from improving the network,
research [48, 56, 24, 11, 10, 66, 39] is directed toward addressing the issue of class imbalance semantic segmentation. However, the effectiveness of these methods not significant. In this paper, aim to improve the performance of long-tailed semantic segmentation from an AUC optimization perspective.
2.2 AUC Optimization
The development of AUC Optimization can be divided into two periods: the machine learning and the deep learning As pioneering study, [20] ushers in the era of AUC in machine learning. studies the necessity of AUC research, which points out that AUC maximization and eπrог rate minimization inconsistent. After that, AUC gains significant attention in linear fields such as Logistic Regression [38] and SVM [46, 47]. Then researchers begin to explore the online [106, 28) and stochastic [94, 63] optimization extensions of the AUC maximization problem. Research from the perspectives of generalization analysis [2, 73, 17] and consistency analysis [1, 29] provides theoretical support for AUC optimization algorithms. [57] is the first extend AUC optimization to deep neural networks, ushering in the era of AUC in deep learning. Meanwhile, series of AUC variants [87, 86, 68, 88, 69, 90] emerge, gradually enriching AUC optimization algorithms. Furthermore, in practice, AUC optimization demonstrates its effectiveness in various class-ing inss-immalanced tasks, such as recommendation systems [5, 6, 4, 7]. disease prediction [79, 30]. domain adaptation [89]. and adversarial training [40, 91].
Despite significant progress, existing studies of AUC optimization mainly pay attention to the instance- level imbalanced classification tasks. This paper starts an early trial to introduce AUC optimization to semantic segmentation. However, due the high complexity of pixel-level multi-class AUC optimization, such a goal cannot be attained by simply using the current techniques in the AUC community.
Preliminaries
In this section, we briefly introduce the semantic segmentation task and the AUC optimization problem.
3.1 Semantic Segmentation Training Framework
Let D [(X', ''), E HxW3 Y HxHWWX be the training dataset, where H and W represent the height and width the images, and K denotes the total number of classes. Let fa be semantic segmentation model (0 is the model parameters), which commonly follows
encoder-decoder backbone [75, 105, 108, 83, 32]. Let Y fo(X') Hx be the dense
3

---

pixel-level prediction, i.e.
=
where the encoder fü extracts features from the image X and then the decoder fä predicts each pixel based extracted features and outputs dense segmentation map with the same size Y
Furthermore, let Y u.v and Y u.y represent the ground truth and prediction of the (u, w)-th pixel of the i-th image, respectively. To train the model fg, most current studies [14, 80, 83, 65] usually adopt the cross-entropy (CE) loss:
H 1--W--
K yic a.
de un
lee
log
(2)
0=0
0=00
where Y a,e and Y Yu,, are the one-hot encoding of ground truth and the prediction of pixel (X) class c, respectively.
Yi,e)
3.2 AUC Optimization
Area under the Receiver Operating Characteristic Curve (AUC) is a well-known ranking performance metric for binary classification task, which measures the probability that a positive instance has higher score than a negative one [35]:
AUC(fe) (fo(x)) fo (X -.y
(3)
where (X* yyt and (X . represent positive and negative samples, respectively. When AUC' 1, it indicates that the classifier can perfectly separate positive and negative samples.
+
According [87, 86, 88], given finite datasets, maximizing AUC(ho) usually realized by maximizing its unbiased empirical estimation:
AUC(ho) n=
(Xho(X+) he (XT)),
where is a differentiable surrogate loss [86] measuring the ranking error between two samples, n and n denote the number of positive and negative samples, respectively.
Moreover, we can directly optimize the following problem for AUC maximization:
min
((h((X+)
)).
(5)
n
==1=1
Note that, AUC has achieved significant progress in long-tailed classification [100, 88, 68). Due to the limitations of space, we refer interested readers to the literature [86, 99] for more introductions to AUC. However, most existing studies merely focus on the instance-level or image-level problems. Inspired by its iastributiinninsensitti property [26], this paper starts an early trial to introduce AUC to PLSS.
4 AUC-Oriented Semantic Segmentation
In this section, we introduce our proposed AUCSeg method for semantic segmentation. A brief overview provided in Figure AUCSeg generic optimization method that can be directly applied to any SOTA backbone for semantic segmentation. Specifically, AUCSeg includes two crucial components: (1) AUC optimization where theoretically grounded loss function explored for PLSS and (2) Tail-class Memory Bank, an effective augmentation scheme to ensure efficient optimization the proposed AUC loss. In what follows, we will go into more detail about them. For clarity, we include table of symbol definitions in Appendix A.

---

Training Batch
Ground Trugh
Store
Image
road
vegelation
rider
Sumple
Branch
T-Memory Bank
Input
Memory Branch
Augmented Batch
traffic light
bus
rider
hicycle
Ground Truth
Tail Classes
Imagee
Somple
Outpur
Rano
Retrieve
Resize
Branch
Encoder
AUC Optimization
AUC
Ground Truth*
Decoder
Prediction
+1
Maxiince AUIC
Ground Truth* Prodiction
laue
tce
Theoretical Result: (Z(()) - By Ro(o) (TV/log(-NB)).N
Figure 2: An overview of AUCSeg.
4.1 Pixel-level AUC Optimization
Semantic segmentation is a multi-class classification task. Therefore, to apply AUC, we follow popular multi-class AUC manner, i.e. the One vs. One (ovo) strategy [64, 34, 86], which is an average of binary AUC score introduced in Section 3.2. Specifically, on top of the notation of Section 3.1, we further denote DP {(X) u.u Y Ya,o)(
) E [1, n], u E [0, H 1], E [0, W - 1]} as the set of all pixels; the j-th element (j E [1, n x (H 1) x (W - 1)] D" abbreviated as (X). Yz)
for convenience. Given the model prediction fo (f( fo {(K)), Vc [K]. S [0, 1], where
p(() serves as continuous score function supporting class c, AU Cng calculates the average of seg
binary AUC scores for every class pair:
AU AOvo
AlCoe(fo)
(6)
K(K
c=1
AUCoC P(F X
YX c. YY
To this end, introduced in Section 3.2, the goal is to minimize the following unbiased empirical risk:
lave : 33
pe,e m,,
Well/N
sg
F''' EN. X.ENN
where we adopt the widely used square loss (x)(T) (1 (1= as the surrogate loss [29]; gc.e', ,m. == Exg (
p(c) (x :r (X = c} represents the set of pixels with label e in the set DP, and Wal denotes the size of the set.
(f(()) (XP)
4.2 Generalization Bound
In this section, we explore the theoretical guarantees of the AUC loss function in semantic segmenta- tion tasks and demonstrate that AUCSeg generalize well unseen data.
key challenge that standard techniques for generalization analysis [62, 8, 21] require the loss function to be expressed sum of independent terms. Unfortunately, the proposed loss function does

---

not satisfy this assumption because there are two layers of interdependency among the loss terms. On one hand, semantic segmentation can be considered a structured prediction problem [16], where couplings between output substructures within given image create the first layer of interdependency. On the other hand, the AUC loss creates a pairwise coupling between positive and negative pixels, so any pixel pairs sharing the same positive/negative instance are interdependent, resulting in the second layer of interdependency.
We present our main result in the following theorem and the proof is deferred to Appendix B.
Theorem 1 (Generalization Bound for AUCSeg). Let ED [D (f) be the population risk of ED (f). Assume F S (f X - H where H and W represent the height and width of the image, and K represents the number of categories. _ is the risk over i-th sample, and is μ- μ-Lipschitz with
respect the lo norm, (i.e. [|[(x) [( S p || yloo). There exists three constants A > B > O and C > O, the following generalization bound holds with probability at least 1 over a random draw of
if. i.i.d training data (at the image-level):
[ (1) -ED (2 [
8 N
Qannr + Quater
A Alg (2BpTNk
VN
1 N
4K(K -1)
+3
K
log
2N
where
48pr In
(c) mmax
2
ninner
Binter = 22 ==
max cE(K]
N
Tmmean
7mmx maxx n (x( pixel of class in image X.
(e)
(c)
n(x N = (D) k H W and ((e) represents the (0)
Temean
Remark 1. We achieve bound of δ ( log (TNA) /N indicating reliable generalization with
large training set. Here, t represents the degree of pixel-level imbalance. More interestingly. even though we have l classifiers for every single image, the generalization bound only has algorithm dependent on k suggesting that pixel-level prediction doesn't 't hurt generalization too much.
4.3 Tail-class Memory Bank
Motivation. Although we have examined the effectiveness of AUC for PLSS from the theoretical point of view, there is a practical challenge when conducting AUC optimization for semantic segmentation, discussed in Section Specifically, the stochastic AUC optimization, defined in Equation (7), requires at least one sample from each class in a mini-batch. In instance-level AUC optimization, recent studies [87, 86] often use stratified sampling technique that generates batches consistent with the original class distribution, as shown in Figure 3(a). Such a strategy will work well when each image belongs a unique category (say, 'Banana', 'Apple', or 'Lemon') ") in traditional classifications. Yet it cannot apply to pixel-level cases because each sample involves multiple and coupled labels, making hard split them for stratified sampling, as illustrated in Figure 3(b). Meanwhile, we also provide a bound (Proposition I) to show that simply adopting random sampling will suffer from an overlarge batch size B, making an unaffordable GPU memory burden.
Proposition 1. Consider dataset DD that includes images with K different pixel categories. Let represent the probability of observing a pixel with label in a given image. Randomly select B images from D as training data, where
log(E/K)
B=
log(1 min ps)
Then with probability least 1- 8, for any E [K], there exists X. in the training data that contains pixels of label c.
Remark 2. The proof is deferred to Appendix C. Proposition suggests that the value of B is inversely proportional to min; pt. Note that P; will be smaller as the long-tail degree becomes more

---

Instance-Level (Clasiffiaation)
Pixel-Level (Semantic Segmentation)
Head Class
Tall Class
Tall Cless
Datased
Thil-class
Memory
Bank
Banana
Apple
Lemon
Stratified
Sampling
Sampling
Sampling
Training Batch
Augmented
Training Batch
Batch
Missing
Indin buible
Pieels
tn Tail Class
Random
(a)
(c)
Figure 3: Instance-level and pixel-level task sampling.
severe, leading to larger B. For example, in terms of the Cityscapes dataset with K classes, assuming 8 = 0.01 and min; P; = 1%, B should be at least 759 to guarantee that each class of pixels appears at least once with a high probability. This results significant strain on GPU memory.
To address this, considering that the tail-class samples generally have less opportunity to be included a mini-batch and are often more crucial for final performance, we thus develop a novel Tail- class Memory Bank (T-Memory Bank) to efficiently optimize Equation (7) and manage GPU usage effectively. As depicted Figure 3(c), high-level ideas of the T-Memory Bank are as follows: I) identify missing tail classes of all images involved in mini- and 2) randomly replace some pixels in the image with missing classes based on stored historical class information in T-Memory Bank. In this sense,
obtain approximated batch-version of Equation (7), i.e.
K Σ
Laue=
Σ
Σ X ENNUU.
Ge m, Eg
(8)
WellWe
d'o ReRyy #OX,EN,NUT
where No. and To represent the set of pixels with label in the original image and those pixels stored in the T-Memory Bank, respectively: jo,e' m,n == lxg "ag
(X") m p(() (X")); x" represents the sample after replacing some pixels with tail classes pixels from the T-Memory Bank.
(()
Detailed Components. As shown Figure 2, T-Memory Bank comprises three main parts: (1) Memory Branch stores set with SM (the Memory Size) images for each tail class. We define the set as M (.M.)...,,Me,
), where C, {c:) so denotes the labels tail classes, and ne the total number of selected tail classes; (2) Retrieve Branch seleets pixels from the Memory Branch to supplement the missing tail classes and (3) Store Branch updates the Memory Branch whenever new image arrives. Algorithm I summarizes a short version of AUCSeg equipped with T-Memory Bank. Please refer to the detailed version in Appendix D. Note that we introduce CE loss as a regularization term for proposed AUCSeg, which is widely used in the AUC community [99] to pursue robust feature learning. Experiments demonstrate that the performance insensitive to the regularization weight X, shown in Figure 5d.
At the start of training, the Memory Branch empty. In this case, we only calculate the loss function for the classes present in the mini-batch, while the Retrieve Branch will not take any action. Meanwhile, the Store Branch will continuously append pixel data of tail classes to the Memory Branch. As the Memory Branch reaches its maximum capacity SM, adopt random replacement strategy to update the Store Branch (Lines to 6 in Algorithm I or Lines 6 to in Algorithm 2).
As the training process progresses, if the Memory Branch is not empty, the Retrieve Branch kicks in count the missing classes in each image of the mini-batch, denoted as Cmiss- It then calculates the number of classes needed to be added for optimization, Neample [|Cmiss] X Rs]. Here, we introduce a tunable sample ratio Rs to strike a trade-off' between the original and missing tail-class semantic information. Finally, it uniformly retrieves the corresponding pixels of Nsample missing classes from the Memory Branch, resizes them by the resize ratio Rn, and randomly selects positions to overwrite (Lines 7 to in Algorithm or Lines 13 to 18 in Algorithm 2).
7

---

Algorithm 1: AUCSeg Algorithm (Short Version)
Input: Training data D, number of tail classes ny, labels tail classes {cx) Memory Branch M = S.Mas...Mee J. memory size SM, sample ratio Rs. resize ratio Ra.
max iteration Taars batch size No.
Output: model parameters 0
for iter = 1 to T man do
2
Dg = {X,, Y.) + SampleBatch(D. No):
Cmiss C C. MissingT aaliainsssillllssssssssssss (DB):
Cmiss -Cisis
--for Cm in Ciiiee do L Extract pixels of class Cm from D3 and save them to Men + Random
>-for i == 1 to Cmiisl x Rs] do
Randomly choose Cu from Cmiss and sample pixels from Men. paste into DB +- SizeSSale(Sn):
Calculate Y, fo (X,) and é = lave + Aleei
10
Backpropagation updates t.
Discussions. We recognize that Memory Bank [82, 36] has achieved great success in deep learning. However, our T-Memory Bank behaves differently compared to earlier studies. The key difference is that the Memory Bank and T-Memory Bank are designed for different tasks. The goal of the previous Memory Bank is to facilitate the traditional classifications by storing instance-level original pixels for each object. This strategy is particularly beneficial for our PLSS task. Addi- tionally, the T-Memory Bank enables AUCSeg without substantially increasing GPU workload as well as the number of samples per mini-batch by selectively replacing non-essential pixels. Our experiments, detailed Appendix G.6, include a comparison of GPU overhead. For more discussion on the T-Memory Bank, please refer to Appendix E.
image-level features, while our T-Memory Bank specifically stores the
Experiments
In this section, describe some details of the experiments and present results. Due to space limitations, please refer to Appendix F, Appendix G and Appendix for an extended version.
5.1 Experimental Setups
The experiment includes three benchmark datasets: Cityscapes [19], ADE20K [109], and COCO- Stuff 164K [9]. We use SegNeXt [32] as the backbone for our model and the mean of Intersection over Union (mloU) as the evaluation metric. We compare our method with 13 recent advancements and 6 long-tail approaches in semantic segmentation. All the long-tail methods also SegNeXt as the backbone. To ensure fairness, we re-implement the listed methods using their publicly shared code and test them on the same hardware. Detailed introductions are deferred Appendix F.
5.2 Overall Performance
Table 1 shows the quantitative performance comparisons. We draw the following conclusions: First, most current algorithms perform poorly in long-tail scenarios. Specifically, performance drops sharply from head to tail classes. For instance, the performance gap for PointRend and OCRNet on the Cityscapes reaches up to 40%. Second, models using tail approaches generally achieve better results than those that do not. However, they still fail produce satisfactory outcomes. One possible reason is that these long- oaig-tail tail approaches focus on reweighting, giving too much attention to the tail classes and leading to overfitting. Additionally, our proposed AUCSeg method surpasses all competitors in most metrics. This success is due to the appealing properties of AUC. Our method consistently outperforms the runner-up by +1 21%, +0.75% 75%, and +0.38% tail classes mloU across the datasets. Overall mloU also improves by + +105%, + -0227, and +0.31 3... In some Hcad/Middle

---

Table I: Quantitative results on Cityscapes, ADE20K and COCO-Stuff 164K val set in terms of mloU (%). The champion and the runner-up are highlighted in bold and underline.
ADE20K
Cityscapes
COCO-Stuff 164K
Method
Overall
Head
Middle
Tail
Overall
Head
Middle
Tuil
Overall
Head
Middle
Tail
DeepLahVV3 [14]
EneNet [102]
32.12
75.34
51.60
26.32
71.34
91.62
60.76
63.03
27.31
49.89
30.41
23.09
FasPPNN [80]
29.78
74.20
49.44
23.86
63.97
90.37
52.43
51.22
28.37
50.60
32.52
23.96
EMANe [55]
32.83
75.77
50.03
27.36
70.93
91.69
60.61
61.97
28.48
49.73
29.97
24.85
DANet [27]
33.83
89.66
54.26
HRNet [71]
31.83
75.35
49.98
26.19 19
73.40
91.98
65.79
64.00
28.65
48.00
30.74
25.
OCRNet [97]
29.64
74.00
49:40
23.72
66.95
90.24
63.18
50.21
28.67
51.04
32.41
24.33
[93]
PointRend [50]
17.77
67.18
37.60
11.46
60.67
89.79
53.92
41.49
11.17
21.17
13.64
9.04
BiSeNotV2 [95]
10.26
60.38
28.72
4.10
73.04
92.00
63.52
64.93
10,30
34.96
12.71
5.92
[98]
STDC|25]
30.17
73.36
48.02
24.58
76.30
92.58
65.09
71.94
29.83
51.74
33.40
25.61
SegNeXi [12]
47.45
80.54
60.35
43,28
62.41
94.08
72.46
80.92
42.42
$7.05
41.71
40.33
[S[4
24.72
75.30
48.02
17.86
55.40
92. 16
52.52
26,
24.27
47.80
30.38
19.19
[6]]
LDAM [30]
33.11
74.06
51.26
27.65
65.95
92.72
69.27
40.17
42.39
56.85
41.59
40.34
Rocal Loss [56]
47.68
80.54
59.04
43.73
82.44
93.90
72.79
80.89
41.98
56.87
41.51
39.79
DisAlign [104]
48.15
80.33
59.14
44.31
81.94
93.61
72.12
80.36
42.10
55.20
41.24
40.28
BLV [7]
46.76
79.96
58.96
42.67
81.81
93.84
71.83
80.05
42.17
56.83
41,52
40.06
AUCSeg (Ours)
49.20
80,59
59:45
45.52
82,71
93.91
72.72
81.67
42,73
56.95
41,93
40.72
metrics, AUCSeg does achieve the best performance. Even in these cases, AUCSeg still secures the runner-up status. We analyze the performance trade-off between head and tail classes in Appendix H. These experimental results underscore the effectiveness of our proposed method. We further present the results for each tail class in Appendix G.I, and analyze the reasons for the varying performance improvements of tail classes across the three datasets in Appendix G.2.
Figure 4 displays the qualitative results on the Cityscapes validation set. Benefiting from our proposed AUC and T-Memory Bank techniques, AUCSeg segments objects in tail classes accurately. It correctly distinguishes between bicycles and motorcycles and successfully identifies distant traffic lights, which other methods overlook. More qualitative results be found in Appendix G.3.
5.3 Backbone Extension
In Section 5.1, we select the current SOTA Seg- NeXt as the backbone. Nevertheless, AUC- Seg can also adapt to other backbones, con- sistently delivering effective results. Table 2 presents the experimental results of AUCSeg when using DeepLabV3+, EMANet, OCRNet, and ISANet as backbones. These results re- veal significant improvements in both overall mloU and tail classes mloU with AUCSeg. No- tably, on ISANet, the increases are 5.54% and 6.49%. Moreover, AUCSeg enhances perfor- mance across various model sizes and different pixel-level long-tail problems, as detailed in Ap- pendix G.4 and Appendix G.4. This demon- strates the superiority of our propased AUC- Seg for long-tailed semantic segmentation.
Table 2: Results of AUCSeg using different back- bones in terms mloU (%).
Backbone
AUCSeg
Overall
Tail
31.95
26.01
DeepL.bbV3+
V
36.13
31.10
X
32.83
27.36
EMANet
V
36.32
31.39
X
29.64
23.72
OCRNet
34.82
29.75
X
29.53
23.64
ISANet
35.07
30.13
5.4 Ablation studies
We perform several ablation studies to test the effectiveness of different modules and hyperparameters. All experiments are conducted on the ADE20K validation

---

(a) Input
(b) Ground Truth
(c) Lb+++
(d) SegNeXt
(e) AUCSeg (Ours)
Figure 4: Qualitative results on the Cityscapes val set. Red rectangles highlight and magnify the image details the lower left corner.
50
50
48
68
Overa
meRu 2.45
Tail
Best
42
42
40
60
5g
(a) Memory Size (SM)
(b) Sample Ratio (Rs).
(c) Resize Ratio (Rn).
(d) The weight A.
Figure 5: Ablation Study on Hyper-Parameters
The Effectiveness of AUC Optimization and T-Memory Bank, Table details our step-by- step ablation study the AUC and T-Memory Bank components of AUCSeg. Compared to the baseline Seg NtXt, AUC enhances perfor- mance by +1.01 % and +1.42% in overall and tail classes. The T-Memory Bank further ad- dresses the imbalance issue, yielding improve- ments of +1.75% overall and +2.24% tail classes. Our results also show that employing T-Memory Bank without AUC yields no signif- icant improvements, underscoring the necessity of AUC Loss. More ablation experiments on the
Table 3: Ablation study on the effectiveness of
AUC Optimization and T-Memory Bank (TMB) in terms of mloU (%).
Model
AUC
TMB
Overall
Tail
SegNeXt Seg SegNeX++TMB AUCSeg
47.45
43.28
48.46
44.70
47.86
43.86
49.20
45.52
effectiveness of AUC optimization and TMB are deferred Appendix G.6, G.7, G.8, and G.9.
Ablation Study on Hyper-Parrameters Figure 5a ablates the maximum number of images stored per class in the Memory Branch, referred Memory Size (SM). For the ADE20K dataset, optimal performance occurs when S 5. and performance shows little sensitivity to changes in SM- Figure 5b ablates the Sample Ratio (Rs), the fraction of classes sampled from the Memory Branch relative to the total number of missing tail classes. Figure 5c ablates the Resize Ratio (RR), the scaling factor for the sampled pixels. For ADE20K, the best result is obtained when Rs 0.05 and RR = 0.4. A potential reason for their small value is that the original image is overwritten when Rs and R& are too large, resulting in poor training performance. Figure 5d ablates the weight À for tee and lauc, with À providing slightly better results. The influence of À on performance is minimal. Detailed results from this parammerrameter ablation study are available in Appendix G.10 and 1.11.
6 Conclusion
This paper explores AUC optimization in the context PLSS tasks. To begin with, we theoretically study the generalization performance of AUC-oriented PLSS by overcoming the two-layer coupling issue across the loss terms of AUCSeg therein. The corresponding results show that applying AUC optimization to PLSS could also enjoy promising performance. Subsequently, we propose a novel T- Memory Bank to reduce the significant memory demand for the mini-batch optimization of AUCSeg. Finally, comprchensive experiments suggest the effectiveness of our proposed AUCSeg.
10

---

Acknowledgments
This work was supported in part by the National Key R&D Program of China under Grant 2018AAA0102000, in part by National Natural Science Foundation of China: 62236008, U21B2038, U23B2051, 61931008, 62122075, 92370102, 62406305, 62471013 and 62476068, in part by Youth Innovation Promotion Association CAS, in part by the Strategic Priority Research Program of the Chinese Academy of Sciences, Grant No. XDB0680000, part by the Innovation Funding of ICT, CAS under Grant 1000000000, in part by the Postdoctoral Fellowship Program of CPSF under Grant GZB20240729 and GZB20230732. and in part by the China Postdoctoral Science Foundation under Grant No.2023M743441.
References
[1] Shivani Agarwal. Surrogate regret bounds for bipartite ranking via strongly proper losses, The Journal of Machine Learning Research, 15(1):1653-1674, 2014.
[2] Shivani Agarwal, Thore Graepel, Ralf Herbrich, Sariel Har-Peled. Roth, Michael Jordan. Generalization bounds for the area under the roc curve. Journal of Machine Learning Research, 6(4), 2005.
[3] Massih-Rees Reza Amini and Nicolas Usunier. Learning with partially labeled and interdependent data. Springer, 2015.
[4] Shilong Bao, Qianqian Xu, Ke Ma, Zhiyong Yang. Xiaochun Cao, and Qingming Huang. Collaborative preference embedding against sparse labels. In ACMMM, pages 2079-2087, 2019.
[5] Shilong Bao, Qianqian Xu, Zhiyong Yang. Xiaochun Cao, and Qingming Huang. Rethinking collaborative metric learning: Toward an efficient alternative without negative sampling. IEEE TPAMI, 45(1):1017- 1035, 2022.
[6] Shilong Bao. Qianqian Xu, Zhiyong Yang. Yuan He, Xiaochun Cao, and Qingming Huang. The minority matters: A diversity-promotie collaborative metric learning algorithm. In NeurlPS, pages 2451 2451-2464, 2022.
[7] Shilong Bao, Qianqian Xu. Zhiyong Yang. Yuan He, Xiaochun Cao. and Qingming Huang. Improved diversity-promottee collahorative metric learning for recommendation. IEFE TPAMI, 2024.
[8] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 3(Nov):463-482, 2002.
[9] Holger Caesar, Jasper Uijlings. and Vittorio Ferrari. Coco-stuff: Thing and stuff classes in context. In CVPR, pages 1209- 1209-1218. 2018.
[10] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datascts with label-distributiin-aaaaa margin loss. In NeurlPS, 2019.
[11] Robin Chan, Matthias Rottmann. Fabian Hüger, Peter Schlicht, and Hanno Gottschalk. Application of decision rules for handling class imbalance in semantic segmentation. arXiv preprint arXiv:1901.0833 2019.
[12) Liang-Chieh Chich Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L Yuille. Decplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. IEEE TPAMI, 80(4):834-848, 2017.
[13] Liang-Chies Chen, George Papandreou. Florian Schroff. and Hartwig Adam. Rethinking atrous convolu- tion for semantic image segmentation. arXiv preprint 3oi::1706.05587, 2017.
[14] Liang- Chich Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam. Encoder- decoder with atrous separable convolution for semantic image segmentation. ECCV, pages 801-818, 2018.
[15] Bowen Cheng, Ishan Misra, Alexander G Schwing, Alexander Kirillov, and Rohit Girdhar. Masked- attention mask transformer for universal image segmentation. In CVPR, pages 1290-1299, 2022.
[16] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A general framework for consistent structured prediction with implicit loss embeddings. JMLR, 21(98):1--66 67, 2020.
11

---

[17] Stéphan Clémençon, Gábor Lugosi, and Nicolas Vayatis. Ranking and empirical minimization of u-statistics. The Annals Statistics, 2008.
[18] MMSegmentation Contributors. MMSegmentation: Openmmlab semantic segmentation toolbox and benchmark. https://githu: www.cooooooooo /oe//oeenn-ee mm1 wwtttmmmmmaammmmmmaaeeeaea www.aaaammmmmmmemiiooooo 2020.
[19] Marius Cordts, Mohamed Omran, Scbastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Be- nenson, Uwe Franke, Stefan Roth, and Bernt Schiele. The cityscapes dataset for semantic urban scene understanding. In CVPR, pages 3213-3223, 2016.
[20] Corinna Cortes and Mehryar Mohri. Auc optimization vs, enor rate minimization. In NeurlPS, 2003.
[21] Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(1):1-49, 2002.
[22] Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: large-scale hicrarchical image database. In CVPR, pages 248 285, 2009,
(23] Henghui Ding, Xudong Jiang, Ai Qun Liu, Nadia Magnenat Thalmann, and Gang Wang. Boundary-aware feature propagation for seene segmentation. In ICCV, pages 6819-6829, 2019.
[24] Rongsheng Dong, Xiaoquan Pan, and Fengying Li. Denseu-net-based semantic segmentation of small objects in urban remote sensing images. IEEE Access, 7:65347-65356, 2019.
[25] Mingyuan Fan, Shenqi Lai, Junshi Huang, Xiaoming Wei, Zhenhua Chai, Junfeng Luo, and Xiaolin Wei. Rethinking bisenet for real-timo semantic segmentation. In CVPR, pages 9716 9725, 2021.
[26] Tom Fawcett. An introduction roc analysis. Pattern recognition letters, 27(8):861-874 2006.
[27] Jun Fu, Jing Liu, Haijie Tian, Yong Li, Yongjun Bao, Zhiwei Fang, and Hanqing Lu. Dual attention network for scene segmentation. In CVPR, pages 3146-3154, 2019.
[28] Wei Gao, Rong Jin, Shenghuo Zhu, and Zhi-Hua Zhou. One-pass aue optimization. In ICML, pages 906-914, 2013.
[29] Wei Gao and Zhi-Hua Zhou. On the consistency of auc pairwise optimization. arXiv preprint 16X45 2012.
[30] Damian Gola, Jeannette Erdmann, Bertram Müller-Myhson Heribert Schunkert, and Inke R König. Polygenic risk scores outperform machine learning methods in predicting coronary artery disease status. Genetic epidemiology, 44(2):125-138, 2020.
[31] Meng-Hao Guo, Zheng-Ning Liu, Tai-Jiang Mu, and Shi-Min Hu. Beyond self-attention: External attention using linear layers for visual tasks. IEEE TPAMI, 45(5):5436-5447, 2022.
[32] Meng-Hap Hao Guo, Cheng Ze Lu, Qibin Hou, Zhengning Liu, Ming-Ming Cheng, and Shi-Min Hu. Segnext: Rethinking convolutional attention design for semantic segmentation. In NeurlPS, pages 1140-1156. 2022.
[33] Meng-Hao Guo, Tian-Xing Xu, Jiang- Liu, Zheng-Ning Liu, Peng- Tao Jiang, Tai-Jiang Mu, Song- Hai Zhang, Ralph R Martin, Ming-Ming Cheng, and Shi-Min Hu. Attention mechanisms in computer vision: A survey. Computational visual media, 8(3):331-368, 2022.
[34] David Hand and Robert Till. simple generalisation of the area under the roc curve for multiple class classification problems. Machine learning, 15:1711886, 2001.
[35] James Hanley and Barbara McNeil. The meaning and use of the area under receiver operating characteristic (roc) curve. Radiology, 143(1):29-36, 1982.
[36] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, pages 9729-9738, 2020.
[37] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
[38] Alan Herschtal and Bhavani Raskutti. Optimising area under the roc curve using gradient descent. In ICML, pages 385-392, 2004.
[39] Md Sazzad Hossain, John M Betts, and Andrew P Paplinski. Dual focal loss to address class imbalance in semantic segmentation. Neurocomputing, 462:69 07:669-8,220 2021.
12

---

[40] Wenzheng Hou, Qianqian Xu. Zhiyong Yang, Shilong Bao, Yuan He, and Qingming Huang. Adaue: End-to-end adversarial optimization against long-tail problems. In ICML, pages 8903-8925, 2022.
[41] Hanzhe Hu, Fangyun Wei, Han Hu, Qiwei Ye, Jinshi Cui, and Liwei Wang. Semi-supervised semantic
segmentation via adaptive equalization learning. In NewrIPS, pages 22 22106-22118, 2021.
[42] Cong Hua, Qianqian Xu, Shilong Bao, Zhiyong Yang. and Qingming Huang. Reconboost: Boosting achiove modality reconcilement. In ICML, pages 19573- 19597, 2024.
[43] Zilong Huang, Xinggang Wang, Lichao Huang, Chang Huang, Yunchao Wei, and Wenyu Liu. Cenet: Criss-cross attention semantic segmentation. In ICCV, pages 603-612, 2019.
[44] Svante Janson. Large deviations for sums of partly dependent random variables. Random Structures & Algorithms, 24:234-248, 2004.
[45] Zhenchao Jin, Xiaowei Hu, Lingting Zhu, Luchuan Song, Li Yuan, and Lequan Yu. Idmet: Intervention- driven relation network for semantic segmentation. NeurlPS, 2024.
[46] Thorsten Joachims. support vector method for multivariate performance measures. In ICML, pages 377-38 -84, 2005.
[47] Thorsten Joachims. Training linear syms linear time. In SIGKDD, pages 217-226, 2006.
[48] Michael Kampffmeyer, Artt- Borre Salberg, and Robert Jenssen. Semantic segmentation small objects and modeling of uncertainty in urban remote sensing images using deep convolutional neural networks. In CVPR workshops, pages 1-9, 2016.
[49] Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label- imbalanced and group-sensitive classification under overparameterization NewrIPS, pages 18970-18983, 2021.
[50] Alexander Kirillov, Yuxin Wu, Kaiming He, and Ross Girshick. Pointrend: Image segmentation as rendering. In CVPR, pages 9799-9808. 2020.
[51] Fahad Lateef and Yassine Ruichek. Survey semantic segmentation using deep learning techniques. Neurocomputing, 338:321-348, 2019.
[52] Antoine Ledent, Yunwen Lei, and Marius Kloft. Improved generalisation bounds for deep learning through &o covering numbers. arXiv preprint a905: /24.90 /2430, 2019.
[53] Feiran Li. Qianqian Xu, Shilong Bao, Zhiyong Yang. Runmin Cong. Xiaochun Cao, and Qingming Huang. Size-invariang matters: Rethinking metries and losses imbalanced multi-object salient object detection. In ICML, pages 28989-29021, 2024.
[54] Shaojie Li and Yong Liu. Towards sharper generalization bounds structured prediction. In NeurlPS, pages 26844-26857, 2021.
[55] Li, Zhisheng Zhong, Jianlong Wa, Yibo Yang, Zhouchen Lin, and Hong Liu. Expectation- maximization attention networks for semantic segmentation. In ICCV, pages 9167-9176, 2019.
[56] Tsung- Yi Lin, Priya Goyal. Ross Girshick, Kaiming Hc, and Piotr Dollár. Focal loss for dense object detection. In ICCV, pages 2980-2900 2988, 2017.
[57] Mingrui Liu, Zhuoning Yuan. Yiming Ying, and Tianbao Yang. Stochastic auc maximization with deep neural networks. In ICLR, 2020.
[58] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmen- tation. In CVPR, pages 3431-3444 2015.
[59] Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. In ICLR, 2018.
[60] Xiangrui Meng. Scalable simple random sampling and stratified sampling. In ICML, pages 531-539,
2013.
[61] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In ICLR, 2020.
[62] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
13

---

[63] Michael Natole, Yiming Ying, and Siwei Lyu. Stochastic proximal algorithms for auc maximization. In ICML, pages 3710-3719, 2018.
[64] Foster Provost and Pedro Domingos. Tree induction for prohability-hased ranking. Machine learning. 52:199-215 2003.
[65] René Ranftl, Alexey Bochkovskiy, and Vladlen Koltun, Vision transformers for dense prediction. In ICCV, pages 12179-12188, 2021.
[66] Mina Rezaci, Haojin Yang, and Christoph Meinel, Recurrent generative adversarial network for learning imbalanced medical image semantic segmentation. Multimedia Tools and Applications, 79:21-22):15329- 15348, 2020.
[67] Olaf Ronneherger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assisted Intervention, pages 234-241, 2015.
[68] Huiyang Shao, Qianqian Xu, Zhiyong Yang, Shilong Bao, and Qingming Huang. Asymptotically unbiased instance-wise regularized partial auc optimization: Theory and algorithm. In NewrlPS, pages 38667-38679, 2022.
[69] Huiyang Shao, Qiangian Xu, Zhiyong Yang. Peisong Wen, Gao Peifeng, and Qingming Huang. Weighted roc curve in cost space: Extending auc to cost-sensitive learning. In NewrlPS, pages 17357-17368 2024.
[70] Ravindra Singh, Naurang Singh Mangat, Ravindra Singh, and Naurang Singh Mangat. Stratified sampling. Elements of survey sampling, pages 102-144, 1996.
[71] Ke Sun, Bin Xiao, Dong Liu, and Jingdong Wang. Deep high-resolution representation learning for human pose estimation. In CVPR, pages 5693-5703, 2019.
[72] Nicolas Usunier, Massih R Amini, and Patrick Gallinari. Generalization error bounds for classifiers trained with interdependent data. In NeurlPS, 2005.
[73] Nicolas Usunier, Massih Rezsa Amini, and Patrick Gallinari. A data-dependent generalisation error bound for the auc. In JCML Workshop, 2005.
[74] Haonan Wang, Qixiang Zhang, Yi Li, and Xiaomeng Li. Allspark:
Reborn labeled features from unlabeled in transformer for semi-supervised semantic segmentation. In CVPR, 2024.
[75] Jingdong Wang, Ke Sun, Tianheng Cheng, Borui Jiang, Chaorui Deng, Yang Zhao, Dong Liu, Yadong Mu, Mingkui Tan, Xinggang Wang. et al. Deep high-resolution representation learning for visual recognition. IEEE TPAMI, 43( 10):349933364, 2020.
[76] Yikai Wang, Xinghao Chen, Lele Cao, Wenbing Huang, Fuchun Sun, and Yunhe Wang. Multimodal token fusion for vision transformers. In CVPR, pages 12186-12195, 2022.
[77] Yuchao Wang, Jingjing Fei, Haochen Wang, Wei Li. Tiappegg Bao, Liwei Wu, Rui Zhao. and Yujun Shen. Balancing logit variation for long-tailed semantic segmentation. In CVPR, pages 19561-19573, 2023.
[78) Zitai Wang, Qianqian Xu, Zhiyong Yang, Yuan He, Xiaochun Cao, and Qingming Huang. A unified generalization analysis re-weighting and adjustmentt for imbalanced learning. NeurlPS, pages 48417-48430, 2023.
[79] Andrew Westcott, Dante Capaldi, David G McCormack, Aaron Ward, Aaron Fenster, and Grace Parraga. Chronic obstructive pulmonary disease: thoracic et texture analysis and machine learning to predict pulmonary ventilation. Radiology, 293(3):676 684, 2019.
[80] Huikai Wu, Junge Zhang, Kaiqi Huang. Kongming Liang, and Yizhou Yu. Fastfen: Rethinking dilated convolution in the hackhone for semantic segmentation. arXiv preprint arXiv: 1903. 1816, 2019.
[81] Yu-Huan Wu, Yun Liu, Le Zhang, Ming-Mingg Cheng, and Bo Ren. Edn: Salient object detection via doanmelly-dwnsampple network. IEEE Tip, 31:3125 3136, 2022.
[82] Zhirong Wu, Yuanjun Xiong. Stella X Yu. and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In CVPR, pages 3733-3742, 2018.
[83] Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, Jose M Alvarez, and Ping Luo. Segformer: Simple and efficient design for semantic segmentation with transformers. In NewrIPS, pages 12077- 12090, 2021.
14

---

[84] Saining Xie. Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaimingg He. Aggregated residual transforma- tions for deep neural networks. In CVPR, pages 1492-1500. 2017.
[85] Tianbao Yang and Yiming Ying. Auc maximization in the of big data and ai: A survey. ACM computing surveys, 55(8):1337, 2022.
[86]
Zhiyong Yang, Qianqian Xu, Shilong Bao, Xiaochun Cao, and Qingming Huang. Learning with multiclass auc: Theory and algorithms. IEEE TPAMI, 44(11):7747-7763 2021.
[87] Zhiyong Yang. Qianqian Xu, Shilong Bao, Yuan He, Xiaochun Cao, and Qingming Huang. When all we need is a piece of the pie: A generie framework for optimizing two-way partial auc. In ICML, pages 11820-11829, 2021.
[88] Zhiyong Yang, Qianqian Xu, Shilong Bao, Yuan He, Xiaochun Cao, and Qingming Huang. Optimizing two-way partial with an end-to-end framework. IEEE TPAMI, 2022.
[89] Zhiyong Yang. Qiangian Xu, Shilong Bao, Peisong Wen, Yuan He, Xiaochun Cao, and Qingming Huang. Auc-oriented domain adaptation: From theory to algorithm. IEEE TPAMI, 2023.
[90] Zhiyong Yang, Qianqian Xu, Xiaochun Cao, and Qingming Huang. Task-featurr collaborative learning with application to personalized attribute prediction. IEEE TPAMI, 43(1 ):4094-4100, 2020.
[91] Zhiyong Yang. Qianqian Xu, Wenzheng Hou, Shilong Bao, Yuan He, Xiaochun Cao, and Qingming Huang. Revisiting auc-oriented adversarial training with loss-agnostic perturbations. IEEE TPAMI, 2023.
[92] Zhiyong Yang, Qianqian Xu, Zitai Wang. Sicong Li, Boyu Han, Shilong Bao, Xiaochun Cao, and Qing- ming Huang. Harnessing hierarchical label distribution variations in test agnostic long-tail recognition. In ICML, pages 56624-56664, 2024.
[93] Minghao Yin, Zhuliang Yao, Yue Cao, Xiu Li, Zheng Zhang, Stephen Lin, and Han Hu. Disentangled non-local neural networks. ECCV, pages 191-207, 2020.
[94] Yiming Ying. Longyin Wen, and Siwei Lyu. Stochastic online aue maximization. In NeurIPS, 2016.
[95] Changqian Yu, Changxin Gao, Jingbo Wang. Gang Yu, Chunhua Shen, and Nong Sang. Bisenet v2: Bilateral network with guided aggregation for real-time semantic segmentation. IJCV, 129:3051-3068 2021.
[96] Fisher Yu and Vladlen Koltun. Multi-scale context aggregation by dilated convolutions. arXiv preprint 151 1.0112,, 2015,
[97] Yuhui Yuan, Xilin Chen, and Jingdong Wang. Object-contextual representations for semantic segmenta- tion. In ECCV, pages 173-190, 2020.
[98] Yuhui Yuan, Lang Huang, Jianyuan Guo, Chao Zhang, Xilin Chen, and Jingdong Wang. Ocnet: Object context for semantic segmentation. IJCV, 129(8)1--24 2021.
[99] Zhuoning Yuan, Zhishuai Guo, Nitesh Chawla, and Tianbao Yang. Compositional training for end-to-end deep auc maximization. In ICLR, 2021.
[100] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep auc maximization: A new surrogate loss and empirical studies on medical image classification. In ICCV, pages 3040-3049, 2021.
[101] Zhuoning Yuan, Dixian 7hu, Zi-Hao Qiu, Gang Li, Xuanhui Wang, and Tianbao Yang. Libauc: A deep learning library for x-risk optimization. In KDD, pages 5487-5499, 2023.
[102] Hang Zhang, Kristin Dana, Jianping Shi, Zhongyue Zhang, Xiaogang Wang, Ambrish Tyagi. and Amit Agrawal. Context encoding for semantic segmentation. CVPR, pages 7151-7160, 2018.
[103] Rui-Ray Zhang and Massih-Reza Amini Generalization bounds for learning under graph-dependence: survey. Machine Learning. pages 1-31, 2024.
[104] Songyang Zhang, Zeming Li, Shipeng Yan, Xuming He, and Jian Sun. Distribution alignment: A unified framework for long-tail visual recognition. In CVPR, pages 2361-22222 23700, 2021.
[105] Hengshuang Zhao, Xiaojuan Qi. Xiaoyong Shen, Jianping Shi, and Jiaya Jia. Icnet for real time semantic segmentation on high- resouuteoo images. In ECCV, pages 405 405-420, 2018
15

---

[106] Peilin ZHIAO, Steven CH HOI, Rong JIN, and Tianbo YANG. Online auc maximization. In JCML, pages 233-240, 2011.
[107] Mingmin Zhen, Jinglu Wang, Lei Zhou, Shiwei Li, Tianwei Shen, Jiaxiang Shang. Tian Fang, and Long Quan. Joint semantic segmentation and boundary detection using iterative pyramid contexts. In CVPR, pages 13666-13675. 2020.
[108] Sixiao Zheng. Jiachen Lu, Hengshuang Zhao, Xiatian Zhu, Zekun Luo, Yabiao Wang, Yanwei Fu, Jianfeng Feng. Tao Xiang, Philip Torr, Rethinking semantic segmentation from sequence-tor to-sequeenc perspective with transformers. In CVPR, pages 6881-688888888 6890, 2021.
[109] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba, Scene parsing through ade20k dataset. In CVPR, pages 633-641, 2017.
[110] Ding-Xuse Zhou. The covering number learning theory. Journal of Complexity, 18:739 -67999-777700 2002.
16

---

Contents
Symbol Definitions
18
B Generalization Bounds and Its Proofs
18
B.1 Preliminary Lemmas
18
B.2 Key Lemmas
19
B.3 Proof of the Main Result
22
Proof for Propositions of Tail-class Memory Bank
26
D Details of T-Memory Bank Algorithm
27
More Discussions about T-Memory Bank
27
E.1 Discussion on the Improved Version of Stratified Sampling
27
E.2 Discussion on Why the T-Memory Bank Works
28
E.3
Discussion on AUC and Contrastive Learning from the Perspective of the Loss Function
29
F
Additional Experimental Settings
30
F.1
Datasets
30
F22
Implementation Details
30
F3 Competitors
30
Additional Experimental Results
33
G.I Per-tail-class Results
33
G.2 Performance Differences Across Different Datasets
33
G.3 More Qualitative Results
34
G.4 Backbone Extension Different Model Sizes
35
G.5 Backbone Extension of Different Pixel-level Long-tal Problems
35
G.6 Spatial Resource Consumption
35
G.7 Results of Different AUC Surrogate Losses and Calculation Methods
36
G.8 Results of the Comparison Between PMB and TMB.
36
G.9 Results of Different Memory Bank Update Strategies
37
G.10 Detailed Results of the Ablation Study Hyper-Parameters
38
G.Il Results of the Ablation Study on the Impact Batch Size
38
H More Discussions About AUCSeg
39
Broader Impact
39
17

---

A Symbol Definitions
In this section, Table includes summary of key notations and descriptions in this work.
Table 4: summary of key notations and descriptions in this work.
Notations
Descriptions
Training datasct.
H/W
The height/wicth
images dataset D.
N
The number of image samples dataset D.
K
The total number of classes datasct D.
XX, Y.)
The i-th sample and its ground-truth in dataset D. where i E [1, X e RRiiiKK, Y FRRRRR The semantic segmentation model, where A is its parameter. The encodcr/decoder in the semantic segmentation model fo-
Jo
18/58
The prediction model fo. where V = fo(X') E RuxwxK
(X Y
The sample its ground truth/preddicion of the (M, 1)-th pixel pixel (X...r Y.,.) class
image.
Y
The ground-truth one-hot sescoding/predittinn
D
The set of all pixels in dataset D.
(X) V3)
The j-th element in Dr, where [1, x (H 1) (W 1]]-
19
The continuous score function supporting class c.
The pixels with label the DP, where N. (X = =).
LAI
The number of elements set A.
The Lipschitz constant.
The lower bound.
The pixels with lahel in the original image/those pixels stored the T-Memory Bank. The sample after replacing some pixels with tail classes pixels from the T-Memory Bank. classes.
The number
The labels of tail classes, where C. (ci)er
M
The Memory Brunch, where M [MM Me... b.
SM
The memory size.
Rs
The sample ratio. The resize ratio.
T Tmaa
The max iteration.
Nb
The batch size.
B Generalization Bounds and Its Proofs
B.1 Preliminary Lemmas
Lemma (Jensen's Inequality). If X is random variable and to is a convex convex function, then
(E [X) < (x))
(9)
Assumption 1. Assume that f j-Lipschitz continuous, that is (e) e (s) < p4/ s).
(10)
Assumption is a pretty mild assumption. The square loss Exg (x) = =01 -1-x)) satisfies Assumption
1.
Lemma 2. The empirical Rademacher complexity of function with respect to the predictor f is defined as:
Rg(g) = Es(sup JEF N
aig(f (f
(11)
where F X R is a family of predictors, and N refers to the size of the dataset, and a,s independent uniform random variables taking values in 1-1, +1). The random variables o, called Rademacher variables.
18

---

Lemma 3. Let [g] and E [g] represent the expected risk and empirical risk. and F S { Then with probability at least over the draw of an iid. sample S of size n, the generalization bound holds:
log 2
sup fer
[ -f) - 2R (g) 3V
(12)
2n
Definition (Fractional Independent Vertex Cover, and Fractional Chromatic Number [103]). Let graph be G 3 (V,
(1) A fractional vertex cover of G family (())) of pairs (F), where Fj S V(G). wj E (0, 1]. and EjNEF, 4j = 1, Vu E V(G).
(2) An independent set of G is set of vertices in G with no two adjacent. Let I(G) denote the set of independent sets of G.
(3) fractional vertex cover is a fractional independent vertex cover {(),,,)), of G if
1 E I(G).
(4) A fractional coloring of a graph G is mapping g .I(G) (0, such that EIEI 9(1) 2 Yv E V(G). The fractional chromatic number (G the minimum of the value Eier(o) g(T) over fractional colorings of G.
Notably, the minimum of Σj Wj over all fractional independent vertex covers ((1,,,y)} of the fractional chromatic number (G)).
Definition 2 (Dependency Graph [44]. An (undirected) graph G = (V, is called dependency
graph associated with a random vector (or random variables) x [x] (.l.,.... Tmm if
(1) (GG) = [m]]
(2) For all disjoint vertex sets J S [m], if I, are not adjacent in G, then random variables {x; her and jrybee are independent.
A useful result is Janson's 's decomposition property [44], which combines the concept of dependency graphs with fractional independent vertex covers. The property states that if interdependent random variables (i:))e(m) is associated with dependency graph G with fractional independent vertex cover W))W)))E(M)) (E()) then, the sum of the interdependent variables, can be equivalently decomposed into a weighted sum of sums of independent variables:
W/ lig
Wj Σ Dz.
(13)
1=1
ieL,
B.2 Key Lemmas
Lemma 4. Let D represents the training set, and +/- respectively denote the categories c/é'. The
function fes represents the score function for the (i.j)-th pixel in category c. For a set A, A denotes the number of elements in the set. We have:
d++)
EP
pc,e' auc
EN
Σ
Σ
pose' 60
Woll
F'NENe xHEN,
(14)
E XynDD
jimner
Tinter
X,, X
19

---

where,
DIn (X ) n (XT)
Eog
f(tt) Jesdi Frotle x, Y
Ginner
E
IN+ [-
[D]n (xt) n (Xi)
(fn-)Jexf
(62d2)EXX
[D( - 1)m (x+) n (x5)
log (1idd 12.22
x(+) X, Y
finter
Σ
I+
[D - 1)m (xt) n (x²)
(GJiJeX (62J2)EX,
and n (X+)) / /// (X-) represents the number of positive/negative samples in image X.
Definition 3 (Covering Number [110, 54]). Let F be class of real-valued fucntions, defined over a space 2 and S == {({1 Y1) y.... (X,. Y, E 2 of cardinality For any > O, the empirical -norm covering number N (F,) Ilso, S,c) w.r. S is defined as the minimal number m a collection of vectors vl, v E R" such that (v/ is the i-th component of the vector v
sup min (EFj=1,,.p I....
fX, Y.) - se.
Se.
(15)
In this case, we call {v) ..... vm) an (e, -ooerr of F w.r.t
Lemma
5. Let P(X) represents the pixels in image X. (+) {
F
{eo (X, E $) and fo F= ( {((St) (1,5) P(X), (X, E
(ofr()t (5()
EF}
According to
Definition 3, we have:
N M( SN 1o,0 S,e/See//// 22(2ppmax)
(16)
where Pmax max IPin(-t)n(X )x(x))
WilW
Proof. For any g lo f. can find g = to f that satisfies the following conditions:
l1g 9lloo.5 max (X,Y)ES
19(X, Y) (XX Y)
[D] (X+ n (X-)
Σ
1
Bog Exa]
max (X. Y)S
W+
n (XX+) nn
(NNdeX (Had))ee
(17)
(D) n (x
1
Csg Eag
max (X, X)SS)
W+II
(X n (X-)
(fxi)ex (fajz)EX
where
lsg log Log (frr (ittisstthee x,Y) leg (Fth), Aer
According to Assumption 1, we have:
Kmg
(+) (fa.) 1252 x, Y) lsg (+) ((-)
1252 :
1 x, Y)
(1ht) (X,Y) 1lt) (X, x))
(Aht), (X, Y) f(t) (x, Yi)
2 1
(fSt) (xY)) Att (X, Y) + (1tt), (X, Y) ,(t) (X, Y))
4
(18)
S μ
(X,Y) Al.). (X Y)
ftt) (X,Y) 11t), (X,
Y) (X,Y)
(X A1t) (X, Y)
[1(t (X, Y) -/St) (x, (x, Y)
= #
20

---

Denote p(x: by [x IPIx(x))n((-) Therefore, Wi 1V
l1g 3 S 2p max max (()) (x (iJ]eX
1i5 (X.Y) - -33 x)
a(t)
max max S 2ppmax
(x,))
(19)
(X.Y)ES (FJ))x
2/1pmax Ilf flloo.s.
where Pmax max (X).
X
Define 2ypPmax
covering of the class F with ||- lloe norm:
CN],
with
N - 1| 1,,,,,,,,
S, S.c/2ppmax)
(20)
There exists a fc.
(1 (1.5) E P(X)}. such that for
any
{[1+): (1.5) E(.)) EC
(1( f8g 2ppmaax
(21)
(i))EP(X)
which implies that
191 1g 2/4mmax 241pmax
(22)
(L.))E((X)
where gf = to I and gycr C fcz,
Denote
Cg. = 95
max 19, 195 Or-llccsse
(23)
(tx)))(X
then [C.,1: ... Cy.N) realizes an e-covering of f. Hence, the minimum size of the e-covering at most N. Mathematically, we then have:
(eo F, 1lll-
SN S 11 S,c/2ppmax)
(24)
This completed the proof.
Lemma 6 ([52)). Let FF be real-valued function class taking values in [0, 1). and assume that F. Let be a finite sample of size n. For any 2 S p S cc, we have the following relationship between the Rademacher complexity &i (F) and the covering number N (F, 11.11111 S,,,
4a + Vn ('' VlogN (F, S,.
R(F S inf as0
(25)
Lemma 7 ([72, 3)). Given a sample D = [(2,, })) where ā. E X, ÿr E 5 and is associated
with dependency graph G, where XG) is its fractional chromatic number, and a loss function
L X x x F + J0, M), where F F= [ X R). Then, for any (0, 1), the following generalization bound holds with probability at least 1 - 8:
Xr(G)
2 3
FEF S R (L F) 3M,
log
(26)
2m
where S o F) is the fractioal Rademacher complexity of the loss space.
Lemma Given a sample D = {(ā,, (:)): Ymm where ã, E X, ÿJ. 5 and D is associated with dependency graph G, where (G) is its fractional chromatic number, and each fractional independent vertex cover contains two independent samples, one positive and one negative. Under these conditions, Xx (G) satisfies:
(G) (2m
(27)
21

---

Proof. The calculation of the fractional chromatic number can be transformed into finding how many groups can be formed where each group contains m ordered pairs of positive and negative samples. In each group, each sample appears only once, and there are duplicate ordered pairs of positive and negative samples across all groups.
For example, in a dataset where 2m 4, there exist 6 groups:
Group 1: (1, (3, 4)
Group 2: (4,3)
Group 3: (1,3), (2, 4)
Group 4: (3, (4,2)
Group 5: (1, (2,3)
Group 6: (4, (3,2)
Therefore, X/(G) 6.
For 2m samples, we can extract A3m ordered pairs of positive and negative samples. Since these samples have an equal status in the dataset, they appear the same number of times among these A pairs.
After selecting the first group from these A2.. pairs, A2m. pairs of positive and negative samples remain. The frequency of each sample appearing in these remaining pairs remains equal.
We continue to select the second group, and so on, until the last group. The frequency of each sample the remaining pairs still remains equal.
Thus, we can find Alm. groups, i.e. xy(G)) 2(2m - 1).
This completed the proof.
B.3 Proof of the Main Result
Restate of Theorem (Generalization Bound for AUCSeg). Let ED (f) be the population risk of Cp (f). Assume F {f X " where H and W represent the height and width of the image, and K represents the number categories, _(0) is the risk over i-th sample, and y-Liischitz with respect to the lx norm, (i.e. ||((x) L(y) S u. || - sl) There exists three constants A >> 0, B > 0 and C 0, the following generalization bound holds with probability at least 1 over a random draw of i.i.d training data (at the image-level):
(2) Ed [2)
8 N
Thoner + Tinter
A Alog (2B +
VN
1
4K(K
+3 3
K
log
2N
N
where
48 In N
Tinter 2//T.
Maner
N
7 Fanax
max cE|K]
7mmx maxx n (xX()) ((), niaan = ΣN nxX! pixel of class in image X.
(c)
(1) N [D], k = H x W and ( represents the
Proof. First, we find that the calculation of pair-wise AUC requires both positive and negative samples. These two samples can come from the same image from two different images. Therefore,
22

---

we transform the original problem into two sub-proble teb-problems:
(f)- ED [DD
sup FEF
1
pe.e' anc
Σ
ED
poie" azve
K(K
K(K -
e,e
6,0
(Lem.1)
-
sup
pe.d' aave
EDD
(28)
K(K 1)
JEF
c.e'
(Lem.4)
1
sup feF
Ganner
E
pinner 4.-
sup fet
piater
ED
janter
K(K
Part
where +/ respectively denote the categories c/c.
For Part I, we use the complexity measure technique of the covering number.
Assuming log.N (FF, || |o S, E) I $ log -. [D] k C)2 where k H x W is the pixel count an image. A, B and C represent constants. Based on Lemma 5, we have:
log N (f 11,o, S,c) S log (F, 11. S,c2,/uausss
4A₁²²
Pinxx
log
2B
IDI.K+C
(29)
2
DD] n (X+) (X-)
Pmax
1
max max
D
n 7m
<
DD
where:
71 max
max n (XX*) XEX
71 max
max TI (i(X XEX
IDI
+
Σ n(X)),
mean
i=1
ID]
Σ n(X)),
71 Tmmean
2
[c)
and
max K][
Thraan
23

---

Denoted by a : S.ApPPmaxe b: = 2Bppmax ( k and c: C. Based on Lemma 6 and Lemma A.3 in [54], we have:
12
S. VlogN(eo 1l,0, S,e)de
9 (L
inf
4a
020
VIDI
12
Valog (b/e +c) de
inf 020
4a
VIDI
6 a log (b|2) + c)
(30)
4
12
de
D
VIDI DIIPD
4
12 [D]
aa log (b|D) c).
D
VIDI
Substituting this result into Lemma 3, with probability at least 1 - 6, we have
sup SEF
inner +,-
Ep
pinner +
(31)
log (<((K1)
8
48pT In [D] D
+
Alog (2Bur [D] C) +31
D
2 D
For Part 2, use the complexity measure technique of the fractional chromatic number and covering number.
According to Lemma 7, calculating the generalization bound only requires knowing the chromatic complexity. Based on Equation (13), we have
Å ()o [D] (1D) - 11) E,
Σ
W
sup fef (Ha32)el,
Σ
o
pl)))
(1i Poe
jE|j]
(32)
where p(x) ID((D)-1)x(X* )n() W II
and Wy denotes the weight assigned to the subset in the
fractional vertex cover.
Similar to Part 1, using the covering number get
Ri sup JeF (insh) (12.j2)el,
Σ (1)
70t)
S mmj.mj.
(33)
where we define cj as In2 [D] A n2, Prax -log 2B p. Pinxx |D]2 c) as cj. and define
my as |,,1.
24

---

Assume that the number of images in the dataset is even, i.e. |D] 0 (mod 2). We have:
A(oo F) ( - 1)
[E(J]
(D) -1) Σ
W Cj my
jE[M
X²(G)
Bjj
Xz(G) Vcm,
(D((D) - 1) jE(J]
VXr(G)
Σ
(34)
(2) 11)
JEIJ
Σ WymscJ
VXy(G) JE(J]
VIDI (I) 1)
[DI -)
Σ wyej
SEI
//DI/2
2((D) - 1)¹
where (+) follows the Lemma 8.
The second-order inequality based on the fact that:
R, Vcj mjj
(35)
define Plax the largest p in the j-th cluster, and that:
Vo = Pinax (loggBBuumaa (D]² k: + C)
[D] ( - 1) maxx
Alog(2B(PPmax 1D) k C)
W+
(36)
max maxx
A
(D]2 k + C?
Tmmean 7mmean
< r TV Alog(2B Dk++0
where:
max n(X ) XEX
max
71 max
max n(X XEA
IDI
m(X)),
mean
1=1
[D]
=] n(7)).
7 Amean
2
[e) max [K]
and T
Combining Equation (34) and Equation (36), we obtain:
1
(
TV A Algg(2BuT D k CC.
(37)
/2 /2
25

---

Based on Lemma and Lemma 8, it comes:
sup fer
pinter
ED
pinter
Xx(G)
4K(K -
29 (l 3M,
log
(38)
2m
8
2v2
[D]
4K(K 1)
TV Alog (2BuT D + 3K
log
VPD
Therefore, by combining Equation (28),Equation (31) and Equation (38), we can obtain: 2D (f) - Eo [20 (f)
Vinner
Tinter
V Aloog (2BuTNk+G C
N
VN
(39)
4K(K -
+
2N +
V Vogg
N
8
where Vnnner
484r Iu N
P/inter
2/22,, N |D] and k H W.
This completed the proof.
C Proof for Propositions of Tail-class Memory Bank
Restate of Proposition 1. Consider a dataset D that includes images with K different pixel categories. Let P; represent the probability of observing pixel with label in given image. Randomly select B images from DD as training data, where
log(8/K)
B=
log(1
min p;)
Then with probability at least 6, for any [K]. there exists X in the training data that contains pixels of label c.
Proof. Define event Aj the extraction of N images where the pixels of class j appear at least once.
Let pm = min(pi, : ,K), where m [K].
The probability that each category appears at least once when randomly selecting N images:
K
K
I
A
A
i=l
K
2 1
Σ
P (A:)
(40)
1=1
K
Σ -P)
2 K(1 - pm)
K
When
n A4
21 11-0 - 5,
8 82 K(1 Pm)
(41)
Therefore,
log(5/K)
log(5/K)
B Ω
(42)
log(1 pm))
log(1 min ps)
This completed the proof.
26

---

D Details of T-Memory Bank Algorithm
In this section, Algorithm 2 provides full version of Algorithm
Algorithm 2: AUCSeg Algorithm (Full Version)
Input: Training data D. number of tail classes ne, labels tail classes C, = {c) Memory Branch M (.Ma-..-MMa., }. memory size SM, sample ratio Rs, resize ratio Ra. max iteration Taa batch size No.
Output: model parameters 0
for iler = to maa do
DB = {X,, Y.) + SampleBatch( Nb);
Cmiss C C. Missing ailClaasess
Cmiss = C, Ciissi
Store Branch
for Cm in Ciiis do
Divide picture containing only the 7m class pixels from DB and name it P;
if [M Sa then
Add the divided image P to Mami else
10
11
Randomly replace an image in Mam with the divided image P;
12
Retrieve Branch
13
Nsample = [[Cmiss| x Rs]: for i to naample do
15
Randomly choose cm from Cmisei
Remove Cm in Cmissi
17
[MMM 전 then
Sample from Me.., scale according to Rn, paste randomly into Da;
Semantic Segmentation
20
xX)o(X;):
Calculate f f= = Alee with Equation (2) and Equation (8); Backpropagation updates 0.
22
E
More Discussions about T-Memory Bank
E.1 Discussion on the Improved Version of Stratified Sampling
In this section, we introduce the definition of the improved version of stratified sampling and explain why it is not applicable to the PLSS task.
The definition of the improved version of stratified sampling. The improved version of stratified sampling starts by grouping images according to their categories. Due to the multi-label nature, different categories may contain the same images. After that, stratified sampling is applied each category, making sure that even if an image is sampled more than once (as both head and tail), each mini-batch still includes least sample from every category.
Reasons for inapplicability to PLSS task. Conventional stratified sampling can hardly cover all the involved classes with a small batch size. To ensure coverage, has to employ much larger batch size, which results in a significantly higher computational burden. Although the improved version of stratified sampling
cover all classes, images from tail classes may appear repeatedly, leading to overfitting and consequently a degradation in performance. In contrast, our Tail-class Memory Bank only involves pasting a portion of one image onto another, effectively functioning augmentation. This approach mitigates the sampling problem without compromising generalization ability. The following empirical results support our assertion.
implicit data
27

---

First, we counted the number of images containing pixels from each class in the Cityscapes, ADE20K, and POCO-Stuff 164K datasets. The results are shown in Table 5, Table 6, and Table 7.
Table 5: The number of images containing pixels from each class in the Cityscapes. Class ID represents the class number in the original dataset.
Class ID 5 2949
2
13
7
10
11
6
18
12
3
17
14
15
16
Num
2934
2934
2891
2832
2811
2808
2686
2343
1658
1654
1646
1296
1023
970
513
359
274
142
Table 6: The number of images containing pixels from each class in the ADE20K. Class ID represents the class number in the original dataset.
Class ID
5
6
2
13
16
18
7
23
15
20
21
37
12
11
44
Num
11558
9314
8240
6674
6579
6042
5009
4687
4266
3995
3990
3295
3276
32.88
3161
3053
3061
2851
2646
Class ID
83
10
19
88
8
14
17
40
42
25
33
67
1.36
28
24
126
48
31
29
Num
2508
2421
2148
1987
1825
1741
1890
1447
1437
1404
1285
1308
1229
1191
1191
1181
1172
1132
Class ID
68
99
58
54
35
149
22
139
70
27
113
Num
1112
992
920
580
799
792
781
773
702
650
6.2
143
32
146
133
Num
583
556
556
549
531
530
528
521
504
492
479
468
465
452
451
Class ID
1.0
124
38
51
140
66
73
46
101
128
109
64
71
76
61
125
47
Num
421
417
411
4044
402
397
395
378
369
367
354
347
340
335
3.0
524
320
319
510
Class ID
98
77
49
133
117
63
1.34
69
122
75
62
81
130
142
144
119
145
132
57
Num
3077
304
287
284
282
275
268
266
266
265
261
247
246
228
217
213
206
201
198
Class ID
95
147
56
78
74
59
120
85
91
52.
146
100
121
102
131
105
127
141
Num
170
144
1.53
130
108
99
97
ID
108
112
97
Num
73
71
59
58
41
Table 7: The number of images containing pixels from each class in the COCO-Stuff 164K. Class
ID represents the class number in the original dataset.
Class ID
145
160
112
120
128
111 12667
169
155
601
118
Num
69665
16466
518
51461
27611
23001
23575
3.5576
19895
18311
16338
15402.
14309
1.0522
13257
122.1
11834
11772
Class ID
101
133
98
499
944
355
1.50
127
100
81
185
799
356
45.
26
109
165
185
145
Num
11303
11157
10546
10163
9856
93499
0522
9321
9475
8910
8893
$261
7176
5752
6744
6672
6642
6518
6595
147
Num
6252
6122
5250
S368
4558
4589
Claw ID
14
139
58
87
16
9
50
43
25
5
32
1.5
88
39
67
121
6
75
Num
4575
4550
4490
4450
4420
41.3
41.38
41.35
39945
3959
3950
3679
3948
3757
30,00
3677
3622
35577
3567
Class ID
36
14
30
655
Num
2500
3485
3476
3397
3354
3353
3159)
3241
3217
3200
3173
3159
3129
3082
3016
3007
2982
Class ID
96
55
135
1.9
168
35
156
115
34
Num
7991
78177
2741
71200
7703
7667
7659
7613
2596
2365
2558
2564
7498
7444
747%
Class ID
166
20
28
72
162
1.66
168
33
21
46
110
66
79
134
163
15k
132
Num
2453
2401
2387
2560
2337
2313
229/
2264
2102
2139
2130
2113
2100
3067
2006
2064
2000
2016
2009
Num
1962
1732
1411
Class ID
181
104
82
102
21
76
148
12
124
119
841
91
122
70
78
167
Num
1385
1362
1259
1134
1034
1002
959
919
846
749
703
659
559
477
351
256
217
188
121
The results indicate that images containing tail class pixels are very limited. Specifically, in the ADE20K dataset, there are only 41 images in the training set of 20210 images that contain pixels from the tail class with ID 97. As a result, tail class images are repeatedly sampled when using stratified sampling, leading to overfitting on such repeated images.
Next, we trained on the ADE20K dataset using the improved version of the stratified sampling method. The results show that, compared to using the Tail-class Memory Bank, the performance on tail classes dropped by over 3% due to heavy sample repetition in the batch. However, our T-Memory Bank, with its random pasting technique, diversifies the backgrounds of the tail classes, enabling the model to better learn the features of these tail classes.
E.2 Discussion on Why the T-Memory Bank Works
In this section, discuss why the primary function of the T-Memory Bank is not to enhance the diversity of tail samples.
As shown in Table 3, using memory bank does indeed increase the diversity of tail classes as an implicit frrm of augmentation (comparing the rows for SegNeXt and SegNeXt+TMB in the table). However, we cannot rely solely the bank to fully address the long-tail issue, as the bank's capacity
28

---

is always limited. This is why we also need to consider the problem from the perspective of the loss function. We find that the AUC loss focuses only on the ranking loss between positive and negative samples and is not sensitive to data distribution, fundamentally avoiding the risk of underfitting caused by insufficient training samples. We believe that the use of the T-Memory Bank is intended to both facilitate the effectiveness of the AUC loss and enhance the diversity of tail samples.
E.3 Discussion on AUC and Contrastive Learning from the Perspective of the Loss Function
In this section, we compare AUC and contrastive learning from the perspective of loss functions. Theorem 2 (Comparison between AUC Loss and Contrastive Loss). Minimizing the weighted contrastive loss approximately corresponds to minimizing an upper bound of the logistic AUC loss:
Σ wi log exr) + Ejzi wjello)
ef(a))
log
(It((e))-((N)
1
n;ny
jti
where,
w/
1/ng Enee 1/ng
and wi
Exei 1/mg
144
Proof. For the AUC loss under the logistic surrogate loss function:
plogistic
Elogistic
(f(x*)
f(x)))
ΣΣ
log
+ (
jti
ΣΣ
Willi
log
1 ((())))))
f#1
Σ
W Σ
log(e + log(e (ar()) + e e((ro))
w/
iti
Σ
W;
log
((0))
+ Σ Wy log(c!(e') tc(oll)
log(e + log
Σ
(yy(et(e)) + te((e)))
Σ
log(e (a¹)) + log
s(a') +
(aa))
cf(ar)
Σ Wi - log ef(t)) + Σ we)l(w)
1/n,n; where, wj En+; 1/A,nE
1/n, and w/ Σnzi 1/n2
Exzi 1/ng
ny
This completed the proof.
The theorem indicates that minimizing weighted version of contrastive loss implicitly optimize the ovo logistic AUC loss. This paper adopts a more general form of AUC loss, in which various surrogate loss functions are explored.
29

---

F Additional Experimental Settings
In this section, we make a supplementation to Section 5.1.
F1 Datasets
We use three datasets in our experiments: Cityscapes, ADE20K, and COCO-Stuff 164K.
Cityscapes [19] is a dataset of urban road traffic scenes, with each image sized at 1024 x 2048 pixels. It consists of 5000 images with pixel-level annotations across 19 classes. The training, validation, and testing set numbers are 2975, 500, and 1525, respectively.
ADE20K [109] is benchmark for scene parsing with 150 class labels. It includes over 25000 images, with 20210, 2000, and 3352 images used for training, validation, and testing, respectively.
COCO-Stuff 164K [9] is large-scale dataset with 164K images. It is finely annotated across 171 classes.
We split the three datasets into head class, middle class, and tail class based on the proportion of pixels for each class in the training set. Table 8, Table 9, and Table 10 provide the details of these partitions.
F.2 Implementation Details
Network Architecture. We perform all experiments using mmsegmentation [18] on an NVIDIA 3090 GPU. For our model, ImageNet-IK 1K [22] dataset.
SegNeXt [32] the backbone and pretrain all encoders on the
Data Augmentation. For Cityscapes, we resize the images to 1024 2048, randomly crop them to 1024 x 1024, and then apply random horizontal flips. For ADE20K and COCO-Stufi 164K, the resizing is set to 512 2048, random cropping is done at 512 512, and random horizontal flips applicd as well.
Training Strategy. We use Adam with Weight Decay (AdamW) [59] optimizer with an initial learning rate of 6c-5 and weight decay of 0.01. We adopt the 'poly' learning rate policy, where the initial iter
learning rate is multiplied by maz maæ_iter Moreover, a 'linear' warmup strategy is employed at the beginning of training, allowing the learning rate to increase from 1e-6 to the initial learning rate within 1500 iterations. The batch size is set to 2 for the Cityscapes dataset and for all the other datasets. The total number of iterations is 160000 on Cityscapes and ADE20K and 80000 on COCOOSStufi 164K.
Evaluation Metrics. Following the setup outlined by SegNeXt [32], we conduct experiments using the mean of Intersection over Union (mloU) the evaluation metric on the validation set.
F33 Competitors
Here give more detailed summary of the competitors mentioned in the experiments.
We compared our method with 13 recent advancements and 6 long-tail approaches in semantic segmentation. The recent advancements include DeepLab V3++ EncNet, FastFNN, EMANet, DANet, HRNet, OCRNet, DNLNet, PointRend, BiSeNetV2, ISANet, STDC, and SegNeXt. The long-tail methods are VS, LA, LDAM, Focal Loss, DisAlign, and BLV, all based on SetNeXt. To ensure fairness, we re-implement the listed methods using their publicly shared code and test them on the same hardware.
For the semantic segmentation methods:
DeepLab [14] combines the advantages the spatial pyramid pooling module and the encoder- decoder structure. It explores the Xception model and applies depthwise separable convolution to both the atrous spatial pyramid pooling and decoder modules, resulting in a faster and more robust encoder-decoder network.
EncNet [102] enhances semantic segmentation by utilizing a context encoding module that captures global contextual information to aid in the accurate segmentation of complex scenes.
30

---

Table Cityscapes Dataset Partition Status. The first column represents the head class, the second column represents the middle class, and the third column represents the tail class.
Label Pixel Ratio
Label
Pixel Ratio
Label
Pixel Ratio
road 46.27%
fence
0.85%
truck 0.24%
building
20.62%
person
0.83%
bicycle
0.24%
vegetation
13.40%
terrain
0.61%
bus
0.24%
car 6.62%
pole
0.60%
train
0.21 %
sidewalk 4.42%
wall 0.57%
traffic light
0.11%
sky 3.63%
traffic sign 0.40%
rider 0.08%
motorcycle 0.06%
Table 9: ADE20K Dataset Partition Status. The first column represents the head class, the second column represents the middle class, and the third sixth columns represent the tail class.
Label
Pizel Ratio
Label
Pixel Ratio
Label
Pixel Ratio
Label
Piael Ratio
Label
Pixd Ratio
Label
Pixel Ratio
wall
16.92%
grass
1955%
0,59%
runway
0.32%
streetlight airplane
0.05%
bag
0.05%
building
11.50%%
cabinet
.995%
mirror
0.57%
starway
0.1215
0.08%
step
0.08%
sky
9.53%
sidewalk
-00%
0.49%
rives
0.17%
dirt
0.18%
bicycle
0.04%
floor
6.66%%
person
1.71%
0.49%
screes
0.17%
telsision
Q.18%
Food
0.04%
5.21%
earth
1.61%5
held
0.48%
bridge
0.16%
apparel
OU77
taae
0.04%
cailing
4.86%
doer
1.27%
temeliir
0.48%
backezse
1.16%%
land
0.07%
dishwasher
0.04%
ruad
4.29%
ubl:
1.19%
fonez
0.35%
Bower
0.16%
bansister
0.07%
tank
0.48%
bed
2,47%
mountain
1.17%
desk
0.345
coffee
0.15%
pols
0.17
0.04%
windowpane pane
2.15%
cuntais
2.12%
wandrobe
0.32%
toilet
0.15%
bock
OU17
scuigture
0.04
chuir
1.1%
mek
0.30%
hill
14.45%
0.07%
hood
0.04%
plant
1.09%
lemp
0.28%
book
0.14%
ettonan
0.07%
0.48%
1.07%
bathodl
0.3695
blind
0.14%
escalstor
0.17%
lake
0.04%
0.79%
railing
0.25%
bench
0.14%
0.07%
0.04%
paiming
0.73%
0.25%
polm
0.13%
0.07%
micnowave
0.04%
sofa
0.71%
eudhion
0.25%
counteriop
0.135
buffet
0.06%
sconer
0.04%
shelf
0.67%
0,23%
kitchen
0.121
0,05%
animal
0.04%
0.65%
column
0.23%
0.12%
plaything
0,05%
0.0455
signboard
0.22%
swivel
0.11%
barre
0.08%
blanket
0.0455
chest
0.21%
0.11%
0.08%
traffic
0.04%
bout
Soumain
0
pier
grandstand
0,20%
0.10%
seimming
0,05/
0.05%
sink
0.20%
hovel 0.09%
stool
0.05%
0.00%
0.00%
0
0.05%
ball
0.15%
reliigennor
0,19%
0.09%
waterfull
0.05%
bulletin
0.00%
skyseraper
0.19%
truck
0.09%
washer
0.05%
plate
0.05%
0,19%
light
0.00%
0.15%
0.185
0.08%
minihike
0.15%
cadiator
0,155%
0.00%
0.15%
clock
chandelier
0.0%%
glass
pillow
Table 10: COCO-Stuff 164K Dataset Partition Status. The first column represents the head class, the second column represents the middle class, and the third to sixth columns represent the tail class.
Pioel Ratio
Label
Radio
Label
Pivel Hatle
funce
B.9455
motrecycle
0.40%
shuff
0:7855
0/16%
0.00%
sky other
6.24%
celling other
0.334
elepliact
0,49%
lesies
0.25%
bird
0.16%
parking rettr
0.00%
Inz
5.7%%
wall-tike
0.90%
anttatz
0.49%
grave
0.2872
botil
0.187
tralicc light
0.07%
wall concrete
A415
othrrttue-oteer
13895
eapet
0.48%
wall ganel
0.27%
bagecle
0.10/
site
0.07%
grase
cage
tible
0.27%
skatchesd
0.06%
helldig-other
M455
cahint
0.2995
dog
0.48%
0.26/5
krybward
0.145
tennis
00063
read
2.43%
tuin
0,27%
hause
0,44%
wood
0.26%
light
0.14%
pillow
0.06%
cleads
1455
hos
0,7755
peer
0.4255
cap
0.34/2
0.14%
exiii-itrrr
01653
511
pizza
pettoa plant
0.315
clock
remale
0.95
poveneat
gocudd
0.73%
pistic
burner
0.33/
0.04%
stuff
0.675
0.37%
cordboadd
0.25%
$10w boadd
0.04%
pleyinggeed
1.81%
Sole
0.655
ones
0,37%
plation
0.354
surthoard
0.12%
sctssees
0045
dei
1.35
wall-woed
0.64%
lapup
0.37%
hazan.
0.257
bankei
0.12%
fiiboc
0.00%
ruble
117%
chair
0.45
hoes
0.395
wall-ton
0.25%
Sroe hydran
0.11%
skis 0.05
tuck
0.63%
bench
0.36%
bnach
stp sigs
cellise-Gle
window-ether
0.21%
0.00%
1075
bend
BA11
5.34%%
flwaer
0.305
0.11%
firt am19
buil
0.62%
aiplane
0,34%
sleep
0.19%
handbag
0.10%
0.00%
Bice-sased
0.673
grilic
0.3%%
snow
0.193
diuh
0.19P
spoon
0.08
oir
0.6295
zehra
0.35%
besz
lel 0.19%
dooo mabble
0.105
nous
0.02%
oouch
hea
cell ploos
gove
0.57%
talll
0.00%
wall-bric
0.551
0.325
0.185
0/0P5
toothbeudh
0.00%
river
0.55%
meck
0.32%
siak
0.18%
hackgack
0.092
beachall bu
0.01%
foz
0.55%
silcas
0.32%
book
0.18%
wisc alss
0.09%
sports ball
0.01%
mountain
0.5115
ded--euff
0.31%
windon-Mird
0.185
seat
worendops
0015
other
0.50%
sandwich
0.30%
susctural-tllt
0.17%
laater
0.01%
celload
0.30%
0.17%
snwal
31

---

FastFCN [80] employs novel joint upsampling module called Joint Pyramid Upsampling, which transforms the task of extracting nigh-resolution feature maps into joint upsampling challenge.
EMANet [55] enhances semantic segmentation by utilizing an E.-bbsed attention mechanism that iteratively refines feature representations for more accurate segmentation.
DANet [27] improves scene segmentation by integrating both spatial and channel-wise attention mechanisms to capture rich contextual relationships across features.
HRNet [71] maintains high-resolution representations through the network and progressively adds lower-resolution subnetworks to enhance the learning of spatial hierarchies, significantly improving semantic segmentation.
OCRNet [97] enhances semantic segmentation by leveraging object-contextual representations, which aggregates contextual information around each pixel improve segmentation accuracy.
DNLNet [93] improves performance on tasks like image classification by disentangling the traditional non-local operations into two separate streams for capturing spatial and channel dependencies separately.
PointRend [50] introduces novel rendering-stye algorithm that selectively refines segmentation predictions at adaptively sampled points, enhancing detail accuracy in image segmentation tasks.
BiSeNetV2 [95] utilizes an efficient architecture with inverted residuals and linear bottlenecks, enabling high-performance mobile vision applications with significantly reduced computational cost.
ISANet [98] improves semantic segmentation by using a novel interlaced sparse self-attention mech- anism that efficiently captures long-range dependencies with fewer parameters and computational overhead.
STDC [25] addresses real-time semantic segmentation by proposing a novel and efficient structure that removes structural redundancy. reduces dimensions of feature maps gradually, and uses their aggregation for image representation.
SegNeXt [32] rethinks convolutional attention design for semantic segmentation by introducing advanced network architecture, enhancing the model's ability to focus on relevant features for more accurate segmentation.
For the long-tail methods:
VS [49] proposes to leverage both multiplicative and additive logit adjustments to address label imbalance problems.
LA [61] advances the conventional softmax cross-entropy by ensuring Fisher consistency in minimiz- ing the balanced error.
LDAM [10] improves the performance of tail classes by encouraging larger margins for tail classes.
Focal Loss [56] a modified cross-entropy loss designed to address class imbalance by focusing more hard-to-classify examples, reducing the relative loss for well-classified instances and thus boosting performance on imbalanced datasets.
DisAlign [104] introduces unified framework for long-tail visual recognition by aligning feature distributions across different classes, using a novel distribution alignment technique that adjusts spess-specific thresholds to mitigate the bias towards head classes and enhance recognition of tail classes.
BLV [77] addresses long-tailed semantic segmentation by dynamically adjusting the learning rates for the logits of different classes based on their frequency, effectively reducing the performance gap between head and tail classes.
32

---

G Additional Experimental Results
G.1 Per-tail-class Results
In Figure 6, we present the results for each tail class. We select classes with the fewest training samples from the Cityscapes dataset tail classes: truck, bicycle, bus, train, traffic light, rider, and motorcycle. Our method not only achieves the highest overall mloU but also shows significant improvements in these tail classes. Specifically, outperforms the current SOTA method by more than 1% in several tail classes.
Deepuas/3-
EMANet
SegNext
AUCSeg
100
90
80
(96)
70
60
50
30
Overall
Tall
Truck
Bicycle
Bus Classes Name
Train
Traffic Light
Rider
Motorcycle
Figure 6: Per-tail-class results on Cityscapes val set. The tail class names are listed from left right according to the ascending number of training samples in the dataset, with 'motorcycles' containing the fewest.
G.2 Performance Differences Across Different Datasets
The performance gain depends on the degree of imbalance of the underlying dataset. To see this, we show the pairwise mean imbalance ratio Tm (average the imbalance ratio of each class pair).
mm
Σ Σ
(43)
CA
acCh BEC,
where Cj represents the set containing the pixel counts of each head class, and C, denotes the set containing the pixel counts of each non-head class. The larger the Tm value, the more imbalanced the dataset is.
In Table 11, we compare for ADE20K, Cityscapes, and COCO-Stufi 164K, along with the tail classes performance improvements of AUCSeg compared to the runner-up method.
Table 11: The comparison of imbalance ratio and tail classes performance improvements on ADE20K, Cityscapes, and COCO-Stuff 164K.
Dataset
ADE20K
Cityscapes
COCO-Stuff 164K
Tin
90.43
80.39
38.17
Tail Classes Improvement
1.21%
0.75%
0.38%
The results suggest that the larger the imbalance degree the larger the improvements of method. ADE20K has the largest degree imbalance, therefore gaining the most significant improvement.
33

---

G.3
More Qualitative Results
Here we present more qualitative results on the Cityscapes, ADE20K, and COCO-Stuff 164K validation sets.
Input
Ground Truth
DeepLabV3+
SegNeXI
AUCSeg (Ours)
Input
Ground Truth
DeepLab
SegNeXt
AUCSeg (Ours)
Input
Ground Truth
DeepLabV3+
SegNeXt
AUCSeg (Ours)
Figure 7: More qualitative results on the Cityscapes, ADE20K and COCO-Stuff 164K val set. Red rectangles highlight and magnify the details of the image.
34

---

G.4 Backbone Extension of Different Model Sizes
In this paper, the large version of SegNeXt because of its outstanding performance. We also provide the results for the tiny, small, and base versions of SegNeXt, as shown in Table 12. The experiments indicate that AUCSeg achieves better performance under any model size.
Table 12: Results of AUCSeg on different model sizes of SegNeXt in terms of mIoU (%).
Backbone
AUCSeg
Overall
Tail
38.73
33,96
Tiny
39.00
34.52
X
43.25
38,90
Small
43.29
39.18
X
45.45
41.33
Base
46.37
42.49
47.45
43.28
Large
49.20
45.52
G.S Backbone Extension of Different Pixel-level Long-tail Problems
Apart from semantic segmentation, salient object detection is also pixel-level task. salient object detection, the salient objects often exhibit long-tailed distribution. We apply AUCSeg to this task, using the latest SOTA method SI-SOD-EDN [81, 53] as the backbone. The results are shown in Table 13.
Table 13: Experimental results of AUCSeg in the salient object detection.
ECSSD
HKU-IS p3 m
PASCAL-S
Dataset
MAE L
F8 f
Em
MAE 4
Em f
MAE 4
F 1
Em 1
m
SI-SOD-EDN
0.0358 0.0349
0.9084
0.9375
0.0287 0.0278
0.8986 0,8992
0.9442 0.9455
0.0644 0.0629
0.826 0.8281
0.8859
+AUCSeg
0.9087
0.9377
0.8875
Our AUCSeg achieves improvements across three commonly used evaluation metrics on three datasets, demonstrating that our method is highly versatile and extensible.
G.6 Spatial Resource Consumption
In this section, we thoroughly explore the spatial resource consumption the T-Memory Bank.
Table 14 details the ablation experiments on the spatial resource use of the T-Memory Bank. We set the memory size Sa and conduct experiments on the ADE20K dataset. necessary for samples of all classes to appear in the mini-batch, but rather only minimum of tail class samples are nceded. The results demonstrate that using AUC alone requires a batch size and graphics memory 5.5 times greater than the baseline to satisfy computational demands, which is significant expense. However, the T-Memory Bank substantially reduces this cost, enabling more efficient training without intolerant increase in graphics memory.
no longer
Moreover, we explore the effect of memory size SM on spatial resource consumption. The findings in Figure show that the graphics memory occupation increases slightly Sa rises. However, a smaller memory size generally suffices for effective performance, indicating that AUCSeg can achieve significant improvements with a manageable graphics memory burden. As shown in Figure 5a, when SM = 5, significant performance improvements can achieved with lower spatial resource consumption.
35

---

Table 14: Space resource consumption required for training properly. TMB is the abbreviation of T-Memory Bank.
3909
AUC
TMB
Batch Size
Graphic Memory
X
X
13.29G
1200
000
1008
X
22
72.90G
15.45G
Figure 8: The effect of memory size on spatial resource consumption.
G.7 Results of Different AUC Surrogate Losses and Calculation Methods
AUCSeg can adopt various surrogate losses. In the previous section, we use the square loss. In Table 15, we explore two other popular surrogate losses (hinge loss and exponential loss) for AUCSeg. Additionally, we include results for two AUC loss calculation methods (one-vs-one and one-vs-all) applied to AUCSeg using the square loss. The results are presented in Table 16.
Table 15: Results of different AUC surrogate losses in terms of mloU (%).
Dataset
AUC Surrogate Loss
Overall
Tail
47.45
43.28
Hinge
48.59(+1.14)
44.76(+1.448
ADE20K
Exp
48.86(+1.41)
45.07(+1.79)
Square
49.2(+1.75)
45.52(+2.24)
82.41
80.92
Hinge
82.64(+0.23)
81.35(+0.43)
Cityscapes
Exp
82.45(40.04)
81.55(+0.63)
Square
82.71(+0.30)
81.67(+0.75)
42.42
40.33
Hinge
42.52(+0.10
40.49(+0.16)
COCO-Stuff 164K
Exp
42.52(40.10)
40.53(+0.20)
Square
42.73(+0.31)
40.72(+0.39)
Table 16: Results of different AUC calculation methods terms of mloU (%).
Dataset
AUC Calculation Method
Overall
Tail
48.46
44.58
ADE20K
OVO
49.2
45.52
ova
82.31
80.79
Cityscapes
0V0
82.71
81.67
ova
42.25
40.17
COCO-Stuff 164K
42.73
40.72
The results indicate that AUCSeg shows improved performance with any the surrogate functions. Among them, using square loss and the calculation method delivers the best overall performance.
G.8 Results of the Comparison Between PMB and TMB
There are two differences between the Pixel-level Memory Bank (PMB) and our Tail-class Memory Bank (TMB). First, the PMB stores pixels from all classes, whereas TMB only stores pixels from tail classes. Second, TMB, storing and retrieving processes are conducted on an entire object (we ensure that the pasted pixel forms meaningful object). However, the PMB typically focuses on a fixed number of pixels without structural information (regardless whether these pixels can form complete image).
36

---

Why do we only store tail class pixels instead of all pixels?
Table 17 shows the average number of pixels from head and tail classes per image in the ADE20K, Cityscapes, and COCO-Stuff 164K datasets.
Table 17: The average number of pixels from head and tail classes per image.
Dataset
ADE20K
Cityscapes
COCO-Stuff 164K
Head
46685
294290
60157
Tail
18977
31128
22526
can be observed that the number of head class pixels in each image is 2.46 to 9.45 times greater than that of the tail classes, meaning that storing head class pixels would require significantly more memory.
Table 18 compares the performance differences between storing all and tail class pixels. It shows that the PMB, which incurs additional memory costs, performs almost the same as the TMB, and even shows a noticeable decline in the Cityscapes dataset. This is because head classes appear in almost every image (for example, urban road datasets, it is hard to find an image without head class pixels like 'road' or 'sky"), so they do not need additional supplementation. Even if some images require supplementation of head classes, their larger pixel counts might cause them to overwrite the original tail class pixels when pasted, leading decline in performance. Thus, we only store tail class pixels.
Table 18: The performance differences between PMB and TMB in terms of mloU (%).
Dataset
ADE20K
Cityscapes
COCO-Stuff 164K
PMB
49.09
82.07
42.66
TMB
49.2
82.71
42.73
Why not feasible focus on a fixed number of pixels?
We conduct tests on the ADE20K dataset by supplementing a fixed number of tail class pixels [0000/20000030000/00000000
in each image and find that compared to AUCSeg, the performance differences are - 1199///193///...... -0...000//077"/ of pixels can result in incomplete images, such as only adding the front wheel of bicycle, therefore loss of the structural information. The model is then unable to learn complete and accurate features. Therefore, in TMB, storing and retrieving are conducted all pixels of an entire image.
This is because supplementing a fixed number
G.9 Results of Different Memory Bank Update Strategies
In the previous section, we use the random replacement strategy to update the T-Memory Bank. We experiment with three other selection methods on the ADE20K dataset:
Mirst-In-First-OO (FIFO) replacement: Prioritizes replacing the images that were first stored in the Tail-class Memory Bank.
Last-In-First-One (LIFO) replacement: Prioritizes replacing the images that were last stored in the Tail-class Memory Bank.
Priority Used (PU) replacement: Prioritizes replacing images that have previously been selected by the retrieval branch.
The results shown in table 19.
FIFO and PU both show better performance overall and on tail classes compared to random sampling. However, LIFO, by updating only the most recently added images in the T-Memory Bank, causes the earlier images to remain unchanged. This leads to overfitting and, consequently, a decline in performance.
37

---

Table 19: Results of different memory bank update Strategies on ADE20K in terms of mloU (%).
Overall
Head
Middle
Tail
Random
49.2
80.59
59.45
45.52
FIFO
49.35
80.51
58.71
45.8
LIFO
49.05
80.35
58.76
45.45
PU
49.21
80.24
58.73
45.65
While these complex strategies can improve performance, the gains are relatively limited. On the other hand, the random replacement method is easy to implement. Exploring more complex and effective replacement methods could be promising direction for future work.
G.10 Detailed Results of the Ablation Study on
The detailed results of the ablation study on hyper-parameters are shown in Table 20, Table 21, Table 22, and Table 23.
Table 20: Ablation study on Memory Size (SM) in terms of mloU (%).
Table 21: Ablation study on Sample Ratio (Rg) in terms of mloU (%).
SM
Overall
Tail
Rs
Overall
Tail
48.46
44.68
0,01
48.91
45.13
49.09
45.40
0.04
48.70
44.97
5
49.20
45.52
0.05
49.20
45,52
48.81
45.06
0.07
48.47
44.75
10
48.80
44.99
0.1
48.34
44.53
20
48.63
44.96
0.15
47.27
43.30
Table 22:
Ablation study on Resize Ratio
Table 23: Ablation study on the weight À for Lauc and tee in terms of mIoU (%).
(RR) in terms of mloU (%).
RR
Overall
Tail
A
Overall
Tail
0.3
49.07
45.42
1/6
48.88
45.20
0.4
49.20
45.52
1/5
49.07
45.41
0.5
48.89
45.23
1/4
49.20
45.52
0.6
48.01
44.11
1/3
48.85
45.07
0.7
47.47
43.55
1/2
48.76
44.92
44.41
40.26
1
48.53
44.74
Explanation of the reasons why performance improvement decreases as memory size increases. This is trade-off between diversity and learnability. When the memory size is too large, the probability of any single sample being effectively learned decreases. So the model fails to focus on important examples, and thus fails to capture their features, ultimately leading underfitting. Conversely, if the memory size too small, the diversity of samples limited, which leads to overfitting, Hence, there is no free lunch for increasing the bank.
Therefore, we pursue a reasonable memory size. As shown in Table 20, we believe that a memory size of is suitable in most cases. As the memory size increases/decreeses, the performance slightly declines due model overfiting/underrittnng..
G.11 Results of the Ablation Study on the Impact of Batch Size
We conduct ablation experiments on the ADE20K dataset to evaluate the impact batch size. The results shown in Table 24:
The performance improves as the batch size increases. Moreover, our AUCSeg consistently effective across different batch sizes.
38

---

Table 24: Results of the ablation study on the impact of batch size in terms of mloU (%).
Batch Size
Overall
Tail
34.73
29.66
+AUCSeg
40.14
35.74
2
45.5
41.34
+AUCSeg
46.86
42.93
4
47.45
43,28
+AUCSeg
49.2
45.52
49.35
45,46
+AUCSeg
49.36
45.53
16
50.07
46.32
+AUCSeg
50.96
47.03
H More Discussions About AUCSeg
Training and inference efficiency. During training. since AUCSeg (1.62 + 0.2s per iteration) adopts pairwise loss, will inevitably suffer from extra complexity compared the standard CE-based SegNeXt (0.76 + 0.15s per iteration). Besides, during inference, since AUCSeg does not modify the model's backbone, all algorithms with the same backbone achieve similar inference efficiency (60 + 5ms per image). Overall, AUCSeg could perform well with acceptable efficiency.
Performance trade-off between head and tail classes. We recognize that AUCSeg might slightly impair the performance of head classes due to an increased focus on tail classes. However, this often results in substantial improvements for tail classes, trade-off that is generally beneficial since tail classes are typically more critical. For instance, on the Cityscapes dataset, AUCSeg exhibits marginal decrease of 0. 77% in head classes but gains 0.75% in tail classes compared to the runner-up, SegNeXt. Furthermore, we note that performance decreases in head classes mainly arise from misclassification the blurry edges objects. In contrast, gains tail classes often stem from either the successful detection of smaller objects or the more complete detection of such objects. To summarize, on the Cityscapes datasets, detecting a new tail object like "Traffic Lights' is far more significant than precisely detecting the edge pixels of a head class like 'sky'. Thus, we consider this trade-off highly beneficial.
I Broader Impact
We propose a general semantic segmentation method to deal with the potential bias toward long-tail objects. For nuimess-sensitvee scenarios, it might helpful to improve fairness for long-te mail groups
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We briefly summarize it in the abstract and detail the paper's contributions and scope in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss this issue in Appendix H.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
40

---

We provide complete proofs for each theoretical result in Appendix B and Appendix C.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe our algorithm in Section 4 and fully disclose all the informa- tion needed to reproduce the main experimental results of the paper in Section 5.1 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
41

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide link the data and code in the abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines ( Sittps:/nnipe cc/pu
Alic/guides, Catee/mmdeabbiiiiii S ssi ssionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines ( https://nips: wttccc/cpuuco wtce/uubic//ge gwtcc//ggge//////ee htte//guide///oeubmmmnmmnn cordedeumisssooooliiiioioo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide the completed experimental setting in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report this issue in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
42

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide sufficient information on the computer resources in Appendix F.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the ines?
NeurlPS Code of Ethics https://neurips..
Answer: [Yes]
Justification: The research conducted in the paper conforms in every respect with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss this issue in Appendix I.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
43

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the original paper that produced the code package and dataset.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi thcode. www.cooo/aaaae /atasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
44

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the code with documentation in the link within the abstract.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing and research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "EkNTIQpItp", "reviewer": "Reviewer_WAeT", "summary": "This paper introduces AUC optimization into the domain of long-tailed semantic segmentation. Specifically, the authors developed a pixel-level AUC loss function tailored for long-tailed semantic segmentation tasks and introduced a tail-class memory bank to address the memory demands. Additionally, the authors utilized Rademacher complexity to provide a generalization bound for AUCSeg and theoretically analyzed the potential for AUCSeg to generalize to unseen data. \n\nThe experimental evaluation in this paper assessed the performance of the proposed strategy on various datasets. Generally speaking, this paper is relatively detailed and comprehensive.", "questions": "I thank the author for their detailed work. Nevertheless, there are a few questions I wonder and I hope the author could respond.\n\n- For Tail Class Memory Bank, what would happen if we use a pixel-level memory bank? For example, prototype or similar technology, would this lead to significant performance degradation?\n\n- For the memory bank update problem, is there a more appropriate selection method instead of random replacement?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- It is novel to introduce auc optimization in long-tailed semantic segmentation and give a detailed analysis over the feasibility of this method.\n\n- The proposed method is validated on different datasets(ADE20k, CityScapes, COCO etc.) and has been proven to be effective in tail classes.", "weaknesses": "There are a few concerns about this paper:\n\n- On COCO, the performance improvement of Tail Class seems to be limited. Could the author explain the reason?\n\n- Fig. 6(a) shows the memory size reduction of the tail-class memory bank. The results show that as the memory size increases, the performance improvement decreases. What is the reason for this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments, and we would like to make the following response.\n\n> **Q1:** On COCO, the performance improvement of Tail Class seems to be limited. Could the author explain the reason?\n\n**A1:** Please refer to `C-A1` in `General Response`.\n\n> **Q2:** Fig. 6(a) shows the memory size reduction of the tail-class memory bank. The results show that as the memory size increases, the performance improvement decreases. What is the reason for this?\n\n**A2:** This is a trade-off between diversity and learnability. When the memory size is too large, the probability of any single sample being effectively learned decreases. So the model fails to focus on important examples, and thus fails to capture their features, ultimately leading to underfitting. Conversely, if the memory size is too small, the diversity of samples is limited, which leads to overfitting. Hence, there is no free lunch for increasing the bank!\n\nTherefore, we pursue a reasonable memory size. As shown in `Figure 6(a)` in the initial submission, we believe that a memory size of 5 is suitable in most cases. As the memory size increases/decreases, the performance slightly declines due to model overfitting/underfitting.\n\n> **Q3:** For Tail Class Memory Bank, what would happen if we use a pixel-level memory bank? For example, prototype or similar technology, would this lead to significant performance degradation?\n\n**A3:** Thanks so much for your suggestion! There are two differences between the Pixel-level Memory Bank (PMB) and our Tail-class Memory Bank (TMB). **First**, the PMB stores pixels from all classes, whereas our TMB only stores pixels from tail classes. **Second**, in our TMB, the storing and retrieving processes are conducted on an entire object (we ensure that the pasted pixel forms a meaningful object). However the PMB typically focuses on a fixed number of pixels without structural information (regardless of whether these pixels can form a complete image).\n\n**We will first explain why we only store tail class pixels instead of all pixels.**\n\nThe table below shows the average number of pixels from head and tail classes per image in the ADE20K, Cityscapes, and COCO-Stuff 164K datasets.\n\n|Dataset|ADE20K|Cityscapes|COCO-Stuff 164K|\n|-------|------|----------|---------------|\n| Head| 46685| 294290 | 60157|\n| Tail| 18977| 31128| 22526|\n\nIt can be observed that the number of head class pixels in each image is 2.46 to 9.45 times greater than that of the tail classes, meaning that storing head class pixels would require significantly more memory.\n\n**The table below** compares the performance differences between storing all and tail class pixels. It shows that the PMB, which incurs additional memory costs, performs almost the same as the TMB, and even shows a noticeable decline in the Cityscapes dataset. This is because head classes appear in almost every image (for example, in urban road datasets, it is hard to find an image without head class pixels like 'road' or 'sky'), so they do not need additional supplementation. Even if some images require supplementation of head classes, their larger pixel counts might cause them to overwrite the original tail class pixels when pasted, leading to a decline in performance. Thus, we only store tail class pixels. \n\n| Dataset | ADE20K    | Cityscapes | COCO-Stuff 164K |\n| ------- | --------- | ---------- | --------------- |\n| PMB     | 49.09     | 82.07      | 42.66           |\n| TMB     | **49.20** | **82.71**  | **42.73**       |\n\n**Next, we will explain why it is not feasible to focus on a fixed number of pixels.**\n\nWe conduct tests on the ADE20K dataset by supplementing a fixed number of tail class pixels (10000/20000/30000/40000) in each image and find that compared to AUCSeg, the performance differences are -3.00%/-1.93%/-0.86%/-0.73%. This is because supplementing a fixed number of pixels can result in incomplete images, such as only adding the front wheel of a bicycle, therefore loss of the structural information. The model is then unable to learn complete and accurate features. Therefore, in our TMB, storing and retrieving are conducted on all pixels of an entire image.\n\nWe will include this part in the final version of the paper.\n\n> **Q4:** For the memory bank update problem, is there a more appropriate selection method instead of random replacement?\n\n**A4:** Thank you for your constructive suggestion! Based on your suggestion, we have now tried three other different selection methods on the ADE20K dataset:\n\n- **First-In-First-Out (FIFO) replacement**: Prioritizes replacing the images that are first stored in the Tail-class Memory Bank.\n- **Last-In-First-Out (LIFO) replacement**: Prioritizes replacing the images that are last stored in the Tail-class Memory Bank.\n- **Priority Used (PU) replacement**: Prioritizes replacing images that have previously been selected by the retrieve branch.\n\nThe experimental results are shown in the table below.\n\n|        | Overall   | Head      | Middle    | Tail      |\n| ------ | --------- | --------- | --------- | --------- |\n| Random | 49.20     | **80.59** | **59.45** | 45.52     |\n| FIFO   | **49.35** | 80.51     | 58.71     | **45.80** |\n| LIFO   | 49.05     | 80.35     | 58.76     | 45.45     |\n| PU     | 49.21     | 80.24     | 58.73     | 45.65     |\n\nFIFO and PU both show better performance overall and on tail classes compared to random sampling. However, LIFO, by updating only the most recently added images in the T-Memory Bank, causes the earlier images to remain unchanged. This leads to overfitting and, consequently, a decline in performance.\n\nWhile these complex strategies can improve performance, the gains are relatively limited. The random replacement method, on the other hand, is easy to implement. We will include this part in the final version of the paper. In the future, we will explore more complex and effective replacement methods, hoping to provide a direction for other researchers to explore as well.", "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": "oAvsmQ3wvj", "reviewer": "Reviewer_TAdP", "summary": "This paper investigates AUC optimization within the context of pixel-level long-tail semantic segmentation (PLSS), a complex task due to intricate loss term coupling and extensive memory requirements. Initially, the authors demonstrate the potential of AUC for PLSS from a theoretical perspective by addressing the two-layer coupling issue across loss terms. Subsequently, they propose a novel Tail-Classes Memory Bank (T-Memory Bank) to manage the significant memory demands of AUC-oriented PLSS. Finally, comprehensive experiments show the effectiveness of the proposed method.", "questions": "Please refer to the weakness part.", "limitations": "None", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. This paper addresses a compelling problem with clear motivations and significant contributions, offering insightful ideas for both the AUC and segmentation communities. \n\n2. Developing a theoretically grounded loss from an AUC perspective is novel, and the proposed T-memory bank effectively mitigates the memory burden associated with pixel-level AUC optimization. \n\n3. The performance of the proposed AUCSeg seems promising.", "weaknesses": "Overall, I believe this is a qualified paper for publication after addressing the following minor concerns:\n\n1. The notations in this paper should be carefully defined. Some key symbols are used repeatedly, such as $N$ representing both batch size (In Alg.1) and sample size (In Thm.1).\n\n2. This paper only examines the square AUC surrogate loss without considering two other popular surrogate losses for AUC optimizations (i.e., hinge and exponential losses). It is essential to provide empirical verification by applying the ignored losses to AUCSeg.\n\n3. In Alg.1, the batch size scale will also impact the final performance of long-tailed classifications. The authors are recommended to conduct an ablation study on this aspect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your time and effort in providing us with such constructive comments. We would like to respond to them as follows:\n\n> **Q1:** The notations in this paper should be carefully defined. Some key symbols are used repeatedly, such as 𝑁 representing both batch size (In Alg.1) and sample size (In Thm.1).\n\n**A1:** Thank you for the suggestion! We carefully reviewed the symbol definitions in the paper. The symbol $𝑁$ representing batch size in Algorithm 1 has been changed to $N_b$. Additionally, for ease of reading, we will include **a table of symbol definitions** in the final version of the paper (See `Table 1` in the PDF submitted in the `General Response`).\n\n> **Q2:** This paper only examines the square AUC surrogate loss without considering two other popular surrogate losses for AUC optimizations (i.e., hinge and exponential losses). It is essential to provide empirical verification by applying the ignored losses to AUCSeg.\n\n**A2:** Thank you for your constructive suggestion! In this version, we have explored two other popular surrogate losses (hinge loss and exponential loss) to AUCSeg. Additionally, we have included results for two AUC loss calculation methods (one-vs-one and one-vs-all) applied to AUCSeg.\n\n\nThe performance of these three surrogate losses (hinge loss, exponential loss, and square loss) is presented in the table below:\n\n| Dataset         | AUC Method | Overall          | Tail             |\n| --------------- | ---------- | ---------------- | ---------------- |\n| ADE20K          | -          | 47.45            | 43.28            |\n|                 | Hinge      | 48.59(+1.14)     | 44.76(+1.48)     |\n|                 | Exp        | 48.86(+1.41)     | 45.07(+1.79)     |\n|                 | Square     | **49.2(+1.75)**  | **45.52(+2.24)** |\n| Cityscapes      | -          | 82.41            | 80.92            |\n|                 | Hinge      | 82.64(+0.23)     | 81.35(+0.43)     |\n|                 | Exp        | 82.45(+0.04)     | 81.55(+0.63)     |\n|                 | Square     | **82.71(+0.30)** | **81.67(+0.75)** |\n| COCO-Stuff 164K | -          | 42.42            | 40.33            |\n|                 | Hinge      | 42.52(+0.10)     | 40.49(+0.16)     |\n|                 | Exp        | 42.52(+0.10)     | 40.53(+0.20)     |\n|                 | Square     | **42.73(+0.31)** | **40.72(+0.39)** |\n\nThe performance of the two AUC calculation methods (ova and ovo) when using square loss is as follows:\n\n| Dataset         | AUC Method | Overall   | Tail      |\n| --------------- | ---------- | --------- | --------- |\n| ADE20K          | ova        | 48.46     | 44.58     |\n|                 | ovo        | **49.20** | **45.52** |\n| Cityscapes      | ova        | 82.31     | 80.79     |\n|                 | ovo        | **82.71** | **81.67** |\n| COCO-Stuff 164K | ova        | 42.25     | 40.17     |\n|                 | ovo        | **42.73** | **40.72** |\n\nThe results indicate that AUCSeg shows improved performance with any of the surrogate functions. Among them, using square loss and the ovo calculation method delivers the best overall performance. We will include this discussion in the final version of the paper.\n\n> **Q3:** In Alg.1, the batch size scale will also impact the final performance of long-tailed classifications. The authors are recommended to conduct an ablation study on this aspect.\n\n**A3:** Please refer to `C-A2` in `General Response`.", "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": "msk1RgGgTI", "reviewer": "Reviewer_tNYv", "summary": "This paper explores AUC optimization methods for pixel-level long-tail semantic segmentation, addressing complex dependencies and space complexity challenges. The authors propose a novel pixel-level AUC loss function and conduct a dependency-graph-based theoretical analysis to enhance generalization. They also introduce a Tail-Classes Memory Bank (T-Memory Bank) to manage memory demands, and experiments confirm the effectiveness of their AUCSeg method.", "questions": "1. For a long-tail semantic segmentation problem, which is also a pixel-wise classification task, I am uncertain why the authors chose this perspective. From the standpoint of the loss function, it emphasizes the contrast between the current class and other classes. Would a contrastive classification approach achieve similar results?\n2. The significance of Proposition 1 is not very clear. What is the meaning of the $\\Omega$? My understanding is that for a tail class, it is naturally difficult to randomly sample such a sample due to the scarcity. Therefore, re-sampling techniques are needed, which seems quite intuitive. What additional information is this proposition supposed to convey?\n3. The logic of using a memory bank in this paper seems weired. The authors argue that it is difficult to randomly sample a tail sample, hence the need for a memory bank. Most long-tail based work considers batch re-sampling a very conventional approach. However, this paper's method enhances the diversity of tail samples, thereby improving the model's learning ability for tail samples. Perhaps rephrasing this aspect would be more effective.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper presents a novel perspective by using AUC as the loss function.\n2. The paper has performed a tail class cache to boost the performance and control the memory demand.", "weaknesses": "Please refer to the questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your time and effort in providing us with such constructive comments. We would like to respond to them as follows:\n\n> **Q1:** Why did the authors choose the segmentation perspective? Would a contrastive classification approach achieve similar results?\n\n**A1:** Thank you for the helpful suggestion! We will first explain why this paper focuses on the long-tailed semantic segmentation task. Then, we will discuss new findings by comparing AUC and contrastive learning from the perspective of loss functions.\n\n**Firstly**, semantic segmentation, as a pixel-level classification task, also suffers from a severe long-tail problem, yet it has been largely overlooked or insufficiently explored by the long-tail community. We approach this issue from the perspective of loss functions, aiming to find a theoretically grounded loss. Noticing that AUC is popular and effective in image-level tasks, we extend it to address the pixel-level long-tail problem.\n\nWe chose to address this challenge from the loss function perspective because 1) The quality of the loss function directly impacts the model's learning quality and is directly related to performance. 2) Loss functions are more general and have the potential to be extended to other pixel-level tasks to address their long-tail issues. For example, in salient object detection, the salient objects often exhibit a long-tailed distribution. We apply AUCSeg to this task, using the latest SOTA method SI-SOD-EDN [1,2] as the backbone. See `Table 5` in the PDF submitted in the `General Response` for the results.\n\nOur AUCSeg achieves improvements across three commonly used evaluation metrics on three datasets. This demonstrates that our method is highly versatile and extensible.\n\n**Next**, we will discuss new insights comparing AUC and contrastive learning from the perspective of loss functions, supported by theoretical analysis and experimental validation.\n\n> **Theorem:** Minimizing the weighted contrastive loss approximately corresponds to minimizing an upper bound of the logistic AUC loss:\n> $$\n> \\sum_{i}w_i\\left[-\\log\\frac{e^{f(x^i)}}{e^{f(x^i)}+\\sum_{j\\neq i}w_je^{f(x^j)}}\\right]\\geq\\sum_{i}\\sum_{j \\neq i}\\frac{1}{n_in_j}\\left[-\\log\\left(\\frac{1}{1+e^{f(x^j)-f(x^i)}}\\right)\\right]\n> $$\n> where, $w_j=\\frac{1/n_j}{\\sum_{k\\neq i}1/n_k}$ and $w_i=\\frac{\\sum_{k\\neq i}1/n_k}{n_i}$.\n\nDue to space constraints, the proof will be provided in the next version. This theorem indicates that minimizing a **weighted version** of contrastive loss can implicitly optimize the OVO logistic AUC loss. The experiments in the table below also verify that Contrastive Loss + TMB and AUCSeg (Logistic) produce similar results. Our paper adopts a more general form of AUC loss, with the square surrogate loss showing the best performance.\n\n|| Overall| Tail|\n|--------------------|---------|---------|\n| Contrastive Loss+TMB| 47.47| 43.55|\n| AUCSeg (Logistic)| 47.86| 43.96|\n| AUCSeg (Hinge)| 48.59| 44.76|\n| AUCSeg (Exp)| 48.86| 45.07|\n| AUCSeg (Square)|**49.20**|**45.52**|\n\n> **Q2:** The significance of Proposition 1 is not very clear, What additional information is this proposition supposed to convey?\n\n**A2:** Thank you for your question. In `Proposition 1`, $x = \\Omega(y)$ means $\\exists c>0, x > c \\cdot y $. It represents the minimum batch size required to include pixels from all classes with a high probability. For ease of reading, we will include **a table of symbol definitions** in the final version of the paper (See `Table 1` in the PDF submitted in the `General Response`).\n\nDue to the scarcity of tail classes and the coupling between pixels, random sampling becomes challenging. This proposition quantifies the minimal batch size to cover all classes with a high probability. As we discussed in `Remark 2` of the initial submission, random sampling that meets the required conditions would necessitate sampling 759 images at once to form a mini-batch, an unbearable memory cost for model training.\n\n> **Q3:** The logic of using a memory bank in this paper seems weird. Why not use batch re-sampling? Rephrase this aspect of diversity.\n\n**A3:** Thank you for your constructive suggestion! \n\n- **The reason for not directly using batch re-sampling:** Please refer to `C-A3` in `General Response`.\n- **Why is the primary function of the T-Memory Bank not aimed at enhancing the diversity of tail samples:** As shown in `Table 2` of our initial submission (we also provide this table below), using a memory bank does indeed enhance the diversity of tail classes as an implicit way of augmentation (comparing the rows for SegNeXt and SegNeXt+TMB in the table). However, we cannot rely on the bank to fully address the long-tail issue, since the bank capacity is always limited. That's why we also need to consider the problem from the loss perspective. We find that AUC loss focuses only on the ranking loss between positive and negative samples and is not sensitive to data distribution, fundamentally avoiding the risk of underfitting caused by insufficient training samples. **We believe that the use of the TMB in our paper is intended to both facilitate the effectiveness of AUC loss and enhance tail sample diversity.** \n\n| Model | AUC  | TMB  | Overall   | Tail      |\n| ----------- | ---- | ---- | --------- | --------- |\n| SegNeXt     |   |   | 47.45| 43.28|\n| SegNeXt+AUC |yes |   | 48.46     | 44.70     |\n| SegNeXt+TMB |   | yes  | 47.86     | 43.86     |\n| AUCSeg      | yes  | yes  | **49.20** | **45.52** |\n\nWe acknowledge that, to some extent, the TMB also contributes to performance improvement by enhancing tail class diversity. Therefore, in the final version of the paper, we will discuss this point further in the `Discussions` section (`Line 223` in the initial submission).\n\n------\n\n[1] EDN: Salient object detection via extremely-downsampled network, TIP 2022.\n\n[2] Size-invariance Matters: Rethinking Metrics and Losses for Imbalanced Multi-object Salient Object Detection, ICML 2024.", "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": "RTu8UEDecq", "reviewer": "Reviewer_eudJ", "summary": "The authors extend AUC optimization techniques to pixel-level long-tail semantic segmentation and propose a general pixel-level AUC loss function. They decompose the loss function into inner-image and inter-image terms to decouple the interdependency, and calculate bounds to theoretically prove the effectiveness of this loss. Additionally, they design a Tail-Classes Memory Bank to reduce memory demand. Qualitative and quantitative comparisons have been made on three benchmark datasets, showing the efficiency of their method.", "questions": "1. I am confused about Tail-Class Memory Bank design, please refer weaknesses section above explaining them accordingly.\n2.  Authors should clarify certain experimental outcomes referring weakness points mentioned earlier.\n3. NeurIPS Paper Checklist lacks honest responses e.g., code provision/error bars reporting/new assets do not be contained, but all marked “YES”.", "limitations": "The authors have addressed the limitation of this method.  This method might slightly impair the performance of head classes due to an increased focus on tail classes.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is clearly organized and well written.\n2. The general idea of the paper is clear, and the motivation is interesting.\n3. The authors provide detailed theoretical proofs.", "weaknesses": "1. In the tail-class memory bank module, how do you ensure that pasted tail pixels do not completely cover any category?\n2. As shown in Fig 3(b), authors argue that because images contain multiple labels, it is impossible to use stratified sampling techniques to ensure each mini-batch contains at least one sample from each class. However, I believe this view is incorrect; we can group images by category, different categories may include identical images due to multi-label nature. Then we can use stratified sampling technique for each category so that although it might sample identical images (the same sample being sampled twice as both head and tail), it still ensures each mini-batch contains at least one sample from every class,  and small batch sizes can also achieve this goal. Therefore I think there’s no need for designing a Tail-Class Memory Bank.\n3. How does Tail-Class Memory Bank store data? Does it directly use ground truth or predicted results? If using ground truth directly why design Store Branch? You could directly build memory bank using ground truth. If using predictions then why not just use ground truths?\n4. Pasting tail-class pixels onto original image might occlude original image classes; would this behavior affect performance?\n5. This method mainly relies on SegNeXt; while sometimes environmental factors prevent exact replication of other works' results. However, SegNeXt provides training logs & pre-trained weights, why did your reproduction show significant performance gaps compared with SegNeXt's original work (e.g., nearly 4% gap on ADE20K)?\n6. In Table 1, this method shows significant improvement only on ADE20K but limited gains across two other datasets suggesting poor real-world generalizability inconsistent with theoretical conclusions.\n7. Currently effective methods trained over small datasets often fail scaling up large-scale models. Hence the author should further provide the results with large-scale pretrained models like SAM/CLIP etc., demonstrating broader applicability/generalization potentiality thereof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your time and effort in providing us with such constructive comments. We would like to respond to them as follows:\n\n> **Q1:** In the tail-class memory bank module, how do you ensure that pasted tail pixels do not completely cover any category?\n\n**A1:**  The number of head class pixels in each image is 2.46 to 9.45 times greater than that of the tail classes (see the response to Reviewer `WAeT`'s `Q3`), meaning that the number of tail class pixels is too small to completely cover the head classes.\n\nWe conduct 10000 random coverage experiments on the ADE20K, Cityscapes, and COCO-Stuff 164K. In the experiments, we track the number of instances where pixels of a certain category in the original image are completely covered during the random coverage process. The experimental results are as follows:\n\n| ADE20K  | Cityscapes | COCO-Stuff 164K |\n| ------- | ---------- | --------------- |\n| 7/10000 | 2/10000    | 9/10000         |\n\nThe experimental results indicate that the likelihood of complete coverage occurring is less than one in a thousand.\n\n> **Q2:** An improved version of stratified sampling can ensure coverage of all classes. So why use the Tail-Class Memory Bank?\n\n**A2:** Please refer to `C-A3` in `General Response`.\n\n> **Q3:** How does Tail-Class Memory Bank store data? Does it directly use ground truth or predicted results? \n\n**A3:**  The Tail-Class Memory Bank stores a certain number of pixels for each tail class, as detailed in `Line 201-222` of the initial submission. We use ground truth to assist in storing the original image data. The storage branch is designed with three main purposes:\n\n- The storage branch uses **ground truth** to extract corresponding pixels from the original image, which is what you referred to as \"directly building a memory bank using ground truth.\"\n- The storage branch records the original **positional information** of each pixel, which facilitates the restoration of their spatial positions by the Retrieve Branch during sampling.\n- The storage branch also assists in the **scheduling of the Memory Branch**. When the number of stored items in the Memory Branch reaches the memory size, we use a replacement method as described in the paper (see the response to Reviewer `WAeT`'s `Q4`).\n\n> **Q4:** Pasting tail-class pixels onto original image might occlude original image classes; would this behavior affect performance?\n\n**A4:** As we mentioned in `Q1`, pasting tail class pixels almost never completely covers other classes. Below, we can explore the impact of occluding the original image on performance through ablation experiments.\n\nThe parameter \"Resize Ratio\" in the T-Memory Bank represents the scale of the image before pasting (see `Lines 220-222` in the initial submission). Ablation experiments on this parameter allow us to investigate how the area of occlusion affects performance. In the initial submission `Figure 6(c)`, we conducted this experiment on the ADE20K dataset. Below, we present additional experimental results on the Cityscapes and COCO-Stuff 164K datasets.\n\nCityscapes:\n\n| Resize Ratio | Overall   | Tail      |\n| ------------ | --------- | --------- |\n| 0.1          | 82.18     | 80.69     |\n| 0.3          | 82.40     | 80.87     |\n| 0.5          | 82.62     | 81.50     |\n| 0.7          | **82.71** | **81.67** |\n| 0.9          | 82.53     | 81.51     |\n| 1            | 82.69     | 81.38     |\n\nCOCO-Stuff 164K:\n\n| Resize Ratio | Overall   | Tail      |\n| ------------ | --------- | --------- |\n| 0.05 | 42.59     | 40.55     |\n| 0.1  | **42.73** | **40.72** |\n| 0.3 | 42.52     | 40.42     |\n| 0.5  | 41.58     | 39.79     |\n| 0.7    | 42.57     | 40.50     |\n| 1     | 42.62     | 40.64     |\n\nIt can be observed that when the Resize Ratio is too large, severe occlusion occurs, resulting in a decline in model performance. Due to the differences in image sizes across datasets, the Resize Ratio should be adjusted accordingly when switching to other datasets.\n\n> **Q5:**  Why did your reproduction show significant performance gaps compared with the original work?\n\n**A5:** We used the code and parameters provided by MMSegmentation. To ensure fair comparisons, we reproduced all the experiments using a batch size of 4 instead of the original 16. The performance difference is due to the different batch sizes. We have further supplemented the experimental results with different batch sizes. Please refer to `C-A2` in the `General Response`.\n\n> **Q6:** Inconsistent performance gain.\n\n**A6:** Please refer to `C-A1` in `General Response`.\n\n> **Q7:** Comparison on large-scale pretrained models.\n\n**A7:** We extend AUCSeg to fine-tune CLIP, using DenseCLIP[1] as the backbone (batch size=4, iterations=80000). The experimental results are as follows:\n\n|| Overall| Head| Middle| Tail|\n| --------------------- | --------- | --------- | --------- | --------- |\n| DenseCLIP (ResNet-50) | 32.21| 73.37| 48.49| 26.99|\n| +AUCSeg| **34.59** | **74.04** | **50.13** | **29.60** |\n| DenseCLIP (ViT-B)| 48.63| 80.36| 57.80| 45.06|\n| +AUCSeg| **49.51** | **80.70** | **59.25** | **45.91** |\n\nOur AUCSeg is also effective on large-scale pretrained models.\n\n> **Q8:** NeurIPS Paper Checklist lacks honest responses.\n\n**A8:** There may have been some misunderstandings in our responses to the Checklist questions.\n\n- In the initial submission, we provided reasons for our \"yes\" answers regarding code provision/new assets: \"We will release the data and code once it is accepted.\" This might have caused some concerns. However, due to the rules during the rebuttal period, we have sent an anonymous link to the AC containing our core code (AUC Loss and T-Memory Bank), and you may need to request it from the AC.\n- When calculating the time cost for AUCSeg in the initial submission, we reported error bars. You can see this in `Lines 1178-1182` of the initial submission.\n\n------\n\n[1] Denseclip: Language-guided dense prediction with context-aware prompting, CVPR 2022.", "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:
**General Response**

Dear SAC, AC, and reviewers,

Thank you for your invaluable feedback. Based on your comments, we have revised the details and now offer a summary of our responses.

- **Additional Experiments:**
  1. Different sampling methods for the Tail-class Memory Bank 
  2. Different AUC surrogate losses and AUC calculation methods 
  3. New ablation experiments for the hyperparameters
  4. Extend AUCSeg to other pixel-level long-tail tasks
- **Explanations of the Method and Theory:**
  1. The motivation for introducing the Tail-class Memory Bank, its mechanism, and why it is effective
  2. Theoretical comparison between contrastive and AUC loss
  3. Detailed analysis of dataset distribution to further explain the variations in experimental results across different datasets
- **Organization:**
  1. Reorganize the symbol definitions and include a table of symbol definitions
  2. Update our responses to the checklist

Below, we provide responses to some **Common Questions**:

------

> **C-Q1:** [Reviewer `WAeT` and `eudJ`] The performance improvement of the tail class varies across the three datasets. ADE20K shows a significant improvement, while the other two show relatively limited results. Could the author explain the reason?

**C-A1:** The performance gain depends on the degree of imbalance of the underlying dataset. To see this, we show the pairwise mean imbalance ratio $r_{m}$ (average the imbalance ratio of each class pair). 

In the table below, we compare $r_{m}$ for ADE20K, Cityscapes, and COCO-Stuff 164K, along with the tail classes performance improvements of AUCSeg compared to the runner-up method.

| Dataset                  | ADE20K | Cityscapes | COCO-Stuff 164K |
| ------------------------ | ------ | ---------- | --------------- |
| $r_{m}$                  | 90.43  | 80.39      | 38.17           |
| Tail Classes Improvement | 1.21%  | 0.75%      | 0.38%           |

The results suggest that the larger the imbalance degree the larger the improvements of our method. ADE20K has the largest degree imbalance, therefore gaining the most significant improvement.


> **C-Q2:** [Reviewer `TAdP` and `eudJ`] The author should include ablation experiments for the batch size.

**C-A2:** We conduct ablation experiments on the ADE20K dataset to evaluate the impact of batch size. The results are shown below:

| Batch Size | Overall   | Tail      |
| ---------- | --------- | --------- |
| 1          | 34.73     | 29.66     |
| +AUCSeg    | **40.14** | **35.74** |
| 2          | 45.50     | 41.34     |
| +AUCSeg    | **46.86** | **42.93** |
| 4          | 47.45     | 43.28     |
| +AUCSeg    | **49.20** | **45.52** |
| 8          | 49.35     | 45.46     |
| +AUCSeg    | **49.36** | **45.53** |
| 16         | 50.07     | 46.32     |
| +AUCSeg    | **50.96** | **47.03** |

The performance improves as the batch size increases. Moreover, our AUCSeg is consistently effective across different batch sizes. In the initial submission, we selected a batch size of 4. Although this does not yield the highest performance, this batch size ensures that our experiments can be replicated on any GPU with 24GB of memory (such as the NVIDIA 3090 or 4090). We will include this part in the final version of the paper.

> **C-Q3:** [Reviewer `tNYv` and `eudJ`] Why design a Tail-class Memory Bank instead of using an improved version of stratified sampling for batch re-sampling?

**C-A3:** Stratified sampling can hardly cover all the involved classes with a small batch size (such as 4 in our paper). To ensure coverage, one has to employ a much larger batch size, producing a much higher computational burden. **Even if we can cover the classes**, tail class images may appear repeatedly, leading to overfitting and therefore a performance degradation. Our Tail-class Memory Bank, however, only involves pasting a portion of one image onto another, which behaves like an implicit data augmentation. It mitigates the sampling problem without sacrificing the generalization ability. The following empirical results demonstrate our belief.

**First**, we counted the number of images containing pixels from each class in the Cityscapes, ADE20K, and COCO-Stuff 164K datasets. See `Table 2-Table 4` in the PDF submitted in the `General Response`.

The results show that images with tail class pixels are very limited. Particularly in the ADE20K, there are only 41 images in the training set of 20210 images that contain pixels with the tail class ID of 97. The tail class images will be repeatedly sampled when using stratified sampling, leading to overfitting to such repeated images.  

**Next**, we train on the ADE20K dataset following the stratified sampling method. The experimental results are as follows:

|                     | Overall   | Head      | Middle    | Tail      |
| ------------------- | --------- | --------- | --------- | --------- |
| Stratified Sampling | 46.20     | 79.55     | 57.65     | 42.21     |
| T-Memory Bank       | **49.20** | **80.59** | **59.45** | **45.52** |

The overfitting of stratified sampling brings a performance reduction for both head and middle classes. The tail classes experience an even more significant performance drop due to the heavy sample repetition in the batch. However, our T-Memory Bank, with its random pasting approach, diversifies the background of the tail classes, thus helping the model to better learn the features of the tail classes.

------

Please refer to the specific responses below for more information. We will update all these improvements in the next version.

Meta-review: This paper proposes an AUC optimization method for long-tail semantic segmentation. A pixel-level AUC loss function is proposed along with a theoretical analysis, and the Tail-Class Memory Bank strategy to manage memory issues. Most of the reviewers’ comments were addressed in the rebuttal and all the reviewers were on the positive side after rebuttal. The AC agrees with the consensus among the reviewers, and recommends to accept it.
Decision: Accept (poster)