Out-Of-Distribution Detection with Diversification (Provably)

The detailed proof of the validity of the assumption "Since $\mathcal X_{aux}\subset\mathcal X_{ood}$ , then $\mathcal H^*_{ood}\subset \mathcal H^*_{aux}$".

For simplicity, we omit $\mathcal X_{id}$, assuming that the behavior is similar in this input space region for $h^*_{ood}$ and $h^*_{aux}$.

We first express the expected error of hypotheses $h$ on the training data distribution $\mathcal P_{\widetilde{\mathcal X}}$ and the unknown test-time data distribution $\mathcal P_{\mathcal X}$ as follows:

$$\begin{cases} \epsilon_{\mathcal P_{\widetilde{\mathcal X}}}(h, f) = \int_{\mathcal X_{aux}} |h(x) - f(x)|dx = \epsilon_1, \\\\ \int_{\mathcal X_{ood} \setminus \mathcal X_{aux}} |h(x) - f(x)|dx = \epsilon_2, \\\\ \epsilon_{\mathcal P_{\mathcal X}}(h, f) = \int_{\mathcal X_{ood}} |h(x) - f(x)|dx = \int_{\mathcal X_{aux}} |h(x) - f(x)|dx + \int_{\mathcal X_{ood} \setminus \mathcal X_{aux}} |h(x) - f(x)|dx = \epsilon_1 + \epsilon_2. \end{cases}$$

From the above expressions, we obtain:

$$\begin{cases} \mathcal{H}^*_{aux} = \\{ h : \arg \min\limits_h \epsilon_1 \\}, \\\\ \mathcal{H}^*_{other} = \\{ h : \arg \min\limits_h \epsilon_2 \\}, \\\\ \mathcal{H}^*_{ood} =\\{ h : \arg \min\limits_h (\epsilon_1 + \epsilon_2) \\}. \end{cases}$$

The model is over-parameterized (line 126), which implies that our hypothesis space is large enough. Consequently, there exists the ideal hypothesis $h$ such that both $\epsilon_1$ and $\epsilon_2$ are minimized, i.e., $\mathcal{H}^*_{aux} \cap \mathcal{H}^*_{other} \neq \emptyset$. In this scenario, $\min_h (\epsilon_1 + \epsilon_2) = \min\limits_h \epsilon_1 + \min\limits_h \epsilon_2$. We denote $\mathcal{H}^*_{ood} = \mathcal{H}^*_{aux} \cap \mathcal{H}^*_{other}$, thus $\mathcal{H}^*_{ood} \subset \mathcal{H}^*_{aux}$.

The detailed proof from line 530 to the definition of $\beta$.

Let's first review line 530 on the demonstration of theorem 1:

$$GError(h)\leq\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h,f)+\textcolor{blue}{\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h^*_{ood},f)}+\textcolor{blue}{\epsilon_{x\sim\mathcal P_{\mathcal X}}(h^*_{ood},f)} \\ +\int |\phi_{\mathcal X}(x) -\phi_{\widetilde{\mathcal X}}(x) |\left| h(x)-h^*_{aux}(x) \right| \,dx +\epsilon_{x\sim\mathcal P_{{\mathcal X}}}(h^*_{aux},h^*_{ood}) \\ +\textcolor{blue}{\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h^*_{aux},f)}+\textcolor{blue}{\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h^*_{ood},f)}$$

We denote $\beta_1=\underset{h\in\mathcal H}{\min}\epsilon_{x\sim\mathcal P_{\mathcal X}}(h,f)$, $\beta_2=\underset{h\in\mathcal H}{\min}\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h,f)$ as the error of $h^*_{ood}$ and $h^*_{aux}$ on $\mathcal P_{\mathcal X}$ and ${\mathcal P}_{\widetilde{\mathcal X}}$, respectively.

In other word, for any $h\in \mathcal H^*_{ood}$, $\epsilon_{x\sim\mathcal P_{\mathcal X}}(h,f)=\beta_1$. For any $h\in \mathcal H^*_{aux}$, $\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X} }}(h,f)=\beta_2$.

As a result, $\textcolor{blue}{\epsilon_{x\sim\mathcal P_{\mathcal X}}(h^*_{ood},f)=\beta_1}$, $\textcolor{blue}{\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h^*_{aux},f)=\beta_2}$.

Considering that $\mathcal H^*_{ood}\subset \mathcal H^*_{aux}$ (mentioned in line 126), for any $h\in \mathcal H^*_{ood}$, $h\in \mathcal H^*_{aux}$ is holds. As a result, $\textcolor{blue}{\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h^*_{ood},f)=\beta_2}$. We have:

