acceptodds
Under review as a conference paper at ICLR 2027

Benign Overfitting Does Not Occur in Diffusion Models

Abstract

Benign overfitting and double descent have shaped our understanding of generalization in deep learning, painting a consistent picture: overfitting is not only compatible with good generalization but can actively benefit it. Since diffusion models share much of the machinery of standard deep learning, it is natural to assume that they also exhibit these properties. In this work, we show that this assumption is largely incorrect. We establish a fundamental impossibility result: for any score network architecture, overfitting and good generalization cannot occur simultaneously unless the sample size grows exponentially with the intrinsic dimension of the data. Through a linear model analysis, we trace this to a key difference between regression and score matching: regression benefits from a kernel–target alignment that is absent in score matching, making overfitting irreparably harmful. We then examine mechanisms that prevent overfitting, identifying implicit regularization from time-smoothness in the score, and early stopping in training. Our findings are then supported by high-dimensional experiments. Together, our results indicate that generalization in diffusion models is governed by mechanisms distinct from those of classical settings.

Primary area:
learning theory
Keywords:
benign overfitting, double descent, diffusion models, generalization, deep learning theory, random features

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_m1waOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper examines whether benign overfitting occurs in diffusion models. Its main result gives a sample-size lower bound for a data-dependent score estimator to achieve both small empirical ESM loss and good population performance, including a condition expressed through the KL divergence of the generated distribution. The bound depends on intrinsic dimension, noise scale, and time weighting. The paper then analyzes linear random feature networks to compare score matching with regression and studies how time smoothness and early stopping prevent overfitting. Random feature and CIFAR-10 experiments support parts of this picture.

Critical strengths
  1. The general lower bound goes beyond a particular network model. Theorem 3.2 allows the score estimator to depend on the training data and does not restrict its architecture. Its dependence on intrinsic dimension and noise scale makes the limitation more informative than the observation that the exact empirical score reproduces training data.

  2. The linear analysis provides useful explanations of overfitting and regularization. The comparison with regression identifies the role of the empirical covariance null space. The analysis of time integration and early stopping gives explicit results that help explain how generalization can be maintained before the model approaches the empirical solution.

Critical weaknesses
  1. The absence of benign overfitting and the absence of double descent are different claims. Theorem 3.2 concerns whether empirical fitting and population accuracy can be achieved simultaneously; it does not rule out a second decrease in test error as model width grows. Section 4 studies linear random feature networks, whose function class no longer expands once (p\geq d), so the resulting curves do not establish the same behavior for general nonlinear networks. George et al. [1], already cited in the submission, explicitly report double descent for DSM with finitely many noise samples. This does not contradict Theorem 3.2, but requires a clearer distinction between the settings. Figure 1 also needs clarification: Appendix C.1 lists (n=20{,}000), (N_g=10), and a maximum width of (10{,}000), which does not reach the stated number of training samples. It is therefore unclear what interpolation threshold is marked in the figure.

  2. Theorem 3.2 assumes small empirical ESM loss, which measures approximation to the empirical score. The reported training curves mainly use DSM loss, differing from ESM by a data-dependent constant. The paper should establish whether the experimental models satisfy the required ESM tolerance. In addition, the numerical discussion in Appendix B.1 substitutes an estimated intrinsic dimension for the lower Rényi dimension and applies a bound that holds for sufficiently small noise. The paper acknowledges that the dimension notions may differ, but does not verify either this correspondence or the required noise scale. Consequently, the numerical sample-size estimate is suggestive rather than a demonstrated lower bound for the CIFAR-10 setting.

[1] Denoising Score Matching with Random Features: Insights on Diffusion Models from Precise Learning Curves.

Questions for authors
  1. Can the Figure 1 hyperparameters and the marked interpolation threshold be reconciled? How does the curve change with the number of noise samples per training example?
  2. Can the empirical ESM loss be evaluated, or related quantitatively to the reported DSM loss, to check the premise of Theorem 3.2?
  3. Section 5.1 studies time-independent networks. What conclusions can be drawn for networks that retain time conditioning?
