We sincerely thank you for spending time and providing valuable feedback. We appreciate all of your suggestions and we have addressed all your questions below by providing our responses as well as our additional experimental results.

W1. More general setting with arbitrary anomaly scores.

R1. The form of the anomaly score adopted in this paper, derived as classification confidence for the K+1 class, is a specific case in implementation. We have conducted experiments with more general forms of anomaly scores and provide the corresponding experimental results. In particular, we chose two distinct anomaly scores, energy and OE, for the application of our method. The experimental results are outlined below:

The experimental results demonstrate that our method is effective in broader settings, accommodating different widely-used anomaly scores.

W2. Differences with PixMix [a]

R2. PixMix stands out as an elegant and effective data augmentation technique, introducing new complexity information into the training procedure through the utilization of fractals and feature visualizations, which comprehensively improves safety measures. However, there are several key differences between this approach and ours: (1) Different Motivations: Pixmix approach is introduced for multiple important purposes, e.g., enhancing OOD robustness, ensuring prediction consistency, enhancing resilience against adversaries, obtaining well-calibrated uncertainty estimates, and facilitating the detection of anomalous inputs. Our work focuses on theoretical analysis to show why and how the diversity of outliers impacts the OOD detection ability. As a result, we apply mixup to increase the diversity of outliers and thus improve OOD detection capabilities. (2) Different Mixup Goal: The main role of mixup in Promix is to fuse the original images with complex fractals and feature visualizations, as fractals and feature visualizations do not belong to any particular class, this method does not change the semantics of the original data. However, mixup in our method is to combine outliers with different semantic information to generate new outliers, and the new outliers have different semantic information with the original data. Moreover, unlike pixmix, we do not perform any operations on the ID data, only on outliers.

W3. Missing related works which replace auxiliary negatives with properly trained generative models.

R3: We thank the reviewer for pointing out these exciting works that use generative models to synthesize outliers for training OOD detectors. [b] is the first to propose using a generative model to generate outliers on the classification boundary of ID data for training. [c] obtains the the synthetic outliers by sampling a generative model based on normalized flow that is trained alongside a dense discriminative model in order to produce samples at the border of the training distribution, which produces better performance. [d] Building a discriminator on features computed by a closed-world K-way network and carefully selected The GAN discriminators on some real outlier data, augmenting the outlier set with adversarially synthesized "fake" data, which achieves good performance in open-set recognition. We will review these works in the manuscript.

[a] Dan Hendrycks, Andy Zou, Mantas Mazeika, Leonard Tang, Bo Li, Dawn Song, Jacob Steinhardt: PixMix: Dreamlike Pictures Comprehensively Improve Safety Measures. CVPR 2022

[b] Kimin Lee, Honglak Lee, Kibok Lee, Jinwoo Shin: Training Confidence-calibrated Classifiers for Detecting Out-of-Distribution Samples. ICLR 2018

[c] Matej Grcic, Petra Bevandic, Sinisa Segvic: Dense Open-set Recognition with Synthetic Outliers Generated by Real NVP. VISIGRAPP 2021

[d] Shu Kong, Deva Ramanan: OpenGAN: Open-Set Recognition via Open Data Generation. ICCV 2021

We sincerely thank you for all the comments, we have addressed all your questions below and hope they have clarified all confusion you had about our work.

W1. more careful and rigorous with the theoretical terms , such as the "generalization risk" is not rigorous in theory.

R1. Thank you for the important suggestion. We have changed "generalization risk" to "generalization error."

W2. Discussion about the assumptions made in theory.

R2. The key assumptions made in the theoretical analysis are: (1) Semantic difference under mixup: This assumption states that when two samples belonging to different classes are mixed, the resulting mixed sample may have a semantic meaning different from the original samples. This assumption is grounded in the observation that mixed samples often presents an ambiguous semantic information. The practice of using 'soft labels' in vanilla mixup also supports this assumption, suggesting that the mixup process alters the original semantics of the samples. (2) Low error of the ideal OOD detector $\lambda$: This assumes we can find an ideal detector in the hypothesis class H that achieves a sufficient small or near zero error on the OOD distribution. With powerful deep networks, we can expect to find detectors with small $\lambda$. As if $\lambda$ is large, there does not exists a good OOD detectors in the hypothesis classes, which implies that we cannot expect to achieve good OOD detection. (3) Equal empirical error when training with more diverse outliers: The assumption is rooted in the over-parameterized setting of deep neural networks. The abundance of trainable model parameters enables these models to achieve near-perfect fitting to a wide range of functions during training, resulting in sufficiently small training losses. This implies that, when well-trained, the model can attain comparable and low empirical errors when exposed to more diverse outliers.

W3. For theorem 2, did the authors consider the sample complexity of both the vanilla auxiliary outlier set and the diverse outlier set? The sample complexity and model complexity should play an important role in the bound during analysis for these two cases.