$$GError(h)\leq \epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h,f)+\textcolor{blue}{\beta_2}+\textcolor{blue}{\beta_1}+\int |\phi_{\mathcal X}(x) -\phi_{\widetilde{\mathcal X}}(x) |\left| h(x)-h^*_{aux}(x)\right|dx +\epsilon_{x\sim\mathcal P_{\mathcal X}}(h^*_{aux},h^*_{ood})+\textcolor{blue}{\beta_2}+\textcolor{blue}{\beta_2}$$

We denote $1/4*\beta=\max\\{ \beta_1,\beta_2\\}$, so:

$$GError(h)\leq\epsilon_{x\sim\mathcal P_{\widetilde{\mathcal X}}}(h,f)+\int|\phi_{\mathcal X}(x)-\phi_{\widetilde{\mathcal X}}(x)||h(x)-h^*_{aux}(x)|dx+\epsilon_{x\sim\mathcal P_{\mathcal X}}(h^*_{aux},h^*_{ood})+\textcolor{blue}{\beta}$$

Proof of the negligible effect of $\mathcal X_{div}$ on $\beta_2$.

Specifically, $\beta_1$ and $\beta_2$ represent the error of the ideal hypothesis on the unknown test-time data distribution $P_{\mathcal{X}}$ and the training data distribution $P_{\widetilde{\mathcal{X}}}$, respectively. We can derive that $\beta_2 \leq \beta_1$. Moreover, given that our model is over-parameterized, we have a sufficiently large hypothesis space to include a near-ideal hypothesis such that $\beta_1$ is sufficiently small, i.e., $\beta_1 \rightarrow 0$. As a result, we can conclude that $\beta_2 \rightarrow 0$. We have put the detailed proof in the official comment.

The detailed proof as follows:

Considering that $\beta_1$ and $\beta_2$ represent the error of the ideal hypothesis on the unknown test-time data distribution $P_{\mathcal{X}}$ and the training data distribution $P_{\widetilde{\mathcal{X}}}$, respectively, we have:

$$\beta_2 = \underset{h \in \mathcal H}{\min} \epsilon_{x \sim \mathcal P_{\widetilde{\mathcal X}}}(h, f) = \min\limits_{h \in \mathcal H} \int_{\widetilde{\mathcal X}} |h(x) - f(x)|dx \\$$ $$\beta_1 = \underset{h \in \mathcal H}{\min} \epsilon_{x \sim \mathcal P_{\mathcal X}}(h, f)= \min\limits_{h \in \mathcal H} \int_{\mathcal X} |h(x) - f(x)|dx = \min\limits_{h \in \mathcal H} \left( \int_{\widetilde{\mathcal X}} |h(x) - f(x)|dx + \int_{\mathcal X \setminus \widetilde{\mathcal X}} |h(x) - f(x)|dx \right) \ge \min\limits_{h \in \mathcal H} \int_{\widetilde{\mathcal X}} |h(x) - f(x)|dx + \min\limits_{h \in \mathcal H} \int_{\mathcal X \setminus \widetilde{\mathcal X}} |h(x) - f(x)|dx \ge \beta_2$$

In our setting, the model is over-parameterized, meaning we have a sufficiently large hypothesis space to include a near-ideal hypothesis such that $\beta_1$ is sufficiently small. Therefore, we can denote $\beta_1 \rightarrow 0$. Given that $\beta_2 \leq \beta_1$, $\beta_2 \rightarrow 0$. Thus, $\beta_1$ and $\beta_2$ are both negligible, and we use a small value $\beta$ to unify them in Theorem 1.

We thank the reviewer for recognizing our novel method and satisfying experiments. We appreciate your support and constructive suggestions and address your concerns as follows.

---

W1. The quantities $h^*_{ood}$ and $h^*_{aux}$ are never defined. Why would an argmin be a set in that case?

Thank you for your valuable comment. We agree that clearer definitions of $h^*_{ood}$ and $h^*_{aux}$ would improve our manuscript. Our choice to define the argmin as a set was purposeful and well-founded and we appreciate to clarify this as follow:

1) The definition of quantities $h^{*}_{aux}$ and $h^{*}_{aux}$.

$h^*_{ood}$ and $h^*_{aux}$ is defined as the element in $\mathcal H^*_{ood}$ and $\mathcal H^*_{aux}$, respectively, which can be denoted as: $h^*_{ood}\in \mathcal H^*_{ood}, h^*_{aux} \in \mathcal H^*_{aux}$, where $\mathcal H^*_{ood}$ and $\mathcal H^*_{aux}$ refers to the sets of ideal hypotheses on the training data distribution $P_{\widetilde{\mathcal{X}}}$ and test-time data distribution $P_{\mathcal{X}}$. We will add the definition in manuscript.

