Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data

Thank you for your encouraging review. We will take your suggestions into account when preparing the final version. Please find responses to your specific questions below.

1. Essential References Not Discussed: The key contribution ... However, [1] has extended Cao's analysis to multiclass scenarios. Moreover, recent advances [2] also provide a fine-grained and tighter generalization guarantee for re-weighting and loss adjustment. I strongly suggest the authors provide some more essential discussion.

Weaknesses 1. Insufficient citation of relevant literature: The paper asserts that only one study has analyzed generalization guarantees. However, this overlooks several other significant works [1,2]. In particular, [2] offers insights that align closely with your research and analyzes existing reweighting methods by deriving tighter bounds. It might be beneficial to reference these works and compare their approaches with your findings to enrich the discussion.

Response: Thank you very much for bringing these references to our attention. They are indeed important contributions to the analysis of generalization guarantees in imbalanced learning. Briefly, these works focus on generalization with respect to the balanced loss, whereas our work addresses generalization guarantees with respect to the standard zero-one misclassification loss. We will include a more detailed discussion and comparison in the final version.

2. Weaknesses 2. Lack of empirical analysis on the hyperparameter: The IMMAX loss function introduces a hyperparameter for each class, which could pose significant tuning challenges, especially in large-scale datasets. The presence of numerous hyperparameters may also lead to unstable outcomes. A thorough empirical analysis is crucial to understand the impact and manageability of these hyperparameters. Conducting tests on a widely recognized dataset like ImageNet, which contains 1000 labels, would be highly beneficial to assess the scalability and robustness of the proposed method.

Response: The number of hyperparameters is indeed an important consideration. As discussed at the end of Section 5, when the number of classes is very large, the search space can be significantly reduced by assigning identical $\rho_k$ values to underrepresented classes while reserving distinct values for the most frequently occurring ones.

Moreover, while $\rho_k$ values can be freely searched, the search can be guided by the vector $[\rho_k / \sum_{k = 1}^c \rho_k]_k$ near $\mathbf{r}$, which corresponds to the theoretically optimal values in the separable case. This approach was also adopted in our experiments.

We have not observed instability issues in our experiments. However, as suggested by the reviewer, we will include additional experimental results in the final version to further study this point empirically. ImageNet would indeed be an interesting dataset to try.

3. Questions: Does the proposed IMMAX loss function work like a class-wise temperature scaling technique based on the CE loss? Can I interpret it this way?

Response: Yes, one could interpret it as a class-based temperature scaling derived from the logistic loss. However, our choice is grounded in a theoretical argument that justifies its ability to establish distinct confidence margins across classes, as elaborated in our analysis. In fact, our theoretical framework could provide an insightful interpretation and justification for the familiar temperature parameters.

Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.

1. Methods And Evaluation Criteria: The methods used for the theoretical study in the paper are based on functional analysis for the related generalization error and 0-1 error and Rademacher analysis. These are appropriate and convincing. If more approximation theory or deep neural network analysis could be used, they would lead to further research activities in dealing with nonlinear or bounded hypotheses.

Response: To clarify, the margin-based generalization bounds we presented also apply to families of neural networks. The reviewer is correct that a deeper analysis from the perspective of approximation theory could further complement our results. However, this is a broader question that extends to other types of learning guarantees as well.

2. Essential References Not Discussed: Consistent bounds for imbalanced binary classification have been well studied, much earlier than the first reference. One can find such results in the literature of Zhang (Ann. Stat. 2004), Bartlett-Jordan-McAuliffe (JASA 2006), Chen-Wu-Ying-Zhou (JMLR 2004).

Response: Thank you for your suggestion. We will add these references. However, we note that these studies focus on Bayes consistency in standard binary classification, rather than specifically addressing the imbalanced setting.

3. Other Comments Or Suggestions: It would be better if more general hypothesis sets generated by deep neural networks could be considered. Moreover, the authors might consider consistency bounds for a class-imbalanced margin loss when the hypothesis set is not complete, especially those corresponding to Theorem 4.1, with uniformly bounded hypotheses.

Response: Thank you for the suggestions. Our H-consistency bounds in Theorem 3.3 can indeed be extended to the uniformly bounded hypothesis sets considered in Theorem 4.1. In this case, the bounds would depend on the complexity of the hypothesis class, similar to the H-consistency bounds presented in [1]. We will include this extension in the final version.

We would be happy to discuss extensions to other neural network families the reviewer might suggest.

[1] Awasthi et al. H-Consistency Bounds for Surrogate Loss Minimizers. ICML 2022.

Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.

1. Essential References Not Discussed: The paper cites key literature in the field of imbalanced learning, including data modification techniques, cost-sensitive methods, and logistic loss modifications. However, it could benefit from discussing more recent advances in deep learning-based approaches for imbalanced data, such as those involving neural network architectures specifically designed to handle class imbalance.

