Double Descent Meets Out-of-Distribution Detection: Theoretical Insights and Empirical Analysis of the role of model complexity

Authors: Mouin Ben Ammar, David Brellmann, Arturo Mendoza, Antoine Manzanera, Gianni Franchi
Primary area: learning theory
Keywords: out-of-distribution, double descent.

Abstract:
While overparameterization is known to benefit generalization, its impact on Out-Of-Distribution (OOD) detection is less understood. This paper investigates the influence of model complexity in OOD detection. We propose an expected OOD risk metric to evaluate classifiers confidence on both training and OOD samples. Leveraging Random Matrix Theory, we derive bounds for the expected OOD risk of binary least-squares classifiers applied to Gaussian data. We show that the OOD risk depicts an infinite peak, when the number of parameters is equal to the number of samples, which we associate with the double descent phenomenon. Our experimental study on different OOD detection methods across multiple neural architectures extends our theoretical insights and highlights a double descent curve. Our observations suggest that overparameterization does not necessarily lead to better OOD detection. Using the Neural Collapse framework, we provide insights to better understand this behavior. To facilitate reproducibility, our code will be made publicly available upon publication.

Decision: reject
Reviewer scores: 8, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1730097709884

thread_type:
official_review

<thread_object>
creator: reviewer_zogq

<content>
summary:
This work focuses on exploring the Double Descent phenomenon in Out-of-Distribution (OOD) Detection. Theoretically, it proposes an expected OOD risk metric and, by leveraging Random Matrix Theory, establishes the relationship between OOD detection and the Double Descent phenomenon within a linear binary classification framework. Experimentally, the study conducts a comprehensive empirical investigation across various datasets and models. In the experiments, model complexity is indicated by different filter sizes, allowing for the observation of the Double Descent phenomenon in OOD detection under varying filter configurations. The conclusion is valid; however, the novelty of the work is not particularly significant.

strengths:
1.	This work focuses on two recent cutting-edge concepts: OOD detection and the Double Descent phenomenon. Both concepts have significant implications for deep learning applications and the understanding of deep learning optimization.
2.	The paper provides clear and rigorous results for OOD detection and the Double Descent phenomenon.
3.	Both the theoretical and experimental results appear to be valid.

weaknesses:
1.	Although the issues considered are cutting-edge concepts, I believe that the motivation presented is weak. The paper does not explore in depth the connections between these two concepts; it primarily provides derivations and experiments based on existing results. Maybe, the authors could discuss potential implications of their findings for model selection in OOD detection tasks, or to analyze how the double descent phenomenon might inform the design of more robust OOD detection methods.
2.	The motivation for expected OOD risk metric is unclear to me; I would appreciate a more detailed explanation. The authors could provide examples of how this metric might be used in practice, or to compare it with existing OOD detection metrics to highlight its unique contributions.
3.	Experimentally, the use of different filter sizes to represent model complexity is appropriate, but it also introduces certain limitations in the experimental results.

questions:
1.	In Section 5.2, the article states, “We report NC metrics, where lower values imply better performance in terms of both generalization and Out-of-Distribution (OOD) detection.” I find this statement insufficiently rigorous. While NC serves as a paradigm to illustrate the optimization process in deep learning, its lower values do not necessarily imply better performance regarding generalization. However, the authors carefully demonstrate the relationship between NC and generalization. Consequently, I remain skeptical of the authors' position and believe that this statement lacks the necessary rigor.
2.	I have concerns about the conclusion of Remark 4.1 of expected OOD risk metric. If the proposed expression (5) yields a lower value, it should not be possible to simultaneously derive conclusions (1) and (2). A more detailed explanation would be appreciated. I would appreciate a more detailed explanation.
3.	Since the Double Descent phenomenon is also based on a linear model, could the depth of the model be related to this phenomenon? Or does the model complexity mentioned in the context of Double Descent pertain solely to the model's width? Additionally, what is the relationship between the Double Descent phenomenon and the depth of the model?
4.	Please refer to “Weaknesses”.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730673416336

thread_type:
official_review

<thread_object>
creator: reviewer_eohk

<content>
summary:
This paper investigates the influence of model complexity on the out-of-distribution (OOD) detection problem by examining its connection to the double descent phenomenon. Specifically, This paper proposes a novel OOD risk metric and establishes bounds for the excess risk of both test samples and OOD samples, assuming Gaussian data. Leveraging these theoretical findings, this paper demonstrates that the model achieves optimal performance when the number of parameters matches the number of samples. Extensive experiments have been conducted across multiple neural network architectures to validate their claims.