2) Why would an argmin be a set?

(i) Our setting requires us to represent the optimal hypothesis as a set. In our setting, $\mathcal H_{aux}$ contains all hypotheses optimal for the training data distribution. However, these hypotheses may perform inconsistently on the test-time data distribution, necessitating the use of a set rather than a single $h^*_{aux}$.

(ii) The optimization problem behind deep neural networks is highly non-convex and the optimal solution is not unique [1] [2]. Therefore, defining argmin as a set offers generality.

(iii) Representing argmin as a set is not unprecedented in the field. For example, the theoretical analysis in [3] also employs this set-based representation.

---

W2. The authors define $\beta_1$ and $\beta_2$ as constants, but 1) they depend on $P_\mathcal X$ which is supposed to be affected by the later-introduced $\mathcal X_{div}$ and 2) the parts of line 530 that are replaced do not seem to match the definition of $\beta$'s.

Sincerely thank you for your thorough review. We realize our derivation omitted some explanations, leading to misunderstandings. We're happy to clarify in detail as follow:

1) Clarification of $\beta_1$and $\beta_2$.

(i) We do not define $\beta_1$and $\beta_2$ as constants. This misunderstanding may have arisen from our definition of $\beta$ as a constant in Theorem 1. We will clarify this in the revised paper.

(ii) $\beta_1$ is not affected by $\mathcal X_{div}$. $\beta_1$ depends on the unknown test data distribution $P_{\mathcal X}$. The later-introduced $\mathcal X_{div}$ only affects the training data distribution, thus $\beta_1$ is unaffected by $\mathcal X_{div}$.

(iii) While $\beta_2$ is indeed influenced by $\mathcal X_{div}$, we can prove that $\beta_2$ is bounded by a very small constant. Therefore, in subsequent analyses, the effect of $\mathcal X_{div}$ on $\beta_2$ is negligible. We have put the detailed discussion and proof in the official comment (1).

2) The parts of l.530 that are replaced do not seem to match the definition of $\beta$'s.

Upon careful examination, we believe the derivation is accurate. However, we recognize that the presentation could be enhanced for clarity. We have provided a detailed derivation in the official comment (2).

---

W3. Demonstrations of Theorems 2 and 3 seem to rely on one argument, which is: "Since $\mathcal X_{aux}\subset\mathcal X_{ood}$ , then $\mathcal H^*_{ood}\subset \mathcal H^*_{aux}$" I am concerned with the validity of this assumption.

Thank you for your valuable feedback and we greatly appreciate your attention to detail. We illustrate the validity of this assumption as follow:

(i) The assumption is reasonable in the over-parameterized setting. Considering that we can decomposing the ideal error on $\mathcal X_{ood}$ into two components: one for $\mathcal X_{aux}$ and another for the remaining OOD data $\mathcal X_{ood} \setminus \mathcal X_{aux}$. Considering that the model is over-parameterized (line 126), there exists the ideal hypothesis minimizing both error simultaneously. In other word, $\mathcal X_{ood}$ is the intersection of the sets of optimal hypothesis for auxiliary and remaining data, thereby $\mathcal H^*_{ood}\subset\mathcal H^*_{aux}$. We have provided a detailed derivation in the official comment (3).

(ii) Discussion of the Counterexample. The counterexample suggests that the model's optimal solution in $\mathcal X_{ood}$ may not be optimal in $\mathcal X_{aux}$ because it balances performance in $\mathcal X_{ood} \setminus \mathcal X_{aux}$. This assumes there is no hypothesis $h \in \mathcal H$ that achieves optimal performance in both $\mathcal X_{aux}$ and $\mathcal X_{ood} \setminus \mathcal X_{aux}$. However, in over-parameterized setting, there exists the ideal hypothesis that is optimal in both $\mathcal X_{aux}$ and $\mathcal X_{ood} \setminus \mathcal X_{aux}$. Therefore, the counterexample does not hold in our setting.

---

4. line 111 perhaps you meant $\mathcal X_{id}$ instead of $\mathcal Y_{id}$?

5. line 122 $\epsilon$ is called a probability, whereas it is an expectation.

6. Some typos

Thank you for your valuable suggestions, we have addressed your concerns as follows:

(i) We would like to clarify that $\mathcal X_{ood}$ is outside the support of $\mathcal Y_{id}$. In other words, $\mathcal X_{id}$ is within the support of $\mathcal Y_{id}$.

(ii) We acknowledge the error on line 122 and have corrected it.

