{"id":"1198f91a-05ca-46dd-b9be-7ba20b9515f1","arxiv_id":"1908.09880","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"An abstract theorem gives dimension-independent, smoothness-improving approximation rates for shallow kernel networks, covering ReLU networks, RBFs, manifold learning, and quasirandom integration.","lead":"This paper proves rates at which sums of a fixed kernel, called shallow G-networks, approximate functions built as continuous superpositions of that same kernel, and shows the exponents need not blow up with the ambient dimension. The result is a general theorem covering ReLU networks, radial basis functions, and manifold out-of-sample extension, and it is used to argue that deep networks lose part of their theoretical edge when stable parameter selection is not required.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The deep-vs-shallow consequence is not entailed by Theorem 3.1: the theorem is an upper bound for the integral-representation class (2.6), with no shallow lower bound and no proof that the deep-network targets belong to that class.","rationale":"The reader's verdict is CONDITIONAL and already flags the deep-versus-shallow overstatement and the no-saturation hypothesis gap; my read agrees with the first of these as the most consequential issue. I do not think this requires a change of verdict: the mathematical core of Theorem 3.1, conditional on the integral-representation hypothesis, is a plausible and well-constructed upper bound. The stress-test concern is that the paper's framing converts an upper bound for a restricted representation class into a comparative statement about deep and shallow networks without the requisite lower bound or class-inclusion argument. The wording 'degree of approximation alone' may mean existence of a non-robust shallow network with comparable rate, but existence for a class and guaranteed rates for the particular compositional targets are different statements. This is a scope/interpretation issue rather than an algebraic error; hence the verdict should remain CONDITIONAL, not move to REJECT. A useful concrete check is to construct the deep-network target from the Conclusions and test membership in the Barron-type class (2.6); this would settle whether the advertised comparison is within the theorem's hypotheses. A secondary technical caveat worth noting but not central: the proof uses Π_R and D_R for R that is allowed to be real in Definition 3.3, so the statement should either require integer R or define E_s and Π_s for real s consistently; this is fixable without changing the rates.","tokens_in":20509,"tokens_out":30747,"duration_ms":330606,"concrete_test":"Select the concrete binary-tree compositional function F used in the Conclusions (e.g., F(x1,...,x1024)=f(f1(x1,x2),f2(x3,x4),...) with the branch structure of [24]); verify whether F can be written as F(x)=∫_{S^{1024}} |x·y| dτ(y) for some q-admissible τ with q=1024 and finite total variation. If such a τ cannot be exhibited or its total variation grows with the depth/size of the composition, then Corollary 4.1 is not applicable and the reported shallow exponent does not cover the deep-network example.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and Conclusions claim that, absent robust parameter selection, deep ReLU networks provide no significant advantage over shallow networks in degree of approximation alone. What Theorem 3.1 proves is an upper bound for functions f of the form f(x)=∫ G(x,y) dτ(y) with q-admissible τ. It says nothing about how well shallow networks must approximate functions outside this class, and it does not establish that the compositional target functions for which [24] obtains O(N^{-1.25}) deep rates admit such a representation with q=Q=1024. Without either a matching lower bound for shallow networks on the same class or a proof that the deep-network functions lie in the class (2.6), the displayed comparison in Conclusions (O(N^{-1.25}) vs O(N^{-0.5015})) compares bounds for possibly different function classes. Thus the paper's headline consequence is an interpretive overreach rather than a theorem. The core approximation estimate itself, conditional on (2.6), appears internally coherent.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves an abstract approximation theorem for shallow G-networks on compact metric measure spaces. Assuming the target f has an integral representation f(x)=∫G(x,y)dτ(y) for a q-admissible measure τ, and assuming kernel smoothness and exceptional-set dimension conditions, the author constructs an N-term G-network with coefficients bounded by O(1/N) and an error bound of the form O((log N / N^{1+2r/q}(ε*)^{s-q})^{1/2}), specialized to rates such as O(N^{-(Q+3)/(2Q)}) for ReLU networks on the sphere. Applications include radial basis function networks, zonal function networks, manifold learning with out-of-sample extension, and non-tensor-product cubature. The paper also claims as a consequence that, absent robust parameter selection, deep ReLU networks offer no significant advantage over shallow networks in degree of approximation alone.","tokens_in":20689,"tokens_out":7817,"duration_ms":82344,"significance":"If taken as a theorem about the integral-representation class (2.6), the main result is a substantial and useful unification: it combines the probabilistic dimension-independent approach of Barron with a smoothness-driven improvement that does not saturate, and it applies in a genuinely general metric measure setting. The proof is self-contained and the construction via partitions, Tchakaloff quadrature, Hoeffding concentration, and a union bound is coherent. The applications to manifold out-of-sample extension and to cubature on non-tensor-product domains are well motivated. The paper does not provide code or machine-checked proofs, but the analytic proof is explicit. The main weakness is that the headline deep-versus-shallow comparison is not entailed by the theorem as stated, since there is no shallow lower bound and no proof that the relevant deep-network target functions lie in the class (2.6).","major_comments":[{"comment":"The headline conclusion that deep ReLU networks provide no significant advantage over shallow networks in degree of approximation alone is not a consequence of Theorem 3.1. The theorem is an upper bound for the class of functions satisfying the integral representation (2.6), and it contains no lower bound for shallow networks. Moreover, the paper does not prove that the compositional target functions for which [24] obtains deep rates such as O(N^{-1.25}) admit a representation (2.6) with q=Q=1024 and a q-admissible τ. The displayed comparison in Section 6 between O(N^{-1.25}) and O(N^{-0.5015}) therefore compares upper bounds for possibly different function classes. This claim should be removed or explicitly recast as conditional on the target lying in the integral-representation class, and the comparison with deep rates should be suppressed unless membership is established.","section":"Abstract and Section 6 (Conclusions)"},{"comment":"The 'no saturation' statement for infinitely smooth kernels with Ex=X, s=q, and F≡c is not covered by Theorem 3.1 as stated. The theorem requires that tilde-F(t)=F(t)/t^{(q-s)/2} tend to infinity as t tends to 0, but in this limiting case tilde-F is constant. The rate O((sqrt(log N)) N^{-S}) for every S>0 may be obtainable by a direct argument with ε*=1/n, but that argument is not present. Corollary 4.4 relies on this limiting case for its O(N^{-S}) claim, so the theorem statement or the corollary needs a separate proof for the case s=q with bounded F.","section":"Theorem 3.1, Remark 3.3, and Corollary 4.4"}],"minor_comments":[{"comment":"The summation split in (5.14) uses the condition A∩Ex≠∅, whereas the bound (5.13) was derived under the condition A∩B(Ex,ε*_n)≠∅. The notation should be made consistent, since the counting argument depends on the ε*_n-neighborhood rather than on Ex itself.","section":"Section 5.3, Eq. (5.13)-(5.14)"},{"comment":"There is a typo in the sentence beginning 'However, Thereom 5.3 applied with the system...'; 'Thereom' should be 'Theorem'.","section":"Proof of Theorem 5.2"},{"comment":"The sentence 'where is X is some Banach space of functions on X' contains a duplicated 'is' and should be corrected.","section":"Section 2, Eq. (2.1)"},{"comment":"The phrase 'dimension independent bounds' is used for the rate, but the constants in Theorem 3.1 depend on the ambient dimension Q. This is stated in the body, but the abstract could be more precise by saying 'dimension independent rates' or 'bounds whose exponent is independent of dimension'.","section":"Title and Abstract"}],"recommendation":"major_revision","confidential_remarks":"The main theorem appears sound and the paper makes a useful technical contribution, but the advertised deep-versus-shallow consequence is an overreach and the s=q limiting case is not rigorously covered. I recommend asking for a revision that qualifies the deep-network comparison and supplies the missing argument or theorem hypothesis for the infinitely smooth case."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: Theorem 3.1 is a real theorem, and the proof is worth taking seriously. The paper gives a unified treatment of dimension-independent approximation for G-networks: Barron-type integral-representation classes, ReLU and RBF networks, out-of-sample extension on manifolds, and non-tensor-product cubature. What is new is mixing the Bourgain–Lindenstrauss probabilistic quadrature idea with local smoothness of the kernel and the dimension of the measure support, so the rate improves with kernel smoothness and depends on q rather than ambient Q. That is a solid contribution. The partition/Tchakaloff/Hoeffding/union-bound proof is assembled carefully, and the examples in Corollaries 4.1–4.4 are genuinely useful.\n\nThe main soft spot is the abstract and Conclusions claim that without robust parameter selection deep ReLU networks offer no significant advantage over shallow ones. Theorem 3.1 is an upper bound for functions f(x)=∫G(x,y)dτ(y) with q-admissible τ. It is not a lower bound for shallow networks on the same class, and there is no argument that the compositional targets for which [24] gets O(N^{-1.25}) lie in class (2.6) with q=Q=1024. The displayed comparison in Conclusions therefore compares bounds for possibly different function classes. This is an interpretive overreach; the theorem itself is not damaged.\n\nSecond soft spot is the no-saturation statement in Remark 3.3 and Corollary 4.4. Setting E_x=X, s=q, R=r gives F constant, which conflicts with the assumption \\tilde F(t)→∞ and makes the epsilon* definition degenerate. The no-saturation conclusion may be recoverable with a different F or a limiting argument, but as written it needs repair. The reader's report flagged this, and I think it is a legitimate issue, though minor compared with the deep/shallow framing.\n\nThe integral representation assumption (2.6) is heavy but standard in Barron-type work, and the paper is honest about using it. That is not a flaw if the claims are kept inside that class.\n\nWho is this for? Approximation theorists and machine-learning theorists who care about when shallow networks escape the curse of dimensionality. It deserves a serious referee. I would send it out, with the expectation that the author narrows the deep/shallow conclusions and fixes the no-saturation corollary.","headline":"The abstract theorem is coherent and worth taking seriously; the headline 'deep networks give no advantage' goes beyond what the theorem proves, and one smoothness corollary needs a fix.","tokens_in":21205,"tokens_out":3809,"would_cite":true,"duration_ms":40428,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A25","41A46","65D32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single abstract theorem gives dimension-independent approximation rates for shallow kernel networks.","keywords":["shallow networks","dimension independent bounds","curse of dimensionality","G-networks","integral representation","manifold learning","out-of-sample extension","tractability of integration"],"falsifier":"Take $X=[-1,1]^Q$, $G(x,y)=e^{-|x-y|^2}$, and $\\tau$ the uniform measure on the diagonal $\\{(t,\\dots,t):t\\in[-1,1]\\}$ ($q=1$). The theorem predicts that an $N$-term Gaussian network approximating the extension to the whole cube has uniform error $(\\log N/N)^{1/2}$ times an arbitrarily high power $N^{-S}$. If the actual uniform error on the cube decays only like $N^{-c/Q}$ with $c$ independent of the smoothness, then the no-saturation claim for out-of-sample extension would be false.","tokens_in":20296,"feed_emoji":"📉","tokens_out":11722,"duration_ms":100398,"temperature":0.7,"pith_summary":"This paper proves one abstract theorem that covers when a shallow network — a linear combination of a fixed kernel $G$ — can approximate a target function without the curse of dimensionality. The target must be an integral superposition $f(x)=\\int G(x,y)\\,d\\tau(y)$ with $\\tau$ a measure of bounded total variation supported on a $q$-dimensional subset of a compact metric space; the error bound for an $N$-term $G$-network then depends on $q$, not on the ambient dimension. The same theorem yields, as corollaries, rates for ReLU networks on the sphere, radial-basis-function networks on the cube, and out-of-sample extension in manifold learning. A by-product is the existence of quadrature formulas for high-dimensional integration with no tensor-product structure. The paper also argues that, without requiring robust parameter selection, deep networks hold no significant degree-of-approximation advantage over shallow ones.","feed_headline":"Shallow networks beat the curse of dimensionality for integral targets","feed_subtitle":"Error rates track the data's intrinsic dimension, not the ambient one, for any kernel superposition.","key_machinery":"The machinery is a probabilistic quadrature construction on the metric measure space. A partition theorem (Theorem 5.1) tiles the support of $\\tau$ into cells with controlled volume and density, using maximal distinguishable sets whose covering counts $H_\\epsilon(A)$ define the notion of dimension. On each cell, Tchakaloff's theorem supplies a discrete probability measure with the same moments up to degree $R$ as the restricted target measure; the cell measures are then treated as independent random variables, and Hoeffding's inequality bounds the probability that the resulting network deviates from $f$ at any point. A net over the space transfers the pointwise bound to the uniform norm. The kernel's 'smoothness in the large' enters through the exceptional sets $E_x$, the growth function $F$, and the scale $\\epsilon_n^*$ defined by $\\widetilde F(t)=F(t)/t^{(q-s)/2}$, which balances the smoothness gain against the dimension loss.","core_discovery":"The central claim is Theorem 3.1: if $\\tau$ is $q$-admissible and $G$ belongs to the class $\\mathcal{G}(\\alpha,r,R,F)$ with $\\{\\operatorname{supp}(\\tau)\\cap E_x\\}$ an $s$-dimensional family, then every $f(x)=\\int G(x,y)\\,d\\tau(y)$ can be uniformly approximated by an $N$-term $G$-network whose centers lie within $1/n$ of $\\operatorname{supp}(\\tau)$, whose coefficients are $O(1/N)$, and whose error is at most $c\\left((\\log n-\\log\\epsilon_n^*)/(n^{q+2r}(\\epsilon_n^*)^{s-q})\\right)^{1/2}\\|\\tau\\|_{TV}$, with $N\\sim n^q$. The bound merges the dimension-independent $\\sqrt{\\log N/N}$ term with a smoothness-driven factor $N^{-r/q}$; for infinitely smooth kernels the approximation does not saturate. Specializing to ReLU activation on the sphere with $q=Q$ gives $O(N^{-(Q+3)/(2Q)}\\sqrt{\\log N})$, and the same theorem, with $\\tau$ supported on a $q$-dimensional manifold, gives rates on the manifold with constants independent of the ambient space, plus rates for the out-of-sample Nyström extension to the ambient space. All of this is achieved without a robust parameter selector: the centers and coefficients are chosen depending on the target, which is what allows the improved rates.","pith_inferences":["The proof is existential: it shows that good networks exist but does not give an efficient algorithm to find the centers and coefficients; finding them may require solving a non-convex problem, so the bounds describe expressive power, not trainability.","The notion of dimension via maximal distinguishable sets is essentially a covering (Assouad-type) dimension; the arguments are likely to extend to fractal sets with fractional $q$, and the $q$-admissibility condition could be relaxed or shown necessary for the concentration step.","The rates depend on the total variation norm $\\|\\tau\\|_{TV}$; this suggests that sparsity of the representing measure is the operative complexity measure, connecting to sparse dictionary approximation and potentially guiding kernel choice so targets have sparse representations.","The no-saturation property for analytic kernels hints that uniform-norm approximation of kernel superpositions is limited only by representability, not smoothness; a testable extension would compare these bounds against kernel ridge regression on manifolds."],"forward_implications":["For functions whose representing measure lives on a $q$-dimensional manifold in $\\mathbb{R}^Q$, shallow $G$-networks achieve rates governed by $q$ alone; the ambient dimension enters only through constants.","For ReLU networks on the sphere $S^Q$, allowing target-dependent centers and coefficients improves the guaranteed rate from $O(N^{-2/Q})$ to $O(N^{-(Q+3)/(2Q)}\\sqrt{\\log N})$.","For infinitely smooth kernels (e.g., the Gaussian), the bounds do not saturate: for every $S>0$ the error is $O(N^{-S})$ on the manifold, and the same extension rate holds in the ambient space, giving a degree-of-approximation estimate for the Nyström extension.","Corollary 3.1 yields $N$-point quadrature formulas for integrals over arbitrary compact metric measure spaces, with error $O(N^{-c})$ and no tensor-product structure on the domain or the measure.","Without robust parameter selection, the gap between deep and shallow ReLU degrees of approximation is much smaller than with it: on 1024 inputs, $O(N^{-1.25})$ versus $O(N^{-0.5015})$ without, versus $O(N^{-1})$ versus $O(N^{-0.002})$ with."],"supporting_citations":[{"why":"Supplies the probabilistic zonotope idea that the proof adapts to general metric measure spaces.","marker":"[4]"},{"why":"Tchakaloff's theorem, used to replace each cell measure by a discrete measure with matching moments.","marker":"[29]"},{"why":"Hoeffding's inequality, the concentration tool that converts the random cell construction into a uniform error bound.","marker":"[28]"},{"why":"The ball-counting lemma and partition construction behind Theorem 5.1.","marker":"[11]"},{"why":"Establishes the equivalence between ReLU networks on Euclidean space and even spherical networks used in Corollary 4.1.","marker":"[1]"},{"why":"Prior constructive bound with robust parameter selection that the new non-robust bound improves upon.","marker":"[23]"},{"why":"Deep-versus-shallow comparison that motivates the claim about degree of approximation alone.","marker":"[24]"}],"fun_headline_variants":["Shallow nets dodge dimension curse for integral targets","Dimension-free error bounds for shallow networks","Deep no better than shallow for smooth kernel targets","Shallow networks: dimension-independent approximation bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The target function must be representable as an integral superposition of the kernel with respect to a finite-variation measure supported on a $q$-dimensional set; without that representation, the construction has no starting point, and the dimension-independent rates do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Shallow nets dodge dimension curse for integral targets","Dimension-free error bounds for shallow networks","Deep no better than shallow for smooth kernel targets","Shallow networks: dimension-independent approximation bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001153,"raw_usage":{"total_tokens":4851,"prompt_tokens":1093,"completion_tokens":3758,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":709,"completion_tokens_details":{"reasoning_tokens":3701}},"tokens_in":709,"tokens_out":3758,"duration_ms":28336,"temperature":1.0,"reasoning_tokens":3701,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:00:41.167372+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $X=[-1,1]^Q$, $G(x,y)=e^{-|x-y|^2}$, and $\\tau$ the uniform measure on the diagonal $\\{(t,\\dots,t):t\\in[-1,1]\\}$ ($q=1$). The theorem predicts that an $N$-term Gaussian network approximating the extension to the whole cube has uniform error $(\\log N/N)^{1/2}$ times an arbitrarily high power $N^{-S}$. If the actual uniform error on the cube decays only like $N^{-c/Q}$ with $c$ independent of the smoothness, then the no-saturation claim for out-of-sample extension would be false.","supporting_citations":[{"cited_title":"Bourgain and J","cited_arxiv_id":null,"evidence_quote":"Supplies the probabilistic zonotope idea that the proof adapts to general metric measure spaces."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Tchakaloff's theorem, used to replace each cell measure by a discrete measure with matching moments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Hoeffding's inequality, the concentration tool that converts the random cell construction into a uniform error bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the equivalence between ReLU networks on Euclidean space and even spherical networks used in Corollary 4.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Prior constructive bound with robust parameter selection that the new non-robust bound improves upon."}],"review_version":1}