{"id":"1cbb8482-b86b-4565-ae14-6d1f541d8b2a","arxiv_id":"2608.01357","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"When approximation quality is measured per bit instead of per parameter, neural networks do not fundamentally beat classical methods; the real limit is the metric entropy of the target function class.","lead":"A new theory paper argues that comparing approximation methods by parameter count is misleading: the correct measure is the number of bits needed to store parameters. It finds that neural networks do not fundamentally beat classical methods once bit cost is counted, and that metric entropy sets the true limit.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 8's bit rate rests on a sufficient Lipschitz bound; if a poly(n)-weight deep ReLU construction exists, deep networks are bit-optimal and the claim that superconvergence does not transfer is not established.","rationale":"The paper develops a useful metric-entropy framework and the classical bit-rate analyses are coherent. However, the central claim that 'no method fundamentally exceeds the approximation order achieved by classical approaches' is only as strong as the deep-network bit-rate analysis, which is the one example where the parameter-based rate is superconvergent. Corollary 8 is an upper bound produced by a uniform quantization argument based on the exponential Lipschitz bound of Lemma 1. The paper itself concedes in Remark 2 that this bound is not sharp. The gap between the upper rate N_b^{-2r/3d} and the entropy lower bound N_b^{-r/d} leaves room for a more compact encoding of deep ReLU parameters; if such an encoding exists, the deep bit rate would match classical methods, and the narrative that superconvergence is merely a parameter-count artifact would collapse. The reader identified the same weakest assumption, and the conditional verdict is appropriate: the paper should either prove a lower bound on the bit complexity of the deep-network class or explicitly restrict its conclusions to the quantization scheme analyzed. The concrete test of whether a poly(n)-weight construction achieves the parameter rate would settle the matter.","tokens_in":24210,"tokens_out":12072,"duration_ms":117785,"concrete_test":"Check whether a deep ReLU network can approximate B(H^r([0,1]^d)) in L2 with error O(N^{-2r/d}) using depth n, constant width, and all weights and biases bounded by poly(n). If such a construction exists, recompute Corollary 8 with M = poly(n): Lemma 1 then gives log Lip = O(n log n), so τ = O(n log n), N_b = O(n^2 log n), and the bit rate becomes (N_b/log N_b)^{-r/d}, matching the entropy lower bound and classical polynomial rates. This would refute the paper's stated N_b^{-2r/3d} rate and the claim that superconvergence is offset by bit cost. If no poly(n)-bounded construction exists, Corollary 8 is more credible. A tractable first instance is d = 1, r = 2, where the target rate is N^{-4} and the bit-counting can be checked explicitly on the Yarotsky-style construction.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing step is Corollary 8, which converts the deep-network parameter rate of Theorem 10 into a bit rate. The conversion uses Lemma 1's worst-case Lipschitz bound Lip(M, S̃_N) ≲ (n+1)(W+1)^{n+1} M^{n+1}. With M = 2^{C_4 n} from Theorem 10, Proposition 3 forces τ = O(N^2) bits per parameter, hence N_b = O(N^3) and the rate N_b^{-2r/3d}. But this is an upper bound for one specific encoding scheme: uniform quantization of the parameters of the [61] construction. It is not a lower bound on the bit complexity of the deep-network function class. The lower bound quoted in Corollary 8 is the metric entropy of the target class H^r, not of Σ_{W,n}(M), so it does not close the gap to N_b^{-r/d}. Remark 2 explicitly concedes that a refined construction could improve the bit rate. If a deep ReLU network approximating B(H^r) at parameter rate N^{-2r/d} can be realized with all weights and biases bounded by poly(n), then Lemma 1 gives log Lip = O(n log n), hence τ = O(n log n) and N_b = O(n^2 log n), yielding bit rate (N_b/log N_b)^{-r/d}, which matches the entropy lower bound and the classical polynomial rate. In that case the paper's conclusion that deep superconvergence is a parameter-count artifact offset by bit cost would be false, and the abstract's universal claim would be supported only by a non-tight upper bound. The central argument therefore needs a matching lower bound on the bit complexity of any encoding of the deep-network approximant class, or a qualification of Corollary 8 and the abstract to the specific quantization scheme analyzed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper develops a bit-complexity framework for approximation theory, replacing parameter count by the number of bits required to encode approximants and linking it to metric entropy. The authors analyze classical methods (Legendre polynomials, finite elements, kernel interpolants, sparse grids) and neural networks (shallow ReLU^k, linearized shallow, spectral Barron, deep ReLU). For Sobolev classes they show bit-based rates of the form (N_b/log N_b)^{-r/d} for classical methods, against a metric-entropy lower bound of N_b^{-r/d}. For Barron spaces, shallow networks match the entropy bound up to logarithms. For deep ReLU networks on H^r, they use a Lipschitz bound (Lemma 1) to convert the parameter rate N^{-2r/d} into the bit rate N_b^{-2r/3d}, which is slower than the entropy lower bound. The paper concludes that no method fundamentally exceeds classical approximation order in bits, and that deep-network superconvergence is a parameter-count artifact offset by bit cost.","tokens_in":24558,"tokens_out":18138,"duration_ms":147946,"significance":"The paper's core framework is valuable: Proposition 2 cleanly identifies metric entropy with the optimal worst-case error under a fixed bit budget, and Proposition 3 provides a general conversion from parameter-based to bit-based rates. The bit-based analyses of classical methods are correct and reveal genuine log-factor gaps relative to entropy lower bounds. The treatment of Barron and spectral Barron spaces correctly attributes dimension-independent rates to the small metric entropy of the target classes. The main weakness is that the deep-network superconvergence discussion is supported only by a sufficient upper bound for one known construction, not by a lower bound on the bit complexity of the deep-network function class, so the paper's central explanatory claim about superconvergence is not fully established.","major_comments":[{"comment":"The conclusion that deep superconvergence is a parameter-based phenomenon offset by bit cost is not established by the results presented. Corollary 8 bounds the error of a specific uniform quantization of the [61] construction whose weights satisfy M = 2^{C_4 n}; this is an upper bound on the achievable error of one encoding scheme, not a lower bound on the bit complexity of the class Σ_{W,n}(M). The lower bound quoted in Corollary 8 is the metric entropy of the target space H^r, which applies to all methods and therefore cannot attribute any gap to the deep-network architecture. Because Remark 2 explicitly concedes that a refined construction with poly(n)-bounded weights would yield the near-optimal bit rate (N_b/log N_b)^{-r/d}, the paper's strong claim in Section 6 requires either a matching lower bound on ε_m(Σ_{W,n}(M)) or a rephrasing that limits the conclusion to the specific construction analyzed. This issue is load-bearing for the paper's central explanatory claim about superconvergence.","section":"§4.4, Corollary 8, Remark 2, §6"},{"comment":"The universal claim that 'no method fundamentally exceeds the approximation order achieved by classical approaches' is stated as a conclusion of the bit-based analysis, but it is actually a direct consequence of the metric-entropy lower bounds (Proposition 2 together with Theorems 1 and 2), independent of the deep-network calculation. The deep-network upper bound in Corollary 8 is consistent with this claim but does not support it, since a faster bit rate for deep networks would not violate the entropy lower bound. The authors should state explicitly that the universal claim follows from the entropy lower bounds, and should present the deep-network analysis as a sufficient (not necessary) bit cost for one known construction rather than as the basis for the universal statement.","section":"Abstract and Section 6"}],"minor_comments":[{"comment":"The comparison of the bit-based lower bound (N log N)^{-r/d} with the parameter rate N^{-r/d} is ambiguous; the authors should state explicitly that the polynomial method with N parameters requires N_b ≃ N log N bits, so the demonstrated suboptimality is in the bit-based sense, not in the parameter-based sense.","section":"§5.1.1, Eq. (5.3)"},{"comment":"The same ambiguity appears in the Barron-space example, where the lower bound (N log N)^{−β} is compared to the parameter rate N^{−β}; please add the explicit bit-count conversion for clarity.","section":"§5.1.2"},{"comment":"The introduction states a construction with width 25d+31, while Theorem 10 uses W = d3^{d+3}; please reconcile the constants or clarify that these refer to different constructions with the same rate.","section":"Introduction, Eq. (1.5), and Theorem 10"},{"comment":"The proof sets τ = C_5 N^2 without stating the dependencies of C_5; please note that C_5 depends on d, r, and W and that N_b = τ N, making the relation N_b ≃ N^3 explicit.","section":"Corollary 8, proof"},{"comment":"The notation L2(T^d) appears where Ω is used elsewhere; please correct the domain in that item.","section":"§5.2, item 1"}],"recommendation":"major_revision","confidential_remarks":"The paper's framework and the bit-based rates for classical methods are sound and likely useful to the approximation-theory community. The main concern is that the deep-network superconvergence conclusion is an upper-bound illustration rather than a proven impossibility; the authors should either provide a lower-bound analysis for Σ_{W,n}(M) or carefully qualify the scope of the claim. The paper is honest in Remark 2, but the abstract and concluding section currently overstate the strength of the result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper proposes a bit-complexity view of approximation rates, and the core framework is sound. But the abstract and Section 6 make a universal claim that the results do not support, and the deep-network rate in Corollary 8 is an upper bound for one quantization scheme, not a lower bound. It's worth reading and worth sending to referees, but the authors need to qualify the main conclusion.\n\nWhat's actually new: the paper sets up a clean framework connecting metric entropy, binary encoding, and approximation error (Propositions 2 and 3 are correct and useful), and uses it to compare classical methods with neural networks. The comparison of parameter-based rates and bit-based rates for shallow and deep networks is a fresh and useful perspective. The observation that deep ReLU superconvergence (rate N^{-2r/d} for H^r) does not survive the bit-cost conversion is a real result for the specific construction from [61] under component-wise uniform quantization. The exposition is clear and honest; Section 5 honestly points out gaps in the spectral Barron lower bound.\n\nThe soft spots: the abstract's \"no method fundamentally exceeds\" is an overclaim. It's an observation about the analyzed examples, not a theorem. More concretely, Corollary 8 uses Lemma 1's exponential Lipschitz bound to force tau = O(N^2) bits per parameter, giving N_b^{-2r/3d}. That's a sufficient bound for one network construction, not a lower bound on the bit complexity of the deep-network function class. The lower bound quoted is the metric entropy of H^r, not of Sigma_{W,n}(M), so the gap to the entropy limit N_b^{-r/d} is not closed. The authors know this: Remark 2 explicitly concedes a refined construction could improve the rate. If anyone comes up with a deep ReLU construction with poly(n)-bounded weights and the same parameter rate, the bit rate would become (N_b/log N_b)^{-r/d}, matching the classical rate, and the central claim would collapse. That's not a remote hypothetical; the paper needs a matching lower bound or a qualified statement.\n\nAlso, the lower bounds in the classical sections are standard metric entropy estimates; the paper re-derives parameter rates and adds a log factor, but that's synthesis, not new depth.\n\nThe citation pattern looks fine. The authors cite their own work where relevant, but those are published results and not used circularly.\n\nWho this is for: researchers in approximation theory, finite-precision ML, and network compression who want a readable comparison of parameter vs bit costs. The paper deserves a serious referee: the framework is useful and the core lemmas are correct, but the main claim needs to be pinned down. I'd send it for peer review, and I'd recommend the referee push for a sharpened theorem or a clearly qualified conclusion. If the authors can close the lower bound, this could be a nice paper; as it stands, it's a good working draft.","headline":"Read this as a framework and case studies, not as a proof of the abstract's universal claim: the deep-net bit rate is a non-tight upper bound, so the paper needs a lower bound or a qualification before the main conclusion holds.","tokens_in":25076,"tokens_out":2951,"would_cite":true,"duration_ms":24854,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A46","41A25","65D15","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Measured in bits rather than parameters, neural networks do not beat classical approximation methods.","keywords":["bit complexity","metric entropy","curse of dimensionality","deep ReLU networks","approximation rates","finite precision","Barron space","superconvergence"],"falsifier":"Compute the metric entropy of the deep ReLU class $\\Sigma_{W,n}(M)$ from Theorem 10 with $M=2^{C_4 n}$ directly, or try to encode its parameters with a correlated, shared-weight, or recursive scheme; if either shows that $m$ bits can achieve error below the rate $N_b^{-2r/3d}$ on $H^r$, then Corollary 8's bound is not tight and the bit-based loss of superconvergence would be called into question. A simpler empirical version: train finite-precision deep ReLU networks on a known $H^r$ function and plot error against total bits; if the slope beats $N_b^{-r/d}$, the entropy lower bound or the experimental setup is the culprit.","tokens_in":23999,"feed_emoji":"💾","tokens_out":8213,"duration_ms":69861,"temperature":0.7,"pith_summary":"The paper argues that counting parameters overstates what neural networks achieve, because real computation stores parameters in finitely many bits. It builds a unified framework in which the minimum worst-case error achievable with $m$ bits is exactly the metric entropy of the target function class, then converts parameter-based rates for polynomials, finite elements, sparse grids, kernels, shallow networks, and deep ReLU networks into bit-based rates. The central finding is that deep ReLU superconvergence, $O(N^{-2r/d})$ on $H^r$ in parameter count, becomes only $O(N_b^{-2r/3d})$ in bits, while the metric-entropy lower bound is $N_b^{-r/d}$; the apparent advantage is eaten up by the extra precision needed. A sympathetic reader should care because this reframes the curse of dimensionality as a curse of bit complexity: if the paper is right, the real limit on approximation is the finite-precision budget, and many apparent neural-network gains are artifacts of comparing function classes with different complexity.","feed_headline":"Neural nets lose their edge when accuracy is counted in bits","feed_subtitle":"Metric entropy sets a hard lower bound, and the extra precision deep nets need swallows their speed advantage.","key_machinery":"The load-bearing object is metric entropy, $\\epsilon_m(K)_X$, the smallest radius such that $K$ can be covered by $2^m$ balls in $X$. Proposition 2 identifies it exactly with the best worst-case approximation error attainable with an $m$-bit code, so entropy is bit-complexity, not merely a bound on it. The lower-bound engine is Lemma 2, which compares the entropy of the target class with the entropy of the approximating class to force a minimum approximation error. For deep ReLU networks the crucial quantitative input is Lemma 1, an $O((n+1)(W+1)^{n+1} M^{n+1})$ Lipschitz bound on the reconstruction map; because the weights in Theorem 10 are bounded by $M=2^{C_4 n}$, this bound grows exponentially in depth and forces a polynomial-in-$N$ number of bits per parameter, degrading the bit rate from $N^{-2r/d}$ to $N_b^{-2r/3d}$.","core_discovery":"The paper's discovery is a re-evaluation of approximation rates under finite precision. Its formal claim is that when the cost of an approximant is measured in binary bits instead of parameter count, no method fundamentally exceeds the approximation order of classical approaches such as polynomials and finite elements. The mechanism is metric entropy: for any compact function class $K$, the minimal worst-case error achievable with $m$ bits equals the entropy number $\\epsilon_m(K)_X$, so entropy acts as a universal lower bound. On Sobolev spaces $H^r(\\Omega)$ the paper shows that deep ReLU networks, which reach the superconvergent parameter rate $N^{-2r/d}$ in Theorem 10, have a bit-based rate only $N_b^{-2r/3d}$ (Corollary 8), strictly worse than the entropy lower bound $N_b^{-r/d}$; therefore the superconvergence is a parameter-count artifact, not an architectural superiority. It also claims that dimension-independent rates for Barron and spectral Barron spaces reflect the small metric entropy of those target classes rather than a special power of the network.","pith_inferences":["This suggests a testable engineering rule: for a fixed bit budget, compare methods on the same target class by measuring bits-to-error directly; if a deep network's empirical bit-rate falls below the entropy lower bound of the class, the bound or the experiment is wrong.","The paper's bit-rate for deep networks relies on independent per-parameter quantization; correlated encodings such as weight sharing or low-rank factorizations could in principle compress deep ReLU parameters below that cost, potentially reviving some superconvergence in bit terms—Remark 2 admits this open possibility.","The same entropy-based machinery could be applied to modern architectures such as transformers or tensor networks to check whether their advertised rates survive finite precision, a direction the paper does not pursue."],"forward_implications":["Classical methods—polynomials, finite elements, kernels, and sparse grids—keep their parameter-based rates up to logarithmic factors after quantization: roughly $(N_b/\\log N_b)^{-r/d}$ for Sobolev classes.","Deep ReLU superconvergence does not transfer to bits: the same network that achieves $N^{-2r/d}$ in parameters needs so many bits per parameter that its bit rate drops to $N_b^{-2r/3d}$, slower than the $N_b^{-r/d}$ entropy bound.","Dimension-independent rates of shallow networks on Barron spaces should be read as statements about the small entropy of Barron classes, not about an architectural escape from the curse of dimensionality.","Metric entropy provides a universal benchmark: no method can beat the entropy rate of the target class, and methods whose binary encodings carry extra redundancy are provably suboptimal in bits.","In finite-precision practice, deep networks may need precision that grows with network size to deliver their theoretical parameter rates, so bit budgets, not parameter counts, determine which method wins."],"supporting_citations":[{"why":"introduces metric entropy, the central complexity measure the paper equates with bit-complexity.","marker":"[31]"},{"why":"gives the sharp Sobolev entropy estimate $\\epsilon_m(B(H^r))_{L^2}\\simeq m^{-r/d}$ used in all the lower bounds.","marker":"[39]"},{"why":"supplies sharp parameter rates and entropy estimates for shallow ReLU$_k$ networks on Barron spaces, the target comparison for shallow networks.","marker":"[66]"},{"why":"provides the deep ReLU superconvergence rate $N^{-2r/d}$ on Sobolev spaces whose bit conversion is the paper's main negative result.","marker":"[61]"},{"why":"underlies the width-theory lower bounds for polynomial and finite-element approximation in terms of parameters.","marker":"[18]"},{"why":"supplies the classical polynomial approximation upper bound $N^{-r/d}$ that anchors the classical side of the comparison.","marker":"[19]"},{"why":"gives the finite-element lower bounds used in Theorem 4 and the saturation remark.","marker":"[37]"},{"why":"provides the coefficient stability estimate for finitely smooth kernel interpolation used to convert kernel parameter rates to bit rates.","marker":"[76]"}],"fun_headline_variants":["Bit complexity dethrones neural nets' edge","Curse of bits: entropy bounds all approximants","Neural speed fades in bit-accuracy metric","Metric entropy: the true limit on approximation","Superconvergence is a parameter-count mirage"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument's load-bearing premise is that a network's parameters must be treated as independent numbers, each stored with the same number of bits set by a worst-case sensitivity bound; if deep ReLU parameters can be encoded more compactly than that bound suggests, the claimed disappearance of superconvergence in bit cost would not hold.","fun_headline_variants_meta":{"raw":{"variants":["Bit complexity dethrones neural nets' edge","Curse of bits: entropy bounds all approximants","Neural speed fades in bit-accuracy metric","Metric entropy: the true limit on approximation","Superconvergence is a parameter-count mirage"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000131,"raw_usage":{"total_tokens":1155,"prompt_tokens":997,"completion_tokens":158,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":85}},"tokens_in":613,"tokens_out":158,"duration_ms":2234,"temperature":1.0,"reasoning_tokens":85,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:07:13.098256+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the metric entropy of the deep ReLU class $\\Sigma_{W,n}(M)$ from Theorem 10 with $M=2^{C_4 n}$ directly, or try to encode its parameters with a correlated, shared-weight, or recursive scheme; if either shows that $m$ bits can achieve error below the rate $N_b^{-2r/3d}$ on $H^r$, then Corollary 8's bound is not tight and the bit-based loss of superconvergence would be called into question. A simpler empirical version: train finite-precision deep ReLU networks on a known $H^r$ function and plot error against total bits; if the slope beats $N_b^{-r/d}$, the entropy lower bound or the experimental setup is the culprit.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces metric entropy, the central complexity measure the paper equates with bit-complexity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the sharp Sobolev entropy estimate $\\epsilon_m(B(H^r))_{L^2}\\simeq m^{-r/d}$ used in all the lower bounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies sharp parameter rates and entropy estimates for shallow ReLU$_k$ networks on Barron spaces, the target comparison for shallow networks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the deep ReLU superconvergence rate $N^{-2r/d}$ on Sobolev spaces whose bit conversion is the paper's main negative result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"underlies the width-theory lower bounds for polynomial and finite-element approximation in terms of parameters."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the classical polynomial approximation upper bound $N^{-r/d}$ that anchors the classical side of the comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the finite-element lower bounds used in Theorem 4 and the saturation remark."}],"review_version":2}