acceptodds
Under review as a conference paper at ICLR 2027

Score Approximation for Diffusion Models on Arbitrary Low-dimensional Structures

12 views

Abstract

Score-based diffusion models have achieved remarkable empirical success, motivating extensive theoretical work to establish their foundations. However, existing complexity bounds for score approximation, a vital step in diffusion modeling, rely on rigid constraints such as Lipschitz continuous scores or lower bounded densities. This severely limits their applicability to real-world perceptual data, where singularities, sharp boundaries, and disjoint clusters routinely violate such restrictive assumptions. We bridge this gap between theory and practice, presenting the first universal score approximation theorem applicable to any compactly supported distribution in . Using a novel discretization technique that directly models the underlying distribution, we prove that the neural network complexity is governed by the support’s upper Minkowski dimension rather than the ambient dimension . Furthermore, by leveraging the inherent smoothing of Gaussian kernels, we show that even for irregular, fractal distributions, an approximation error can be achieved with local Taylor modules each at size of , an -scaling rate previously achieved only for distributions with -Holder smoothness. Thus, we reveal a possible mechanism by which score-based diffusion models represent non-smooth data distributions.

Primary area:
learning theory
Keywords:
Diffusion Model, Score Approximation

Reviews

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

This paper studies the theory for approximating score functions with deep neural networks. Unlike prior works that assume smooth data distributions, it proves that neural networks can approximate the score functions of arbitrary compactly supported, non-smooth distributions. It further shows that the network size is governed by the intrinsic (Minkowski) dimension, rather than the ambient dimension, and introduces a new network architecture to achieve this rate. A key innovation in the proof technique is the "EA" regularity, which is a relaxation of Ahlfors regularity and proven by the authors to hold for any compact distributions.

Critical strengths

Understanding whether neural networks can approximate score functions of non-smooth distributions and how the network complexity depends on the dimension and smoothness is an important and interesting question in learning theory for generative models.

Critical weaknesses
  • The paper, to me, is relatively hard to follow. It may be easy to read for someone familiar with related works such as Zhang et al. (2026), but for a general machine learning audience, the paper can be hard to read. Below are specific questions and suggestions.
    • More background on Ahlfors regularity, its relation to low-dimensional structures and connection to Minkwoski dimension will be appreciated.
    • It's unclear what the order M in Theorem 1 and the "M-th order complexity bound" on Line 192 mean. They don't appear to be standard terms in approximation theory. Furthermore, the authors may want to clarify its relation with the M in "(M+1)-Holder smoothness". Do these two M's represent the same quantity?
    • The error term from previous works (line 181) depends on t, but the derived network complexity (line 184) and the result in Theorem 1 depends on t0. Can the authors explain why they simplified the dependence to t0?
    • Can the authors clarify whether CβC^\beta on line 178 denotes continuous derivatives through order β\beta or β\beta-Holder smoothness? If it refers to Holder smoothness, what's the relation between β\beta and M, which is also used to define Holder smoothness?
    • There are several grammatical errors. For example, "Using a discrete-mixture framework, our network avoids the exponential curse of ambient dimensionality, its complexity governed by the support’s Minkowski dimension."
Questions for authors

Besides the questions raised in the Weakness section, can the authors comment on what information does one need to construct the network architecture introduced in the paper? Do we need to calculate the number of covers from a predefiend approximation error? How can this be achieved? Is the value of Minkwoski dimension needed? Ultimately, is this network mainly a theoretical construction or a potential alternative to the networks currently used in practice?

2 comments
AuthorsOpenReview ↗

Response to Weaknesses

Thank you for recognizing the importance of our research question, and for your detailed suggestions on improving accessibility for a broader ML audience. We clarify all ambiguities below.

W1(1): Background on Ahlfors regularity and its relationship to Minkowski dimension

  • Definition: A measure μ\mu is dd-Ahlfors regular if there exist constants 0<c≤C0 < c \leq C such that crd≤μ(B(x,r))≤Crdc r^d \leq \mu(B(x, r)) \leq C r^d for every x∈supp(μ)x \in \mathrm{supp}(\mu) and 0<r<diam(supp(μ))0 < r < \mathrm{diam}(\mathrm{supp}(\mu))—meaning every ball centered on the support carries mass comparable to rdr^d. Classic examples include the volume/Hausdorff measure on a compact dd-dimensional smooth manifold, as well as the 11-D Cantor measure (d=log⁡2/log⁡3d = \log 2 / \log 3, which has no density function).
  • Relation to Minkowski dimension: Ahlfors dd-regularity implies that supp(μ)\mathrm{supp}(\mu) has Minkowski dimension dd, though the converse fails: Minkowski dimension only counts how many radius-rr balls are needed to cover the support (≍r−d\asymp r^{-d}), while Ahlfors regularity also enforces a uniform mass distribution across them.
  • Role in our paper: Crucially, we assume only the Minkowski covering condition, not Ahlfors regularity. EA regularity (Definition 1) is a much weaker, pointwise condition: balls near xx need not have mass ≍rd\asymp r^d; they simply must not be exponentially lighter than distant balls. Every Ahlfors regular measure is EA regular everywhere (with C1=2dC/c,C2=0C_1 = 2^d C / c, C_2 = 0), and Theorem 3 proves that for any compact measure, all but a δ\delta-fraction of its mass is EA regular.

We will add this concise background and the EA-vs-Ahlfors comparison to Section 3.


W1(2) & W1(4): Meaning of order MM, CβC^\beta smoothness, and how MM and β\beta relate

Thank you for pointing out this ambiguity; these two questions are closely linked.

  • What CβC^\beta means (line 178): CβC^\beta denotes standard β\beta-Hölder smoothness—a function has continuous partial derivatives up to order ⌈β⌉−1\lceil\beta\rceil - 1, and its highest-order derivatives are (β−⌈β⌉+1)(\beta - \lceil\beta\rceil + 1)-Hölder continuous. To facilitate a direct side-by-side comparison between our work and Zhang et al. (2026), we examine the case β=M+1\beta = M + 1 (i.e., (M+1)(M+1)-Hölder smoothness).
  • What "order MM" means and whether the two MM's are the same: The two MM's are not the same conceptual quantity:
    • β\beta in Zhang et al. (2026) is a hard constraint on the underlying data: p0p_0 must be β\beta-Hölder smooth.
    • M∈N+M \in \mathbb{N}^+ in our Theorem 1 is a tunable hyperparameter: the truncation degree of the Gaussian kernel's Taylor expansion (whose coefficients are Hermite tensor polynomials) inside Figure 1's modules. As the Gaussian kernel is C∞C^\infty, our theorem allows setting MM to any integer 1≤M≤n1 \leq M \leq \sqrt{n} with no smoothness requirements on p0p_0. Calling it an "MM-th order complexity bound" simply refers to the complexity achieved by this MM-th order Taylor expansion on the Gaussian kernel.
    • Why "(M+1)(M+1)-Hölder smoothness" appears in the Abstract: β\beta is expressed as M+1M+1 solely to show that our exponent in 1/ϵ1/\epsilon, namely d/(M+1)d/(M+1), coincides with Zhang et al.'s exponent d/βd/\beta when β=M+1\beta = M+1 (at the cost of a larger exponent in 1/t01/t_0).

We will change "CβC^{\beta}" to "β\beta-Hölder smooth", define "MM-th order complexity bound" explicitly before Section 2.1/Section 3 and clarify this comparison in the Abstract and Section 2.1.


W1(3): Why complexity depends on t0t_0 rather than tt

One neural network must satisfy the approximation error tolerance uniformly for every t∈[t0,T]t \in [t_0, T], and both Zhang et al.'s bound (line 181: MSE O(n2γ+d+2δ2/t)\mathcal{O}(n^{2\gamma+d+2}\delta^2/t)) and our bounds are worst at the smallest noise level t=t0t = t_0. Setting the worst-case MSE at t=t0t = t_0 to ϵ2\epsilon^2 in Zhang et al. yields δ\delta of order ϵt0⋅n−(γ+1+d/2),\epsilon\sqrt{t_0} \cdot n^{-(\gamma+1+d/2)}, which, upon substituting into O(δ−d/β)\mathcal{O}(\delta^{-d/\beta}) with 2γ+2=42\gamma+2=4 from Footnote 2, gives the t0−d/(2β)t_0^{-d/(2\beta)} dependence in line 184. Similarly, our Theorem 1 sizes the network for the bottleneck time t0t_0.

We will insert this explicit 2-line substitution directly after line 181.