strengths:
Overall, this paper presents a robust theoretical framework for analyzing the OOD detection problem and introduces a valid method supported by theoretical derivations and extensive numerical studies.

weaknesses:
The main weakness lies in the strong assumptions on both the data and the model. 

1. The model is a one-hidden-layer network with a single neuron.

2. The data is assumed to be Gaussian and isotropic. First, the Gaussian distribution may not reflect the real data application.

3. From lines 830 to 835, the nonlinear function is approximated by a linear function. However, the validity of this approximation is unclear—specifically, the conditions under which this approximation is valid and the rationale behind deriving it. Furthermore, this simplification may reduce the analysis to a purely linear case, potentially limiting the paper's contribution.

===============================

(comments after rebuttal) I changed my score from 6 to 5 (borderline reject) because I believe this paper is not yet ready for publication. 

1. The Gaussian input assumption.
2. The simplicity of the model, which involves only one hidden layer with a single neuron.
3. A new concern was raised during discussions with the authors: the limited technical contributions compared to existing works, which also focus on linear models.
4. The current version contains multiple mistakes in the proof.

questions:
(1) I feel that Eqn. (5) is unclear, as $z$ depends on $x$. The current format gives the impression that $z$ is fixed in both terms.

(2) Why Gaussian distribution is necessary for the proof?

(3) Could you provide more details for understanding remark 4.6? Also, how Theorems 1 & 2 are related to the OOD detection method?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730696140275

thread_type:
official_review

<thread_object>
creator: reviewer_unvj

<content>
summary:
This paper examines the impact of model complexity on (supervised) out-of-distribution (OOD) detection, showing that, similar to in-distribution (ID) generalization, OOD detection exhibits a double descent behavior as models become overparameterized.

Theoretically, the authors show that, in a setup similar to Belkin et al. (2020), both ID and OOD detection risks follow a double descent pattern in linear least-squares regression. Empirically, they explore various datasets, architectures, and OOD detection techniques, showing that logit-based metrics produce a smoother double descent curve compared to feature-based ones. They also relate the improvement seen with overparameterization to improvements in neural collapse (NC) within the feature space.

strengths:
The paper is written clearly. The authors discuss connections to previous work well and provide extensive experiments across various metrics, architectures, and datasets to support their claims.

weaknesses:
(see below)

questions:
1.  Can you comment on the significance of your theoretical results? It seems that theorem 2 is a simple extension of theorem 1 applied to both ID and OOD distributions, and theorem 1 closely resembles theorem 1 in Belkin et al. (2020), with the addition of the activation function/non-linearity $\phi(\cdot)$ (as also acknowledged in the paper). But do you use $\phi(\cdot)$ to link OOD detection and overparameterization for your overall conclusion? In other words, without $\phi(\cdot)$, what is the technical challenge for extending theorem 1 in Belkin et al. (2020) to the OOD risk?

2.  Your theorem doesn’t specify assumptions on the OOD distribution. Would your theory provide any insights on how the expected behavior of the OOD risk might change with varying degrees of distributional shift between ID and OOD distributions?

3.  The trace operation in the NC1 metric is applied to $d\times d$ matrices ($d$ being the dimension of last-layer features). Thus, I suspect that the value of NC1 would be sensitive to changes in the value of $d$. Is the last-layer dimension in your experiments in both the under- and over-parameterized settings similar?  Or do you vary them as you increase the widths of the intermediate layers of the network? In the latter case, I am wondering if comparing the NC1 values when $d$ is different is fair. 

4.  The paper makes heuristic connections between how much over-parameterization improves OOD detection and how well the features align with ETF. ETF is only predictive of the last-layer's features' geometry if the training data is balanced (e.g., see [1]). Are all your training datasets balanced across classes?  If yes, would OOD detection under overparameterization behave differently if the training data were imbalanced?

[1] Thrampoulidis et al. "Imbalance trouble: Revisiting neural-collapse geometry." Advances in Neural Information Processing Systems 35 (2022)
</content>
</thread_object>

</thread>
<thread>
creation date:
1731010733635

thread_type:
official_review

<thread_object>
creator: reviewer_wrdx

<content>
summary:
The paper investigates the influence of model complexity on Out-Of-Distribution (OOD) detection in machine learning models, with a specific focus on the double descent phenomenon. The authors propose a theoretical framework using Random Matrix Theory to explore OOD risks associated with binary least-squares classifiers on Gaussian data. The experimental analysis extends these theoretical insights across various neural network architectures, suggesting that overparameterization does not always enhance OOD detection.

strengths:
- This paper provides a notable contribution by extending the concept of double descent, originally associated with generalization error, to OOD detection. This new perspective highlights a less explored aspect of model overparameterization, offering valuable insights into the robustness of overparameterized models.