4 comments

We thank the reviewer for their interesting remarks and the positive evaluation of our work. We answer your questions below.

Weakness 1

The absence of benign overfitting and the absence of double descent are different claims ...

This is a good remark. What Section 3 shows is that benign overfitting is impossible for diffusion models. This means, at least, that there cannot be a second descent all the way down to zero. The reviewer is correct that [George et al] point out that, when a finite number of Gaussian samples is used, a peak might be observed. This is not the setting that we are considering in our theory, where we use the true expectation over the noise. In practice, during training, Gaussian samples are sampled at every iterations, so we consider that the true expectation over noise is what is being targeted. In a sense, having a finite number of Gaussian samples returns the learning problem closer to a traditional regression problem and so we would expect benign overfitting and double descent to follow.

In Figure 1 (right) the sample size is n=30n=30, the data dimension is d=3d=3, and we sample Ng=10N_g=10 Gaussian noises. In that case the number of gaussian noises is large enough compared to the data dimension for this setup to approximate the behavior of the (true) expected loss, which is the goal of our experiment. When the true expectation is used, no double descent is observed in this experiment.

We thank the reviewer for this interesting question and leave further investigation for future works.

Figure 1 also needs clarification: ...

We thank the reviewer for spotting this typo in Section C. The sample size used in this experiment is n=30n=30 an not n=20,000n=20,000. Therefore, the range of model widths cover the interpolation threshold and the vertical line on the diagram is correct.

In the revised version, we have now corrected the hyperparameters for this figure and have also included additional plots in the appendix in Section C, where we vary some of the hyperparameters used for this experiment.

Weakness 2

In addition, the numerical discussion in Appendix B.1 substitutes an estimated intrinsic dimension for the lower Rényi dimension ...

This is a good remark. There are two different reasons for the asymptoticity in the noise scale:

First, we need 2αϵ−1σϵ(log⁡(64)+d)<12 \alpha_\epsilon^{-1}\sigma_\epsilon (\sqrt{\log(64)} + \sqrt{d}) < 1 for the lower bound to be exponential in d′d'. This first condition on σϵ\sigma_\epsilon only depends on the ambient dimension, not the intrinsic dimension itself, and we have precise estimate of the required values for ϵ\epsilon (see the numerical evaluation).

Secondly, the last step of the proof of Proposition B.5 uses the limit defining the lower Renyi dimension. This asymptoticity in ϵ\epsilon depends on how fast this limit is converging. This can only be made more explicit under additional geometric assumptions, such as Ahlfors regularity of the data distribution. We discuss this in detail in the response to reviewer bfd6, Question 2. In the revised version, we have added a remark in Section B.

Moreover, we agree that it is unclear how the lower Renyi dimension can be estimated from a finite dataset. However, under the assumption that the data is supported on a manifold, the lower Renyi dimension coincides the manifold dimension. The dimension estimators we report in our discussion also target the same intrinsic/manifold dimension, hence why we discuss them interchangeably. That being said, we agree that our estimation of the lower bound is only suggestive and is only meant to provide intuition about its order of magnitude. In the revised version, we have added remarks to discuss these facts more precisely in Section B.

Question 1

Can the Figure 1 hyperparameters and the marked interpolation threshold be reconciled

As explained in the answer to the first weakness above, there was indeed a typo in the hyperparameters listed in the appendix. The sample size used in Figure 1 (right) is n=30n=30, which is consistent with the marked interpolation threshold on the figure.

How does the curve change with the number of noise samples per training example?

As remarked in our answer to weakness 1, we do not believe the case where a finite number of Gaussians is used in the train loss is particularly relevant. We believe that this setting shares much more in common with traditional regression than how diffusion models are trained in practice. However, we agree with the reviewer that this setting deserves consideration. We have added plots in Section C where we vary NgN_g (with d=3d=3). With such a low dimension, a peak is barely visible. However, a peak is expected at the effective dataset size n×Ngn \times N_g for higher dimensions, as suggested by [George et al]. It is clear that there are some distinctions between this finite Gaussian diffusion model setting and traditional regression (namely that the effective training data is no longer i.i.d.) and so we agree that this is an interesting direction of research that we will suggest as future work in the updated manuscript.