W1(5): Grammatical errors

Thank you for catching this. In our revision, we will correct your example sentence to: "Using a discrete-mixture framework, our network avoids the exponential curse of ambient dimensionality, with its complexity governed by the support's Minkowski dimension." We have also audited the manuscript and corrected additional issues (e.g., line 23 "each at size" →\to "each of size"; line 93 "weighed" →\to "weighted"; line 147 "analysis ... focus" →\to "focuses"; line 298 "mass ... dominate" →\to "dominates"; line 452 "bounds ... predicts" →\to "predict"; line 461 "network ... require" →\to "requires"; line 488 "Deepseek" →\to "DeepSeek").

AuthorsOpenReview ↗

Response to Questions

Q1(1): Theoretical existence result, or practical alternative?

Our construction is primarily a theoretical existence result, not a new engineered architecture meant to replace U-Nets or Diffusion Transformers. The network in Theorem 4 is a standard fully connected ReLU MLP; Figure 1 simply illustrates how its weights are organized inside the proof.

In other words, our theorems prove that standard ReLU MLPs of sufficient depth and width naturally contain our construction in their hypothesis class, establishing expressivity rather than gradient-descent learnability or justification for alternative network designs.

Q1(2): Are dd or CPC_P needed in advance?

No, one only needs to run a covering algorithm on all samples (though knowledge of the manifold dimension d′d' is needed if one wishes to invoke the tighter manifold-case bound rather than the general nn-dependent bound). While dd governs the asymptotic scaling as ϵ→0\epsilon \to 0 and t0→0t_0 \to 0, it is not required to instantiate the network for fixed (t0,ϵ)(t_0, \epsilon). One can verify directly from Appendix B.6 (lines 1306--1323) and Theorem 1 that CPC_P and dd enter our complexity bound through only two quantities:

  1. The total number of sub-distributions P=CPr−dP = C_P r^{-d}, which is directly proportional to the number of Taylor modules;
  2. The maximum possible number of far-group balls PfarP_{\mathrm{far}}, upper-bounded by CP(λt−r)−dC_P(\lambda\sqrt{t} - r)^{-d}, which controls the far-group contribution and produces the term 17log⁡CP+d14log⁡1t0\frac{1}{7}\log C_P + \frac{d}{14}\log \frac{1}{t_0} inside λ\lambda (whereas all remaining terms in λ\lambda depend only on n,d′,R,ϵ,t0n, d', R, \epsilon, t_0).

For fixed (ϵ,t0)(\epsilon, t_0) and t≥t0t \geq t_0, the definitions of λ\lambda (lines 646--647, 674--676) together with r≤t0/50r \leq \sqrt{t_0}/50 (lines 649--652) guarantee that λt−r>nt0\lambda\sqrt{t} - r > \sqrt{n t_0} in the general case (and >d′t0> \sqrt{d' t_0} in the manifold case). Consequently, PfarP_{\mathrm{far}} can be upper-bounded directly by the number of balls of radius nt0\sqrt{n t_0} (or d′t0\sqrt{d' t_0}) needed to cover supp(p0)\mathrm{supp}(p_0) (or the observed samples in practice), replacing 17log⁡CP+d14log⁡1t0\frac{1}{7}\log C_P + \frac{d}{14}\log\frac{1}{t_0} in λ\lambda with 17log⁡Pfar\frac{1}{7}\log P_{\mathrm{far}}. From λ\lambda, rr follows directly via Theorem 1, and PP is simply the number of radius-rr balls a standard clustering or greedy rr-net algorithm uses to cover the samples.

Q1(3): What information the construction needs

Replicating our construction requires (1) The far-group cover count PfarP_{\mathrm{far}} at radius nt0\sqrt{n t_0} (or d′t0\sqrt{d' t_0}), from which λ\lambda and the covering radius rr follow via Theorem 1 using (ϵ,t0,M,R,n)(\epsilon, t_0, M, R, n) (and d′d' in the manifold case); (2) an rr-ball cover {B(yi,r)}i=1P\{B(y_i, r)\}_{i=1}^P of the support/samples; and (3) each ball's empirical probability mass wiw_i and local moments up to order MM. All cover counts and local moments can be estimated directly from finite samples without knowing dd or CPC_P.

Reviewer_GGNdOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the universal approximation of score function using neural networks: given a specific constraint on network size, how well can a neural network approximate the score function ∇log⁡pt\nabla \log p_t. The authors propose the decomposition of ptp_t into sub-distributions, then the score function can be approximated by averaging ∇log⁡pt,i\nabla \log p_{t,i} with softmax as weighting function. The authors then proceed to show the bounds on network depth D and width W under which guarantee in squared-error of the score function is achieved, culminating in Theorem 4, where the universality theorem is shown.

Critical strengths
  1. I think Theorem 1 & 4 are good contributions to the theoretical study of neural networks' sizes in diffusion models. These theorems don't require smoothness or Lipschitz assumption on the score, which is nice, since those assumptions are pretty strong in practice.

  2. While the core idea of the paper's first contribution (decomposition of ptp_t into sub-distributions) is not new, I think the use of EA regularity to help control the softmax weight is nice.

Critical weaknesses
  1. I think the advertised rate in the abstract is pretty misleading, it omits the factor (λ/t0)dM+2M+1(\lambda/\sqrt{t_{0}})^{d\frac{M+2}{M+1}} from Theorem 1. The rate is fine if t0t_{0} is fixed. But as t0→0t_{0}\rightarrow 0, the rate blows up. To the authors' credit, this was briefly mentioned in the Conclusion. However, I still believe this makes the "(M+1)-Holder smoothness" comparison somewhat unfair, since the cost of not needing smoothness is now seem to be paid for in how fast this rate blows up as t0→0t_{0}\rightarrow 0.

  2. Maybe the authors could be more clear on what they mean by "first universal score approximation theorem"? I think it's more fair to say this is universality with Minkowski dimension instead of ambient dimension. As far as I know, universality in this context is not new (also mentioned in line 169-170).

Questions for authors
  1. Can you compare your Theorem 1 to Theorem 17 from https://arxiv.org/pdf/2603.03700, which is also cited in the paper. I think the Theorem 17 is also free of smoothness assumption.
  2. Just my curiosity, how would the result look like for zero-order case, i.e. M=0? I think this is somewhat relevant to the experiment in Appendix H.1
3 comments
AuthorsOpenReview ↗

Response to Weaknesses

Thank you for your thoughtful, encouraging remarks and for helping us sharpen both the positioning and the clarity of our claims.

W1: Blowup of network size as t0→0t_0 \to 0 and the scaling trade-off

Thank you for pointing out that our abstract omitted the λ\lambda factor and the t0t_0 blowup. The reviewer is completely right that removing smoothness assumptions comes at the cost of a larger exponent in 1/t01/t_0.

We will revise the abstract to state: "an ϵ\epsilon approximation error on [t0,T][t_0, T] can be achieved with O~((ϵθ)−d/(M+1)θ−d)\tilde{\mathcal{O}}\big((\epsilon\theta)^{-d/(M+1)} \theta^{-d}\big) local Taylor modules each of size O(nM)\mathcal{O}(n^M), where θ=t0/n\theta = \sqrt{t_0/n} for general distributions and t0/d′\sqrt{t_0/d'} for distributions supported on d′d'-dimensional manifolds," making this trade-off explicit and upfront.

To explain why our t0t_0 exponent naturally arises (expanding on lines 199--213), consider an oracle network family vp(x,t)∣p∈P\\{v_p(x, t) \mid p \in \mathcal{P}\\}, approximating

∇log⁡pt(x)∣t∈[t0,T]\\{\nabla \log p_t(x) \mid t \in [t_0, T]\\}

with L2L^2 error ϵ\epsilon (MSE ≤ϵ2\leq \epsilon^2), where P\mathcal{P} denotes all distributions pp supported on B(0,R)B(0, R) that can be covered by Cr−dC r^{-d} balls of radius rr for all 0<r<10 < r < 1. For any scaling factor s≥1s \geq 1, this same family can also approximate

∇log⁡pt(x)∣t∈[s2t0,s2T]\\{\nabla \log p_t(x) \mid t \in [s^2 t_0, s^2 T]\\}

with L2L^2 error ϵ/s\epsilon/s for any distribution pp, as long as supp(p)⊆B(0,R)\mathrm{supp}(p) \subseteq B(0, R) can be covered by Csdr−dC s^d r^{-d} balls of radius rr for all 0<r<s0 < r < s. Indeed, letting p~:=τ(s)∘p\tilde{p} := \tau(s) \circ p be the distribution of x/sx/s (x∼px \sim p), we have

supp(p~)⊆B(0,R/s)⊆B(0,R)\mathrm{supp}(\tilde{p}) \subseteq B(0, R/s) \subseteq B(0, R)

and covering number

Csd(sr)−d=Cr−d,∀0<r<1,C s^d (s r)^{-d} = C r^{-d}, \forall 0 < r < 1,

so p~∈P\tilde{p} \in \mathcal{P}. Furthermore, under the VE scheme,

∇log⁡pt(x)=1s∇log⁡p~t2(xs),t2=ts2\nabla \log p_t(x) = \frac{1}{s}\nabla \log \tilde{p}_{t_2}\left(\frac{x}{s}\right), t_2=\frac{t}{s^2}

so 1svp~(x/s,t/s2)\frac{1}{s} v_{\tilde{p}}(x/s, t/s^2) approximates ∇log⁡pt(x)\nabla\log p_t(x) with L2L^2 error ϵ/s\epsilon/s on [s2t0,s2T][s^2 t_0, s^2 T] using the exact same network complexity.

Therefore, if the optimal complexity scales as Cϵ−at0−bC \epsilon^{-a} t_0^{-b} (linear in the covering constant), this symmetry requires

(Csd)(ϵ/s)−a(s2t0)−b≤Cϵ−at0−b,∀s≥1,(C s^d)(\epsilon/s)^{-a}(s^2 t_0)^{-b} \leq C \epsilon^{-a} t_0^{-b}, \quad \forall s \geq 1,

forcing b≥(a+d)/2b \geq (a + d)/2. For a=d/(M+1)a = d/(M+1), this yields

b≥(M+2)d2(M+1),b \geq \frac{(M+2)d}{2(M+1)},

which is precisely what we attain in Formula (5) (up to logarithmic factors in Theorem 4, logarithmic factors in λ\lambda, and the nMn^M per-module cost).


W2: Regarding the claim "first universal score approximation theorem"

We apologize for the imprecise phrasing. By "universal," we meant "applicable to any compactly supported distribution." Because prior works such as Chakraborty et al. (2026) also handle the empirical score of distributions with arbitrary compact supports (though with network parameter size exponential in the ambient dimension), we will revise our abstract to claim: "the first score approximation theorem to break the exponential curse of ambient dimensionality for arbitrary compact distributions."

AuthorsOpenReview ↗

Response to Questions

Q1: Comparison to Chakraborty et al. (2026), Theorem 17

(To compare directly, in Q1 we adopt Chakraborty et al.'s notation where nn denotes the sample size, and DD denotes the ambient dimension.)

Thank you for raising this important comparison. Our Theorem 4 and Theorem 17 of Chakraborty et al. (2026) address fundamentally different targets and exhibit contrasting ambient-dimension dependencies.

First, Theorem 17 of Chakraborty et al. (2026) approximates the empirical score of nn discrete sample points (which requires no smoothness assumptions because the empirical measure is already discrete), rather than the population score of a general continuous or fractal distribution p0p_0. Second, to achieve a squared error tolerance (Formula 14) of O(n−κ),κ=2(1+p(q−p))d(q−p),\mathcal{O}(n^{-\kappa}), \quad \kappa = \frac{2(1 + p(q-p))}{d(q-p)}, their bound on the number of network weights W(s)\mathcal{W}(s) has nn-exponent (noting that Theorem 17's main-text statement appears to omit a (q−p)(q-p) factor; we use the full derivation on Page 45, Line 3): D+2+(Dp+D+2p)(q−p)d(q−p).\frac{D + 2 + (Dp + D + 2p)(q-p)}{d(q-p)}. Solving for W(s)\mathcal{W}(s) in terms of the L2L^2 error ϵ≍n−κ/2\epsilon \asymp n^{-\kappa/2} (up to the difference in error metric—weighted L∞L^\infty-squared in Formula 14 vs. L2L^2 in our Theorem 1), the exponent of ϵ−1\epsilon^{-1} is D+2+(Dp+D+2p)(q−p)1+p(q−p)=D+2+D(q−p)1+p(q−p)>D,\frac{D + 2 + (Dp + D + 2p)(q-p)}{1 + p(q-p)} = D + 2 + \frac{D(q-p)}{1 + p(q-p)} > D, consistent with Page 44 of Chakraborty et al. (2026), where local sub-networks invoke a O(ϵapprox−Dlog⁡(1/ϵapprox))\mathcal{O}(\epsilon_{\mathrm{approx}}^{-D}\log(1/\epsilon_{\mathrm{approx}})) Sobolev approximation bound in RD\mathbb{R}^D. Thus, while their statistical convergence rate is governed by intrinsic dimension dd, their network size still grows exponentially with the ambient dimension DD.

In contrast, our network size scales exponentially only with the Minkowski dimension dd. Furthermore, noting that a discrete empirical measure of nn sample points has Minkowski dimension d=0d=0, our Theorem 4 is particularly well-suited for this special case. In fact, treating each sample point as an independent sub-distribution of radius r=0r=0 eliminates all central moments (j≥1j \geq 1) and Taylor remainder errors, yielding an explicit ReLU network of width O(nD⋅Polylog(nRTϵt0))\mathcal{O}\big(n D \cdot \mathrm{Polylog}(\frac{nRT}{\epsilon t_0})\big) and depth O(Polylog(nRTϵt0))\mathcal{O}\big(\mathrm{Polylog}(\frac{nRT}{\epsilon t_0})\big) to approximate the empirical score with L2L^2 error ϵ\epsilon, directly complementing Chakraborty et al. (2026).


Q2: Regarding M=0M=0 in Appendix H.1

Thank you for this astute observation. The network width vs. error slope for both tested distributions at t0=1.5625×10−4t_0=1.5625\times 10^{-4} indeed looks remarkably close to what we would get from plugging M=0M=0 into our bound, that is, ϵ∝W−1/d\epsilon \propto W^{-1/d}, 1/d≈1.161/d\approx1.16, at fixed t0t_0, and ϵ∝t0−1\epsilon \propto t_0^{-1} at fixed WW. This is also the convergence rate one would expect if the local expectations of each sub-distribution cannot be accurately learned and baked into network weights using SGD or Adam.

However, we believe that we currently lack sufficient evidence to definitively claim that our experiment produces exactly such a scaling behavior, due to the observed plateauing effect at large widths documented in lines 460--461, the fact that scaling at t0=6.25×10−4t_0=6.25\times 10^{-4} produces a somewhat different slope (−0.98-0.98), and the fact that three groups of tests are not currently enough to reach a definitive conclusion.

We will pay closer attention in our added experiments (which are currently under way) to investigate whether our theory with M=0M=0 provides a consistent explanation for all observed phenomena.

I appreciate the authors' comments. It addresses most of my question, but doesn't substantially improve the paper for a strong accept. Hence, I'm keeping the same rating.

Reviewer_YYeWOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies neural-network approximation of score functions in diffusion models for compactly supported data distributions. The authors propose a discretization-based construction that decomposes the data distribution into local components, approximates their Gaussian convolutions using Taylor expansions, and combines the resulting local score estimates through a Softmax mixture. They introduce EA regularity to control the approximation error and prove that it holds with high probability for arbitrary compact distributions. The resulting ReLU-network complexity bounds depend on the support's upper Minkowski dimension. Numerical experiments on controlled fractal-like distributions examine the scaling of score-approximation error with network width, noise scale, and different notions of dimensionality.

Critical strengths

S1. Broad theoretical coverage.
The paper establishes a score-approximation guarantee for arbitrary compactly supported distributions, substantially weakening the smoothness and manifold assumptions used in prior work. A key strength is that the approximation-rate exponent is governed by the support's upper Minkowski dimension dd rather than the ambient dimension nn.

S2. A technically elegant proof framework.
The paper leverages Gaussian smoothing to locally approximate the noised density with Taylor expansions, combines the local approximations through a Softmax mixture, and introduces EA regularity to control irregular mass distributions. Since EA regularity is then shown to hold for arbitrary compact distributions with high probability, the framework achieves broad applicability without reintroducing strong smoothness assumptions.

S3. Careful and transparent empirical validation.
The experiments are designed to isolate the roles of Minkowski, manifold, and ambient dimensions, and the appendix provides detailed construction, training, evaluation, and raw-result information. This makes the empirical evidence easy to inspect and reproduce, even though the experimental scope is intentionally controlled and synthetic.

Critical weaknesses

W1. Gap between representability and learnability.
The main theoretical results establish the existence of ReLU networks that can approximate the score of arbitrary compactly supported distributions. However, the constructive proof assumes access to exact local distributional moments, which are effectively encoded into the network weights. It therefore remains unclear whether such representations can be learned efficiently from finite samples using standard denoising score matching. This gap is also present in the experiments: rather than standard denoising score matching, the networks are trained against the exact posterior mean E[x0∣xt]E[x_0 \mid x_t]. The authors' own pilot experiment shows a substantial performance gap between this oracle target and the standard noisy denoising target. Thus, while the representability result is theoretically interesting, its implications for practical score learning remain unclear.

W2. The central dependence on Minkowski dimension is not directly validated experimentally.
A central claim of the paper is that score-approximation complexity is governed by the support's Minkowski dimension dd, rather than the ambient dimension nn or the manifold dimension d′d'. However, in the current experiments, the two test distributions have the same Minkowski dimension, while only their manifold dimensions differ (dX′=1d'_X=1 and dY′=2d'_Y=2). Therefore, the experiments provide evidence that the scaling is not strongly controlled by d′d', but they do not directly demonstrate that changing dd produces the theoretically predicted change in approximation complexity. In addition, each configuration is evaluated with a single training seed, despite the presence of optimization outliers and large-width plateaus, leaving some uncertainty about the robustness of the reported scaling exponents.

W3. The experimental setting does not fully exercise the generality of the theoretical result.
One of the main theoretical contributions is the extension of score approximation guarantees beyond smooth manifolds or linear subspaces to arbitrary compact supports, including highly irregular or fractal structures. However, the experimental distributions are embedded entirely within low-dimensional linear subspaces (of dimensions 3 and 4, respectively), even when the ambient dimension is increased from n=32n=32 to n=64n=64. Moreover, the experiments use finite-depth approximations with K=6K=6, represented by 16,384 atoms. As the authors explain in Appendix G, these finite constructions are intended to behave like fractals of the target Minkowski dimension over the noise scales relevant to score approximation, rather than constituting the limiting fractal construction itself. This is a reasonable controlled testbed, but it means that the experiments validate a finite-scale proxy of the general theoretical setting rather than its full generality.

Questions for authors

Q1.
The main theorem establishes representability using a construction in which local distributional moments are effectively encoded into the network weights, while the numerical experiments further simplify learning by regressing against the exact posterior mean E[x0∣xt]E[x_0 \mid x_t]. Could the authors clarify how they expect this representability result to translate to standard finite-sample denoising score matching? In particular, is there a path toward a sample-complexity or learnability result, or could additional experiments with standard DSM help quantify this gap?

Q2.
Since the central theoretical claim concerns dependence on the Minkowski dimension dd, could the authors directly vary dd while keeping the ambient dimension nn and manifold dimension d′d' fixed, and test whether the observed width-error scaling changes accordingly? For example, it would be informative to examine whether the empirical scaling exponent changes systematically with dd in the direction predicted by the theory. Repeating these experiments across multiple random seeds would also help establish the robustness of the reported scaling laws.

Q3.
Could the authors strengthen the empirical evidence for the claimed generality beyond settings in which the data remain contained in very low-dimensional linear subspaces? For example, it would be useful to test a genuinely nonlinear support that is not contained in such a low-dimensional subspace. In addition, could the authors clarify more explicitly in the main text that the finite-depth experimental distributions approximate the intended fractal behavior over the noise scales relevant to the experiments, rather than constituting the limiting fractal construction itself?

5 comments
AuthorsOpenReview ↗

Response to W1 & Q1

Thank you for astutely pointing out the limitations of our current experiments. We have been running new experiments to address W2 & Q2 and W3 & Q3 over the past several days (with the remaining high-width and high-span control runs completing in about 36 hours).

While the final runs finish, we begin by addressing the representability-learnability gap in W1 & Q1

W1 & Q1: Gap between representability and learnability (and Oracle vs. DSM)

Thank you for raising this important distinction. We fully agree that Theorems 1–4 establish expressivity rather than gradient-descent learnability, and we will state this boundary clearly in the main text. Meanwhile, our results connect to finite-sample Denoising Score Matching (DSM) in two meaningful ways:

  1. Finite-sample distribution recovery: In finite-sample scenarios, the error between the ground-truth distribution p0p_0 and the reconstructed distribution can be decomposed into: (a) the gap between p0p_0 and the NN-sample empirical distribution qNq_N (plus early-stopping differences between qNq_N and qN,t0q_{N,t_0}), and (b) the error between qN,t0q_{N,t_0} and the network-reconstructed distribution.

    For (a), existing finite-sample Wasserstein bounds without smoothness assumptions (most notably Chakraborty et al., 2026) carry directly to our setting. For (b), because all NN samples lie in supp(p0)\mathrm{supp}(p_0), the empirical score ∇log⁡qN,t(x)\nabla\log q_{N,t}(x) can be approximated using Theorems 1 and 4 with a network no more complex than that required for approximating the original ∇log⁡pt(x)\nabla\log p_t(x). In fact, an rr-covering of p0p_0 must be an rr-covering of the NN samples, and sub-distribution moments can be simply replaced by empirical moments of samples falling into each ball. Combining this empirical score guarantee with smoothness-free backward SDE convergence bounds (e.g., Chen et al., 2023a; Li & Yan, 2024) controls the reconstruction error.

    Meanwhile, proving that SGD converges to these weights under noisy DSM remains an open problem, a point we will make clear in our revised PDF.

  2. Oracle target vs. noisy DSM: In our experiments, p0p_0 is fixed and known, and training draws fresh noisy samples online every 100,000 steps with no fixed training set. Thus, the oracle target E[x0∣xt]\mathbb{E}[x_0 \mid x_t] and noisy DSM share the same population minimizer.

    Meanwhile, the pilot gap (0.530.53 vs. 1.351.35) comes purely from target noise. At t0=1.5625×10−4t_0 = 1.5625 \times 10^{-4}, small score error requires x0x_0-accuracy around 10−510^{-5}, whereas the noisy DSM target fluctuates at scale t0=0.0125\sqrt{t_0} = 0.0125 (roughly 103×10^3\times larger). Using the exact posterior mean removes this target noise, thus allowing us to run full width sweeps within our modest GPU budget.

AuthorsOpenReview ↗

Response to W2 & Q2

We would also like to present the experimental design and initial findings for W2 & Q2 and W3 & Q3 below; we will follow up with the finalized tables and plots upon completion.

W2 & Q2: Experiment settings involving varying dd and multi-seed runs

1. Directly varying dd while fixing (n,d′)(n, d'): We added a third distribution pZp_Z defined by Z=(z1,z2,sin⁡(πz1)20,sin⁡(πz2)20)⋅V2,Z = \left(z_1, z_2, \frac{\sin(\pi z_1)}{20}, \frac{\sin(\pi z_2)}{20}\right) \cdot V_2, where V2∈R4×32V_2 \in \mathbb{R}^{4\times 32} is the same orthonormal embedding matrix used for YY, and z1,z2z_1, z_2 are generated using the algorithm in Appendix G from Cantor trees T4,5,K,ω1T_{4,5,K,\omega_1} and T4,5,K,ω2T_{4,5,K,\omega_2} (K=6K=6). Consequently, pZp_Z shares the same ambient dimension (n=32n=32), linear subspace dimension (44-D), manifold dimension (d′=2d'=2), and embedding geometry as pYp_Y, while doubling the upper Minkowski dimension to dZ=log⁡16log⁡5=2dY≈1.723.d_Z = \frac{\log 16}{\log 5} = 2 d_Y \approx 1.723. We then train score-matching networks to approximate ∇log⁡pZ,t(x)\nabla\log p_{Z,t}(x) across widths W∈[16,768]W \in [16, 768] at t0=1.5625×10−4t_0 = 1.5625 \times 10^{-4} and t0=6.25×10−4t_0 = 6.25 \times 10^{-4} (with W≤384W \leq 384 already completed). Defining ErrY(log⁡W)\mathrm{Err}_Y(\log W) and ErrZ(log⁡W)\mathrm{Err}_Z(\log W) as the log⁡ϵ\log \epsilon curves with respect to log⁡W\log W at t0=1.5625×10−4t_0 = 1.5625 \times 10^{-4}, our completed results through W=512W=512 closely follow a 2×2\times horizontal stretch: ErrZ(log⁡W)≈ErrY(log⁡W2+ΔW)+C,\mathrm{Err}_Z(\log W) \approx \mathrm{Err}_Y\left(\frac{\log W}{2} + \Delta W\right) + C, for example, ϵZ\epsilon_Z drops from 0.4880.488 at W=64W=64 to 0.1900.190 at W=192W=192 and 0.11550.1155 at W=512W=512, closely tracking ϵY\epsilon_Y from 0.5430.543 at W=28W=28 to 0.2080.208 at W=48W=48 and 0.10970.1097 at W=96W=96. Exact fitted coefficients ΔW,C\Delta W, C will be reported once all runs finish.

This observation suggests that doubling Minkowski dimension dd on the same manifold roughly halves the error's sensitivity to log⁡W\log W (requiring quadratically larger width for comparable error reduction), supporting our theoretical claim.

2. Multi-seed validation: We repeated the width-scaling experiments at t0=1.5625×10−4t_0 = 1.5625 \times 10^{-4} across W∈32,48,64,96,128,192W \in \\{32, 48, 64, 96, 128, 192\\} using two additional random seeds for all three distributions pX,pYp_X, p_Y, and pZp_Z. The results remain roughly consistent across seeds. Due to compute constraints, the extreme-width runs of pZp_Z (W≥256W \geq 256) and our newly added high-span curve experiments (W3 & Q3) are evaluated on a single seed, which we will expand in future work.

AuthorsOpenReview ↗

Response to W3 & Q3

W3 & Q3: Manifolds spanning higher-dimensional linear subspaces, and finite-KK clarification

1. Experiments on nonlinear manifolds spanning up to 31 dimensions: To test supports that cannot be contained in low-dimensional linear subspaces, we construct variants X3X_3, X5X_5, and X15X_{15} of XX defined by

XN=(x2,(ρNcos⁡(2πkx),ρNsin⁡(2πkx))k=1N)⋅VN,X_N = \left(\frac{x}{\sqrt{2}}, \Big(\rho_N\cos(2\pi k x), \rho_N\sin(2\pi k x)\Big)_{k=1}^N\right) \cdot V_N,

where

ρN=1/2(2π)2∑k=1Nk2,\rho_N = \sqrt{\frac{1/2}{(2\pi)^2 \sum_{k=1}^N k^2}},

VN∈R(2N+1)×32V_N \in \mathbb{R}^{(2N+1)\times 32} has orthonormal rows, and xx is the same 11-D Cantor variable used for generating the original XX and pXp_X. Because the functions cos⁡(2πkx),sin⁡(2πkx)k=1N\\{\cos(2\pi k x), \sin(2\pi k x)\\}_{k=1}^N are linearly independent on [0,1][0,1] (being mutually orthogonal Fourier modes), each XNX_N linearly spans 2N+12N+1 dimensions of R32\mathbb{R}^{32}. Meanwhile, ρN\rho_N ensures unit curve speed \left\\|\frac{d X_N}{dx}\right\\|_2 = 1, \quad \forall x \in [0,1], matching the original speed \left\\|\frac{dX}{dx}\right\\|_2 = 1.012 to prevent covering number from becoming a confounding variable.

To further control the confounding variable "manifold reach"—which naturally shrinks as NN grows and increases approximation difficulty (Theorem 1, manifold case)—we also construct curvature-matched 33-D control variables X~N\tilde{X}_N for N=3N=3 and N=15N=15, defined as

X~N=(x2,ρ~Ncos⁡(ωNx),ρ~Nsin⁡(ωNx))⋅V~N,\tilde{X}_N = \left(\frac{x}{\sqrt{2}}, \tilde{\rho}_N\cos(\omega_N x), \tilde{\rho}_N\sin(\omega_N x)\right) \cdot \tilde{V}_N,

where

ωN=2π∑k=1Nk4∑k=1Nk2,ρ~N=12,ωN,\omega_N = 2\pi\sqrt{\frac{\sum_{k=1}^N k^4}{\sum_{k=1}^N k^2}}, \tilde{\rho}_N = \frac{1}{\sqrt{2}\\,\omega_N},

and V~N∈R3×32\tilde{V}_N \in \mathbb{R}^{3\times 32} has orthonormal rows. Like XX, each X~N\tilde{X}_N lies in a 33-D linear subspace while maintaining unit speed

\left\\|\frac{d\tilde{X}_N}{dx}\right\\|_2 = 1, \quad \forall x\in[0,1].

Meanwhile, the embedding manifolds of XNX_N and X~N\tilde{X}_N share the same constant local curvature

\kappa_N = \left\\|\frac{d^2 X_N}{dx^2}\right\\|_2 = \left\\|\frac{d^2\tilde{X}_N}{dx^2}\right\\|_2 = \frac{\omega_N}{\sqrt{2}},

which increases with NN and is greater than the curvature of XX's original embedding manifold.

Currently completed runs at W=64W=64 and W=192W=192 (t0=1.5625×10−4t_0 = 1.5625 \times 10^{-4}) already show two encouraging trends: first, even the approximation error on X15X_{15} (spanning 31 out of 32 ambient dimensions) drops cleanly to ϵ=0.1195\epsilon = 0.1195 at W=192W=192 (down from 0.52150.5215 at W=64W=64), with its log⁡W\log W–log⁡ϵ\log \epsilon slope (≈−1.34≤−1\approx -1.34 \leq -1) clearly not dampened by the larger subspace span. Second, while score approximation errors for XNX_N are larger than those for XX at identical widths, the curvature-matched 3-D controls track the multi-frequency curves closely—for instance, X~3\tilde{X}_3 vs. X3X_3 yields nearly identical errors at both W=64W=64 (0.15580.1558 vs. 0.18070.1807) and W=192W=192 (0.06080.0608 vs. 0.06540.0654), showing that higher curvature, not higher subspace dimension, accounts for a substantial share of the narrow-width error increase. We will provide the comprehensive data table and detailed analysis once the remaining widths on XNX_N and X~N\tilde{X}_N finish within 36 hours.

2. Finite-KK truncation clarification: We apologize for not explicitly noting this detail in Section 4, and thank the reviewer for recognizing that our finite-KK setup still constitutes a "reasonable controlled testbed," as the finest atom spacing 5−6≈6.4×10−55^{-6} \approx 6.4 \times 10^{-5} is more than two orders of magnitude smaller than the smallest noise scale (t0=0.0125\sqrt{t_0} = 0.0125 at t0=1.5625×10−4t_0 = 1.5625 \times 10^{-4}). We will revise Section 4 to clearly explain that the K=6K=6 discrete mixture serves as a finite-scale proxy over the tested noise scales [t0,T][t_0, T] rather than the limiting K→∞K \to \infty fractal itself.

Reviewer_J2zkOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The manuscript analyzes the approximation capabilities of MLPs with ReLU activation when the data support has a low covering number complexity. The paper combines local moment expansions, Gaussian mixture representations and the approximation capabilities of nural networks to obtain explicit complexity bounds. The results cover smooth manifold as well as irregular sets, such as fractals. However, i have concerns about the proof and novelty of the work. See my concerns below.

Critical strengths
  • The results cover smooth manifold as well as irregular sets, such as fractals.
  • The score-denominator is controlled without a lower-bounded density assumption, which is quite interesting.
Critical weaknesses

The contribution A higher-order expansion improves the dependence on the accuracy of the approximation, but introduces an nMn^M term, where nn is the ambient dimension. It is unclear as to whether the gains in the exponent order of the approximation accuracy are worth the trade-off.

Novelty The extension to irregular supports is the most interesting part of the paper. However, the proof technique repurposes alreadyv well known results in the literature. The Hessian tail bound appears related to Chen, Lee, and Lu (Lemma C.7), who already prove a sub-exponential bound for the log-density Hessian under Gaussian smoothing. Tang et al. (2025) also establish manifold-dimension adaptive rates for diffusion models. Although the extension from manifold dimension to Minkowski dimension slightly generalizes the result, the bounds are mainly obtained by controlling the covering numbers. The paper should explain what its result adds beyond the well-known proof technique.

Proof concern (Appendix B.4, page 22, lines 1152–1154). The bound takes the absolute value after summing the weighted density errors, although these errors multiply different component-dependent vectors. Nonnegativity of the mixture weights does not justify this step. The density approximation errors can have opposite signs, so their cancellation does not imply cancellation of the vector-weighted terms. A direct application of the triangle inequality gives a sum of absolute errors. The authors should provide the correction and verify that the stated bounds remain valid.

Approximation of the reciprocal function(Appendix E.2, page 32, lines 1674–1678). I could not see how the claimed dependence on UU follows from the cited result of Opschoor et al. (2021) The paper states that approximating 1/x1/x on [1,U][1,U] to accuracy δ\delta requires width O(log⁡2(U/δ))O(\log^2(U/\delta)) and depth O(log⁡(U/δ)log⁡log⁡(U/δ))O(\log(U/\delta)\log\log(U/\delta)). However, the cited approximation theorem has constants that depend on the domain of analyticity. After rescaling [1,U][1,U] to [−1,1][-1,1], the reciprocal becomes $ f_U(z)=\frac{2}{U+1+(U-1)z}, $ whose singularity approaches −1-1 as U→∞U \to \infty. The dependence of those constants on UU therefore needs to be accounted for. Could the authors provide an explicit construction or a reference establishing the stated bounds uniformly in UU?

References

Tang, R., Lin, L., & Yang, Y. (2024). Conditional diffusion models are minimax-optimal and manifold-adaptive for conditional distribution estimation. arXiv preprint arXiv:2409.20124.

Questions for authors
  1. Can the argument in Appendix B.4 be corrected without changing the stated bounds?
  2. What construction gives the claimed reciprocal approximation complexity uniformly in UU?
7 comments
AuthorsOpenReview ↗

Correcting the Proof Gap in Question 1

Thank you for your detailed and professional review. We would like to immediately provide corrections to the gaps you insightfully discovered, which do not affect the final bounds of our theorems. We have also followed up with our ideas on the novelty, contribution, and positioning of our paper after a thorough reading of the two mentioned works, and will upload the corrected PDF document after finishing the experiments required by other reviewers.

Due to Openreview's issues with displaying math formulas, we were forced to break long formulas into shorter chunks, and use slightly nonstandard (but clear and non-ambiguous) expressions for some formulas involving min⁡\min and max⁡\max. Sorry for this inconvenience.

Q1: Regarding the deduction in Appendix B.4, lines 1152-1154.

We revise the formula in lines 1152-1154 to:

∑i∈Ajwip~i,t(x)⋅(3n+1)rt\sum_{i\in A_j}w_i\tilde{p}_{i,t}(x)\cdot\frac{(3\sqrt{n}+1)r}{t}

plus

∑i∈Ajwi∣pi,t(x)−p~i,t(x)∣⋅∥z−zj∥+λ(ϵ)tt.\sum_{i\in A_j}w_i\big|p_{i,t}(x)-\tilde{p}_{i,t}(x)\big|\cdot\frac{\left\|z-z_j\right\|+\lambda(\epsilon)\sqrt{t}}{t}.

To bound

∑i∈Ajwi∣pi,t(x)−p~i,t(x)∣,\sum_{i\in A_j}w_i\big|p_{i,t}(x)-\tilde{p}_{i,t}(x)\big|,

we note that lines 1012-1013 upper bounds ∣log⁡pi,t(x)−log⁡p~i,t(x)∣|\log p_{i,t}(x)-\log \tilde{p}_{i,t}(x)|

by

log⁡32+F(r,t,λ1,i,λ2,i),\log \frac{3}{2}+F(r,t,\lambda_{1,i},\lambda_{2,i}),

and hence upper bounds

∣pi,t(x)−p~i,t(x)∣|p_{i,t}(x)-\tilde{p}_{i,t}(x)|

by the product of min⁡(pi,t(x),p~i,t(x))\min\big(p_{i,t}(x),\tilde{p}_{i,t}(x)\big) and

32eF(r,t,λ1,i,λ2,i)−1,\frac{3}{2}e^{F(r,t,\lambda_{1,i},\lambda_{2,i})}-1,

which, in this case, is upper bounded by min⁡(pi,t(x),p~i,t(x))\min\big(p_{i,t}(x),\tilde{p}_{i,t}(x)\big) times

32eϕ(r,t,∥z−zj∥),\frac{3}{2}e^{\phi(r,t,\|z-z_j\|)},

noting the discussion regarding ϕ(r,t,∥z−zj∥)\phi(r,t,\|z-z_j\|) in lines 1058-1066 shows that

F(r,t,λ1,i,λ2,i)≤ϕ(r,t,∥z−zj∥).F(r,t,\lambda_{1,i},\lambda_{2,i})\leq\phi(r,t,\|z-z_j\|).

We can thus further upper bound

∑i∈Aj∣wi(pi,t(x)−p~i,t(x))∣\sum_{i\in A_j}\big|w_i\big(p_{i,t}(x)-\tilde{p}_{i,t}(x)\big)\big|

by

∑i∈Ajwipi,t(x)⋅32eϕ(r,t,∥z−zj∥)\sum_{i\in A_j}w_ip_{i,t}(x)\cdot \frac{3}{2}e^{\phi(r,t,\|z-z_j\|)}

and hence

∑i∈Ajwi⋅(max⁡β∈Ajpβ,t(x))⋅32eϕ(r,t,∥z−zj∥).\sum_{i\in A_j}w_i\cdot \big(\max_{\beta\in A_j}p_{\beta,t}(x)\big)\cdot \frac{3}{2}e^{\phi(r,t,\|z-z_j\|)}.

Now, Formula (20) upper bounds

∑i∈Ajwi∑i∈A~0wi\frac{\sum_{i\in A_j}w_i}{\sum_{{i\in \tilde{A}_0}}w_i}

by

μ(B(zj,λ(ϵ)t))μ(B(z0,λ(ϵ)t))\frac{\mu(B(z_j,\lambda(\epsilon)\sqrt{t}))}{\mu (B(z_0,\lambda(\epsilon)\sqrt{t}))}

which, citing (C1,C2,r)(C_1,C_2,r)-EA regularity, is bounded by

C1⋅exp⁡(C2(∥z0−zj∥λ(ϵ)t))≤C1⋅exp⁡(C2(∥z0−z∥+∥z−zj∥λ(ϵ)t)).C_1\cdot \exp(C_2(\frac{\|z_0-z_j\|}{\lambda(\epsilon)\sqrt{t}}))\leq C_1\cdot \exp(C_2(\frac{\|z_0-z\|+\|z-z_j\|}{\lambda(\epsilon)\sqrt{t}})).

Lines 1111-1113 then upper bounds

max⁡β∈Aj(pβ,t(x))⋅exp⁡(G(∥z−zj∥)−9λ2(ϵ)t−92k1Kλ3(ϵ)tt2t){\max_{\beta\in A_j}(p_{\beta,t}(x))}\cdot \exp\big(\frac{G(\left\|z-z_j\right\|)-9\lambda^2(\epsilon)t-\frac{9}{2}k_1K\lambda^3(\epsilon)t\sqrt{t}}{2t}\big)

by

min⁡(min⁡(pα,t(x),e−∥x−yα∥22t)∣α∈A~0),\min\Big(\min\big(p_{\alpha,t}(x),e^{-\frac{\|x-y_\alpha\|^2}{2t}}\big)|\alpha\in\tilde{A}_0\Big),

and hence

min⁡(min⁡(pα,t(x),32p~α,t(x))∣α∈A~0)\min\Big(\min\big(p_{\alpha,t}(x),\frac{3}{2}\tilde{p}_{\alpha,t}(x)\big)|\alpha\in\tilde{A}_0\Big)

due to the fact that R1,αR_{1,\alpha} is clamped within the range [−13,13][-\frac{1}{3},\frac{1}{3}].

Multiplying the above bounds together finally bounds ∑i∈Aj∣wi(pi,t(x)−p~i,t(x))∣\sum_{i\in A_j}\big|w_i\big(p_{i,t}(x)-\tilde{p}_{i,t}(x)\big)\big|

by

32C1H1(x,t)eϕ(r,t,∥z−zj∥)E(t,∥z−zj∥),\frac{3}{2}C_1 H_1(x,t)e^{\phi(r,t,\left\|z-z_j\right\|)}E(t,\left\|z-z_j\right\|),

checking the definitions of E(t,∥z−zj∥)E(t,\left\|z-z_j\right\|) on lines 1124-1129,

log⁡E(t,∥z−zj∥)=C2(∥z−z0∥+∥zj−z∥λ(ϵ)t)+12(9λ2(ϵ)+92k1Kλ3(ϵ)t−G(∥z−zj∥)t).\log E(t,\left\|z-z_j\right\|)=C_2\left({\frac{\left\|z-z_0\right\|+\left\|z_j-z\right\|}{\lambda(\epsilon)\sqrt{t}}}\right)+\frac{1}{2}({9\lambda^2(\epsilon)+\frac{9}{2}k_1K\lambda^3(\epsilon)\sqrt{t}}-\frac{G(\left\|z-z_j\right\|)}{t}).

then checking the definitions of H1(x,t)H_1(x,t) (which does not display properly here and can be found on lines 1121-1123), and noting that H1(x,t)H_1(x,t) is an upper bound for

∑i∈A~0wi\sum_{i\in\tilde{A}_0}w_i

times

min⁡(min⁡(pα,t(x),32p~α,t(x))∣α∈A~0).\min\Big(\min\big(p_{\alpha,t}(x),\frac{3}{2}\tilde{p}_{\alpha,t}(x)\big)|\alpha\in\tilde{A}_0\Big).

We will modify lines 1115-1117 to

∑i∈Aj∣wipi,t(x)−wip~i,t(x)∣,\sum_{i\in A_j}|w_ip_{i,t}(x)-w_i\tilde{p}_{i,t}(x)|,

lines 1152-1154 to

∑i∈Ajwip~i,t(x)⋅(3n+1)rt\sum_{i\in A_j}w_i\tilde{p}_{i,t}(x)\cdot\frac{(3\sqrt{n}+1)r}{t}

plus

∑i∈Ajwi∣pi,t(x)−p~i,t(x)∣⋅∥z−zj∥+λ(ϵ)tt,\sum_{i\in A_j}w_i\big|p_{i,t}(x)-\tilde{p}_{i,t}(x)\big|\cdot\frac{\left\|z-z_j\right\|+\lambda(\epsilon)\sqrt{t}}{t},

and line 1060 to say

the term ∑i∈Ajwi∣pi,t(x)−p~i,t(x)∣\sum_{i\in A_j}w_i|p_{i,t}(x)-\tilde{p}_{i,t}(x)|,

instead of the current

difference between ∑i∈Ajwipi,t(x)\sum_{i\in A_j}w_ip_{i,t}(x) and ∑i∈Ajwip~i,t(x)\sum_{i\in A_j}w_i\tilde{p}_{i,t}(x),

in our revised PDF, and add the detailed explanations above for clarity to account for these changes.

AuthorsOpenReview ↗

Correcting the Proof Gap in Question 2

Q2: Regarding using Opschoor et al. (2021) to approximate 1/x1/x on [1,U][1,U].

Thank you for catching this nuance. Here, we provide an explicit construction that meets the error bound in lines 1660-1661 with width O(log⁡Ulog⁡2(Uδ))\mathcal{O}(\log U \log ^2(\frac{U}{\delta})) and depth O(log⁡(Uδ)log⁡log⁡(Uδ))\mathcal{O}(\log (\frac{U}{\delta})\log \log (\frac{U}{\delta})).

While this complexity differs from our original statement by a log⁡U\log U factor in network width, we note that the function 1/x1/x only needs to be calculated once in computing Softmax (and subsequently propagated into UU copies via a single linear layer). Because this is a one-time operation compared to evaluating exe^x and multiplication (which must be calculated P=UP=U times), this explicit fix has no impact on the overall complexity of the Softmax network (width O(P⋅log⁡2(Pδ))\mathcal{O}(P\cdot \log ^2(\frac{P}{\delta})), depth O(log⁡(Pδ)log⁡log⁡(Pδ))\mathcal{O}(\log (\frac{P}{\delta})\log \log (\frac{P}{\delta})), with P=UP=U). We will also adjust our statements in lines 1674-1677 accordingly.

For the construction, we note that approximating the function 1/x1/x on the interval [2j−14,2j+1+14][2^j-\frac{1}{4},2^{j+1}+\frac{1}{4}] with error ϵ/8\epsilon/8 is no harder than approximating 1/x1/x on [34,94][\frac{3}{4},\frac{9}{4}] with error ϵ/8\epsilon/8. In fact, assuming that the base network sθs_\theta can approximate 1/x1/x on [34,94][\frac{3}{4},\frac{9}{4}] with error ϵ/8\epsilon/8, 12jsθ(x2j)\frac{1}{2^j}s_\theta\left(\frac{x}{2^j}\right) is a network with the exact same complexity that achieves this purpose.

With this in mind, we can approximate 1/x1/x on the interval [1,2N][1,2^{N}] with error upper bounded by ϵ\epsilon using the network structure h(x)=∑j=0N−1gj(x)sj,θ(x),h(x)=\sum_{j=0}^{N-1}g_{j}(x)s_{j,\theta}(x), where sj,θ(x)s_{j,\theta}(x) approximates 1/x1/x on [2j−14,2j+1+14][2^j-\frac{1}{4},2^{j+1}+\frac{1}{4}] with error ϵ/8\epsilon/8, and gjg_j is a piecewise linear gating function such that gj(x)=0,∀x∉[2j−14,2j+1+14];gj(x)=1,∀x∈[2j+14,2j+1−14]g_j(x)=0,\forall x\notin [2^j-\frac{1}{4},2^{j+1}+\frac{1}{4}]; \quad g_j(x)=1,\forall x\in [2^j+\frac{1}{4},2^{j+1}-\frac{1}{4}] (except for the two end modifications for g0g_0 and gN−1g_{N-1}), and gj=1−2(2j+14−x),∀x∈(2j−14,2j+14);gj=1−2(x+14−2j+1),∀x∈(2j+1−14,2j+1+14),g_j=1-2(2^j+\frac{1}{4}-x), \forall x\in (2^j-\frac{1}{4},2^j+\frac{1}{4}); \quad g_j=1-2(x+\frac{1}{4}-2^{j+1}), \forall x\in(2^{j+1}-\frac{1}{4},2^{j+1}+\frac{1}{4}), specifically modifying g0g_0 such that g0(x)=1g_0(x)=1 on (−∞,54](-\infty,\frac{5}{4}] (making the left ramp flat) and modifying gN−1g_{N-1} such that gN−1(x)=1g_{N-1}(x)=1 on [2N−14,+∞)[2^{N}-\frac{1}{4},+\infty) (making the right ramp flat), to ensure that ∑j=0N−1gj(x)=1,∀x∈[1,2N].\sum_{j=0}^{N-1}g_j(x)=1, \forall x\in[1,2^N]. In the above expression, gjg_j can be exactly calculated, and at most two gjg_js can take nonzero values for any x∈[1,2N]x\in[1,2^N]. Because Yarotsky (2017)'s method of calculating multiplication, sj,θ⋅gj=(sj,θ+gj2)2−(sj,θ−gj2)2s_{j,\theta}\cdot g_j=\left(\frac{s_{j,\theta}+g_j}{2}\right)^2-\left(\frac{s_{j,\theta}-g_j}{2}\right)^2 outputs exactly zero when gj=0g_j=0 and the two squaring operations use identical network structures, it suffices to implement the functions g0,...,gN−1,g_0,...,g_{N-1}, the functions s0,θ,...,sN−1,θs_{0,\theta},..., s_{N-1,\theta}, and NN multiplication operations on [0,43]2[0,\frac{4}{3}]^2 (i.e., 2N2N squaring operations on [−23,43][-\frac{2}{3},\frac{4}{3}]), each with error no more than ϵ8\frac{\epsilon}{8}.

We then calculate the total network complexity. Implementing each instance of gjg_j requires a network of fixed width and depth, so NN instances require a network of width O(N)\mathcal{O}(N) and constant depth. Implementing each multiplication instance requires a network of width O(log⁡1ϵ)\mathcal{O}(\log \frac{1}{\epsilon}) and depth O(log⁡1ϵ)\mathcal{O}(\log \frac{1}{\epsilon}), so NN instances require a network of width O(Nlog⁡1ϵ)\mathcal{O}(N\log \frac{1}{\epsilon}) and depth O(log⁡1ϵ).\mathcal{O}(\log \frac{1}{\epsilon}). Finally, implementing sj,θs_{j,\theta} is no harder than approximating 1/x1/x on [34,94][\frac{3}{4},\frac{9}{4}] with error ϵ/8\epsilon/8, so NN instances require a network of width O(Nlog⁡21ϵ)\mathcal{O}(N\log^2 \frac{1}{\epsilon}) and depth O(log⁡1ϵlog⁡log⁡1ϵ)\mathcal{O}(\log \frac{1}{\epsilon} \log \log \frac{1}{\epsilon}).

Thus, approximating 1/x1/x on [1,2N][1,2^N] with error ϵ\epsilon requires a total neural network of width O(Nlog⁡21ϵ)\mathcal{O}(N\log ^2\frac{1}{\epsilon}) and depth O(log⁡1ϵlog⁡log⁡1ϵ).\mathcal{O}(\log \frac{1}{\epsilon} \log \log \frac{1}{\epsilon}). Plugging in N=⌈log⁡2U⌉N=\lceil\log _2 U\rceil and ϵ=δ3U\epsilon=\frac{\delta}{3U} finishes the construction.

We will include this explicit construction in the revised appendix and modify the mentioned complexity of approximating 1/x1/x accordingly.

AuthorsOpenReview ↗

W1: Regarding the scaling trade-off

W1: Regarding the nMn^M scaling trade-off

Thank you for your insight. The additional complexity incurred by nMn^M scaling is precisely why we formulate MM as a tunable, rather than fixed, parameter, and we welcome the opportunity to discuss its optimal balance.

As noted in lines 193--195, when approximating distributions with arbitrary compact support, the complexity of our network scales as: O~(t0−d/2nd/2⋅nM⋅(nϵt0)d/(M+1)).\tilde{\mathcal{O}}\Big(t_0^{-d/2}n^{d/2}\cdot n^M\cdot \Big(\frac{\sqrt{n}}{\epsilon\sqrt{t_0}}\Big)^{d/(M+1)}\Big). Thus, increasing the expansion order from MM to M+1M+1 scales the complexity bound by a multiplicative factor of: n⋅(nϵt0)−d(M+1)(M+2).n\cdot \Big(\frac{\sqrt{n}}{\epsilon\sqrt{t_0}}\Big)^{-\frac{d}{(M+1)(M+2)}}. This ratio exceeds 11 (after which increasing MM is no longer beneficial) when (M+1)(M+2)(M+1)(M+2) exceeds d⋅Ld \cdot L, where L=log⁡(n/(ϵt0))log⁡n.L = \frac{\log(\sqrt{n}/(\epsilon\sqrt{t_0}))}{\log n}. As we have L∈[12,72]L \in [\frac{1}{2}, \frac{7}{2}] whenever ϵt0\epsilon\sqrt{t_0} lies in the very wide and realistic range [n−3,1][n^{-3}, 1], setting M≈O(d)M \approx \mathcal{O}(\sqrt{d}) achieves a near-optimal trade-off, ensuring the bound is never dominated by the nMn^M term.

Alternatively, if one wishes to be extremely conservative regarding the ambient dimension (for example, when dealing with distributions supported on manifolds with large reach, where Theorem 1 allows us to remove the ndn^d-type factor), simply setting M=1M=1 allows the network width to scale at rate O(ϵ−d/2)\mathcal{O}(\epsilon^{-d/2}). This matches the ϵ\epsilon-exponent that state-of-the-art works (Zhang et al., 2026) achieve only under strict 2-Hölder smoothness. At the same time, our network's dependence on the ambient dimension—O(n(3d/4)+1)\mathcal{O}(n^{(3d/4)+1}) for arbitrary compact supports, and O(n1)\mathcal{O}(n^1) for manifolds with large reach—remains substantially better than the O(n(d2+4d)/(2β))\mathcal{O}(n^{(d^2+4d)/(2\beta)}) scaling in Zhang et al. (2026) for β≤2\beta \leq 2 and all d≥2d \geq 2.

In summary, the nMn^M term is not an unavoidable bottleneck, but rather a flexible knob that can be tuned to optimize rates across diverse dimensional regimes.

Comments on the paper

3 comments
Area_Chair_ebwWOpenReview ↗

Reviewer-author discussion kickoff

Dear Reviewers,

Thank you for your review. The authors have now provided their rebuttal. We would appreciate it if you could take some time to read their responses and engage in the discussion, particularly on whether your concerns have been adequately addressed.

Thank you for your time and contributions to the review process!

AuthorsOpenReview ↗

We Have Uploaded the Revised PDF

Dear Reviewers and Area Chair:

We have uploaded a revised version of the PDF with all weaknesses and questions addressed. Please check to see whether you are satisfied by our revision.

Thank you very much for your time and effort, and for providing a helpful and professional review.

AuthorsOpenReview ↗

Summary of How Our Rebuttal and Revisions Addresses the Reviewer' Concerns

Dear Reviewers and Area Chair,

As the author-reviewer rebuttal window closes, we would like to summarize the key revisions incorporated into our newly uploaded 49-page manuscript and how they address each reviewer's concerns:

  1. Mathematical Soundness (Reviewer J2zk — Fully Resolved in the Revised PDF):

    • Appendix B.2–B.4 (Pages 20–23, Equations 19 & 22, lines 1181 & 1216): We traced the root of Reviewer J2zk's first soundness concern (Q1) and resolved it by placing the absolute value inside the summation, ∑i∈Ajwi∣pi,t(x)−p~i,t(x)∣,\sum_{i \in A_j} w_i |p_{i,t}(x) - \tilde{p}_{i,t}(x)|, via the per-kernel bound (19). This allows all downstream reasoning and calculations to proceed identically without any triangle-inequality gap, leaving the final bounds completely unaffected. (Reviewer J2zk noted in their follow-up: "I appreciate the proposed corrections, especially to Appendix B.4," and requested to see these fixes in the revised PDF, which is now uploaded.)
    • Appendix E.2 (Page 32) & Appendix F (Pages 37–39, Lemmas 5 & 6): We added explicit ReLU network constructions for exp⁡(x)\exp(x) on (−∞,0](-\infty, 0] (Lemma 5) and 1/x1/x on [1,U][1, U] (Lemma 6) using range reduction and a partition of unity tactic, eliminating the Opschoor domain-singularity dependency while leaving Theorem 4's exact complexity unchanged.
  2. Expanded Empirical Validation (Reviewer YYeW & Reviewer GGNd — 166 Runs in Section 4 & Appendices G–I):

    • Varying Minkowski dimension dd: We tested pYp_Y vs. pZp_Z (dZ=2dYd_Z = 2 d_Y) on the exact same 2-D manifold across W∈[16,768]W \in [16, 768]. Doubling dd increases error by 3×3\times–7.4×7.4\times at every width, and the curves closely align under the predicted 2×2\times log-width rescaling ErrZ(log⁡W)≈ErrY(12log⁡W+ΔW)+C\mathrm{Err}_Z(\log W) \approx \mathrm{Err}_Y(\frac{1}{2}\log W + \Delta W) + C (Figure 2c, Page 9; Table 7, Page 46, ΔW=1.349\Delta W = 1.349, C=0.015C = 0.015, aligned slopes −1.166-1.166 vs. −1.034-1.034).
    • Higher-dimensional linear subspace spans & curvature controls: We evaluated nonlinear manifold supports spanning up to 31 of 32 dimensions (X3,X5,X15X_3, X_5, X_{15} and their curvature-matched controls mentioned in our earlier comment, renamed X7,X11,X31X_7, X_{11}, X_{31} in the revised manuscript for clarity) across W∈[32,192]W \in [32, 192] (Figure 3, Page 10; Tables 9–10, Page 48). These results confirm that higher linear subspace span does not flatten the error decay, and that tighter curvature (smaller reach 1/k11/k_1), rather than subspace span, accounts for the large-width offset relative to XX. We also added explicit main-text clarifications on the finite-KK proxy (Footnote 6, Page 8) and the expressivity-vs.-learnability boundary (Page 10, lines 515–526).
  3. Presentation and Accessibility (Reviewer sfav, Reviewer GGNd, & Reviewer YYeW):

    • We incorporated the explicit θ=t0/n\theta = \sqrt{t_0/n} trade-off in the Abstract (Page 1), removed overstated "first universal" / "truly universal" phrasing (Page 1, line 18; Page 2, line 86), added the dd-Ahlfors vs. EA regularity background (Section 3.1, Page 6), clarified β\beta-Hölder smoothness, Taylor order MM, and the t→t0t \to t_0 derivation (Section 2.1, Page 4), and thoroughly proofread the manuscript.
  4. Literature Positioning (Section 1, line 96; Section 2.1, line 176; Section 3.2.1, lines 356–365):

    • We added a citation for Tang et al. (2025), properly credited Chen, Lee, and Lu (2023a) for establishing sub-exponential Hessian tail bounds in Lp(pt)L^p(p_t), and correspondingly removed our earlier claims of improving prior SDE convergence works based on sub-exponential Hessian tail bounds.

Thank you very much for your time, feedback, and stewardship of our submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.