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_cc_2024_Conference
Published: 2024-05-10 05:43:36

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.

Main paper: 
 introduction: 
 Semantic segmentation aims to categorize each pixel within an image into a specific class, which is a fundamental task in image processing and computer vision [33, 51, 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-based methods [108, 83, 65, 15, 32] , which have achieved the state-of-the-art (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 to 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 to alleviate this [49, 61, 10, 56, 104, 92, 78] . For example, [77] introduces a category-wise variation technique inversely proportional to distribution to achieve balanced segmentation; [66] introduces a sequence-based generative adversarial network for imbalanced medical image segmentation, and [41] develops a re-weighting scheme for semi-supervised segmentation.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. A question then arises naturally:Can we find a theoretically grounded loss function for PLSS on top of SOTA backbones? This paper provides an affirmative answer from the AUC perspective and proposes a novel framework called AUC-oriented Pixellevel Long-tail Semantic Segmentation (AUC-Seg). Specifically, AUC indicates the likelihood that a positive sample scores higher than a negative one, which has been proven to be insensitive 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] . Motivated 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 generalization analysis [62, 8, 21] require the loss function to be expressed as a sum of independent terms. Unfortunately, the proposed loss function does not satisfy this assumption due to the dual effect of structured inner-image dependency 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 graph [103] to decouple the interdependency. Finally, we reach a bound of O τ log (τ N k) /N , where τ behaves like an indicator for imbalance degree, and k 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 instancelevel long-tail problems. Specifically, the SGD algorithm of AUC requires at least one sample from each class in each mini-batch [99, 85] . 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 to include all classes would require an 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-level long-tail problems.• 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.2 Related Work 
semantic segmentation: 
 Semantic segmentation is a subtask of computer vision, which has seen significant development since the inception of FCN [58] . The most common framework for semantic segmentation networks is 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 as HRNet [75] , ICNet [105] , and multimodal networks [76, 42] . For the decoder, a 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. A series of methods related to Vision Transformer [108, 83, 65, 15, 74] are proposed. SegNeXt [32] , which is the current state-of-the-art (SOTA) method, possesses the same powerful feature extraction capabilities as the Vision Transformer and the same low computational requirements as CNN. Apart from improving the network, some research [48, 56, 24, 11, 10, 66, 39] is directed toward addressing the issue of class imbalance in semantic segmentation. However, the effectiveness of these methods is not significant. In this paper, we aim to improve the performance of long-tailed semantic segmentation from an AUC optimization perspective.The development of AUC Optimization can be divided into two periods: the machine learning era and the deep learning era. As a pioneering study, [20] ushers in the era of AUC in machine learning. It studies the necessity of AUC research, which points out that AUC maximization and error rate minimization are 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 to extend AUC optimization to deep neural networks, ushering in the era of AUC in deep learning. Meanwhile, a 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-imbalanced 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 instancelevel imbalanced classification tasks. This paper starts an early trial to introduce AUC optimization to semantic segmentation. However, due to 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.Let D = {(X i , Y i ) n i=1 |X i ∈ R H×W ×3 , Y i ∈ R H×W ×K } be the training dataset, where H and W represent the height and width of the images, and K denotes the total number of classes. Let f θ be a semantic segmentation model (θ is the model parameters), which commonly follows an encoder-decoder backbone [75, 105, 108, 83, 32] EQUATIONwhere the encoder f e θ extracts features from the image X i , and then the decoder f d θ predicts each pixel based on extracted features and outputs a dense segmentation map with the same size as Y i . Furthermore, let Y i u,v and Ŷi u,v represent the ground truth and prediction of the (u, v)-th pixel of the i-th image, respectively. To train the model f θ , most current studies [14, 80, 83, 65] usually adopt the cross-entropy (CE) loss:EQUATIONwhere Y ic u,v and Ŷic u,v are the one-hot encoding of ground truth and the prediction of pixel(X i u,v , Y i u,v ) in class c, respectively.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 a higher score than a negative one [35] :EQUATIONwhere (X + , y + ) and (X -, y -) represent positive and negative samples, respectively. When AU C → 1, it indicates that the classifier can perfectly separate positive and negative samples.According to [87, 86, 88] , given finite datasets, maximizing AU C(h θ ) is usually realized by maximizing its unbiased empirical estimation:EQUATIONwhere ℓ 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:EQUATIONNote 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 distribution-insensitive property [26] , this paper starts an early trial to introduce AUC to PLSS. 
auc-oriented semantic segmentation: 
 In this section, we introduce our proposed AUCSeg method for semantic segmentation. A brief overview is provided in Figure 2 . AUCSeg is a 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 a theoretically grounded loss function is explored for PLSS and (2) Tail-class Memory Bank, an effective augmentation scheme to ensure efficient optimization of the proposed AUC loss. In what follows, we will go into more detail about them. For clarity, we include a table of symbol definitions in Appendix A. Semantic segmentation is a multi-class classification task. Therefore, to apply AUC, we follow a 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 denoteD p = {(X i u,v , Y i u,v )|i ∈ [1, n], u ∈ [0, H -1], v ∈ [0, W -1]} as the set of all pixels; the j-th element (j ∈ [1, n × (H -1) × (W -1)]) in D p is abbreviated as (X p j , Y p j ) for convenience. Given the model prediction f θ = (f(1) θ , . . . , f (K) θ ), ∀c ∈ [K], f (c) θ ∈ [0, 1], where f (c) θserves as a continuous score function supporting class c, AU C ovo seg calculates the average of binary AUC scores for every class pair:EQUATIONAU C cc ′ (f θ ) = P(f (c) θ (X p m ) > f (c) θ (X p n )|Y p m = c, Y p n = c ′ ).To this end, as introduced in Section 3.2, the goal is to minimize the following unbiased empirical risk:EQUATIONwhere we adopt the widely used square loss ℓ sq (x) = (1 -x) 2 as the surrogate loss [29] ; ℓ c,c ′ ,m,n sq := ℓ sq (f (c) θ (X p m ) -f (c) θ (X p n )); N c = {X p k |Y p k = c}In this section, we explore the theoretical guarantees of the AUC loss function in semantic segmentation tasks and demonstrate that AUCSeg can generalize well to unseen data.A key challenge is that standard techniques for generalization analysis [62, 8, 21] require the loss function to be expressed as a 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 a 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 E D LD (f ) be the population risk of LD (f ).Assume F ⊆ {f : X → R H×W ×K }, where H and W represent the height and width of the image, and K represents the number of categories, L(i) is the risk over i-th sample, and is µ-Lipschitz with respect to the l ∞ norm, (i.e. ∥ L(x) -L(y)∥ ∞ ≤ µ • ∥x -y∥ ∞ ). 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):LD (f ) -E D LD (f ) ≤ 8 N + η inner + η inter √ N A log (2Bµτ N k + C) + 3 1 2N + K 1 - 1 N log 4K(K -1) δ ,whereEQUATION= N i=1 n(X (c) i ), N = |D|, k = H × W and X (c) represents the pixel of class c in image X.Remark 1. We achieve a bound of O τ log (τ N k) /N , indicating reliable generalization with a large training set. Here, τ represents the degree of pixel-level imbalance. More interestingly, even though we have k classifiers for every single image, the generalization bound only has an algorithm dependent on k, suggesting that pixel-level prediction doesn't hurt generalization too much.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, as discussed in Section 1. Specifically, the stochastic AUC optimization, as 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 a 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 to 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 it hard to split them for stratified sampling, as illustrated in Figure 3(b) . Meanwhile, we also provide a bound (Proposition 1) to show that simply adopting random sampling will suffer from an overlarge batch size B, making an unaffordable GPU memory burden. Proposition 1. Consider a dataset D that includes images with K different pixel categories. Let p i represent the probability of observing a pixel with label i in a given image. Randomly select B images from D as training data, whereB = Ω   log(δ/K) log(1 -min i p i )   .Then with probability at least 1 -δ, for any c ∈ [K], there exists X in the training data that contains pixels of label c. Remark 2. The proof is deferred to Appendix C. Proposition 1 suggests that the value of B is inversely proportional to min i p i . Note that p i will be smaller as the long-tail degree becomes more severe, leading to a larger B. For example, in terms of the Cityscapes dataset with K = 19 classes, assuming δ = 0.01 and min i p i = 1%, B should be at least 759 to guarantee that each class of pixels appears at least once with a high probability. This results in a significant strain on GPU memory.To address this, considering that the tail-class samples generally have less opportunity to be included in a mini-batch and are often more crucial for final performance, we thus develop a novel Tailclass Memory Bank (T-Memory Bank) to efficiently optimize Equation ( 7) and manage GPU usage effectively. As depicted in Figure 3 (c), the high-level ideas of the T-Memory Bank are as follows: 1) identify missing tail classes of all images involved in a mini-batch 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, we can obtain an approximated batch-version of Equation ( 7), i.e. ,EQUATIONwhere N c and T c represent the set of pixels with label c in the original image and those pixels stored in the T-Memory Bank, respectively; lc,c ′ ,m,n sq := ℓ sq (f(c) θ ( Xp m ) -f (c) θ ( Xp n ));Xp represents the sample after replacing some pixels with tail classes pixels from the T-Memory Bank.Detailed Components. As shown in Figure 2 , T-Memory Bank comprises three main parts: (1) Memory Branch stores a set with S M (the Memory Size) images for each tail class. We define the set as M = {M c1 , . . . , M cn t }, where C t = {c i } nt i=1 denotes the labels of tail classes, and n t is the total number of selected tail classes; (2) Retrieve Branch selects pixels from the Memory Branch to supplement the missing tail classes and (3) Store Branch updates the Memory Branch whenever a new image arrives. Algorithm 1 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 our proposed AUCSeg, which is widely used in the AUC community [99] to pursue robust feature learning. Experiments demonstrate that the performance is insensitive to the regularization weight λ, as shown in Figure 5d .At the start of training, the Memory Branch is 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 S M , we adopt a random replacement strategy to update the Store Branch (Lines 5 to 6 in Algorithm 1 or Lines 6 to 11 in Algorithm 2).As the training process progresses, if the Memory Branch is not empty, the Retrieve Branch kicks in to count the missing classes in each image of the mini-batch, denoted as C miss . It then calculates the number of classes needed to be added for optimization, n sample = ⌈|C miss | × R S ⌉. Here, we introduce a tunable sample ratio R S to strike a trade-off between the original and missing tail-class semantic information. Finally, it uniformly retrieves the corresponding pixels of n sample missing classes from the Memory Branch, resizes them by the resize ratio R R , and randomly selects positions to overwrite (Lines 7 to 8 in Algorithm 1 or Lines 13 to 18 in Algorithm 2). D B = {(X i , Y i )} N b i=1 ← SampleBatch(D, N b ); C miss ⊆ C t ← M issingT ailClasses(D B ); C miss = C t -C miss ; ▷for c m in C miss doExtract pixels of class c m from D B and save them to M cm ← RandomReplace(S M );▷for i = 1 to ⌈|C miss | × R S ⌉ doRandomly choose c m from C miss and sample pixels from M cm to paste into D B ← SizeScale(S R );▷ Calculate Ŷi = f θ (X i ) and ℓ = lauc + λℓ ce ;Backpropagation updates θ.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 or image-level features, while our T-Memory Bank specifically stores the original pixels for each object. This strategy is particularly beneficial for our PLSS task. Additionally, 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 in Appendix G.6, include a comparison of GPU overhead. For more discussion on the T-Memory Bank, please refer to Appendix E. 