Response: We aimed to provide a comprehensive overview of related work given the space constraints. We would be happy to expand our discussion to include architecture-based solutions, some of which are already covered in the survey paper we referenced. If the reviewer has specific publications in mind, we would gladly incorporate and discuss them in more detail.

2. Weaknesses: The performance of IMMAX in large-scale datasets is not clear, which is the key to its application in practical scenarios.

Questions: How does the IMMAX algorithm scale with increasing dataset size and dimensionality? Are there any computational limitations that might affect its practicality for very large datasets?

Response: The dependency of our solution on sample size and dimensionality is similar to that of standard neural networks trained with cross-entropy loss (that is the logistic loss when softmax is applied to logits). Thus, our approach remains practical when using optimizers such as SGD, Adam, or AdaGrad. Our solution does depend on the number of classes, but this dependency is inherent to standard multi-class neural network solutions as well.

3. Other Comments Or Suggestions: It is suggested to add the top and bottom lines in Tables 1, 2, and 3 to make them more intuitive.

Response: Thank you for the suggestion. We’ll add the lines to the tables in the final version.

Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.

1. Weaknesses 1: The experimental results presented in the paper (including the results of the comparison methods) are significantly better than those reported in previous papers. Could the authors provide further explanation for this discrepancy? For example, are there differences in the experimental setup, data preprocessing, or evaluation metrics that could account for the improved performance?

Question 1: The results in Table 1 appear to differ significantly from those reported in previous papers ... Could the authors provide an explanation for these differences?

Response: Our work focuses on the standard and unmodified zero-one misclassification loss, which remains the primary objective in many machine learning applications, as discussed in the introduction. Accordingly, we report standard accuracy based on this loss function. In contrast, some previous studies report "balanced accuracy," which averages misclassification errors uniformly across classes (i.e., the balanced loss). This difference in evaluation metrics explains the higher values reported in our results. The balanced accuracy of Balanced Softmax (BS) on CIFAR-10 with a ratio of 100 in our experimental setting is also around 80%. We will provide further elaboration in the final version.

Regarding the experimental setup and data preprocessing, we strictly followed the procedure of Cao et al. (2019), ensuring consistency in all these aspects.

2. Weaknesses 2: The selection of $\rho$ appears to be based on the validation set ... Could the authors discuss potential strategies for selecting these parameters in real-world scenarios where validation data may be limited?

Response: We tune the hyperparameters using a validation set held out separately from the training set. Additional details on cross-validation are provided in Appendix B, and further elaboration will be included in the final version. Empirically, performance is not sensitive to variations in the neighborhood of the theoretically optimal values of the $\rho_k$s indicated below.

As discussed at the end of Section 5 (Lines 302-309, second column), while the $\rho_k$ values can be freely searched over a range of values in our general algorithm, the search can be guided by the vector $[\rho_k / \sum_{k = 1}^c \rho_k]_k$ near $\mathbf{r}$, which corresponds to the theoretically optimal values of $\rho_k$ in the separable case. We adopted this approach in our experiments. Moreover, in scenarios with a large number of classes, the search space can be significantly reduced by assigning identical $\rho_k$ values to underrepresented classes, while reserving distinct $\rho_k$ values for the most frequently occurring classes. This strategy enhances practicality when validation data is limited, with only a minor impact on results.

3. Question 2: The IMMAX loss function differs significantly in form from Softmax ... If the training dataset were balanced, would IMMAX perform better than the standard softmax cross-entropy loss?

Response: When the training dataset is balanced, the theoretically optimal values of $\rho_k$ are identical across all classes. In this case, IMMAX becomes equivalent to the standard softmax cross-entropy loss with an appropriate regularization parameter. Therefore, IMMAX would perform similarly to the standard softmax cross-entropy loss in the balanced setting.

4. Question 3: IMMAX seems more akin to a contrastive loss. Could it be applied in a supervised contrastive learning scenario? If so, how would it compare to existing supervised contrastive learning methods?

Response: The form of our loss function has some similarity with supervised contrastive losses (e.g., [1]), where a scalar temperature parameter is used in the inner product argument of the exponential. However, in our case, distinct parameters are introduced to allow different confidence margins across classes, serving a different purpose than in contrastive learning. Nevertheless, our margin analysis could provide a useful tool for analyzing contrastive learning. We will acknowledge this connection, include a brief discussion, and thank the reviewer for the suggestion.

[1] Khosla et al. Supervised Contrastive Learning. NeurIPS 2020.

5. Other Comments Or Suggestions: In the paper, the meaning of $\rho$ appears to be ambiguous, as it is redefined in line 366.

Response: Thank you for pointing this out. We will change the notation here to avoid any overlap with our confidence margin definition of $\rho$ throughout the paper.