(iii) We have thoroughly reviewed and revised all representation issues throughout the paper.

References:

[1] The Loss Surface of Deep and Wide Neural Networks.

[2] On the Quality of the Initial Basin in Overspecified Neural Networks.

[3] Agree To Disagree: Diversity Through Dis-Agreement For Better Transferability.

Thank you for your reviews. We are encouraged that you appreciate our studied problem and state-of-the-art result. We address your concerns as follows.

W1. My biggest concern is that there are already some papers that theoretically analyze the effect of auxiliary outliers and proposed some complimentary algorithms based on mixup, such as [1], [2] and [3]. It might be useful to clarify the differences.

Thanks for mentioning [1] [2] [3]. We first review these related works and then clarify the differences from the perspectives of motivations, techniques, and theory. Additionally, we have incorporated these related works into the manuscript.

(i) Reviews of related works.

DOE [1] proposes a novel and effective approach for improving OOD detection performance by implicitly synthesizing virtual outliers via model perturbation.

DAL [2] introduces a novel and effective framework for learning from the worst cases in the Wasserstein ball to enhance OOD detection performance.

DivOE [3] is an innovative and effective method for enhancing OOD detection performance by using informative extrapolation to generate new and informative outliers.

(ii) Differences in motivations. DiverseMix has a different motivation from DOE, DAL and DivOE. Our DiverseMix is proposed for enhancing the diversity of auxiliary outliers set through semantic-level interpolation to enhance OOD detection performance. In comparison, DOE focuses on improving the generalization of the original outlier exposure by exploring model-level perturbation. DAL focus on crafting an OOD distribution set in a Wasserstein ball centered on the auxiliary OOD distribution to alleviating the distribution discrepancy between auxiliary outliers and unseen OOD data. DivOE focuses on extrapolating auxiliary outliers to generate new informative outliers for enhance OOD detection performance.

(iii) Differences in technique. Our method, DiverseMix, has a different algorithmic design compared to others. Specifically, DiverseMix adaptively generates interpolation strategies based on outliers to create new outliers. In contrast, DOE, DAL, and DivOE primarily rely on adding perturbations. Specifically, DOE, DAL, and DivOE apply perturbations at the model level, feature level, and sample level, respectively, to mitigate the OOD distribution discrepancy issue.

(iv) Differences in theory. We prove that a more diverse set of auxiliary outliers could improve the detection capacity from the generalization perspective, and this theoretical insight inspired our method DiverseMix. We also provide insightful theoretical analysis verifying the superiority of DiverseMix. In comparison, DOE revealing that model perturbation leads to data transformation to enhance the generalization of OOD detector. DAL finds that the distribution discrepancy between the auxiliary and the real OOD data affecting the OOD detection performance. DivOE is based on the perspective of sample complexity to demonstrate its effectiveness.

References:

[1] Out-of-distribution Detection with Implicit Outlier Transformation.

[2] Learning to augment distributions for out-of-distribution detection.

[3] Diversified outlier exposure for out-of-distribution detection via informative extrapolation.

We sincerely thank the reviewer for your valuable comments and appreciate your recognition of the effective method as well as sufficient theoretical guarantees. We provide detailed responses to the constructive comments.

W1. The reviewer has some concerns regarding the empirical evaluations of diverseMix. In particular, the choice of how the ImageNet-1k is split into ImageNet-200 as ID while the remaining data is leveraged as OOD seems arbitrary.

Thank you for raising this important question. We sincerely appreciate your attention to the details of our experiments and pleasure to provide further clarification.

(i) Our splitting strategy was not arbitrary but carefully considered. We randomly selected 200 classes from ImageNet-1K as the ID categories, while the remaining 800 classes were used as OOD categories. This setting ensures the validity of our experiments.

(ii) This experiment setting is consistency with prior work. We followed the benchmark [1] to set ImageNet-200 as the ID dataset for our experiments.

Q1. The primary question of the reviewer is why not leverage the entire ImageNet-1k dataset for ID whilst leveraging other unlabeled datasets for the auxiliary data?

Thanks for the constructive suggestions. We are grateful for this insight and have conducted the additional experiments as suggested. Specifically, we used the entire ImageNet-1K dataset as the ID dataset and employed the SSB-hard dataset as auxiliary outliers. The experimental results are shown below, with columns representing different OOD datasets. The values in the table are presented in the format (FPR $\downarrow$ / AUROC $\uparrow$). From the experimental results, it is evident that our method remains effective even when ImageNet-1K is used as the ID dataset.

References:

[1] OpenOOD v1.5: Enhanced Benchmark for Out-of-Distribution Detection.