Paper deep dive
Depth Enables Local Entropy: Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression
Tao Jiang, Minbo Gao, Shaowei Cai
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/19/2026, 4:56:49 AM
Summary
This paper establishes that the minimax risk for Gaussian regression over deep vector-valued Parhi-Nowak ReLU architectures exhibits a quadratic dependence on depth (L^2), rather than linear. The authors construct a local packing code using bias-corrected approximation and balanced amplification techniques to prove a lower bound of order L^2 w^2 log(w) R^2 / n, matching an upper bound derived from pseudodimension arguments up to logarithmic factors.
Entities (6)
Relation Signals (5)
Parhi-Nowak deep-RBV^2 architecture → exhibits → Quadratic Depth Dependence
confidence 95% · Thus the minimax risk has quadratic polynomial dependence on depth, up to logarithmic factors
Minimax Risk → scaleswith → L^2 w^2 log(w) R^2 / n
confidence 95% · this gives minimax risk at least of order L^2 w^2 log(w) R^2/n.
Balanced Amplification → enables → Local Packing Construction
confidence 90% · The main ingredients are a bias-corrected bounded-coefficient approximation theorem and balanced amplification... We construct a local packing
Parhi and Nowak 2021 → established → Connection between norms and variation spaces
confidence 85% · Exact descriptions of bounded-norm ReLU networks subsequently connected such norms to spline and Radon-domain variation spaces... Parhi and Nowak 2021
Ou et al. 2024 → provides → Bounded-coefficient approximation construction
confidence 85% · The construction originates in Ou et al. 2024.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study Gaussian regression over the explicit vector-valued Parhi--Nowak deep-RBV^2 architecture with depth L, width w, layer-sum variation budget A, and output bound B. For this O(L w^2)-parameterized architecture, the known lower and upper bounds differ by one factor of depth. We construct a local packing showing that the quadratic depth dependence is intrinsic under an explicit sample-size-dependent radius condition. The packing has log-cardinality Omega(L^2 w^2 log w); its codewords lie in an O(lambda) L^2 ball and are pairwise Omega(lambda)-separated. The main ingredients are a bias-corrected bounded-coefficient approximation theorem and balanced amplification: multiplying a depth-D ReLU network by q can be implemented using one constant channel so that every coefficient grows by only q^(1/D). Translation to vector-valued RBV^2 blocks then has layer-sum cost O(D w^2 q^(1/D)). Gaussian Fano yields a radius-explicit lower bound governed by the output, testing, and representation scales. Under A=B=R, sigma proportional to R, and the stated radius condition, this gives minimax risk at least of order L^2 w^2 log(w) R^2/n. A pseudodimension-based finite-net upper bound gives O-tilde(L^2 w^2 R^2/n) for unbounded Gaussian responses. Thus the minimax risk has quadratic polynomial dependence on depth, up to logarithmic factors, and exhibits a transition to representation-limited behavior at smaller radius.
Tags
Links
- Source: https://arxiv.org/abs/2608.17434v1
- Canonical: https://arxiv.org/abs/2608.17434v1
Trouble viewing inline? Open PDF directly →
Full Text
65,352 characters extracted from source content.
Expand or collapse full text
Depth Enables Local Entropy: Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression Tao Jiang Minbo Gao Shaowei Cai Affiliation: Key Laboratory of System Software (Chinese Academy of Sciences) Affiliation: State Key Laboratory of Computer Science Affiliation: Institute of Software, Chinese Academy of Sciences Affiliation: School of Computer Science and Technology, University of Chinese Academy of Sciences Affiliation: Beijing, China Email: jiangt,gaomb,caisw@ios.ac.cn Abstract We study Gaussian regression over the explicit vector-valued Parhi–Nowak deep-ℛBV2RBV^2 architecture with depth L, width w, layer-sum variation budget A, and output bound B. For this O(Lw2)O(Lw^2)-parameterized architecture, the known lower and upper bounds differ by one factor of depth. We construct a local packing showing that the quadratic depth dependence is intrinsic under an explicit sample-size-dependent radius condition. The packing has log-cardinality Ω(L2w2logw) (L^2w^2 w); its codewords lie in an O(λ)O(λ) L2L^2 ball and are pairwise Ω(λ) (λ)-separated. The main ingredients are a bias-corrected bounded-coefficient approximation theorem and balanced amplification: multiplying a depth-D ReLU network by q can be implemented using one constant channel so that every coefficient grows by only q1/Dq^1/D. Translation to vector-valued ℛBV2RBV^2 blocks then has layer-sum cost O(Dw2q1/D)O(Dw^2q^1/D). Gaussian Fano yields a radius-explicit lower bound governed by the output, testing, and representation scales. Under A=B=RA=B=R, σ≍Rσ R, and the stated radius condition, this gives ℜn∗≳L2w2logwR2n. R_n^* L^2w^2 w\,R^2n. A pseudodimension-based finite-net upper bound gives O~(L2w2R2/n) O(L^2w^2R^2/n) for unbounded Gaussian responses. Thus the minimax risk has quadratic polynomial dependence on depth, up to logarithmic factors, and exhibits a transition to representation-limited behavior at smaller radius. 1 Introduction Depth can compress a compositional description dramatically, but whether the corresponding statistical complexity grows linearly or quadratically with depth depends on more than parameter counting. A generic piecewise-linear computation-graph bound pays once for the number of parameters and once for computational depth. The central question is whether the second payment is a proof artifact or reflects information that depth can actually decode. Approximation-theoretic benefits of depth are well established. Depth-separation constructions exhibit exponential savings for selected target families, while quantitative ReLU approximation theory identifies regimes in which growing depth improves or is required for optimal approximation rates (Telgarsky 2016; Yarotsky 2017; Yarotsky 2018). These results concern representation. The question here is whether depth contributes a second factor to the local statistical complexity of a norm-constrained compositional class. Ganguli and Constantinescu 2026 isolate this issue for a deep variation-space architecture on the circle. Under the O(Lw2)O(Lw^2) parameterization used there, their bounds have the schematic form Ω(Lw2R2n)≤ℜn∗≤O~(L2w2R2n). \! ( Lw^2R^2n )\;≤\; R_n^*\;≤\; O\! ( L^2w^2R^2n ). (1) The displayed base-block formula in that work does not explicitly display the intermediate dimensions, while the cited Parhi–Nowak construction and the O(Lw2)O(Lw^2) parameter count correspond to vector-valued intermediate maps. We therefore study the vector-valued interpretation consistent with the cited construction and parameter count: d0=dL=1d_0=d_L=1, dℓ≤wd_ ≤ w, and each compositional block has hidden width at most w. Norm-controlled neural function spaces offer a complementary account of network complexity. Early Barron-type and convex neural-network formulations control approximation and estimation through function-space norms (Barron 1993; Bach 2017). Exact descriptions of bounded-norm ReLU networks subsequently connected such norms to spline and Radon-domain variation spaces (Savarese et al. 2019; Ongie et al. 2020; Parhi and Nowak 2021). The deep compositional and vector-valued extensions developed in Parhi and Nowak 2022; Parhi and Nowak 2026 and Shenouda et al. 2024 provide the function-space setting used here. Within this architecture, the missing depth factor is realized by a local function-space code rather than by a refinement of the generic upper-bound argument. We construct such a code with log||=Ω(L2w2logw). |Z|= (L^2w^2 w). The code begins with bounded-coefficient bit extraction. A width-m, depth-D ReLU network can approximate every bounded 11-Lipschitz function on [0,1][0,1] to accuracy O((m2D2logm)−1)O\! ((m^2D^2 m)^-1 ) (2) while keeping every matrix and bias entry bounded by one. The construction originates in Ou et al. 2024. Under the affine-layer convention with biases, the published layerwise rescaling step requires a correction to obtain homogeneous scaling. We provide this correction by augmenting each hidden state with a constant channel; a unit-coefficient fan-out construction then trades coefficient magnitude for additional depth. The corrected derivation preserves (2) up to universal constants. The same augmented-state idea yields our key architectural lemma. If N has depth D, then qNqN has the same depth and one additional hidden coordinate, with coefficient magnitude only q1/Dq^1/D. A coefficient-s fully connected layer has vector-valued ℛBV2RBV^2 cost O(w2s)O(w^2s), hence D,w(qN)≲Dw2q1/D. V_D,w(qN) Dw^2q^1/D. (3) This converts the 1/M1/M label scale of a bit-extraction code into a statistical margin without paying M in a single layer. The minimax question requires more than a global entropy bound. A bounded-weight network class may contain exponentially many separated functions that either fall outside the layer-sum variation ball or live at an amplitude much larger than the Gaussian testing scale. The relevant obstruction must survive both the representation constraint and localization. Our construction does so: after the statistical amplitude λ is chosen, every codeword has L2L^2 norm O(λ)O(λ), distinct codewords are Ω(λ) (λ) apart, and all codewords remain in the prescribed deep-ℛBV2RBV^2 ball. Tight covering-number bounds for ordinary bounded-weight fully connected ReLU networks already show global entropy of order W2Dlog((W+1)DBDε),W^2D \! ( (W+1)^DB^D ), which is quadratic in D at fixed B=1B=1 and fixed accuracy (Ou and Bölcskei 2026). The present result embeds a comparable quadratic-depth code into the variation-constrained class at the testing scale and converts it into a minimax lower bound. This local viewpoint also connects the construction to statistical analyses of neural regression, which give minimax or near-minimax guarantees under compositional smoothness, Besov-type, and shallow neural variation-space assumptions (Schmidt-Hieber 2020; Suzuki 2019; Parhi and Nowak 2023). Classical entropy methods connect packing and covering numbers to minimax risk (Yang and Barron 1999; Tsybakov 2009), while localized complexity theory emphasizes the geometry near the testing scale (Bartlett et al. 2005). Sharp metric-entropy results for shallow neural variation spaces provide a close comparison (Siegel and Xu 2024). Contributions. 1. We give a bias-corrected derivation of the unit-coefficient approximation rate (2). The new homogeneous-lift lemma handles all biases exactly and replaces the two bias-sensitive scaling steps used in the approximation argument. 2. We construct a local packing of size exp(Ω(M)) ( (M)), with M=Θ(L2w2logw)M= (L^2w^2 w), inside the explicit vector-valued deep-ℛBV2RBV^2 architecture. 3. We prove a radius-explicit minimax lower bound separating the output cap, Gaussian testing scale, and representation-limited scale. A sample-size-dependent corollary gives a less restrictive sufficient condition than the corresponding uniform-in-n condition. 4. We prove a Gaussian-regression upper bound using a formal architecture-to-computation-graph lemma, pseudodimension, population covering, and a finite-class least-squares oracle inequality that handles Gaussian responses directly. Organization. Sections 2–3 give the model and theorems. Section 4 locates the second depth sum. Sections 5–7 construct the packing and prove the lower bound. Section 8 proves the Gaussian upper bound. The appendices contain the corrected approximation reduction and complete technical proofs. 2 Statistical and function-class setting Circle and risk. Identify the circle with t∈[0,2)t∈[0,2) under normalized uniform measure μ(dt)=dt/2μ(\,dt)=\,dt/2. We observe Ti∼μ,Yi=f⋆(Ti)+ξi,ξi∼N(0,σ2),T_i μ, Y_i=f (T_i)+ _i, _i N(0,σ^2), (4) independently. For a class ℱF, ℜn∗(ℱ,σ)≔inff^supf⋆∈ℱf⋆‖f^−f⋆‖L2(μ)2. R_n^*(F,σ) _ f _f E_f f-f _L^2(μ)^2. (5) Vector-valued blocks. For s:ℝd→ℝD′s:R^d ^D of the form s(x)=∑k=1Kvkρ(wk⊤x−bk)+Cx+c0,s(x)= _k=1^Kv_kρ(w_k x-b_k)+Cx+c_0, (6) we use the Parhi–Nowak norm ‖s‖ℛBV2(d,D′) s _RBV^2(d;D ) ≔∑k=1K‖vk‖1‖wk‖2 _k=1^K v_k _1 w_k _2 (7) +∑j=1D′(|sj(0)|+∑r=1d|sj(er)−sj(0)|). + _j=1^D (|s_j(0)|+ _r=1^d|s_j(e_r)-s_j(0)| ). (8) This is the vector-valued Radon-domain variation-space convention of Parhi and Nowak 2022, consistent with the multi-output variation-space framework of Shenouda et al. 2024. Deep architecture. Fix d0=dL=1,1≤dℓ≤w(1≤ℓ<L),d_0=d_L=1, 1≤ d_ ≤ w (1≤ <L), (9) and blocks sℓ:ℝdℓ−1→ℝdℓs_ :R^d_ -1 ^d_ of the form (6), with Kℓ≤wK_ ≤ w. Define the layer-sum representation cost L,w(f)≔inff=sL∘⋯∘s1∑ℓ=1L‖sℓ‖ℛBV2(dℓ−1,dℓ), V_L,w(f) _f=s_L ·s s_1 _ =1^L s_ _RBV^2(d_ -1;d_ ), (10) where the infimum is over (9) and Kℓ≤wK_ ≤ w. We refer to (10) as a representation cost: scalar gains can be distributed across layers, so the resulting functional is not one-homogeneous. Definition 1 (Deep variation architecture class). For A,B>0A,B>0, let L,w(A,B)≔f:[0,2)→ℝ:L,w(f)≤A,‖f‖∞≤B,C_L,w(A,B) \f:[0,2) : V_L,w(f)≤ A,\ f _∞≤ B \, (11) with continuous endpoint identification when periodized. Write ℜn∗(A,B,σ)=ℜn∗(L,w(A,B),σ) R_n^*(A,B,σ)= R_n^*(C_L,w(A,B),σ). The motivating normalization is A=B=RA=B=R and σ≍Rσ R. A block contains O(w2)O(w^2) scalar parameters, so the architecture has Wpar=O(Lw2).W_ par=O(Lw^2). (12) Appendix A gives the exact count and a formal computation-graph realization. Standard-network convention. Let (W,D,B)N(W,D,B) denote scalar-output realizations hℓ=ρ(Aℓhℓ−1+bℓ),1≤ℓ<D,N(x)=ADhD−1+bD,h_ =ρ(A_ h_ -1+b_ ), 1≤ <D, N(x)=A_Dh_D-1+b_D, (13) with hidden width at most W and every matrix and bias entry bounded by B in absolute value. Depth counts affine maps, including the final affine output layer. This is the convention used in the bounded-coefficient approximation result. 3 Main results We first record the approximation input in the corrected form used below. Theorem 2 (Bias-corrected bounded-coefficient approximation). There exist universal constants Capp,D0>0C_ app,D_0>0 such that, for all integers m,D≥D0m,D≥ D_0 and every continuous g:[0,1]→ℝg:[0,1] satisfying ‖g‖∞≤1 g _∞≤ 1 and Lip(g)≤1Lip(g)≤ 1, there is N∈(m,D,1)N (m,D,1) with ‖N−g‖L∞([0,1])≤Cappm2D2logm. N-g _L^∞([0,1])≤ C_ appm^2D^2 m. (14) The bit-extraction construction is due to Ou et al. 2024. Appendix B gives a bias-corrected derivation and tracks all resulting changes in width and depth explicitly. The correction has two steps. Starting from a polynomial-coefficient approximant N∈(W,D,B)N (W,D,B), a homogeneous lift augments each hidden state by one constant coordinate and realizes B−DNB^-DN with unit coefficients. A width-(W+1)(W+1) fan-out construction then trades coefficient magnitude for additional depth, restoring the output amplitude using J=⌈DlogB/log⌊(W+1)/2⌋⌉J= D B/ (W+1)/2 additional layers. In the required case B=W2B=W^2, one has J=O(D)J=O(D); replacing the two bias-sensitive spline-scaling calls by this construction preserves the width/depth asymptotics and yields (14). Let D=L−1,m=w−1,M=⌊c0m2D2logm⌋,D=L-1, m=w-1, M= c_0m^2D^2 m , (15) where c0>0c_0>0 is sufficiently small. One layer is reserved for folding the circle and one hidden coordinate for homogeneous amplification. Theorem 3 (Radius-explicit lower bound). There are universal constants c,C0,Ctr,c0>0c,C_0,C_ tr,c_0>0 and integers L0,w0L_0,w_0 such that, for L≥L0+1L≥ L_0+1, w≥w0+1w≥ w_0+1, every A,B,σ>0A,B,σ>0, and every n≥1n≥ 1, ℜn∗(A,B,σ)≥c[minB,σMn,1M((A−C0)+CtrDw2)D]2. R_n^*(A,B,σ)≥ c [ \B,σ Mn, 1M ( (A-C_0)_+C_ trDw^2 )^D \ ]^2. (16) The packing is local: at its active amplitude λ, every codeword has L2L^2 norm at most CλCλ, and distinct codewords are at least cλcλ apart. The three terms are, respectively, the output cap, Gaussian testing scale, and representation-limited amplification scale. Corollary 4 (Sample-size-dependent quadratic-depth regime). Fix constants 0<cσ≤Cσ<∞0<c_σ≤ C_σ<∞. There exist constants c,c′,Crad>0c,c ,C_ rad>0, depending at most on cσc_σ and CσC_σ, such that the following holds. Assume A=B=RA=B=R, cσR≤σ≤CσRc_σR≤σ≤ C_σR, n≥Mn≥ M, and R≥2C0R≥ 2C_0. If RD−1≥(CradDw2)DM3/2n,R^D-1≥ (C_ radDw^2 )^D M^3/2 n, (17) then ℜn∗(R,R,σ)≥cR2Mn≥c′L2w2logwR2n. R_n^*(R,R,σ)≥ c R^2Mn≥ c L^2w^2 w\,R^2n. (18) We call the parameter range in Corollary 4, in which the Gaussian testing scale is active, the statistical regime. A convenient condition uniform over all n≥Mn≥ M is RD−1≥(CradDw2)DM.R^D-1≥ (C_ radDw^2 )^DM. (19) Equivalently, R R ≥(CradDw2)D/(D−1)M1/(D−1) ≥(C_ radDw^2)^D/(D-1)M^1/(D-1) =CradDw2exp(log(CradDw2)+logMD−1) =C_ radDw^2 \! ( (C_ radDw^2)+ MD-1 ) =CradDw2exp(O(log(Lw)L)). =C_ radDw^2 \! (O\! ( (Lw)L ) ). (20) Theorem 5 (Gaussian pseudodimension upper bound). There exists a universal C>0C>0 such that, for all integers L,w≥1L,w≥ 1, all A,B,σ>0A,B,σ>0, and all integers n≥2n≥ 2, ℜn∗(A,B,σ)≤CminB2,(σ2+B2)L2w2log(2Lw)log(en)n. R_n^*(A,B,σ)≤ C \B^2, (σ^2+B^2)L^2w^2 (2Lw) (en)n \. (21) Consequently, under Corollary 4, cL2w2logwR2n≤ℜn∗≤CL2w2log(Lw)log(en)R2n.c L^2w^2 w\,R^2n≤ R_n^*≤ C L^2w^2 (Lw) (en)\,R^2n. (22) Thus the polynomial depth exponent is quadratic; the remaining discrepancy is logarithmic. Remark 6 (The radius condition is structural). For f=sL∘⋯∘s1f=s_L ·s s_1, the Parhi–Nowak Lipschitz estimate and AM–GM give Lip(f)≤∏ℓ=1L‖sℓ‖ℛBV2≤(A/L)L.Lip(f)≤ _ =1^L s_ _RBV^2≤(A/L)^L. Small layer-sum budget can therefore collapse the nonconstant part of the class. An all-radius lower bound proportional to L2w2B2/nL^2w^2B^2/n would be false. 4 Where the extra depth factor lives The lower and upper bounds in Section 3 determine the polynomial depth exponent. Before constructing the packing, we identify the ordered-pair structure through which the second factor of depth enters the usual layerwise entropy calculation. The motivating upper bound acquires depth in a single generic step: Wpar=O(Lw2),Pdim=O(WparLlogWpar).W_ par=O(Lw^2), =O(W_ parL W_ par). Norm-based capacity bounds provide a different parameter-space route to depth-dependent generalization estimates (Neyshabur et al. 2015; Golowich et al. 2018). The question here is whether the layer-sum function-space constraint still contains a local packing of quadratic depth complexity. Reconstructing a layerwise covering calculation shows the same ordered-pair structure. Suppose layer ℓ has entropy Hℓ(δℓ)≲pℓlog(Cℓ/δℓ)H_ ( _ ) p_ (C_ / _ ) and downstream Lipschitz amplification Aℓ=∏j>ℓajA_ = _j> a_j. A telescoping decomposition gives ‖sL∘⋯∘s1−s~L∘⋯∘s~1‖≤∑ℓ=1LAℓδℓ. s_L ·s s_1- s_L ·s s_1 ≤ _ =1^LA_ _ . (23) The entropy-minimizing allocation under total error ε is δℓ=εpℓ/(PAℓ) _ = p_ /(PA_ ), P=∑ℓpℓP= _ p_ , and produces ∑ℓ=1LpℓlogAℓ _ =1^Lp_ A_ =∑ℓ=1Lpℓ∑j>ℓlogaj = _ =1^Lp_ _j> a_j (24) =∑j=2L(∑ℓ<jpℓ)logaj. = _j=2^L ( _ <jp_ ) a_j. (25) In the homogeneous case pℓ=p_ =p and aj=a>1a_j=a>1, this becomes ∑j=2L(∑ℓ<jp)loga=ploga∑j=2L(j−1)=pL(L−1)2loga. _j=2^L ( _ <jp ) a=p a _j=2^L(j-1)= pL(L-1)2 a. (26) Thus the second factor of depth counts ordered pairs consisting of a perturbed layer and a downstream amplification layer. For p≍w2p w^2, the resulting contribution is Θ(L2w2) (L^2w^2). The calculation identifies the source of the quadratic term in a layerwise covering argument; necessity requires a function-space lower bound, since a global parametrization could in principle avoid this bookkeeping. The packing below provides such a lower bound. At its active amplitude λ, it lies in an O(λ)O(λ) ball, has Ω(λ) (λ) pairwise separation, and has log-cardinality Ω(L2w2logw) (L^2w^2 w). Consequently, the localized covering entropy at this scale is at least Ω(L2w2logw) (L^2w^2 w), precluding a uniform covering-entropy upper bound of order O(Lw2)O(Lw^2) in the statistical regime. Binary grid codelog||=Ω(M) |Z|= (M)Bias-corrected unit-coefficient approximation‖Nz−hz/M‖∞≲M−1\|N_z-h_z/M\|_∞ M^-1Balanced amplificationcost ≲Dw2(λM)1/D Dw^2(λ M)^1/DGaussian Fanorisk ≳λ2 λ^2M=Θ(D2m2logm)M= (D^2m^2 m) Figure 1: Proof mechanism. The constant channel is used twice: to repair coefficient rescaling in the approximation theorem and to amplify the statistical code without concentrating the gain in one layer. 5 A depth-enabled local code Let xj=j/Mx_j=j/M, j=0,…,Mj=0,…,M. For z∈0,1M−1z∈\0,1\^M-1, set z0=zM=0z_0=z_M=0 and let hzh_z linearly interpolate (xj,zj)(x_j,z_j). Then ‖hz‖∞≤1 h_z _∞≤ 1, Lip(hz)≤MLip(h_z)≤ M, and gz=hz/Mg_z=h_z/M is bounded and 11-Lipschitz. Theorem 2 gives Nz∈(m,D,1)N_z (m,D,1) with ‖Nz−gz‖∞≤Cappm2D2logm. N_z-g_z _∞≤ C_ appm^2D^2 m. (27) For M=⌊c0m2D2logm⌋M= c_0m^2D^2 m and sufficiently small c0c_0, the rescaled functions Qz=MNzQ_z=MN_z obey ‖Qz−hz‖∞≤η Q_z-h_z _∞≤η (28) for a fixed small universal η. If dj=zj−zj′d_j=z_j-z_j , direct integration on the jjth cell gives ∫j/M(j+1)/M(hz−hz′)2x=dj2+djdj+1+dj+123M. _j/M^(j+1)/M(h_z-h_z )^2\,dx= d_j^2+d_jd_j+1+d_j+1^23M. (29) Since a2+ab+b2≥(a2+b2)/2a^2+ab+b^2≥(a^2+b^2)/2 and d0=dM=0d_0=d_M=0, ‖hz−hz′‖22≥dH(z,z′)3M. h_z-h_z _2^2≥ d_H(z,z )3M. (30) The Varshamov–Gilbert bound (Tsybakov 2009) therefore yields ⊆0,1M−1Z \0,1\^M-1 such that log||≥cM,c≤‖Qz−Qz′‖2≤C(z≠z′). |Z|≥ cM, c≤ Q_z-Q_z _2≤ C (z≠ z ). (31) The code therefore has the required cardinality and local geometry. The remaining task is to amplify it to scale λ without exhausting the layer-sum budget. 6 Balanced amplification and ℛBV2RBV^2 translation Since Qz=MNzQ_z=MN_z, reaching separation of order λ requires a gain q=λMq=λ M relative to the unit-coefficient approximant. Applying this gain entirely in the final layer would charge order q to one block. Balanced amplification distributes the same gain across depth while a constant homogeneous coordinate transports every bias exactly. Lemma 7 (Balanced amplification). Let N∈(m,D,1)N (m,D,1) have exact depth D≥2D≥ 2. For every q>0q>0, qNqN has a depth-D, width-at-most-(m+1)(m+1) realization with coefficient magnitude at most q1/Dq^1/D. Writing s=q1/Ds=q^1/D, the augmented state is h~ℓ=(sℓhℓ,sℓ) h_ =(s h_ ,s ). The extra coordinate transports the scaled biases, and the final affine map returns sDN=qNs^DN=qN. Appendix D gives the matrices and exact-depth padding. Lemma 8 (Layer translation). Let T(x)=ρ(Ax+b)T(x)=ρ(Ax+b) coordinatewise, with input and output dimensions at most w and |Aij|,|bi|≤s|A_ij|,|b_i|≤ s. Then T is an allowed vector-valued block with at most w atoms and ‖T‖ℛBV2≤Cw2s. T _RBV^2≤ Cw^2s. (32) The same estimate holds for an affine output map. Thus, for N∈(m,D,1)N (m,D,1), D,m+1(qN)≤CtrD(m+1)2q1/D. V_D,m+1(qN)≤ C_ trD(m+1)^2q^1/D. (33) To embed the interval code on the circle, use r(t)=t−2ρ(t−1),0≤t≤2.r(t)=t-2ρ(t-1), 0≤ t≤ 2. (34) It has univariate ℛBV2RBV^2 norm C0=3C_0=3, maps both endpoints to zero, and traverses [0,1][0,1] once in each direction. For Fz(t)=λQz(r(t)),F_z(t)=λ Q_z(r(t)), (35) we have ‖Fz−Fz′‖L2([0,2),dt/2)=λ‖Qz−Qz′‖L2([0,1]) F_z-F_z _L^2([0,2),\,dt/2)=λ Q_z-Q_z _L^2([0,1]) (36) and, using D=L−1D=L-1, m+1=wm+1=w, L,w(Fz)≤C0+CtrDw2(λM)1/D. V_L,w(F_z)≤ C_0+C_ trDw^2(λ M)^1/D. (37) Equation (37) completes the representation step. We now combine this bound with the output and Gaussian testing constraints. 7 From the local code to the minimax lower bound Three constraints determine the admissible amplitude. First, (28) gives ‖Qz‖∞≤1+η Q_z _∞≤ 1+η, so the output cap is satisfied whenever λ≲B.λ B. (38) Second, (37) places the code in the layer-sum ball when A>C0A>C_0 and λ≲1M(A−C0CtrDw2)D.λ 1M ( A-C_0C_ trDw^2 )^D. (39) When A≤C0A≤ C_0, the positive-part convention in the theorem records the resulting trivial lower bound. Finally, the Gaussian testing scale is determined by the size of the code. Since log||≳M |Z| M and the pairwise divergence is of order nλ2/σ2nλ^2/σ^2, Fano’s inequality requires λ≲σMn.λ σ Mn. (40) We therefore choose λ=cλminB,σMn,1M((A−C0)+CtrDw2)D.λ=c_λ \B,σ Mn, 1M ( (A-C_0)_+C_ trDw^2 )^D \. (41) Up to universal constants, (41) is the largest amplitude compatible with all three restrictions. After reducing cλc_λ, equations (28) and (37) imply Fz∈L,w(A,B)F_z _L,w(A,B). Equations (31) and (36) give cλ≤‖Fz−Fz′‖2≤Cλ,‖Fz‖2≤Cλ.cλ≤ F_z-F_z _2≤ Cλ, F_z _2≤ Cλ. (42) Thus the same family is both local and separated at the chosen amplitude. For Gaussian random-design regression, DKL(Pz⊗n∥Pz′⊗n)=n2σ2‖Fz−Fz′‖22≤Cnλ2σ2.D_KL(P_z n\|P_z n)= n2σ^2 F_z-F_z _2^2≤ C nλ^2σ^2. (43) The testing restriction (40) makes this a sufficiently small multiple of M≲log||M |Z|. Nearest-neighbor decoding and Fano’s inequality (Tsybakov 2009) then yield risk Ω(λ2) (λ^2), proving Theorem 3. For Corollary 4, n≥Mn≥ M makes the testing amplitude at most a constant multiple of R. If R≥2C0R≥ 2C_0, then R−C0≥R/2R-C_0≥ R/2, and (17) implies 1M(R−C0CtrDw2)D≥cRMn. 1M ( R-C_0C_ trDw^2 )^D≥ cR Mn. Hence λ2≍R2M/nλ^2 R^2M/n. The uniform condition (19) follows because M3/2/n≤M^3/2/ n≤ M for n≥Mn≥ M. Complete constants appear in Appendix F. 8 A Gaussian upper bound without bounded responses To match the lower bound in its polynomial depth dependence, we now derive a Gaussian upper bound for the same architecture. Lemma 9 (Architecture-to-computation graph). Every function in L,w(A,B)C_L,w(A,B) is realized by a piecewise-linear computation graph with at most CLw2CLw^2 real parameters and computational depth at most CLCL. Consequently, Pdim(L,w(A,B))≤CL2w2log(2Lw).Pdim(C_L,w(A,B))≤ CL^2w^2 (2Lw). (44) The proof in Appendix A explicitly handles vector-valued blocks, affine skips, and variable intermediate dimensions. It then applies the piecewise-linear pseudodimension theorem of Bartlett et al. 2019. For every design distribution P, a [−B,B][-B,B]-valued class of pseudodimension V satisfies logN(ε,L,w(A,B),L2(P))≤CVlogCBε. N( ,C_L,w(A,B),L^2(P))≤ CV CB . (45) For a finite ⊂[−B,B]G⊂[-B,B], least squares under Y=f⋆(X)+ξY=f (X)+ξ, ξ∼N(0,σ2)ξ N(0,σ^2), obeys ‖g^−f⋆‖22≤Cinfg∈‖g−f⋆‖22+C(σ2+B2)log(2||)n.E g-f _2^2≤ C _g g-f _2^2+C (σ^2+B^2) (2|G|)n. (46) The Gaussian multiplier/Bernstein argument applies directly to unbounded Gaussian responses. Taking a population-L2L^2 ε -net, using (45), and optimizing ε yields Theorem 5; Appendix G gives the full proof. Together with Corollary 4, Theorem 5 fixes the polynomial depth exponent. We next interpret the resulting local entropy bound and the competition among the output, testing, and representation scales. 9 Consequences and open directions The packing also yields an explicit localized covering lower bound. At the amplitude selected in (41), all codewords lie in an L2L^2 ball of radius CλCλ, distinct codewords are at least cλcλ apart, and logN(cλ,L,w(A,B)∩f:‖f‖2≤Cλ,L2)≥cM=Ω(L2w2logw). N\! (cλ,C_L,w(A,B)∩\f: f _2≤ Cλ\,L^2 )≥ cM= (L^2w^2 w). Hence the localized entropy at the testing scale is quadratic in depth, precluding a uniform covering-entropy upper bound of order O(Lw2)O(Lw^2) in the statistical regime. This local statement complements sharp entropy results for shallow neural variation spaces (Siegel and Xu 2024) and the general entropy–minimax correspondence (Yang and Barron 1999). 9.1 Radius dependence of the lower bound Theorem 3 can be read as a competition among three amplitudes: λout=B,λstat=σM/n,λrep=1M((A−C0)+CtrDw2)D. _ out=B, _ stat=σ M/n, _ rep= 1M ( (A-C_0)_+C_ trDw^2 )^D. (47) If λout _ out is smallest, the lower bound saturates at the output-diameter scale B2B^2. If λstat _ stat is smallest, ordinary Gaussian testing is active and the risk is Ω(σ2M/n) (σ^2M/n). Under A=B=RA=B=R and σ≍Rσ R, this is the quadratic-depth regime of Corollary 4, namely the statistical regime. If λrep _ rep is smallest, the same construction gives ℜn∗(A,B,σ)≳1M2((A−C0)+CtrDw2)2D. R_n^*(A,B,σ) 1M^2 ( (A-C_0)_+C_ trDw^2 )^2D. (48) Equation (48) identifies the representation-limited scale at which the layer-sum budget prevents the bit-extraction code from reaching the Gaussian testing scale. The transition is structural: the block Lipschitz estimate gives Lip(f)≤∏ℓ=1L‖sℓ‖ℛBV2≤(AL)L,Lip(f)≤ _ =1^L s_ _RBV^2≤ ( AL )^L, (49) so a small ratio A/LA/L can collapse the class exponentially with depth. The radius transition therefore reflects the geometry of the class rather than only the proof technique. 9.2 Limitations and open questions Several questions remain. The lower bound contains logw w, whereas the upper bound contains log(Lw)logn (Lw) n; closing these logarithmic factors may require a sharper localized upper bound or a larger packing. The bounded-coefficient approximation theorem assumes width and depth above universal thresholds, leaving the smallest-width cases open. Finite-precision parameter classes may exhibit a different transition because the bit-extraction mechanism uses real parameters at fine resolution. The theorem concerns the explicit vector-valued Parhi–Nowak architecture consistent with the O(Lw2)O(Lw^2) parameterization in the motivating work; a literal scalar-to-scalar chain has only O(Lw)O(Lw) parameters and defines a different minimax problem. A sharp A-dependent upper bound across all three regimes in (47) remains open. The local packing of entropy Ω(L2w2logw) (L^2w^2 w) therefore survives the layer-sum variation constraint at the Gaussian testing scale. Under the radius condition of Corollary 4, the minimax risk has quadratic, rather than linear, polynomial dependence on depth, up to logarithmic factors. Reproducibility statement All assumptions and architecture conventions are stated explicitly in Sections 2–3, and complete proofs are provided in the appendices, including the corrected approximation reduction, balanced amplification and ℛBV2RBV^2 translation, and the Gaussian lower and upper bounds. The results are entirely analytical; no experiments or external datasets are used. Generative AI use statement Generative AI tools were used for literature search, formulation and critical checking of candidate mathematical claims, proof assistance, algebraic sanity checks, and manuscript editing. All AI-assisted material was independently verified against primary sources or direct derivations. The authors take responsibility for the final content. References Anthony and Bartlett (1999) Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. Bach (2017) Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19):1–53, 2017. Barron (1993) Andrew R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930–945, 1993. Bartlett et al. (2005) Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics, 33(4):1497–1537, 2005. doi: 10.1214/009053605000000282. Bartlett et al. (2019) Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1–17, 2019. Ganguli and Constantinescu (2026) Arkaprabha Ganguli and Emil Constantinescu. A function-space dichotomy for compositional learning: Exponential sub-optimality of the neural tangent kernel. arXiv preprint arXiv:2607.06382, 2026. Golowich et al. (2018) Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297–299. PMLR, 2018. Haussler (1992) David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78–150, 1992. Neyshabur et al. (2015) Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of the 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1376–1401. PMLR, 2015. Ongie et al. (2020) Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width ReLU nets: The multivariate case. In International Conference on Learning Representations, 2020. Ou and Bölcskei (2026) Weigutian Ou and Helmut Bölcskei. Covering numbers for deep ReLU networks with applications to function approximation and nonparametric regression. arXiv:2410.06378v2, 2026. Ou et al. (2024) Weigutian Ou, Philipp Schenkel, and Helmut Bölcskei. Three quantization regimes for ReLU networks. arXiv preprint arXiv:2405.01952, 2024. Parhi and Nowak (2021) Rahul Parhi and Robert D. Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1–40, 2021. URL https://w.jmlr.org/papers/v22/20-583.html. Parhi and Nowak (2022) Rahul Parhi and Robert D. Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. SIAM Journal on Mathematics of Data Science, 4(2):464–489, 2022. doi: 10.1137/21M1418642. Parhi and Nowak (2023) Rahul Parhi and Robert D. Nowak. Near-minimax optimal estimation with shallow ReLU neural networks. IEEE Transactions on Information Theory, 69(2):1125–1140, 2023. doi: 10.1109/TIT.2022.3208653. Parhi and Nowak (2026) Rahul Parhi and Robert D. Nowak. Compositional function spaces for deep learning. SIAM Review, 68(1):127–149, 2026. doi: 10.1137/25M1802948. Savarese et al. (2019) Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? Conference on Learning Theory, pages 2667–2690, 2019. Schmidt-Hieber (2020) Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48(4):1875–1897, 2020. Shenouda et al. (2024) Joseph Shenouda, Rahul Parhi, Kangwook Lee, and Robert D. Nowak. Variation spaces for multi-output neural networks: Insights on multi-task learning and network compression. Journal of Machine Learning Research, 25(231):1–40, 2024. URL https://w.jmlr.org/papers/v25/23-0677.html. Siegel and Xu (2024) Jonathan W. Siegel and Jinchao Xu. Sharp bounds on the approximation rates, metric entropy, and n-widths of shallow neural networks. Foundations of Computational Mathematics, 24(2):481–537, 2024. doi: 10.1007/s10208-022-09595-3. Suzuki (2019) Taiji Suzuki. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: Optimal rate and curse of dimensionality. International Conference on Learning Representations, 2019. Telgarsky (2016) Matus Telgarsky. Benefits of depth in neural networks. In Proceedings of the 29th Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1517–1539. PMLR, 2016. Tsybakov (2009) Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer, 2009. Yang and Barron (1999) Yuhong Yang and Andrew R. Barron. Information-theoretic determination of minimax rates of convergence. The Annals of Statistics, 27(5):1564–1599, 1999. Yarotsky (2017) Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103–114, 2017. doi: 10.1016/j.neunet.2017.07.002. Yarotsky (2018) Dmitry Yarotsky. Optimal approximation of continuous functions by very deep ReLU networks. In Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 639–649. PMLR, 2018. Appendix A Architecture conventions and computation-graph realization A.1 Vector-valued class and relation to the motivating formulation For s(x)=∑k=1Kvkρ(wk⊤x−bk)+Cx+c0s(x)= _k=1^Kv_kρ(w_k x-b_k)+Cx+c_0, we use (8). The Parhi–Nowak deep space composes vector-valued maps across dimensions d0,…,dLd_0,…,d_L (Parhi and Nowak 2022). The motivating work uses an O(Lw2)O(Lw^2) parameter count, while its displayed base-block formula does not explicitly display these dimensions (Ganguli and Constantinescu 2026). Throughout this paper, all class inclusions refer to the explicit architecture d0=dL=1,dℓ≤w,Kℓ≤w.d_0=d_L=1, d_ ≤ w, K_ ≤ w. A.2 Exact parameter count A block with input dimension d, output dimension D′D , and K atoms has D′K+Kd+K+D′d+D′D K+Kd+K+D d+D scalar parameters. If d,D′,K≤wd,D ,K≤ w, this is at most 3w2+2w3w^2+2w. Hence Wpar≤L(3w2+2w).W_ par≤ L(3w^2+2w). (50) A.3 Proof of Lemma 9 For each block, compute the K preactivations wk⊤x−bkw_k x-b_k in one affine stage, apply K ReLUs, and compute ∑kvkρ(⋅)+Cx+c0 _kv_kρ(·)+Cx+c_0 in a second affine stage. The skip CxCx is carried in parallel through the same block and adds no nonlinear depth. Thus an L-block composition is a piecewise-linear computation graph with at most the parameters in (50), at most LwLw ReLU gates, and computational depth at most 2L2L. If a theorem is stated for ordinary feed-forward ReLU networks without affine skips, represent a scalar u by (ρ(u),ρ(−u))(ρ(u),ρ(-u)) and propagate both signs. This converts every affine skip into a constant-factor larger ReLU graph, preserving O(Lw2)O(Lw^2) parameters and O(L)O(L) computational depth. The finitely many choices of dimensions and atom counts are all subarchitectures of the maximal padded graph, obtained by setting unused parameters to zero. The piecewise-linear pseudodimension bound of Bartlett et al. 2019, applied to this maximal graph, gives Pdim≤CWparLlog(2Wpar)≤CL2w2log(2Lw).Pdim≤ CW_ parL (2W_ par)≤ CL^2w^2 (2Lw). The layer-cost and output constraints only restrict the graph class and cannot increase pseudodimension. A.4 Circle coordinate and representation cost The coordinate t∈[0,2)t∈[0,2) is the motivating coordinate t=θ/πt=θ/π with normalized measure dt/2\,dt/2. The tent map (34) satisfies r(0)=r(2)=0r(0)=r(2)=0, so the packed functions periodize continuously. The infimum (10) is generally not one-homogeneous as a functional of the composed map: a scalar gain can be distributed across D stages at cost proportional to Dq1/DDq^1/D. Accordingly, all arguments use only the representation-cost definition. Appendix B A bias-corrected bounded-coefficient approximation theorem This appendix proves Theorem 2. The bit decoder and approximation estimates are imported from the constructive proof of Ou et al. 2024. The coefficient-scaling steps needed to pass from that construction to the unit-coefficient theorem are rederived below under the affine-layer convention (13). B.1 The affine-bias obstruction and its repair Uniformly multiplying every affine pair (Aℓ,bℓ)(A_ ,b_ ) by a>0a>0 scales homogeneous terms and biases by different powers across depth. For example, the depth-two realization N(x)=ρ(x)+1N(x)=ρ(x)+1 becomes a2ρ(x)+a^2ρ(x)+a, not a2N(x)a^2N(x). The last-layer bias receives only one factor of a. A constant homogeneous coordinate repairs this mismatch. Lemma 10 (Homogeneous lift). Let B≥1B≥ 1 and let N∈(W,D,B)N (W,D,B) have exact depth D≥2D≥ 2. For every q>0q>0, qN∈(W+1,D,Bq1/D).qN (W+1,D,Bq^1/D). (51) Proof. Put s=q1/Ds=q^1/D and write the hidden states as in (13). Define h~1=ρ([sA10]x+[sb1s])=[sh1s], h_1=ρ\! ( bmatrixsA_1\\ 0 bmatrixx+ bmatrixsb_1\\ s bmatrix )= bmatrixsh_1\\ s bmatrix, (52) and, for 2≤ℓ<D2≤ <D, h~ℓ=ρ([sAℓsbℓ0s]h~ℓ−1). h_ =ρ\! ( bmatrixsA_ &sb_ \\ 0&s bmatrix h_ -1 ). (53) Induction gives h~ℓ=(sℓhℓ,sℓ) h_ =(s h_ ,s ). The final affine map is N~(x)=[sADsbD]h~D−1=sD(ADhD−1+bD)=qN(x). N(x)= bmatrixsA_D&sb_D bmatrix h_D-1=s^D(A_Dh_D-1+b_D)=qN(x). (54) The width increases by one. Every old coefficient is multiplied by s, and the only new nonzero coefficient is s; since B≥1B≥ 1, the new coefficient magnitude is at most sBsB. ∎ B.2 Trading coefficient magnitude for depth We next use a unit-coefficient fan-out construction. Lemma 11 (Unit-coefficient fan-out). Let W≥2W≥ 2, let N∈(W,D,1)N (W,D,1), and let J≥0J≥ 0. Put r=⌊W/2⌋r= W/2 . Then rJN∈(W,D+J,1).r^JN (W,D+J,1). (55) Proof. The case J=0J=0 is immediate. For J≥1J≥ 1, pad the input realization to exact depth D and write its scalar output as y=ADhD−1+bDy=A_Dh_D-1+b_D. Replace this final affine map by the hidden vector u1=(ρ(y)r,ρ(−y)r)∈ℝ2r.u_1=(ρ(y)1_r,ρ(-y)1_r) ^2r. For each of the next J−1J-1 hidden layers, apply diag(r×r,r×r)diag(1_r× r,1_r× r) with zero bias. The final row (r⊤,−r⊤)(1_r ,-1_r ) returns rJ(ρ(y)−ρ(−y))=rJyr^J(ρ(y)-ρ(-y))=r^Jy. All coefficients belong to −1,0,1\-1,0,1\ and 2r≤W2r≤ W. ∎ Corollary 12 (Bias-correct depth–coefficient conversion). Let W≥4W≥ 4, D≥2D≥ 2, and B≥1B≥ 1. Put r=⌊W+12⌋,J=⌈DlogBlogr⌉,r= W+12 , J= D B r , (56) with J=0J=0 when B=1B=1. Then (W,D,B)⊆(W+1,D+J,1).N(W,D,B) (W+1,D+J,1). (57) If B=WKB=W^K for fixed K, then J≤2KD+1J≤ 2KD+1. Proof. For N∈(W,D,B)N (W,D,B), Lemma 10 with q=B−Dq=B^-D gives B−DN∈(W+1,D,1)B^-DN (W+1,D,1). Apply Lemma 11 at width W+1W+1 to obtain rJB−DNr^JB^-DN. Since rJ≥BDr^J≥ B^D, multiplying the final affine map by BD/rJ≤1B^D/r^J≤ 1 recovers N without violating the unit coefficient bound. Finally, r2≥Wr^2≥ W for W≥4W≥ 4, so logr≥12logW r≥ 12 W and the stated bound on J follows. ∎ B.3 Repairing the bounded-spline realization For a strictly increasing breakpoint sequence X=(xi)i=0MX−1⊂[0,1]X=(x_i)_i=0^M_X-1⊂[0,1], let Σ(X,E) (X,E) denote the continuous functions that are constant outside [x0,xMX−1][x_0,x_M_X-1], affine between consecutive breakpoints, and bounded in absolute value by E. Put Rm(X)=max1≤i≤MX−1(xi−xi−1)−1.R_m(X)= _1≤ i≤ M_X-1(x_i-x_i-1)^-1. The direct construction of Ou et al. 2024, which is independent of the bias-sensitive layerwise scaling identity discussed above, implies that whenever u2v≥MXu^2v≥ M_X, Σ(X,1CkMX6Rm(X)4)⊆(20u,30v,1), \! (X, 1C_kM_X^6R_m(X)^4 ) (20u,30v,1), (58) where 2≤Ck≤1052≤ C_k≤ 10^5 is universal. Lemma 13 (Bias-correct bounded-spline realization). Assume u2v≥MXu^2v≥ M_X, v≥1v≥ 1, ws≥1w_s≥ 1, and ws30v≥MX6Rm(X)4E.w_s^30v≥ M_X^6R_m(X)^4E. (59) Then Σ(X,E)⊆(20u+1,30v,2ws). (X,E) (20u+1,30v,2w_s). (60) Proof. For f∈Σ(X,E)f∈ (X,E), set f0=(2ws)−30vf_0=(2w_s)^-30vf. By (59) and 230v≥230>105≥Ck2^30v≥ 2^30>10^5≥ C_k, ‖f0‖∞≤1CkMX6Rm(X)4. f_0 _∞≤ 1C_kM_X^6R_m(X)^4. Thus f0f_0 belongs to the left side of (58). Lemma 10, with q=(2ws)30vq=(2w_s)^30v, realizes (2ws)30vf0=f(2w_s)^30vf_0=f at the same depth, width at most 20u+120u+1, and coefficient magnitude at most 2ws2w_s. ∎ B.4 Width and depth bookkeeping The remaining decoder identities and approximation estimates in Ou et al. 2024 are explicit and independent of the bias-sensitive affine scaling discussed above. Its bounded-spline proposition is called exactly twice, at equations (144) and (161) of the cited proof. Replacing those calls by Lemma 13 changes the two spline widths from 40m40m and 40n40n to 40m+140m+1 and 40n+140n+1, while preserving the realized functions, depths, and coefficient bounds. The resulting additive width changes fit inside the slack of the original construction. In its first stage, the corrected parallelization and affine-combination bounds give width(f1)≤200m+2n+5+5.width(f_1)≤ 200m+2^n+5+5. In the second stage, width(u)≤max40m+1,40n+1+2.width(u)≤ \40m+1,40n+1\+2. For m,n≥2m,n≥ 2, the first display dominates the second, so the composition of f1f_1 with u retains the first width bound. Three parallel copies followed by the fixed median network have width at most 600m+3⋅2n+5+15≤600m+2n+7.600m+3· 2^n+5+15≤ 600m+2^n+7. Consequently the terminal architecture estimate of the cited bit-extraction proof remains valid without changing its asymptotic or stated width bound: Proposition 14 (Polynomial-coefficient approximation). There exist universal constants C,D1>0C,D_1>0 such that, for all integers W,U≥D1W,U≥ D_1 and every continuous g:[0,1]→ℝg:[0,1] with ‖g‖∞≤1 g _∞≤ 1 and Lip(g)≤1Lip(g)≤ 1, there is N∈(W,U,W2)N (W,U,W^2) satisfying ‖N−g‖∞≤CW2U2logW. N-g _∞≤ CW^2U^2 W. (61) Proof. The corrected construction just described yields, for integers m,n,ℓ≥2m,n, ≥ 2, width(N) (N) ≤600m+2n+7, ≤ 600m+2^n+7, depth(N) (N) ≤101ℓ, ≤ 101 , coeff(N) (N) ≤max8mn,3n+2, ≤ \8mn,3^n+2\, ‖N−g‖∞ N-g _∞ ≤3m2ℓ2n. ≤ 3m^2 ^2n. (62) Choose m=⌊W1000⌋,ℓ=⌊U101⌋,m= W1000 , = U101 , and let n≥2n≥ 2 be the largest integer such that 2n+7≤W/52^n+7≤ W/5. For sufficiently large W,UW,U, one has m≍Wm W, ℓ≍U U, and n≍logWn W. Moreover, 600m+2n+7≤45W,101ℓ≤U,600m+2^n+7≤ 45W, 101 ≤ U, and 8mn≤W2,3n+2≤W28mn≤ W^2, 3^n+2≤ W^2 for all sufficiently large W. Padding unused width and depth places the network in (W,U,W2)N(W,U,W^2). Substituting the parameter choices into (62) proves (61). ∎ B.5 Proof of Theorem 2 Let m,Dm,D be sufficiently large, set m¯=m−1 m=m-1, and put U=⌊D−15⌋.U= D-15 . Proposition 14 gives a network N0∈(m¯,U,m¯2)N_0 ( m,U, m^2) with error at most C/(m¯2U2logm¯)C/( m^2U^2 m). Apply Corollary 12. With r=⌊m/2⌋r= m/2 and r2≥m¯r^2≥ m for sufficiently large m, the additional depth obeys J=⌈Ulog(m¯2)logr⌉≤4U+1.J= U ( m^2) r ≤ 4U+1. Hence the same function has a unit-coefficient realization of width at most m and depth at most U+J≤5U+1≤DU+J≤ 5U+1≤ D. Since m¯≍m m m and U≍DU D, the error is at most Capp/(m2D2logm)C_ app/(m^2D^2 m), proving Theorem 2. The fine-scale bit decoder and its approximation estimate are taken from Ou et al. 2024. The coefficient-rescaling steps used to obtain the unit-coefficient realization have been rederived above under the affine-layer convention in (13). Appendix C The grid code and its local geometry Let M≥8M≥ 8. For z∈0,1M−1z∈\0,1\^M-1, set z0=zM=0z_0=z_M=0 and let hzh_z linearly interpolate (j/M,zj)(j/M,z_j). On Ij=[j/M,(j+1)/M]I_j=[j/M,(j+1)/M], writing u=Mx−ju=Mx-j and dj=zj−zj′d_j=z_j-z_j , we have hz(x)−hz′(x)=(1−u)dj+udj+1.h_z(x)-h_z (x)=(1-u)d_j+ud_j+1. Therefore ∫Ij(hz−hz′)2x _I_j(h_z-h_z )^2\,dx =1M∫01((1−u)dj+udj+1)2u = 1M _0^1((1-u)d_j+ud_j+1)^2\,du (63) =dj2+djdj+1+dj+123M. = d_j^2+d_jd_j+1+d_j+1^23M. (64) Since a2+ab+b2=12(a2+b2)+12(a+b)2a^2+ab+b^2= 12(a^2+b^2)+ 12(a+b)^2, summing and using d0=dM=0d_0=d_M=0 yields ‖hz−hz′‖22≥dH(z,z′)3M. h_z-h_z _2^2≥ d_H(z,z )3M. (65) The Varshamov–Gilbert bound (Tsybakov 2009) gives ⊆0,1M−1Z \0,1\^M-1 and universal cVG,cH>0c_ VG,c_H>0 with log||≥cVGM,dH(z,z′)≥cHM(z≠z′). |Z|≥ c_ VGM, d_H(z,z )≥ c_HM (z≠ z ). (66) Now gz=hz/Mg_z=h_z/M satisfies ‖gz‖∞≤1 g_z _∞≤ 1 and Lip(gz)≤1Lip(g_z)≤ 1. Theorem 2 gives NzN_z. With M=⌊c0m2D2logm⌋M= c_0m^2D^2 m and c0≤η/(2Capp)c_0≤η/(2C_ app), ‖Qz−hz‖∞=M‖Nz−gz‖∞≤η,Qz=MNz. Q_z-h_z _∞=M N_z-g_z _∞≤η, Q_z=MN_z. Thus, for fixed η<cH/3/4η< c_H/3/4, ‖Qz−Qz′‖2 Q_z-Q_z _2 ≥cH/3−2η, ≥ c_H/3-2η, ‖Qz−Qz′‖2 Q_z-Q_z _2 ≤1+2η,‖Qz‖∞≤1+η. ≤ 1+2η, Q_z _∞≤ 1+η. This proves (31) and locality after scaling by λ. Appendix D Balanced amplification for the statistical code Lemma 7 is the coefficient-one specialization of Lemma 10; we repeat the matrices to make the lower-bound dependency self-contained. D.1 Exact-depth padding If an approximating network has depth d<Dd<D, insert D−dD-d identity hidden layers immediately before the final affine map. The hidden state is nonnegative, hence h↦ρ(Ih)=h ρ(Ih)=h. These layers have coefficient magnitude one and do not increase width. D.2 Exact amplification matrices Write h1=ρ(A1x+b1),hℓ=ρ(Aℓhℓ−1+bℓ),N=ADhD−1+bD.h_1=ρ(A_1x+b_1), h_ =ρ(A_ h_ -1+b_ ), N=A_Dh_D-1+b_D. For q>0q>0, put s=q1/Ds=q^1/D and define h~1=ρ([sA10]x+[sb1s])=[sh1s], h_1=ρ\! ( bmatrixsA_1\\ 0 bmatrixx+ bmatrixsb_1\\ s bmatrix )= bmatrixsh_1\\ s bmatrix, (67) h~ℓ=ρ([sAℓsbℓ0s]h~ℓ−1)=[sℓhℓsℓ], h_ =ρ\! ( bmatrixsA_ &sb_ \\ 0&s bmatrix h_ -1 )= bmatrixs h_ \\ s bmatrix, (68) for 2≤ℓ<D2≤ <D, and N~=[sADsbD]h~D−1=sDN=qN. N= bmatrixsA_D&sb_D bmatrix h_D-1=s^DN=qN. (69) The width increases by one, depth is unchanged, and the coefficient bound is s, including when q<1q<1. Appendix E Translation into deep ℛBV2RBV^2 blocks E.1 Coordinatewise ReLU layers Let T(x)=ρ(Ax+b)T(x)=ρ(Ax+b), with rows ai⊤a_i of A. In the block notation (6), T(x)=∑i=1d′eiρ(ai⊤x−(−bi)),T(x)= _i=1^d e_iρ(a_i x-(-b_i)), so K=d′K=d and the variation term is ∑i=1d′‖ei‖1‖ai‖2=∑i=1d′‖ai‖2≤d′ds. _i=1^d e_i _1 a_i _2= _i=1^d a_i _2≤ d d\,s. For the anchor term, |Ti(0)|=|ρ(bi)|≤s|T_i(0)|=|ρ(b_i)|≤ s and, since ReLU is 11-Lipschitz, |Ti(ej)−Ti(0)|≤|aij|≤s.|T_i(e_j)-T_i(0)|≤|a_ij|≤ s. Hence ‖T‖ℛBV2(d,d′)≤d′ds+d′(d+1)s≤3w2s T _RBV^2(d;d )≤ d d\,s+d (d+1)s≤ 3w^2s for d,d′≤wd,d ≤ w and w≥1w≥ 1. For an affine map T(x)=Ax+bT(x)=Ax+b, take K=0K=0, C=AC=A, and c0=bc_0=b. Then ‖T‖ℛBV2(d,d′)=∑i=1d′(|bi|+∑j=1d|aij|)≤d′(d+1)s≤2w2s. T _RBV^2(d;d )= _i=1^d (|b_i|+ _j=1^d|a_ij| )≤ d (d+1)s≤ 2w^2s. Applying these estimates to the D−1D-1 hidden maps and final affine map in Appendix D proves D,m+1(qN)≤CtrD(m+1)2q1/D V_D,m+1(qN)≤ C_ trD(m+1)^2q^1/D with, for example, Ctr=3C_ tr=3 under the displayed conventions. E.2 Tent map and circle isometry The map r(t)=t−2ρ(t−1)r(t)=t-2ρ(t-1) is represented with one ReLU atom and one affine skip. Its norm is ‖r‖ℛBV2(1,1)=|−2||1|+|r(0)|+|r(1)−r(0)|=3. r _RBV^2(1;1)=|-2|\,|1|+|r(0)|+|r(1)-r(0)|=3. Thus one may take C0=3C_0=3. It satisfies r(t)=t(0≤t≤1),r(t)=2−t(1≤t≤2).r(t)=t (0≤ t≤ 1), r(t)=2-t (1≤ t≤ 2). For any measurable u:[0,1]→ℝu:[0,1] , ∫02|u(r(t))|2dt2 _0^2|u(r(t))|^2 \,dt2 =12∫01|u(t)|2t+12∫12|u(2−t)|2t = 12 _0^1|u(t)|^2\,dt+ 12 _1^2|u(2-t)|^2\,dt =∫01|u(x)|2x. = _0^1|u(x)|^2\,dx. This proves (36). Combining the tent block with the D translated blocks gives total depth D+1=LD+1=L and width at most m+1=wm+1=w. E.3 Membership of the packed functions For Fz=λMNz∘rF_z=λ MN_z r, Lemma 7 and the preceding block calculation give L,w(Fz)≤C0+CtrDw2(λM)1/D. V_L,w(F_z)≤ C_0+C_ trDw^2(λ M)^1/D. Also ‖Fz‖∞≤λ(1+η). F_z _∞≤λ(1+η). Therefore Fz∈L,w(A,B)F_z _L,w(A,B) whenever λ≤B1+η,λ≤1M((A−C0)+CtrDw2)D.λ≤ B1+η, λ≤ 1M ( (A-C_0)_+C_ trDw^2 )^D. (70) Universal constant losses in these inequalities are absorbed by cλc_λ in (41). Appendix F Fano proof of the lower bound Let Z be the code from Appendix C, and define FzF_z by (35). There are universal constants a0,a1,a2>0a_0,a_1,a_2>0 such that log||≥a0M,a1λ≤‖Fz−Fz′‖2≤a2λ,‖Fz‖2≤a2λ. |Z|≥ a_0M, a_1λ≤ F_z-F_z _2≤ a_2λ, F_z _2≤ a_2λ. (71) Choose λ=cλminB,σMn,1M((A−C0)+CtrDw2)D,λ=c_λ \B,σ Mn, 1M ( (A-C_0)_+C_ trDw^2 )^D \, where cλc_λ is sufficiently small for (70). Under the n-sample law Pz(n)P_z^(n), the design law is common and the conditional responses are independent Gaussians of variance σ2σ^2. Hence DKL(Pz(n)∥Pz′(n)) D_KL(P_z^(n)\|P_z ^(n)) =nTDKL(N(Fz(T),σ2)∥N(Fz′(T),σ2)) =nE_TD_KL\! (N(F_z(T),σ^2)\|N(F_z (T),σ^2) ) (72) =n2σ2‖Fz−Fz′‖22≤a22cλ22M. = n2σ^2 F_z-F_z _2^2≤ a_2^2c_λ^22M. (73) Choose cλc_λ so the last term is at most (1/16)log||(1/16) |Z|. With the uniform prior, mutual information is bounded by the average pairwise divergence, and Fano’s inequality (Tsybakov 2009) gives a universal lower bound on the worst-case codeword error probability. Given an arbitrary estimator f f, decode by nearest neighbor in L2(μ)L^2(μ). Whenever ‖f^−Fz‖2<a1λ/2 f-F_z _2<a_1λ/2, the decoded index is z. Markov’s inequality therefore yields supz∈z‖f^−Fz‖22≥cλ2. _z E_z f-F_z _2^2≥ cλ^2. Taking the infimum over estimators proves Theorem 3. F.1 The sample-size-dependent radius corollary Fix constants 0<cσ≤Cσ<∞0<c_σ≤ C_σ<∞, and let A=B=RA=B=R, cσR≤σ≤CσRc_σR≤σ≤ C_σR, n≥Mn≥ M, and R≥2C0R≥ 2C_0. The output cap is at least a constant multiple of RM/nR M/n. Further, λrep≥1M(R2CtrDw2)D. _ rep≥ 1M ( R2C_ trDw^2 )^D. Condition (17), with CradC_ rad sufficiently large inside the base of the DDth power, implies λrep≥cRM/n _ rep≥ cR M/n. Therefore λ2≍R2M/nλ^2 R^2M/n and ℜn∗(R,R,σ)≥cR2M/n. R_n^*(R,R,σ)≥ cR^2M/n. For L,wL,w above absolute thresholds, D=L−1D=L-1, m=w−1m=w-1, and (15) imply M≥cL2w2logwM≥ cL^2w^2 w. This proves Corollary 4. Since M3/2/n≤M^3/2/ n≤ M for every n≥Mn≥ M, condition (19) is sufficient uniformly over that sample-size range. Taking (D−1)(D-1)st roots gives (20). Appendix G Proof of the Gaussian upper bound G.1 Pseudodimension and covering numbers The computation graph described in Appendix A has Wpar=O(Lw2)W_ par=O(Lw^2) real parameters, O(Lw)O(Lw) piecewise-linear units, and computational depth O(L)O(L). The piecewise-linear network theorem of Bartlett et al. 2019 therefore yields Pdim(L,w(A,B))≤CWparLlog(2Wpar)≤CL2w2log(2Lw).Pdim(C_L,w(A,B))≤ CW_ parL (2W_ par)≤ CL^2w^2 (2Lw). (74) The norm and output constraints only restrict the unconstrained architecture and hence cannot increase pseudodimension. A standard pseudodimension covering theorem (Haussler 1992; Anthony and Bartlett 1999) states that for every probability measure P and every [−B,B][-B,B]-valued class of pseudodimension at most V, logN(ε,ℱ,L2(P))≤CVlogCBε,0<ε≤B. N( ,F,L^2(P))≤ CV CB , 0< ≤ B. (75) G.2 A finite-class Gaussian oracle inequality Lemma 15. Let G be a finite class of functions g:→[−B,B]g:X→[-B,B], and suppose Y=f⋆(X)+ξY=f (X)+ξ with |f⋆|≤B|f |≤ B and ξ∼N(0,σ2)ξ N(0,σ^2) independent of X. Let g^∈argming∈1n∑i=1n(Yi−g(Xi))2. g∈ _g 1n _i=1^n(Y_i-g(X_i))^2. Then ‖g^−f⋆‖L2(PX)2≤Cinfg∈‖g−f⋆‖L2(PX)2+C(σ2+B2)log(2||)n.E g-f _L^2(P_X)^2≤ C _g g-f _L^2(P_X)^2+C (σ^2+B^2) (2|G|)n. (76) Proof. For g∈g , put dg=g−f⋆d_g=g-f , rg=Pdg2r_g=Pd_g^2, and Zi(g)=dg(Xi)2−2ξidg(Xi),Zn(g)=1n∑i=1nZi(g).Z_i(g)=d_g(X_i)^2-2 _id_g(X_i), Z_n(g)= 1n _i=1^nZ_i(g). Then Zi(g)=rgEZ_i(g)=r_g, and empirical risk minimization implies Zn(g^)≤Zn(g)Z_n( g)≤ Z_n(g) for every g∈g . Because |dg|≤2B|d_g|≤ 2B, the centered random variable Zi(g)−rgZ_i(g)-r_g is sub-exponential with Bernstein variance proxy νg2≤C(σ2+B2)rg _g^2≤ C(σ^2+B^2)r_g (77) and scale at most C(σB+B2)C(σ B+B^2). To see (77), use dg4≤4B2rgEd_g^4≤ 4B^2r_g for the design term and (2ξdg)2=4σ2rgE(2ξ d_g)^2=4σ^2r_g for the multiplier term. The Gaussian conditional moment-generating function, together with |dg|≤2B|d_g|≤ 2B, gives the corresponding sub-exponential scale. Bernstein’s inequality and 2uv≤u/2+2v2 uv≤ u/2+2v imply that, for each u>0u>0, with probability at least 1−2e−u1-2e^-u, 12rg−Caun≤Zn(g)≤32rg+Caun,a=σ2+B2. 12r_g-Ca un≤ Z_n(g)≤ 32r_g+Ca un, a=σ^2+B^2. (78) Increasing C absorbs the scale term because σB+B2≤C(σ2+B2)=Caσ B+B^2≤ C(σ^2+B^2)=Ca. Apply the lower inequality in (78) simultaneously to every g∈g with u=t+log(2||)u=t+ (2|G|), and apply the upper inequality to a fixed comparator g0g_0 with u=tu=t. With probability at least 1−3e−t1-3e^-t, 12rg 12r_ g ≤Zn(g^)+Cat+log(2||)n ≤ Z_n( g)+Ca t+ (2|G|)n ≤Zn(g0)+Cat+log(2||)n ≤ Z_n(g_0)+Ca t+ (2|G|)n ≤32rg0+Ca2t+log(2||)n. ≤ 32r_g_0+Ca 2t+ (2|G|)n. Thus rg^≤3rg0+Ca2t+log(2||)n.r_ g≤ 3r_g_0+Ca 2t+ (2|G|)n. Integrating the exponential tail over t≥0t≥ 0 and minimizing over g0g_0 proves (76). ∎ G.3 Completion of Theorem 5 Let V denote the right-hand side of (74). If (σ2+B2)V/n≥B2(σ^2+B^2)V/n≥ B^2, the zero estimator has risk at most B2B^2, proving the first branch of (21). Otherwise set ε2=(σ2+B2)Vn<B2 ^2= (σ^2+B^2)Vn<B^2 and let G be an ε -net in L2(μ)L^2(μ). By (75), log||≤CVlogCBε≤CVlog(en), |G|≤ CV CB ≤ CV (en), where the last inequality uses ε2≥B2V/n ^2≥ B^2V/n and V≥1V≥ 1. Lemma 15 gives ℜn∗(A,B,σ)≤Cε2+C(σ2+B2)Vlog(en)n≤C(σ2+B2)Vlog(en)n. R_n^*(A,B,σ)≤ C ^2+C (σ^2+B^2)V (en)n≤ C (σ^2+B^2)V (en)n. Substitute (74) to obtain Theorem 5. Appendix H Radius geometry and phase regimes The lower bound is governed by λout=B,λstat=σM/n,λrep=1M((A−C0)+CtrDw2)D. _ out=B, _ stat=σ M/n, _ rep= 1M ( (A-C_0)_+C_ trDw^2 )^D. H.1 The sample-size-dependent statistical regime Fix constants 0<cσ≤Cσ<∞0<c_σ≤ C_σ<∞, and let A=B=RA=B=R, cσR≤σ≤CσRc_σR≤σ≤ C_σR, R≥2C0R≥ 2C_0, and n≥Mn≥ M. Since R−C0≥R/2R-C_0≥ R/2, λrep≥1M(R2CtrDw2)D. _ rep≥ 1M ( R2C_ trDw^2 )^D. A sufficient condition for λrep≥cRM/n _ rep≥ cR M/n is RD−1≥(CradDw2)DM3/2n,R^D-1≥(C_ radDw^2)^D M^3/2 n, (79) where the base constant CradC_ rad absorbs 2Ctr2C_ tr and the fixed noise-comparison constants. This proves Corollary 4. For a condition valid simultaneously for every n≥Mn≥ M, use M3/2/n≤M^3/2/ n≤ M, obtaining (19). Taking (D−1)(D-1)st roots yields (20). H.2 Representation-limited behavior When A is small, the present code gives ℜn∗≳1M2((A−C0)+CtrDw2)2D. R_n^* 1M^2 ( (A-C_0)_+C_ trDw^2 )^2D. By the block Lipschitz estimate of Parhi and Nowak 2022, Lip(f)≤∏ℓ=1L‖sℓ‖ℛBV2≤(A/L)L.Lip(f)≤ _ =1^L s_ _RBV^2≤(A/L)^L. Thus small A/LA/L can collapse the class exponentially in depth, showing that a radius condition is structural rather than merely technical.