{"id":"18c70718-4e92-41f1-a5c5-4f8151945aa4","arxiv_id":"1908.11133","paper_version":5,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Least squares estimators based on fully connected ReLU networks achieve dimension-free rates for hierarchical composition models, with either logarithmic depth and growing width or fixed width and very large depth.","lead":"This paper proves that simple, fully connected neural networks with ReLU activations can achieve fast statistical error rates in high-dimensional regression, without needing specially sparse network designs. The result matters because it shows that the theoretical benefits of depth and width can be obtained with networks that are straightforward to implement.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the theorem's proof is internally coherent and the rate argument balances approximation and complexity correctly.","rationale":"I read the paper as a careful extension of sparse-network regression rates to fully connected ReLU networks, with the main novelty being the new approximation theorems. The reader's verdict of ACCEPT with high confidence is justified: the proof structure is coherent, the approximation and empirical-process terms balance at the claimed rate, and the paper explicitly acknowledges shared approximation results and practical limitations. The reader's weakest_assumption—that the true regression function lies in a known hierarchical composition class with smoothness and Lipschitz requirements—is the main limitation of the result, but it is a domain restriction rather than a defect in the derivation. I found one minor technical issue in Lemma 19: the claim V_{T_βF} ≤ V_F is not obviously true, since composing with a fixed clipping function can increase VC dimension. However, the same bound follows by representing T_βF as a ReLU network with one additional layer, so the theorem's rate is unaffected. Because the only identified issue is repairable and does not threaten the central claim, I do not recommend changing the reader's verdict. The agreement is 'partial' because the reader and I both view the H(l,P) assumption as the principal limitation, but I do not treat it as a load-bearing correctness concern.","tokens_in":59620,"tokens_out":28944,"duration_ms":303713,"concrete_test":"Re-derive Lemma 19 for the truncated class T_βF by applying the Bartlett–Harvey–Liaw–Mehrabian VC bound to the expanded network class {σ(f+β)−σ(f−β)−β : f∈F(L,r)} with one extra layer and width max(r,3). Verify that the covering-number bound remains of the form c (log n) log(L r^2) L^2 r^2 log n with only the constant changed, and confirm that the rate in Theorem 1 is unchanged after this substitution.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is a bias–variance tradeoff: Theorem 3 supplies a sup-norm approximant in F(L_n, r_n) with squared L2 error (log n)^2 max_{(p,K)∈P} n^{-2p/(2p+K)}, and Lemma 19 supplies a covering-number bound whose contribution after division by n is (log n)^6 max_{(p,K)∈P} n^{-2p/(2p+K)}. The parameter bookkeeping checks out: in part (a), L~log n and r~n^{K/(2(2p+K))} gives L^2 r^2 / n ~ (log n)^2 n^{-2p/(2p+K)}; in part (b), L~n^{K/(2(2p+K))} log n with r constant gives the same tradeoff. The hierarchical approximation chains propagate only constants (l, C_Lip, Kmax, component counts) that are absorbed into the constants c6 and c9, so the dimension-free rate is not threatened. The main restrictions—m∈H(l,P), bounded derivatives, Lipschitz continuity, known P and l—are genuine domain limitations but they are stated assumptions rather than internal gaps. The only technical wrinkle I see is in Lemma 19, where the proof asserts V_{T_βF} ≤ V_F; clipping can increase VC dimension. This is repairable because T_β f = σ(f+β) − σ(f−β) − β places T_βF inside a ReLU network class with one extra layer, yielding the same O(L^2 r^2 log(L r^2) log n) covering-number bound with modified constants. Thus I find no load-bearing flaw in the main argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies least-squares regression with fully connected ReLU networks of the form F(L,r) and proves that, for regression functions in a hierarchical composition class H(l,P) with finite level and known smoothness/order constraints, the L2 error is bounded by c (log n)^6 max_{(p,K) in P} n^{-2p/(2p+K)}. Two regimes are covered: logarithmic depth with growing width, and growing depth with fixed width. The authors develop new approximation theorems for (p,C)-smooth functions by fully connected ReLU networks, showing in particular that wide networks with W parameters achieve sup-norm approximation error of order W^{-2p/d}, and they propagate this approximation through the levels of the hierarchical composition. The proof combines the approximation results with standard empirical-process bounds and VC-dimension covering estimates.","tokens_in":59888,"tokens_out":14222,"duration_ms":139854,"significance":"The result is significant because it removes the sparsity constraint that was required in earlier dimension-free neural network regression theory (Schmidt-Hieber; Bauer-Kohler), demonstrating that a simple fully connected topology suffices for the same type of dimension-free rate when the regression function has modular structure. The approximation theorem also improves the parameter-count rate from O(epsilon^{-d/p}) to O(epsilon^{-d/(2p)}) for smooth functions, and the proposed architectures are explicitly implementable. The proof is detailed and essentially self-contained: the Taylor-polynomial and B-spline construction is developed from first principles, the composition induction is explicit, and the statistical part uses standard covering-number arguments. The main limitations, namely that the hierarchical level l and the constraint set P must be known and that the component functions need bounded derivatives and Lipschitz constants, are stated assumptions rather than hidden gaps.","major_comments":[],"minor_comments":[{"comment":"The inequality V_{T_beta F} <= V_F is stated without justification. Under the subgraph definition of VC dimension used in [6] it is correct, because subgraphs of T_beta f at thresholds t in (-beta,beta) coincide with subgraphs of f and thresholds outside this interval give empty or full sets; the authors should add this one-sentence justification or, if a different VC definition is intended, derive the bound from T_beta u = sigma(u+beta) - sigma(u-beta) - beta at the cost of one extra layer.","section":"Supplement B, Lemma 19"},{"comment":"The cross-references in the supplement are incorrect: the proof of Lemma 4 cites Lemma 4 when it means the square-network Lemma 20, the proof of Lemma 8 cites Lemma 6 when it means the multiplier Lemma 4, and the proof of Lemma 5 cites Lemma 10 when it means the product-network Lemma 8.","section":"Supplement B, proofs of Lemmas 4, 5, 8"},{"comment":"Several displayed depth formulas contain stray unmatched braces, for example the expression 'log_2(max{q, d} + 1})' in Theorem 2 and the analogous expression in Lemma 7; these should be cleaned up.","section":"Theorem 2 and Lemma 7"},{"comment":"The statement uses max over P and the proof chooses an argmin over P without assuming that P is finite; the statement should either assume P is finite or replace the max/argmin by the maximum over the finite set of pairs (p_g, K_g) that actually occur in the composition m.","section":"Theorem 1"},{"comment":"The phrase 'W.l.o.g. we assume supp(X) subset of [-a_n, a_n]^d' should say 'for n sufficiently large', since bounded support only guarantees containment in a fixed cube [-A,A]^d while a_n grows with n.","section":"Section 5, proof of Theorem 1"},{"comment":"The notation ||g||_{C^{q_g}(R^d)} is a type error: each g has input dimension K_g, so the norm should be taken on R^{K_g}; the same typo appears in the assumptions of Theorem 3.","section":"Theorems 1 and 3"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: this paper shows that least squares estimators over fully connected ReLU networks, with either wide or deep architectures, achieve dimension-free rates for hierarchical composition models. The rate is the usual n^{-2p/(2p+K)} up to log factors. The genuinely new piece is the full nonparametric regression treatment: previous theory needed sparsity constraints on the architecture, and this paper removes that requirement. The approximation theorem itself is not new—the authors explicitly credit Yarotsky and Zhevnerchuk for the W^{-2p/d} fully connected approximation bound, and Lu et al. for later generalizations. That honesty is good, and it does not undermine the statistical contribution.\n\nWhat the paper does well: the proof structure is clear and load-bearing. The bias–variance tradeoff is handled correctly: the approximation error from Theorem 3 is balanced against the covering-number bound from Lemma 19, and the parameter bookkeeping works out in both architecture regimes. The hierarchical composition class is a natural generalization of previous interaction models. The paper also gives a Python listing for the simple architecture, which is a nice practical touch.\n\nSoft spots, in proportion: the assumptions are real restrictions. The regression function must lie in a finite-level composition class with known smoothness and order parameters, and the architecture selection depends on those parameters. The paper notes this and suggests sample-splitting, but does not prove adaptivity. That is a limitation, not a flaw. The optimization error is ignored, which is standard in this literature but worth remembering when interpreting the result. One technical wrinkle: in Lemma 19, the proof asserts that clipping does not increase VC dimension; that is not obviously true and the stress-test note correctly identifies it. The fix is straightforward—put the clipping inside a ReLU network with one extra layer—so this is repairable, not fatal. The citation pattern is fine; self-citations are to earlier technical lemmas that are genuinely used.\n\nAll in all, the central argument holds. The paper deserves a serious referee: it is careful, honest about prior work, and removes a practical obstacle in the theory. I would cite it if I worked on deep nonparametric regression. For a reading group, it is a good example of how to do a bias–variance analysis for neural networks without hand-waving, though the technical appendix is dense.","headline":"Solid, careful regression-rate paper; the approximation bound is shared with earlier work, but the statistical analysis for fully connected ReLU nets is a real contribution.","tokens_in":60442,"tokens_out":977,"would_cite":true,"duration_ms":13391,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G08","41A25","82C32"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that least squares estimators over fully connected ReLU networks, with no sparsity constraint, attain dimension-free rates for hierarchical composition regression functions, matching earlier sparse-network results up to…","keywords":["deep learning","nonparametric regression","curse of dimensionality","ReLU networks","rate of convergence","hierarchical composition models","fully connected neural networks","approximation theory"],"falsifier":"For a fixed $(p,C)$-smooth bivariate function, for example $f(x,y)=x^2+y^2$ on $[-1,1]^2$, implement the constant-width network of Theorem 2(b) with grid parameter $M$ and measure the sup-norm error. If the error does not scale as $M^{-2p}$ with depth $O(M^d)$, the approximation construction fails; correspondingly, in the regression setting, if the fixed-width estimator with $L_n\\approx n^{d/(2(2p+d))}\\log n$ does not achieve $E\\int(m_n-m)^2 \\approx (\\log n)^6 n^{-2p/(2p+d)}$ on such a function, Theorem 1(b) is false.","tokens_in":59367,"feed_emoji":"📈","tokens_out":6301,"duration_ms":66765,"temperature":0.7,"pith_summary":"This paper shows that fully connected feedforward neural networks, without any sparsity constraint, are enough to sidestep the curse of dimensionality in nonparametric regression. For regression functions that can be written as a finite hierarchical composition of smooth inner functions, the least squares estimator over ReLU networks of suitable depth and width achieves an L2 error of order $(\\log n)^6$ times $\\max_{(p,K)\\in P} n^{-2p/(2p+K)}$, a rate independent of the ambient dimension $d$. The result holds in either of two architectures: a fixed number of neurons per hidden layer with depth growing like a power of $n$, or depth growing only logarithmically with width growing like a power of $n$. This matches, up to logarithms, rates previously proved only for sparse networks, and it relies on new approximation bounds showing that dense networks can approximate smooth functions with error $W^{-2p/d}$ using $W$ parameters, improving on earlier $W^{-p/d}$ bounds.","feed_headline":"Fully connected ReLU nets beat the curse of dimensionality","feed_subtitle":"Least squares on simple dense networks matches sparse-network rates for hierarchical composition regression functions.","key_machinery":"The argument is carried by two new approximation theorems for ReLU networks (Theorem 2), which approximate any $(p,C)$-smooth function $f$ on a cube to sup-norm error $O(M^{-2p})$ with a network using either width $O(M^d)$ and depth $O(\\log M)$ or constant width and depth $O(M^d)$. The construction partitions the cube into $M^{2d}$ cells, uses a two-scale Taylor approximation, and encodes the derivatives of $f$ directly into the network weights, with a check network that nullifies errors near cell boundaries and a tensor-product B-spline weight that blends shifted partitions. Theorem 3 composes these approximations along the levels of the hierarchical composition model, and an empirical-process covering bound (Lemma 19) converts the approximation accuracy into the L2 estimation rate.","core_discovery":"On its own terms, the paper claims that network sparsity is not the engine behind depth's ability to break the curse of dimensionality. Theorem 1 asserts that least squares estimation over the fully connected class $F(L_n, r_n)$, truncated at level $c_3 \\log n$, attains $E\\int|m_n(x)-m(x)|^2 P_X(dx) \\le c_6 (\\log n)^6 \\max_{(p,K)\\in P} n^{-2p/(2p+K)}$ whenever $m$ lies in the hierarchical composition class $H(l,P)$, with either $L_n\\approx c_4\\log n$ and $r_n\\approx c_5\\max n^{K/(2(2p+K))}$, or fixed width $r\\approx c_8$ and $L_n\\approx c_7\\max n^{K/(2(2p+K))}\\log n$. If true, practical dense architectures inherit the theoretical guarantees previously attached to carefully pruned sparse topologies.","pith_inferences":["A testable practical extension is to replace the fixed constants $c_4,\\dots,c_7$ with sample splitting or cross-validation over a grid of depths and widths; the rate should then hold adaptively without knowing $l$ and $P$, at the price of a further logarithmic factor.","The approximation machinery is modular enough that the same proof strategy likely extends to other smoothness classes, such as Besov or mixed-smooth functions, provided the Taylor lemma is replaced by an appropriate local approximation statement.","For applications, the fixed-width regime implies that very deep narrow networks are not merely an engineering choice but can be a theoretically optimal implementation; this suggests that pruning to constant-width subnetworks after training may preserve rates.","The check-network and B-spline blending steps are tied to pointwise sup-norm control; an analogous argument in $L_2$ over the support of $X$ might require fewer shifted partitions and yield sharper constants."],"forward_implications":["Sparse architectures are not needed for dimension-free rates; fully connected networks with the stated depth and width schedules are theoretically justified.","The approximation error bound improves from $W^{-p/d}$ to $W^{-2p/d}$ in terms of total parameters for smooth functions on a cube.","The same convergence rate is achievable in two regimes: constant width with polynomially growing depth, or logarithmically growing depth with polynomially growing width.","Because the rate depends on the smoothness/order pairs in $P$ rather than on the ambient dimension $d$, hierarchical structure alone is enough to avoid the curse of dimensionality.","Truncating the least squares estimator at level $c_3\\log n$ is part of the construction and costs only logarithmic factors in the final bound."],"supporting_citations":[{"why":"Supplies the earlier sparse-network rate results for generalized hierarchical interaction models that this paper extends to fully connected networks.","marker":"[7]"},{"why":"Establishes sparse ReLU network approximation and regression estimation bounds, the main baseline showing sparsity was previously thought necessary.","marker":"[33]"},{"why":"Provides the ReLU approximation result for Hölder-smooth functions that this paper generalizes from Hölder to $(p,C)$-smooth functions.","marker":"[38]"},{"why":"Independently proves a $W^{-2p/d}$ approximation rate for simple fully connected deep networks, the comparison point for the approximation improvement here.","marker":"[39]"},{"why":"Later work generalizing the width-versus-depth approximation result to networks where both width and depth vary simultaneously.","marker":"[26]"},{"why":"Establishes the classical minimax rate $n^{-2p/(2p+d)}$ for $(p,C)$-smooth regression, defining the curse-of-dimensionality baseline.","marker":"[34]"},{"why":"Provides the VC-dimension bounds for piecewise linear neural networks used in the covering number estimate for $F(L,r)$.","marker":"[6]"},{"why":"Supplies the empirical process covering number tools and truncation arguments used in bounding the estimation error.","marker":"[14]"},{"why":"Provides the Taylor approximation lemma used to construct piecewise polynomial approximations of smooth functions.","marker":"[21]"}],"fun_headline_variants":["Dense ReLU nets match sparse rates in regression","Depth alone beats curse of dimensionality, no sparsity","Fully connected deep nets achieve sparse-net rates","Sparse networks not needed: dense nets break curse"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the true regression function is a finite-level hierarchical composition of smooth, Lipschitz inner functions with bounded derivatives, and that the level $l$ together with the smoothness/order set $P$ are known in advance; without that structure the dimension-free rate and the specified depth-width schedules have no foundation.","fun_headline_variants_meta":{"raw":{"variants":["Dense ReLU nets match sparse rates in regression","Depth alone beats curse of dimensionality, no sparsity","Fully connected deep nets achieve sparse-net rates","Sparse networks not needed: dense nets break curse"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000255,"raw_usage":{"total_tokens":1547,"prompt_tokens":899,"completion_tokens":648,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":586}},"tokens_in":515,"tokens_out":648,"duration_ms":6828,"temperature":1.0,"reasoning_tokens":586,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:23:30.243559+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed $(p,C)$-smooth bivariate function, for example $f(x,y)=x^2+y^2$ on $[-1,1]^2$, implement the constant-width network of Theorem 2(b) with grid parameter $M$ and measure the sup-norm error. If the error does not scale as $M^{-2p}$ with depth $O(M^d)$, the approximation construction fails; correspondingly, in the regression setting, if the fixed-width estimator with $L_n\\approx n^{d/(2(2p+d))}\\log n$ does not achieve $E\\int(m_n-m)^2 \\approx (\\log n)^6 n^{-2p/(2p+d)}$ on such a function, Theorem 1(b) is false.","supporting_citations":[{"cited_title":"Bauer and M","cited_arxiv_id":null,"evidence_quote":"Supplies the earlier sparse-network rate results for generalized hierarchical interaction models that this paper extends to fully connected networks."},{"cited_title":"Schmidt-Hieber","cited_arxiv_id":null,"evidence_quote":"Establishes sparse ReLU network approximation and regression estimation bounds, the main baseline showing sparsity was previously thought necessary."},{"cited_title":"Yarotsky","cited_arxiv_id":null,"evidence_quote":"Provides the ReLU approximation result for Hölder-smooth functions that this paper generalizes from Hölder to $(p,C)$-smooth functions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the classical minimax rate $n^{-2p/(2p+d)}$ for $(p,C)$-smooth regression, defining the curse-of-dimensionality baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the VC-dimension bounds for piecewise linear neural networks used in the covering number estimate for $F(L,r)$."},{"cited_title":"Györfi, M","cited_arxiv_id":null,"evidence_quote":"Supplies the empirical process covering number tools and truncation arguments used in bounding the estimation error."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Taylor approximation lemma used to construct piecewise polynomial approximations of smooth functions."}],"review_version":1}