experiments: 
 In this section, we describe some details of the experiments and present our results. Due to space limitations, please refer to Appendix F, Appendix G and Appendix H for an extended version.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 (mIoU) 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 use 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 to Appendix F.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 long-tail approaches generally achieve better results than those that do not. However, they still fail to produce satisfactory outcomes. One possible reason is that these long-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%, and +0.38% in tail classes mIoU across the datasets. Overall mIoU also improves by +1.05%, +0.27%, and +0.31%. In some Head/Middle metrics, AUCSeg does not 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.1, and analyze the reasons for the varying performance improvements of tail classes across the three datasets in Appendix G.2. In Section 5.1, we select the current SOTA Seg-NeXt as the backbone. Nevertheless, AUC-Seg can also adapt to other backbones, consistently delivering effective results. Table 2 presents the experimental results of AUCSeg when using DeepLabV3+, EMANet, OCRNet, and ISANet as backbones. These results reveal significant improvements in both overall mIoU and tail classes mIoU with AUCSeg. Notably, on ISANet, the increases are 5.54% and 6.49%. Moreover, AUCSeg enhances performance across various model sizes and different pixel-level long-tail problems, as detailed in Appendix G.4 and Appendix G.4. This demonstrates the superiority of our proposed AUC-Seg for long-tailed semantic segmentation.We perform several ablation studies to test the effectiveness of different modules and hyperparameters.All experiments are conducted on the ADE20K validation set. The Effectiveness of AUC Optimization and T-Memory Bank. Ablation Study on Hyper-Parameters. Figure 5a ablates the maximum number of images stored per class in the Memory Branch, referred to as Memory Size (S M ). For the ADE20K dataset, optimal performance occurs when S M = 5, and performance shows little sensitivity to changes in S M . Figure 5b ablates the Sample Ratio (R S ), the fraction of classes sampled from the Memory Branch relative to the total number of missing tail classes. Figure 5c ablates the Resize Ratio (R R ), the scaling factor for the sampled pixels. For ADE20K, the best result is obtained when R S = 0.05 and R R = 0.4. A potential reason for their small value is that the original image is overwritten when R S and R R are too large, resulting in poor training performance. Figure 5d ablates the weight λ for ℓ ce and ℓ auc , with λ = 1 4 providing slightly better results. The influence of λ on performance is minimal. Detailed results from this hyper-parameter ablation study are available in Appendix G.10 and G.11. 