- Theoretical contribution: The use of Random Matrix Theory to derive bounds for OOD risk offers valuable insights on understanding OOD detection in the over-paramterized regime.

- The experiments are quite comprehensive, particularly in the variety of OOD detection methods employed.

weaknesses:
- Adding the label noise (Line 305) is a bit artificial for real-world applications, probably also leads to different phenomenon in OOD detection. Is there any result on noiseless experiments for understanding the effect of model size for OOD detection?

- Could the authors provide additional remarks on connecting the derived theoretical results and the empirical OOD detection methods? E.g., is the derived lower bound in Theorem related to one/several of the practical OOD detection methods?

questions:
See Weaknesses.

(Update: increased score from 6 to 8 after author rebuttal)
</content>
</thread_object>

</thread>
<thread>
creation date:
1731930037417

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General answer

comment:
Dear Area Chair and Reviewers,

We sincerely thank you for your thoughtful comments and questions regarding our work. We appreciate the time and effort you have invested in reviewing our research and acknowledge the recognition of the significant effort involved in this study.

Combining extensive experimental validation with theoretical analysis on the double descent phenomenon is indeed rare. While there are notable papers that explore the double descent phenomenon in modern settings (e.g., [1,7,8,9]) and provide theoretical insights ([2,3,4,5,6]), our work aims to bridge these perspectives in a unique and innovative manner, particularly by linking it to Out of Distribution (OOD) Detection. We understand the challenges in reviewing such interdisciplinary contributions and we are grateful for your efforts.

We would like to emphasize the originality of our study. To the best of our knowledge, no one has previously undertaken such a detailed investigation of the link between OOD and Double Descent. We believe that our findings offer valuable contributions to the field.

In response to your feedback, we have addressed all the reviewers' comments and are committed to improving the clarity and quality of the manuscript. A revised version of the paper, incorporating the required corrections, will be submitted by Wednesday.

Thank you once again for your constructive feedback and engagement. We look forward to continuing this conversation with reviewers to further refine our work.

Best regards,


## References

[1] Nakkiran, P., et al. (2020). Deep Double Descent. ICLR 2020.

[2] Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019). Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences, 116(32), 15849-15854.

[3] Louart, C., Liao, Z., & Couillet, R. (2018). A random matrix approach to neural networks. The Annals of Applied Probability, 28(2), 1190-1248.

[4] Liao, Z., Couillet, R., & Mahoney, M. W. (2020). A random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double descent. Advances in Neural Information Processing Systems, 33, 13939-13950.

[5] Belkin, M., Hsu, D., & Xu, J. (2020). Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4), 1167-1180.

[6]  Liu, F., Liao, Z., & Suykens, J. (2021, March). Kernel regression in high dimensions: Refined analysis beyond double descent. In International Conference on Artificial Intelligence and Statistics (pp. 649-657). PMLR.

[7] D'Angelo, E., et al. (2021). Can Neural Nets Learn the Same Model Twice? Investigating Reproducibility and Double Descent from the Decision Boundary Perspective. NeurIPS 2021.

[8] Unraveling the Enigma of Double Descent: An In-depth Analysis through the Lens of Learned Feature Space. ICLR 2024.

[9] Yang, Z., et al. (2020). Rethinking Bias-Variance Trade-off for Generalization of Neural Networks. ICML 2020.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper investigates a double descent phenomenon for out-of-distribution (OOD) detection. Similar to Belkin's original double descent work (2019, 2020), the authors theoretically demonstrate the phenomenon in least squares classifiers with strict assumptions on the training data distribution. The authors back up the theory in this simplified setting with experiments with neural networks that identify a double descent curve corresponding to the under-parameterized and over-parameterized regimes.

Connecting out-of-distribution detection with double descent is novel and will likely be of interest to the OOD community. The general finding may not be surprising given the strong connection between Belkin's proof techniques and this paper. While the paper's theory aims to identify a peak at the interpolation threshold, this paper would be significantly strengthened if the authors made assumptions about the OOD distribution, which would allow for a theoretical characterization of the double descent curve away from the peak.

During the rebuttal period, the authors made non-trivial changes to the proofs in the paper, both to simplify assumptions and to correct errors pointed out by the reviewers. While all of the changes seem benign, the fact that such errors existed in the first place gives me pause, especially since the theorems generally follow the pattern of Belkin et al. (2020). I suggest another round of careful review to ensure the changes are theoretically sound.

Altogether, this paper could benefit from another round of reviewing. This would ensure that the theory is correct while allowing the authors to potentially extend their analysis to incorporate the OOD distribution, ultimately leading to a stronger and more impactful paper.