Question 2

Can the empirical ESM loss be evaluated, or related quantitatively to the reported DSM loss, to check the premise of Theorem 3.2?

We agree with the reviewer that there would be a clearer connection to the theory if the U-Net experiments reported ESM loss instead of DSM loss. This is a minor change as we can estimate the DSM/ESM gap directly from data and subtract it from the existing plots. We will provide this update during the rebuttal period and we thank the reviewer for the suggestion.

Question 3

Section 5.1 studies time-independent networks. What conclusions can be drawn for networks that retain time conditioning?

This is a good question. To the best of our knowledge, our analysis in Section 5.1 is the first to explicitly take into account the time integral in the score matching losses. A time-independent network is an extreme example of a network that is very smooth in time. As such, this result is informative on the impact of time smoothness. Obtaining similar results for a random feature analysis of time-dependent networks with time-integrated losses is beyond the scope of our work and is a fascinating direction for future work. Intuitively, we believe that similar conclusions should hold for networks that have a smooth dependence on time. In fact, a realistic time dependence should interpolate between the two settings discussed in Figure 3 (right): between perfectly smooth and perfectly non-smooth networks.

Thank you for the detailed response and clarifications. I appreciate the correction to Figure 1 and the additional experiments. I also agree that the distinction between benign overfitting and double descent should be made clearer.

I find the discussion of time smoothness and regularization interesting. It is also related to existing explanations of diffusion generalization, such as Bonnaire et al. [1], which studies implicit dynamical regularization and early stopping, and Zhou et al. [2], which investigates how smoothing empirical score weights can reduce single-sample dominance and memorization. Although these works consider different mechanisms, I think they offer complementary perspectives on why regularization can improve generalization in diffusion models.

My main remaining concern is the connection between Theorem 3.2 and practical diffusion models. While I appreciate the generality of the theoretical result, it remains unclear whether the empirical ESM losses and noise scales in the U-Net experiments satisfy the conditions required by the theorem. The proposed additional ESM measurements would help clarify this connection.

Overall, I find the theoretical contribution valuable and appreciate the authors' efforts to address my concerns. I will maintain my original score of 3.

References

[1] Bonnaire, T., Urfin, R., Biroli, G., and Mézard, M. (2025). Why Diffusion Models Don't Memorize: The Role of Implicit Dynamical Regularization in Training. Advances in Neural Information Processing Systems (NeurIPS 2025). https://arxiv.org/abs/2505.17638

[2] Zhou, X., Zhang, J., and Wright, S. J. (2026). Smoothing the Score Function to Enhance Generalization in Diffusion Models. (CVPR 2026). https://arxiv.org/abs/2601.19285

We thank the reviewer for their detailed response to our rebuttal and for maintaining the positive evaluation of our work.

Thank you for taking an interest in the time smoothness discussion. We appreciate the reference [Zhou et al.], whose unconditioned score analysis is related to our Section 5.1, and also analyze other implicit regularization mechanisms, such as temperature smoothing. We have now added this reference alongside the already existing discussion in the related works section. We agree that [Bonnaire et al] is an important reference (especially regarding early stopping) and a paragraph in the related works section is dedicated to the comparison with this work.

We understand the concerns of the reviewer regarding the applicability of Theorem 3.2 to practical settings and the U-Net experiments. To that end, we make two remarks:

  1. Regarding whether the base assumptions of the theorem hold, we refer to the numerical section paragraph in Section B, showing that, at least, the condition to make the lower bound exponential in d′d' is realistic in practice and holds for the case of CIFAR-10 according to best estimates of the effective dimension.
  2. We have now included a discussion in section C.3 that estimates the ESM/DSM gap, demonstrating that for the setup in the U-Net experiment it is negligible. It is not known to the authors whether the population ESM/DSM gap is possible to estimate but we compute the empirical gap over the test set as an (unjustified) estimate.