conclusion: 
 This paper explores AUC optimization in the context of 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 a promising performance. Subsequently, we propose a novel T-Memory Bank to reduce the significant memory demand for the mini-batch optimization of AUCSeg. Finally, comprehensive experiments suggest the effectiveness of our proposed AUCSeg.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The paper does not release data or models that have a high risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: We cite the original paper that produced the code package and dataset.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: In this section, Table 4 includes a summary of key notations and descriptions in this work. The height/width of the images in dataset D.The number of image samples in dataset D.The total number of classes in dataset D.(X i , Y i )The i-th sample and its ground-truth in dataset D, where i ∈[1, n], X i ∈ R H×W ×3 , Y i ∈ R H×W ×K . f θThe semantic segmentation model, where θ is its parameter.f e θ /f d θThe encoder/decoder in the semantic segmentation model f θ .The prediction of model f θ , whereŶi = f θ (X i ) ∈ R H×W ×K . (X i u,v , Y i u,v / Ŷi u,v )The sample and its ground-truth/prediction of the (u, v)-th pixel of the i-th image.Y ic u,v / Ŷic u,vThe ground-truth one-hot encoding/prediction of pixel(X i u,v , Y i u,v ) in class c. D pThe set of all pixels in dataset D.(X p j , Y p j ) The j-th element in D p , where j ∈ [1, n × (H -1) × (W -1)]. f (c) θThe continuous score function supporting class c.The set of pixels with label c in the set D p , whereN c = {X p k |Y p k = c}.The number of elements in set A. µThe Lipschitz constant.The lower bound.N c /T cThe set of pixels with label c in the original image/those pixels stored in the T-Memory Bank.The sample after replacing some pixels with tail classes pixels from the T-Memory Bank. n tThe number of tail classes.The labels of tail classes, whereC t = {c i } nt i=1 . MThe Memory Branch, whereM = {M c1 , . . . M cn t }. S MThe memory size.The sample ratio. R RThe resize ratio.The max iteration.The batch size.Lemma 1 (Jensen's Inequality). If X is a random variable and φ is a convex function, thenEQUATIONAssumption 1. Assume that ℓ is µ-Lipschitz continuous, that isEQUATION)Assumption 1 is a pretty mild assumption. The square loss ℓ sq (x) = (1 -x) 2 satisfies Assumption 1. Lemma 2. The empirical Rademacher complexity of function g with respect to the predictor f is defined as:EQUATION)where F ⊆ {f : X → R K } is a family of predictors, and N refers to the size of the dataset, and σ i s are independent uniform random variables taking values in {-1, +1}. The random variables σ i are called Rademacher variables.Lemma 3. Let E [g] and Ê [g] represent the expected risk and empirical risk, and F ⊆ f : X → R K . Then with probability at least 1 -δ over the draw of an i.i.d. sample S of size n, the generalization bound holds:EQUATION)Definition 1 (Fractional Independent Vertex Cover, and Fractional Chromatic Number [103] ). Let a graph be G = (V, E).(1) A fractional vertex cover of G is a family {(F j , ω j )} j of pairs (F j , ω j ), where F j ⊆ V (G), ω j ∈ (0, 1], and j:v∈Fj ω j = 1, ∀v ∈ V (G).(2) An independent set of G is a set of vertices in G with no two adjacent. Let I(G) denote the set of independent sets of G.(3) A fractional vertex cover is a fractional independent vertex cover {(I j , ω j )} j of G if ∀j, I j ∈ I(G).(4) A fractional coloring of a graph G is a mapping g :I(G) → (0, 1] such that I∈I(G):v∈I g(I) ≥ 1, ∀v ∈ V (G). The fractional chromatic number χ f (G) is the minimum of the value I∈I(G) g(I)over fractional colorings of G.Notably, the minimum of j ω j over all fractional independent vertex covers {(I j , ω j )} j of G is the fractional chromatic number χ f (G).Definition 2 (Dependency Graph [44] ). An (undirected) graph G = (V, E) is called a dependency graph associated with a random vector (or random variables)x = (x 1 , . . . , x m ) if (1) V (G) = [m].(2) For all disjoint vertex sets I, J ⊆ [m], if I, J are not adjacent in G, then random variables {x i } i∈I and {x j } j∈J are independent.A useful result is Janson's decomposition property [44] , which combines the concept of dependency graphs with fractional independent vertex covers. The property states that if interdependent random variables (x i ) i∈[m] is associated with a dependency graph G with a fractional independent vertex cover (I j , ω j ) j∈[J] , then, the sum of the interdependent variables, can be equivalently decomposed into a weighted sum of sums of independent variables: i,j 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:EQUATIONEQUATIONwhere,linner +,-= |D| n X + 1 n X - 1 |N + | |N -| (i1,j1)∈X + 1 (i2,j2)∈X - 1 ℓ sq f (+) i1,j1 , f (+) i2,j2 , X, Y |D| n X + 1 n X - 1 , linter +,-= |D| (|D| -1)n X + 1 n X - 2 |N + | |N -| (i1,j1)∈X + 1 (i2,j2)∈X - 2 ℓ sq f (+) i1,j1 , f (+) i2,j2 , X, Y |D| (|D| -1)n X + 1 n X - 2 ,and n (X + ) /n (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 Z and S :=EQUATIONIn this case, we call v 1 , . . . , v m an (ϵ, ℓ ∞ )-cover of F w.r.t S.Lemma 5. Let P (X) represents the pixels in image X, F = f (+) i,j : (i, j) ∈ P (X) , (X, Y) ∈ S and ℓ • F = ℓ • f (+) i,j : f (+) i,j∈ F . According to Definition 3, we have:EQUATIONwhereρ max = max X |D|n(X + )n(X -) |N+||N-| .Proof. For any g = ℓ • f , we can find g = ℓ • f that satisfies the following conditions:EQUATIONwhereℓ sq -lsq = ℓ sq f (+) i1,j1 , f (+) i2,j2 , X, Y -ℓ sq f (+) i1,j1 , f (+) i2,j2 , X, Y .According to Assumption 1, we have:EQUATIONDenote ρ(x) byEQUATIONwhereEQUATIONThere exists af C k = f C k i,j: (i, j) ∈ P (X) , such that for any f =EQUATIONwhich implies that maxEQUATIONwhereEQUATIONthen {C g,1 , . . . , C g,N } realizes an ϵ-covering of ℓ • f . Hence, the minimum size of the ϵ-covering is at most N . Mathematically, we then have:EQUATIONThis completed the proof.). Let F be a real-valued function class taking values in [0, 1], and assume that 0 ∈ F. Let S be a finite sample of size n. For any 2 ≤ p ≤ ∞, we have the following relationship between the Rademacher complexity R (F) and the covering number N (F, || • || p , S, ϵ).EQUATIONLemma 7 ( [72, 3] ). Given a sample D = {(x i , ỹi )} m i=1 where xi ∈ X , ỹi ∈ Ỹ and D is associated with a dependency graph G, where χ f (G) is its fractional chromatic number, and a loss functionL : X × Ỹ × F → [0, M ],where F = { f : X → R}. Then, for any δ ∈ (0, 1), the following generalization bound holds with probability at least 1 -δ:EQUATIONwhere R * D (L • F) is the empirical fractional Rademacher complexity of the loss space. Lemma 8. Given a sample D = {(x i , ỹi )} 2m i=1 where xi ∈ X , ỹi ∈ Ỹ and D is associated with a dependency graph G, where χ f (G) is its fractional chromatic number, and each fractional independent vertex cover contains two independent samples, one positive and one negative. Under these conditions, χ f (G) satisfies:EQUATIONProof. 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 no 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, 2), (3, 4) Group 2: (2, 1), (4, 3) Group 3: (1, 3), (2, 4) Group 4: (3, 1), (4, 2) Group 5: (1, 4), (2, 3) Group 6: (4, 1), (3, 2)Therefore, χ f (G) = 6.For 2m samples, we can extract A 2 2m 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 2 2m pairs.After selecting the first group from these A 2 2m pairs, A 2 2m -m 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 in the remaining pairs still remains equal.A 2 2mm groups, i.e. , χ f (G) = 2(2m -1). This completed the proof.Restate of Theorem 1 (Generalization Bound for AUCSeg). Let E D LD (f ) be the population risk of LD (f ). Assume F ⊆ {f : X → R H×W ×K }, where H and W represent the height and width of the image, and K represents the number of categories, L(i) is the risk over i-th sample, and is µ-Lipschitz with respect to the l ∞ norm, (i.e. ∥ L(x) -L(y)∥ ∞ ≤ µ • ∥x -y∥ ∞ ). 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):LD (f ) -E D LD (f ) ≤ 8 N + η inner + η inter √ N A log (2Bµτ N k + C) + 3 1 2N + K 1 - 1 N log 4K(K -1) δ ,whereη inner = 48µτ ln N N , η inter = 2 √ 2τ, τ = max c∈[K] n (c) max n (c) mean 2 , n (c) max = max X n(X (c) ), n (c) mean = N i=1 n(X (c) i ), N = |D|, k = H × W and X (c) represents the pixel of class c in image X.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 or from two different images. Therefore, we transform the original problem into two sub-problems:EQUATIONwhere +/respectively denote the categories c/c ′ .For Part 1, we use the complexity measure technique of the covering number.Assuming log N (F, || • || ∞ , S, ϵ) ≤ A ϵ 2 log B ϵ • |D| • k + C ,where k = H × W is the pixel count in an image. A, B and C represent constants. Based on Lemma 5, we have:EQUATIONρ max = max X |D| n (X + ) n (X -) |N + | |N -| = 1 |D| • n + max • n - max n + mean • n - mean ≤ 1 |D| • τwhere:n + max = max X∈X n(X + ), n - max = max X∈X n(X -), n + mean = |D| i=1 n(X + i ), n - mean = |D| i=1 n(X - i ),and τ = max Substituting this result into Lemma 3, with probability at least 1 -δ, we haveEQUATIONFor Part 2, we 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 haveEQUATIONwhereρ(x) = |D|(|D|-1)n(X + )n(X -) |N+||N-|, and ω j denotes the weight assigned to the subset in the fractional vertex cover. Similar to Part 1, using the covering number we can getEQUATIONwhere we define c j asln 2 |D| • A • µ 2 • ρ 2 max • log 2B • µ • ρ max • |D| 2 • k + C as c j ,m j as |I j |.Assume that the number of images in the dataset is even, i.e. , |D| ≡ 0 (mod 2). We have:EQUATIONwhere ( * ) follows the Lemma 8.The second-order inequality is based on the fact that:EQUATIONdefine ρ j max as the largest ρ in the j-th cluster, and that:EQUATIONwhere:n + max = max X∈X n(X + ), n - max = max X∈X n(X -), n + mean = |D| i=1 n(X + i ), n - mean = |D| i=1 n(X - i ).and τ = maxc∈[K] n (c) max n (c) mean 2 .Combining Equation (34) and Equation (36) , we obtain:EQUATIONBased on Lemma 7 and Lemma 8, it comes:EQUATIONTherefore, by combining Equation ( 28),Equation (31) and Equation (38) , we can obtain:EQUATIONwhereη inner = 48µτ ln N N , η inter = 2 √ 2τ , N = |D| and k = H × W .This completed the proof.Restate of Proposition 1. Consider a dataset D that includes images with K different pixel categories. Let p i represent the probability of observing a pixel with label i in a given image. Randomly select B images from D as training data, whereB = Ω   log(δ/K) log(1 -min i p i )   .Then with probability at least 1 -δ, for any c ∈ [K], there exists X in the training data that contains pixels of label c.Proof. Define event A j as the extraction of N images where the pixels of class j appear at least once.Let p m = min{p 1 , p 2 , . . . , p K }, where m ∈ [K].The probability that each category appears at least once when randomly selecting N images:EQUATIONEQUATIONTherefore,EQUATIONThis completed the proof.In this section, Algorithm 2 provides a full version of Algorithm 1.Algorithm 2: AUCSeg Algorithm (Full Version) Input: Training data D, number of tail classes n t , labels of tail classes C t = {c i } nt i=1 , Memory Branch M = {M c1 , . . . M cn t }, memory size S M , sample ratio R S , resize ratio R R , max iteration T max , batch size N b Output: model parameters θ for iter = 1 to T max do D B = {(X i , Y i )} N b i=1 ← SampleBatch(D, N b ); C miss ⊆ C t ← M issingTIn 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 to each category, making sure that even if an image is sampled more than once (as both head and tail), each mini-batch still includes at least one 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, one has to employ a much larger batch size, which results in a significantly higher computational burden. Although the improved version of stratified sampling can 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 as an implicit data augmentation. This approach mitigates the sampling problem without compromising generalization ability. The following empirical results support our assertion.First, we counted the number of images containing pixels from each class in the Cityscapes, ADE20K, and COCO-Stuff 164K datasets. The results are shown in Table 5 , Table 6 , and Table 7 . 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.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:i w i -log e f (x i ) e f (x i ) + j̸ =i w j e f (x j ) ≥ i j̸ =i 1 n i n j -log 1 1 + e f (x j )-f (x i ),where,w j = 1/nj k̸ =i 1/n k and w i = k̸ =i 1/n k ni .Proof. For the AUC loss under the logistic surrogate loss function:ℓ logistic auc = ℓ logistic f (x + ) -f (x -) = i j̸ =i 1 n i n j -log 1 1 + e f (x j )-f (x i ) = i j̸ =i w i w j -log 1 1 + e f (x j )-f (x i ) = i w i j̸ =i w j -log(e f (x i ) ) + log(e f (x i ) + e f (x j ) ) = i w i   -log(e f (x i ) ) + j̸ =i w j log(e f (x i ) + e f (x j ) )   ≤ i w i   -log(e f (x i ) ) + log   j̸ =i w j (e f (x i ) + e f (x j ) )     = i w i   -log(e f (x i ) ) + log   e f (x i ) + j̸ =i w j e f (x j )     = i w i -log e f (x i ) e f (x i ) + j̸ =i w j e f (x j )where,w j = 1/ninj k̸ =i 1/nin k = 1/nj k̸ =i 1/n k and w i = k̸ =i 1/n k ni .This completed the proof.The theorem indicates that minimizing a weighted version of contrastive loss can 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. FastFCN [80] employs a novel joint upsampling module called Joint Pyramid Upsampling, which transforms the task of extracting high-resolution feature maps into a joint upsampling challenge.EMANet [55] enhances semantic segmentation by utilizing an EM-based 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 to 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 a novel rendering-style 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 mechanism 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 an 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 minimizing the balanced error.LDAM [10] improves the performance of tail classes by encouraging larger margins for tail classes.Focal Loss [56] is a modified cross-entropy loss designed to address class imbalance by focusing more on hard-to-classify examples, reducing the relative loss for well-classified instances and thus boosting performance on imbalanced datasets.DisAlign [104] introduces a unified framework for long-tail visual recognition by aligning feature distributions across different classes, using a novel distribution alignment technique that adjusts class-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.In Figure 6 , we present the results for each tail class. We select 7 classes with the fewest training samples from the Cityscapes dataset as tail classes: truck, bicycle, bus, train, traffic light, rider, and motorcycle. Our method not only achieves the highest overall mIoU but also shows significant improvements in these tail classes. Specifically, it outperforms the current SOTA method by more than 1% in several tail classes. 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).EQUATIONwhere C h represents the set containing the pixel counts of each head class, and C h denotes the set containing the pixel counts of each non-head class. The larger the r m value, the more imbalanced the dataset is.In Table 11 , 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. 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.In this paper, we use 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. Apart from semantic segmentation, salient object detection is also a pixel-level task. 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 [81, 53] as the backbone. The results are shown in Table 13 .Table 13 : Experimental results of AUCSeg in the salient object detection.Dataset ECSSD HKU-IS PASCAL-S MAE ↓ F β m ↑ E m ↑ MAE ↓ F β m ↑ E m ↑ MAE ↓ F β m ↑ E m ↑SI-SOD-EDN 0.0358 0.9084 0.9375 0.0287 0.8986 0.9442 0.0644 0.826 0.8859 +AUCSeg 0.0349 0.9087 0.9377 0.0278 0.8992 0.9455 0.0629 0.8281 0.8875Our AUCSeg achieves improvements across three commonly used evaluation metrics on three datasets, demonstrating that our method is highly versatile and extensible.In this section, we thoroughly explore the spatial resource consumption of 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 S M to 5 and conduct experiments on the ADE20K dataset. It is no longer necessary for samples of all classes to appear in the mini-batch, but rather only a minimum of 5 tail class samples are needed. 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 a significant expense. However, the T-Memory Bank substantially reduces this cost, enabling more efficient training without an intolerant increase in graphics memory.Moreover, we explore the effect of memory size S M on spatial resource consumption. The findings in Figure 8 show that the graphics memory occupation increases slightly as S M 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 S M = 5, significant performance improvements can be achieved with lower spatial resource consumption. 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 . The 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.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, in 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).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 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, 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. Why it is not feasible to focus on a fixed number of pixels?We 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 TMB, storing and retrieving are conducted on all pixels of an entire image.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:• First-In-First-Out (FIFO) replacement: Prioritizes replacing the images that were first stored in the Tail-class Memory Bank.• Last-In-First-Out (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 are 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. 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 a promising direction for future work.The detailed results of the ablation study on hyper-parameters are shown in Table 20 , Table 21 , Table 22 , and Table 23 . Explanation of the reasons why performance improvement decreases as memory size increases. 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.Therefore, we pursue a reasonable memory size. As shown in Table 20 , 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.We conduct ablation experiments on the ADE20K dataset to evaluate the impact of batch size. The results are shown in Table 24 :The performance improves as the batch size increases. Moreover, our AUCSeg is consistently effective across different batch sizes. 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, a trade-off that is generally beneficial since tail classes are typically more critical. For instance, on the Cityscapes dataset, AUCSeg exhibits a marginal decrease of 0.17% 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 at the blurry edges of objects. In contrast, gains in 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.We propose a general semantic segmentation method to deal with the potential bias toward long-tail objects. For fairness-sensitive scenarios, it might be helpful to improve fairness for long-tail groups.• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: 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.

Reviews: review: paper_summary: paper_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. 

The experimental evaluation in this paper assessed the performance of the proposed strategy on various datasets. Generally speaking, this paper is relatively detailed and comprehensive.
strength_weakness: strength_weakness: There are a few concerns about this paper:

- On COCO, the performance improvement of Tail Class seems to be limited. Could the author explain the reason?

- 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?
questions: questions: I thank the author for their detailed work. Nevertheless, there are a few questions I wonder and I hope the author could respond.

- 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?

- For the memory bank update problem, is there a more appropriate selection method instead of random replacement?
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: Overall, I believe this is a qualified paper for publication after addressing the following minor concerns:

1. 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).