R3. Thank you for raising questions regarding the complexity of samples and models. In our research, our primary focus lies in addressing the errors induced by distribution shift caused by auxiliary outliers that fail to fully cover the complexity of the real-world out-of-distribution (OOD) scenarios. This limitation stands as a critical factor constraining the performance of OOD detection. Issues related to generalization errors arising from model and sample complexities are more prevalent in traditional machine learning. However, in our specific task, such errors are often overshadowed by the disparities introduced by auxiliary outliers' inability to adequately cover the complexity of real-world OOD data. Therefore, in the context of our paper, we assume the model to be over-parameterized and the training data to be abundant, implying that the model can effectively fit the distribution of the training data [1]. We acknowledge your perspective, we will give a more comprehensive and precise analysis about how sample complexity and model complexity jointly influence the ultimate decision boundaries in future work.

W4. how well the h_mix compared with the predictor h_div.

R4. We conducted experiments to demonstrate the performance comparison between $h_{mix}$, trained with mixed outliers, and $h_{div}$, trained with more diverse outliers. Specifically, we chose CIFAR-100 as the in-domain (ID) dataset. For $h_{mix}$, we extracted data from 250 classes in ImageNet-RC to serve as less diverse outliers, and applied mixup outliers during training. As for $h_{div}$, we utilized the entire set of classes (1000 classes) from ImageNet-RC as more diverse outliers for direct training. Additionally, we trained model $h$ by directly training on data from 250 classes as outliers from ImageNet-RC. The experimental results are as follows:

From the experiments, it is evident that the model $h_{div}$, trained with more diverse outliers, outperforms the model $h$ trained without such diversity. However, after enhancing the diversity of outliers through mixup, the performance of $h_{mix}$ surpasses that of $h_{div}$. This validates the effectiveness of our approach and the underlying theoretical framework. The more intuitive comparison is illustrated in Figure 2(a) of our paper.

We appreciate your thorough and insightful reviews and will address your concerns one by one.

W1. Novelty Concerns.

R1. Our contribution goes beyond employing mixup to improve OOD detection from the following perspectives. (1) We first present a theoretical and empirical understanding demonstrating a more diverse set of auxiliary outliers is critical in improving OOD detection by lowering the upper bound of OOD detection error. Our findings could offer fresh theoretical insights for future OOD detection advancements. (2) Building on the proposed theory, we develop a simple yet effective method by leveraging mixup to enrich outlier diversity with corresponding theoretical evidence. Note that unlike the previous mixup-based methods, our core motivation for introducing mixup is to improve the diversity of the auxiliary outlier dataset instead of designing novel mixup strategy. (3) Unlike the insightful methods proposed in [1, 2, 3] by applying mixup to ood detection, our main contribution is to explore a more diverse auxiliary outlier space. This focus sets our research different from existing ones.

W2. The effectiveness of the modification to mixup from theoretical and experimental perspectives.

R2. Theoretical Perspective: As the potential space for auxiliary outliers data can be excessively large, the majority of outliers uninformative for model regularization, which may lead to inefficient and insufficient exploration and exploitation of these outliers [4][5]. To mitigate this, we strategically select the mixed outlier samples that are closest to the in-distribution boundary. These samples are more likely to be misclassified as in-distribution (ID) data and need to receive more attention. In our theory, mixup can generate new outliers with semantics different from the original data, and this selection strategy can select the newly generated outliers that are easy to be misclassified by the model for training. Empirical Validation: Ablation experiments were performed on this module in Table 2. We present the results here: For cifar10 dataset:

For cifar100 dataset:

These results clearly illustrate that selecting Mixed outliers based on their out-of-distribution (OOD) score consistently enhances OOD detection performance compared to using only Mixup. This underlines the significant benefits of our proposed modification in improving the effectiveness of OOD detection.

W3. Concerns about experimental settings on auxiliary datasets.

R3. Thank you for the detailed and interesting comments. We would address this concern in the following ways: (1) In practical applications, access to a more diverse auxiliary dataset is often possible, such as crawling data from the Internet. This approach allows to train the model with a more diverse auxiliary outlier dataset. Consequently, this setting has been adopted by many related studies within the field. (2) While ImageNet-RC offers greater diversity compared to datasets like CIFAR-10/100, it still does not fully represent the vast and complex nature of true open-world out-of-distribution (OOD) data. This limitation highlights the need for even more diverse datasets to truly model the real-world data. (3) We also experimentally confirm that our method is still effective even when the diversity of auxiliary outliers is not significantly higher than ID data. In the experiment "Q2 Reliability", we tested the effectiveness of our method under the outliers dataset with different diversity. As can be seen from Figure 2, on the cifar-100 dataset, when we restrict the diversity of the outliers dataset (using only 100 classes of the ImagenetRC dataset as outliers, the diversity of the outliers dataset is comparable to that of the ID dataset), the OOD detectors are still able to benefit from outliers. When our method is adopted to improve the diversity of outliers, the performance of the model is significantly improved (The FPR95 metric significantly decreased from 26% to 20%.), which also confirms the effectiveness of our method and theory.

[1] Intra-class Mixup for Out-of-Distribution Detection

[2] CutMix: Regularization Strategy to Train Strong Classifiers with Localizable Features

[3] MixOOD: Improving Out-of-distribution Detection with Enhanced Data Mixup

[4] POEM: Out-of-Distribution Detection with Posterior Sampling

[5] ATOM: Robustifying Out-of-distribution Detection Using Outlier Mining

The authors' responses address most of my concerns—however, the concern regarding the auxiliary dataset remains. Thus, I would like to stand by my original score. However, I would like to note that I will not fight for a rejection.