We thank the reviewer for their time and we hope that our answer helped clarifying the remaining concerns.

Reviewer_LncpOpenReview ↗
Rating
4(+1)
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this paper, the authors study the benign overfitting in diffusion models from a theoretical perspective, and find that it does not occur. They first prove that regardless of the network, the sample complexity has to grow exponentially with the intrinsic data dimension to make the empirical and test loss simultaneously small, which indicates that benign overfitting is difficult.

For a finer-grained analysis, they study the learning of a two-layer linear network with random features. They first consider the learning at a single noise level and derive the asymptotic test and empirical loss. They also compare them against traditional regression where benign overfitting is feasible, since the optimal solution is under-determined and `overfitting' can in turn provide the minimal norm regularization, while the test loss can be low under some labelling. Finally, they consider multi-step denoising training as in real DDPM, and prove that it serves as some kind of ridge regularization that can prevent the empirical loss from being arbitrarily small and test loss from exploding.

Critical strengths
  1. The authors tackle an important problem of diffusion generalization with rigorous theory, and also provide intuitive justifications and remarks for it.
  2. The authors consider multi-step denoising training and formalize it with a ridge-regression, which is a novel and important factor in diffusion generalization.
Critical weaknesses
  1. The network-agnostic argument (Sec.3 ) can be a bit coarse. It proves impossibility but cannot describe other phenomena related to benign overfitting such as double descent. The linear RFNN theory in Sec.4 and 5 is a bit redundant with previous works [1, 2], and also linear RFNNs can not memorize, i.e. generate the empirical distribution.
  2. (minor) Need better organization. Now Sec.3 and Sec. 4/5 seem disconnected? Also, some arguments can be prioritized. For instance, the authors can put a table summarizing diffusion training with traditional regression before the remarks on their differences in Sec.4.

[1] George, Anand Jerry, Rodrigo Veiga, and Nicolas Macris. "Denoising score matching with random features: Insights on diffusion models from precise learning curves." AISTATS2026

[2] Wang, Binxu, Jacob Zavatone-Veth, and Cengiz Pehlevan. "A random matrix theory perspective on the consistency of diffusion models." ICML 2026

Questions for authors
  1. The experiments and theory are somehow not matched. The authors train UNet in Fig.4 and 5, but analyze linear RFNNs for the corresponding theory in Sec.4 and 5. What is the case with the linear RFNNs?
  2. For the related works, [3] also considers the data geometry for diffusion generalization and memorization, and also the representation learning bias of networks that helps generalization, which can be discussed.

[3] Zhang, Zekai, et al. "Generalization of diffusion models arises with a balanced representation space." ICLR 2026

4 comments

We thank the reviewer for their detailed review, and the positive evaluation of our work. We answer your questions below.

Weakness 1

The network-agnostic argument (Sec.3 ) can be a bit coarse. ...

The goal of the network-agnostic arguments is to prove generic impossibility results on benign overfitting. Theorem 3.2 is network-agnostic by essence, as it shows that the population and empirical losses cannot be arbitrarily small simultaneously. Therefore, it does not involve any notion of model complexity and, as such, it is not meant to describe a phenomenon such as double descent. This is thus not due to a lack of tightness of the result. This is one of the reasons why we analyze the linear RFNN in Section 4: providing insights on the role of model complexity.

The linear RFNN theory in Sec.4 and 5 is a bit redundant with previous works [1,2]

We discuss the differences between our work and [George et al.] in the related works section (Section 6). There are three main differences:

  1. We consider the time-integrated loss in Section 5, while George et al focus the analysis on an individual time slice. This is an important difference and our analysis shows that the presence of this time integral leads to better test loss in Section 5.
  2. Our focus in Section 4 is to provide a precise characterization of where diffusion models differ from traditional regression, in order to understand why the self-induced regularization mechanisms of traditional regression cannot occur. This is not present in or relevant to the work of [George et al.]
  3. The setting of Sections 3/4 can be considered a special case of [George et al.], but our goals are different. Their bounds for general RFNNs are tight but rely on solving self-consistent equations. We need easy-to-interpret closed-form asymptotics to understand generalization in diffusion models, and we consider deriving them and finding a setting that allows them a contribution.

We thank the reviewer for pointing out the reference [Wang et al.]. Indeed, they also consider linear score networks. However, [Wang et al] focus on characterizing the statistics of the denoiser in the high-dimensional limit, and not on a precise characterization of the losses or the difference with regression. Nevertheless, consistency of diffusion models is related to their generalization properties and, in the revised version, we now include this reference in the related works section.

linear RFNNs cannot memorize, i.e. generate the empirical distribution.

This is a good remark. Our goal in Section 4 is not to show that linear models can memorize, but rather to 1) compare diffusion models with traditional regression and 2) have a more precise understanding of how the sample size, the data dimension, and the model complexity interact. However, note that the DSM loss of the linear model at a fixed time tt (normalized by dd, as it is the case in the existing works) can become arbitrary small when ψp>ψd\psi_p > \psi_d and ψd\psi_d is large. Therefore, we believe that it is a good setup to analyze the role of model complexity.

Weakness 2

While Section 3 and Sections 4-5 consider different setups, they are strongly connected for several reasons. First, the model-agnostic analysis does not inform us about the role of model complexity, so it is naturally complemented by Section 4, where such a notion appears. Second, after showing that benign overfitting cannot happen, the analysis of Section 4 is essential to really understand where the classical self-induced regularization mechanisms, identified in the linear setting, fail. Finally, Section 5 suggests ways in which overfitting is avoided in practice, which is the natural question raised by section 3. To make these transitions clearer, as suggested by the reviewer, we added a table that summarizes the main differences between score matching and traditional regression. Note that, due to the page limit constraint, we had to include this table in the appendix for now. Following the reviewer's suggestion, we will include it in the main text in the final version. Thank you for this suggestion.

Question 1

The experiments and theory are somehow not matched.

This is a very pertinent remark. Indeed, our theory in Section 5 uses linear models. The reason why we use linear models in this section (especially in Section 5.1), is because it makes the computations tractable even in the presence of the time integral in the loss. Despite this, we believe that the main insight behind this theory extends far beyond the case of linear models: the smoothness in time of the score estimators and the time-integrated loss help reduce the overfitting. A similar conclusion holds for early stopping. The goal of the experiments shown in Fig 4 and 5 is precisely to show that the theoretical insights obtained for the linear model extend to more realistic models.

That being said, the reviewer is correct that some empirical validation of the linear model theory itself could be helpful. We have now added these experiments in the appendix, in Section C. In these new experiments, we test the predictions of Section 4 and Section 5.1 on linear models. We observe that the experiments closely match the theory.

Question 2 Related work

We thank the reviewer for the interesting reference [Zhang et al, 2026]. In this paper, the authors model the data as a Gaussian mixture, which they see as an approximation of data manifolds. It is consistent with our analysis that shows that amount of benign overfitting that is allowed is strongly related to the intrinsic dimension of the data. In [Zhang et al.], it is also argued that there is a representation bias that forces the neural network to learn the underlying low-dimensional structure of the data distribution. We agree that this is another mechanism that might prevent overfitting and benefit generalization.

We have added this reference to the related works section in two places: when discussing the role of data geometry, and when discussing the generalization mechanisms proposed for diffusion models.

I thank the authors for the rebuttal, which helps to clarify the scope and novelty of the paper. The insights comparing diffusion training and traditional regression are particularly interesting.

However, I am still a bit uncertain about the generality of the analysis, especially for linear RFNN, given that the overfitting patterns of linear RFNN and real-world models can be different.

Overall, I like the insights within this paper, but I feel like it lacks some practicality. I can further increase my score while lowering my confidence if the authors would like.

We thank the reviewer for their positive appreciation of our rebuttal and for offering to increase their score. We are happy that it clarified the scope and novelty of our paper.

Regarding the generality of our analysis, let us highlight that our main results in Section 3 are valid for any score network. In particular, this result is not limited to linear RFNNs and is informative for practical diffusion model setups. While we agree that the linear RFNNs setting considered in Sections 4 and 5 are not an accurate depiction of a realistic diffusion model, we do not pursue this setting for that reason. We instead consider this setting to unpack the mechanism behind the phenomena observed in the generic theorem and practical experiments. In particular, the benign overfitting phenomenon was first theoretically studied on linear networks and thus, they are sufficiently expressive to capture this phenomenon. By considering the same setting which offers closed-form expressions of the limiting risk, we are able to identify exactly why benign overfitting does not occur, tracing it to an inability to utilize the typical self-induced regularization mechanisms. We discuss these motivations at the beginning of Section 4

We thank the reviewer for raising this interesting concern and hope that our rebuttal clarifies it. We thank the reviewer for suggesting to increase their score, if they feel that many of their concerns were addressed.

Thank you again for your time and remarks.

Reviewer_bfd6OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper analyzes the generalization properties of denoising diffusion probabilistic models. For standard neural network training, extensive literature analyzing the generalization properties exist. However, the same cannot be said for the DDPM models. The key contribution of this paper is to show that the two established phenomenon that underpin the generalization mechanism for standard neural networks, i.e. double descent and benign overfitting, do not apply to the DDPM training. It establishes this via constructive examples and shows that firstly, minimizing both the training and test error is only possible with sample size exponential in data dimension and secondly, provide an exact analysis for the two-layer linear random feature network case and show that the cause of this incompatibility is the mismatch between the score target and the data covariance. I believe this work gives valuable insight into the mechanism underlying the generalization properties of DDPM models and will provide valuable guidance for future analysis and design of DDPM and related methods.

Critical strengths

The main strengths of the paper lie in the key parts of the DDPM pipeline the work identifies to obtain its main insight.

  1. The result showing the exponential in dimension sample requirement for hold for any measurable score estimator, independent of score network or optimizer, making the result quite generally applicable. The intrinsic dimension dependence tracks with other convergence analyses of DDPM works where sample complexity is related to intrinsic rather than ambient dimension.
  2. The linear 2 layer network analysis, identifies the two key mechanisms which underpin the impossibility of benign overfitting, i.e. the empirical risk can be minimized when the training dimension is large but the population risk blows up in the same regime.
  3. The work further established the implicit regularization occurs as the result of using one training network across time steps. The work also provides an interpretable co-efficient that justifies stopping time choice in a theoretically grounded manner.
Critical weaknesses

The only limitation I can see in the analysis as of now is the fact that the analysis is restricted to a two layer linear network.

Questions for authors
  1. For the results in figures 2 and 4 are these results averaged over seeds? If so how many seeds?
  2. The section 3 bound in stated as holding for 'sufficently small' \epsilon. Is there any upper limit on how big \epsilon can be?
3 comments

We thank the reviewer for their thoughtful review and their positive evaluation of our work. We address below the raised concern and answers your questions.

Weakness The only limitation I can see in the analysis as of now is the fact that the analysis is restricted to a two layer linear network.

While the analysis of Sections 4 and 5 is indeed restricted to linear models, we would like to highlight that this is not the case of Section 3, which contains one of our main results: a generic result on the mathematical impossibility of benign overfitting for diffusion models. Indeed, as stated at the beginning of Section 3.2, our results in this section apply to any random score estimators. In particular, Theorem 3.2 holds for the complex score networks used in practice, as soon as the other assumptions of the theorem are satisfied.

The reason why we then focus on linear models in Sections 4 and 5 is because 1) they allow a rigorous comparison to traditional regression, 2) they provide a fine-grained analysis of the role of model complexity, and 3) it makes the time-independent score computations of Section 5.1 tractable. While there is indeed a gap between these two settings, we believe that the two theoretical settings, along with the experimental results, complement each other to best expose the nature of overfitting in diffusion models.

Question 1 The experiments in figures 2 and 4 are currently not averaged over many seeds and are in fact for one seed.

We agree with the reviewer that running the experiment for multiple seeds would certainly improve the experiments and provide stronger evidence of the claims we make around them. We will provide a 2-seed run by the end of the rebuttal which we will expand to a 5-seed run for the camera ready version (due to the long train time, these experiments are highly expensive). We thank the reviewer for their suggestion.

Question 2 Is there any upper limit on how big ϵ\epsilon can be?

We thank the reviewer for raising this very relevant question. Indeed, the results in Section 3 hold when TT and dd are sufficiently large and ϵ\epsilon and ε\varepsilon are sufficiently small. While we explicitly track the minimum values of TT and dd required for our results to hold, deriving explicit upper bounds on ϵ\epsilon and ε\varepsilon is more delicate.

Let us explain this carefully. For simplicity, we focus on the case of the ELBO weighting mentioned in Remark 3.3 (the other cases are similar). In that case, the condition that w−(32ε)w^-(32\varepsilon) is small enough means two things: First, 32ε≤132\varepsilon \leq 1 and, second, ϵ\epsilon is small enough, in a sense that comes from the proof of Proposition B.5.

In the proof of this proposition, we first obtain a non-asymptotic lower bound on the sample size at line 996, it has the form: n≥cEX∼ν[B(X,2αϵ−1σϵ(log⁡(64)+d))]n \geq \frac{c}{E_{X \sim \nu} [B(X,2 \alpha_\epsilon^{-1}\sigma_\epsilon (\sqrt{\log(64)} + \sqrt{d}))]} where cc is an absolute constant, we recall that ν\nu is the data distribution, and B(x,r)B(x,r) is the ball centered at xx with radius rr. After obtaining this bound, we use the definition of lower Renyi dimension (the intrinsic dimension we consider), which is d′:=lim⁡inf⁡ϵ→0+log⁡∫ν(B(x,ϵ))dν(x)log⁡ϵ.d' := \lim \inf_{\epsilon \to 0^+} \frac{\log \int \nu(B(x, \epsilon)) d \nu(x)}{\log \epsilon}. Therefore, the asymptoticity in ϵ\epsilon is not explicit, and depends on the speed at which the limit defining the intrinsic dimension is converging.

In fact, it is possible to make this more precise under further geometric assumptions. Specifically, if we assume that ν\nu satisfies the well-established Ahlfors regularity condition, namely, there exist a,b>0a,b > 0 and α≥0\alpha \geq 0 such that, for all xx, aδα≤ν(B(x,δ))≤bδα,a \delta^{\alpha} \leq \nu(B(x,\delta)) \leq b \delta^{\alpha}, then d′=αd'=\alpha and the lower bound on the sample size becomes: n≥log⁡cb(2αϵ−1σϵ(log⁡(64)+d))−d′.n \geq \log \frac{c}{b} \left( 2 \alpha_\epsilon^{-1}\sigma_\epsilon (\sqrt{\log(64)} + \sqrt{d}) \right)^{-d'}. In that case, the only condition on ϵ\epsilon for this lower bound to be exponential in the intrinsic dimension becomes that 2αϵ−1σϵ(log⁡(64)+d)<1,2 \alpha_\epsilon^{-1}\sigma_\epsilon (\sqrt{\log(64)} + \sqrt{d}) < 1, which is already discussed in the submitted paper.

In the revised version, we have added a remark about this question from the reviewer and the Ahlfors regularity conditions, in Section B.1. Thank you for raising this point.

We thank the reviewer for their feedback. We hope our response has addressed their main concern, and if so, we would be grateful if they would consider increasing their score.

Thank you for your response. I prefer to keep my positive score.

We thank the reviewer for their time and the positive evaluation of our work.

We have now updated Figures 2 and 4 to contain 2 seeds, and will expand it to 5 seeds in the camera ready version. Thank you for this comment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.