2. 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.

3. 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.
questions: questions: Please refer to the weakness part.
limitations: limitations: None
paper_summary: paper_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.
strength_weakness: strength_weakness: Please refer to the questions.
questions: 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?
2. 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?
3. 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: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. In the tail-class memory bank module, how do you ensure that pasted tail pixels do not completely cover any category?
2. 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.
3. 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?
4. Pasting tail-class pixels onto original image might occlude original image classes; would this behavior affect performance?
5. 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)?
6. 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.
7. 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.
questions: questions: 1. I am confused about Tail-Class Memory Bank design, please refer weaknesses section above explaining them accordingly.
2.  Authors should clarify certain experimental outcomes referring weakness points mentioned earlier.
3. NeurIPS Paper Checklist lacks honest responses e.g., code provision/error bars reporting/new assets do not be contained, but all marked “YES”.
limitations: 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.

Comments: title: Comments from Reviewer tNYv
comment: Thank you so much for your feedback and acceptance. Following your suggestions, we will enrich the content of our paper in the final version. If you have any further questions, we would be happy to address them.
I appreciate the author's detailed response. Some of my concerns have been addressed. I am going to maintain my original score.
Thank you so much for your feedback and acceptance. Following your suggestions, we will enrich the content of our paper in the final version.
Thank you for the response. I have read your rebuttal and the comments from other reviewers, and I will maintain my original score.
We are thankful for your acceptance and constructive feedback.
The authors have addressed my concerns, I will raise my score correspondinly.
Thank you so much for your feedback. 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. The full code will be released after the acceptance. If you have any further questions, we would be happy to address them.
Thanks for the response. I will consider slightly increasing the score because some of my concerns are being relieved. 
By the way, will the code be released after the acceptance?
We provide the proof of the theorem used in the rebuttal below:

> **Theorem:** Minimizing the weighted contrastive loss approximately corresponds to minimizing an upper bound of the logistic AUC loss:
> $$
> \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]
> $$
> 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}$.

**Proof.**

For the AUC loss under the logistic surrogate loss function:
$$
\begin{aligned}
\ell_{auc}^{logistic}&=\ell_{logistic}\left(f(x^+)-f(x^-)\right)\\\\
&=\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]\\\\
&=\sum_{i}\sum_{j \neq i}w_iw_j\left[-\log\left(\frac{1}{1+e^{f(x^j)-f(x^i)}}\right)\right]\\\\
&=\sum_{i}w_i\sum_{j\neq i}w_j\left[-\log(e^{f(x^i)})+\log(e^{f(x^i)}+e^{f(x^j)})\right]\\\\
&=\sum_{i}w_i\left[-\log(e^{f(x^i)})+\sum_{j\neq i}w_j\log(e^{f(x^i)}+e^{f(x^j)})\right]\\\\
&\leq \sum_{i}w_i\left[-\log(e^{f(x^i)})+\log\left(\sum_{j\neq i}w_j(e^{f(x^i)}+e^{f(x^j)})\right)\right]\\\\
&=\sum_{i}w_i\left[-\log(e^{f(x^i)})+\log\left(e^{f(x^i)}+\sum_{j\neq i}w_je^{f(x^j)}\right)\right]\\\\
&=\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]
\end{aligned}
$$
where, $w_j=\frac{1/n_in_j}{\sum_{k\neq i}1/n_in_k}=\frac{1/n_j}{\sum_{k\neq i}1/n_k}$ and $w_i=\frac{\sum_{k\neq i}1/n_k}{n_i}$.

This completed the proof.