Depth Enables Local Entropy: Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression

# Depth Enables Local Entropy:Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression
Source: [https://arxiv.org/html/2608.17434](https://arxiv.org/html/2608.17434)
Minbo GaoShaowei CaiAffiliation:Key Laboratory of System Software \(Chinese Academy of Sciences\)Affiliation:State Key Laboratory of Computer ScienceAffiliation:Institute of Software, Chinese Academy of SciencesAffiliation:School of Computer Science and Technology, University of Chinese Academy of SciencesAffiliation:Beijing, ChinaEmail:[\{jiangt,gaomb,caisw\}@ios\.ac\.cn](mailto:)

###### Abstract

We study Gaussian regression over the explicit vector\-valued Parhi–Nowak deep\-ℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{2\}architecture with depthLL, widthww, layer\-sum variation budgetAA, and output boundBB\. For thisO⁡\(L​w2\)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Ω⁡\(L2​w2​log⁡w\)\\Omega\(L^\{2\}w^\{2\}\\log w\); its codewords lie in anO⁡\(λ\)O\(\\lambda\)L2L^\{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\-DDReLU network byqqcan be implemented using one constant channel so that every coefficient grows by onlyq1/Dq^\{1/D\}\. Translation to vector\-valuedℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{2\}blocks then has layer\-sum costO⁡\(D​w2​q1/D\)O\(Dw^\{2\}q^\{1/D\}\)\. Gaussian Fano yields a radius\-explicit lower bound governed by the output, testing, and representation scales\. UnderA=B=RA=B=R,σ≍R\\sigma\\asymp R, and the stated radius condition, this gives

ℜn∗≳L2​w2​log⁡w​R2n\.\\mathfrak\{R\}\_\{n\}^\{\*\}\\gtrsim\\frac\{L^\{2\}w^\{2\}\\log w\\,R^\{2\}\}\{n\}\.A pseudodimension\-based finite\-net upper bound givesO~​\(L2​w2​R2/n\)\\widetilde\{O\}\(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\.

## 1Introduction

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](https://arxiv.org/html/2608.17434#bib.bib22);[Yarotsky 2017](https://arxiv.org/html/2608.17434#bib.bib25);[Yarotsky 2018](https://arxiv.org/html/2608.17434#bib.bib26)\)\. 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](https://arxiv.org/html/2608.17434#bib.bib6)isolate this issue for a deep variation\-space architecture on the circle\. Under theO⁡\(L​w2\)O\(Lw^\{2\}\)parameterization used there, their bounds have the schematic form

Ω⁡\(L​w2​R2n\)≤ℜn∗≤O~​\(L2​w2​R2n\)\.\\Omega\\\!\\left\(\\frac\{Lw^\{2\}R^\{2\}\}\{n\}\\right\)\\;\\leq\\;\\mathfrak\{R\}\_\{n\}^\{\*\}\\;\\leq\\;\\widetilde\{O\}\\\!\\left\(\\frac\{L^\{2\}w^\{2\}R^\{2\}\}\{n\}\\right\)\.\(1\)The displayed base\-block formula in that work does not explicitly display the intermediate dimensions, while the cited Parhi–Nowak construction and theO⁡\(L​w2\)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\_\{\\ell\}\\leq w, and each compositional block has hidden width at mostww\.

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](https://arxiv.org/html/2608.17434#bib.bib3);[Bach 2017](https://arxiv.org/html/2608.17434#bib.bib2)\)\. Exact descriptions of bounded\-norm ReLU networks subsequently connected such norms to spline and Radon\-domain variation spaces\([Savarese et al\. 2019](https://arxiv.org/html/2608.17434#bib.bib17);[Ongie et al\. 2020](https://arxiv.org/html/2608.17434#bib.bib10);[Parhi and Nowak 2021](https://arxiv.org/html/2608.17434#bib.bib13)\)\. The deep compositional and vector\-valued extensions developed in[Parhi and Nowak 2022](https://arxiv.org/html/2608.17434#bib.bib14);[Parhi and Nowak 2026](https://arxiv.org/html/2608.17434#bib.bib16)and[Shenouda et al\. 2024](https://arxiv.org/html/2608.17434#bib.bib19)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⁡\|𝒵\|=Ω⁡\(L2​w2​log⁡w\)\.\\log\|\\mathcal\{Z\}\|=\\Omega\(L^\{2\}w^\{2\}\\log w\)\.The code begins with bounded\-coefficient bit extraction\. A width\-mm, depth\-DDReLU network can approximate every bounded11\-Lipschitz function on\[0,1\]\[0,1\]to accuracy

O⁡\(\(m2​D2​log⁡m\)−1\)O\\\!\\left\(\(m^\{2\}D^\{2\}\\log m\)^\{\-1\}\\right\)\(2\)while keeping every matrix and bias entry bounded by one\. The construction originates in[Ou et al\. 2024](https://arxiv.org/html/2608.17434#bib.bib12)\. 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](https://arxiv.org/html/2608.17434#S1.E2)\) up to universal constants\.

The same augmented\-state idea yields our key architectural lemma\. IfNNhas depthDD, thenq​NqNhas the same depth and one additional hidden coordinate, with coefficient magnitude onlyq1/Dq^\{1/D\}\. A coefficient\-ssfully connected layer has vector\-valuedℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{2\}costO⁡\(w2​s\)O\(w^\{2\}s\), hence

𝔙D,w​\(q​N\)≲D​w2​q1/D\.\\mathfrak\{V\}\_\{D,w\}\(qN\)\\lesssim Dw^\{2\}q^\{1/D\}\.\(3\)This converts the1/M1/Mlabel scale of a bit\-extraction code into a statistical margin without payingMMin 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λ\\lambdais chosen, every codeword hasL2L^\{2\}normO⁡\(λ\)O\(\\lambda\), distinct codewords areΩ⁡\(λ\)\\Omega\(\\lambda\)apart, and all codewords remain in the prescribed deep\-ℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{2\}ball\. Tight covering\-number bounds for ordinary bounded\-weight fully connected ReLU networks already show global entropy of order

W2​D​log⁡\(\(W\+1\)D​BDε\),W^\{2\}D\\log\\\!\\left\(\\frac\{\(W\+1\)^\{D\}B^\{D\}\}\{\\varepsilon\}\\right\),which is quadratic inDDat fixedB=1B=1and fixed accuracy\([Ou and Bölcskei 2026](https://arxiv.org/html/2608.17434#bib.bib11)\)\. 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](https://arxiv.org/html/2608.17434#bib.bib18);[Suzuki 2019](https://arxiv.org/html/2608.17434#bib.bib21);[Parhi and Nowak 2023](https://arxiv.org/html/2608.17434#bib.bib15)\)\. Classical entropy methods connect packing and covering numbers to minimax risk\([Yang and Barron 1999](https://arxiv.org/html/2608.17434#bib.bib24);[Tsybakov 2009](https://arxiv.org/html/2608.17434#bib.bib23)\), while localized complexity theory emphasizes the geometry near the testing scale\([Bartlett et al\. 2005](https://arxiv.org/html/2608.17434#bib.bib4)\)\. Sharp metric\-entropy results for shallow neural variation spaces provide a close comparison\([Siegel and Xu 2024](https://arxiv.org/html/2608.17434#bib.bib20)\)\.

#### Contributions\.

1. 1\.We give a bias\-corrected derivation of the unit\-coefficient approximation rate \([2](https://arxiv.org/html/2608.17434#S1.E2)\)\. The new homogeneous\-lift lemma handles all biases exactly and replaces the two bias\-sensitive scaling steps used in the approximation argument\.
2. 2\.We construct a local packing of sizeexp⁡\(Ω⁡\(M\)\)\\exp\(\\Omega\(M\)\), withM=Θ⁡\(L2​w2​log⁡w\)M=\\Theta\(L^\{2\}w^\{2\}\\log w\), inside the explicit vector\-valued deep\-ℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{2\}architecture\.
3. 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\-nncondition\.
4. 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](https://arxiv.org/html/2608.17434#S2)–[3](https://arxiv.org/html/2608.17434#S3)give the model and theorems\. Section[4](https://arxiv.org/html/2608.17434#S4)locates the second depth sum\. Sections[5](https://arxiv.org/html/2608.17434#S5)–[7](https://arxiv.org/html/2608.17434#S7)construct the packing and prove the lower bound\. Section[8](https://arxiv.org/html/2608.17434#S8)proves the Gaussian upper bound\. The appendices contain the corrected approximation reduction and complete technical proofs\.

## 2Statistical and function\-class setting

#### Circle and risk\.

Identify the circle witht∈\[0,2\)t\\in\[0,2\)under normalized uniform measureμ⁡\(d​t\)=d​t/2\\mu\(\\,\\mathrm\{d\}t\)=\\,\\mathrm\{d\}t/2\. We observe

Ti∼μ,Yi=f⋆​\(Ti\)\+ξi,ξi∼N⁡\(0,σ2\),T\_\{i\}\\sim\\mu,\\qquad Y\_\{i\}=f^\{\\star\}\(T\_\{i\}\)\+\\xi\_\{i\},\\qquad\\xi\_\{i\}\\sim N\(0,\\sigma^\{2\}\),\(4\)independently\. For a classℱ\\mathcal\{F\},

ℜn∗​\(ℱ,σ\)≔inff^supf⋆∈ℱ𝔼f⋆​‖f^−f⋆‖L2​\(μ\)2\.\\mathfrak\{R\}\_\{n\}^\{\*\}\(\\mathcal\{F\},\\sigma\)\\coloneqq\\inf\_\{\\widehat\{f\}\}\\sup\_\{f^\{\\star\}\\in\\mathcal\{F\}\}\\mathbb\{E\}\_\{f^\{\\star\}\}\\left\\lVert\\widehat\{f\}\-f^\{\\star\}\\right\\rVert\_\{L^\{2\}\(\\mu\)\}^\{2\}\.\(5\)

#### Vector\-valued blocks\.

Fors:ℝd→ℝD′s:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{D^\{\\prime\}\}of the form

s⁡\(x\)=∑k=1Kvk​ρ​\(wk⊤​x−bk\)\+C​x\+c0,s\(x\)=\\sum\_\{k=1\}^\{K\}v\_\{k\}\\rho\(w\_\{k\}^\{\\top\}x\-b\_\{k\}\)\+Cx\+c\_\{0\},\(6\)we use the Parhi–Nowak norm

‖s‖ℛ​BV2​\(d,D′\)\\displaystyle\\left\\lVert s\\right\\rVert\_\{\\mathcal\{R\}\\mathrm\{BV\}^\{2\}\(d;D^\{\\prime\}\)\}≔∑k=1K‖vk‖1​‖wk‖2\\displaystyle\\coloneqq\\sum\_\{k=1\}^\{K\}\\left\\lVert v\_\{k\}\\right\\rVert\_\{1\}\\left\\lVert w\_\{k\}\\right\\rVert\_\{2\}\(7\)\+∑j=1D′\(\|sj\(0\)\|\+∑r=1d\|sj\(er\)−sj\(0\)\|\)\.\\displaystyle\\quad\+\\sum\_\{j=1\}^\{D^\{\\prime\}\}\\left\(\|s\_\{j\}\(0\)\|\+\\sum\_\{r=1\}^\{d\}\|s\_\{j\}\(e\_\{r\}\)\-s\_\{j\}\(0\)\|\\right\)\.\(8\)This is the vector\-valued Radon\-domain variation\-space convention of[Parhi and Nowak 2022](https://arxiv.org/html/2608.17434#bib.bib14), consistent with the multi\-output variation\-space framework of[Shenouda et al\. 2024](https://arxiv.org/html/2608.17434#bib.bib19)\.

#### Deep architecture\.

Fix

d0=dL=1,1≤dℓ≤w\(1≤ℓ<L\),d\_\{0\}=d\_\{L\}=1,\\qquad 1\\leq d\_\{\\ell\}\\leq w\\quad\(1\\leq\\ell<L\),\(9\)and blockssℓ:ℝdℓ−1→ℝdℓs\_\{\\ell\}:\\mathbb\{R\}^\{d\_\{\\ell\-1\}\}\\to\\mathbb\{R\}^\{d\_\{\\ell\}\}of the form \([6](https://arxiv.org/html/2608.17434#S2.E6)\), withKℓ≤wK\_\{\\ell\}\\leq w\. Define the layer\-sum representation cost

𝔙L,w\(f\)≔inff=sL∘⋯∘s1∑ℓ=1L‖sℓ‖ℛ​BV2​\(dℓ−1,dℓ\),\\mathfrak\{V\}\_\{L,w\}\(f\)\\coloneqq\\inf\_\{f=s\_\{L\}\\circ\\cdots\\circ s\_\{1\}\}\\sum\_\{\\ell=1\}^\{L\}\\left\\lVert s\_\{\\ell\}\\right\\rVert\_\{\\mathcal\{R\}\\mathrm\{BV\}^\{2\}\(d\_\{\\ell\-1\};d\_\{\\ell\}\)\},\(10\)where the infimum is over \([9](https://arxiv.org/html/2608.17434#S2.E9)\) andKℓ≤wK\_\{\\ell\}\\leq w\. We refer to \([10](https://arxiv.org/html/2608.17434#S2.E10)\) 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\)\.

ForA,B\>0A,B\>0, let

𝒞L,w\(A,B\)≔\{f:\[0,2\)→ℝ:𝔙L,w\(f\)≤A,‖f‖∞≤B\},\\mathcal\{C\}\_\{L,w\}\(A,B\)\\coloneqq\\left\\\{f:\[0,2\)\\to\\mathbb\{R\}:\\mathfrak\{V\}\_\{L,w\}\(f\)\\leq A,\\ \\left\\lVert f\\right\\rVert\_\{\\infty\}\\leq B\\right\\\},\(11\)with continuous endpoint identification when periodized\. Writeℜn∗​\(A,B,σ\)=ℜn∗​\(𝒞L,w​\(A,B\),σ\)\\mathfrak\{R\}\_\{n\}^\{\*\}\(A,B,\\sigma\)=\\mathfrak\{R\}\_\{n\}^\{\*\}\(\\mathcal\{C\}\_\{L,w\}\(A,B\),\\sigma\)\. The motivating normalization isA=B=RA=B=Randσ≍R\\sigma\\asymp R\.

A block containsO⁡\(w2\)O\(w^\{2\}\)scalar parameters, so the architecture has

Wpar=O⁡\(L​w2\)\.W\_\{\\rm par\}=O\(Lw^\{2\}\)\.\(12\)Appendix[A](https://arxiv.org/html/2608.17434#A1)gives the exact count and a formal computation\-graph realization\.

#### Standard\-network convention\.

Let𝒩⁡\(W,D,B\)\\mathcal\{N\}\(W,D,B\)denote scalar\-output realizations

hℓ=ρ⁡\(Aℓ​hℓ−1\+bℓ\),1≤ℓ<D,N⁡\(x\)=AD​hD−1\+bD,h\_\{\\ell\}=\\rho\(A\_\{\\ell\}h\_\{\\ell\-1\}\+b\_\{\\ell\}\),\\quad 1\\leq\\ell<D,\\qquad N\(x\)=A\_\{D\}h\_\{D\-1\}\+b\_\{D\},\(13\)with hidden width at mostWWand every matrix and bias entry bounded byBBin absolute value\. Depth counts affine maps, including the final affine output layer\. This is the convention used in the bounded\-coefficient approximation result\.

## 3Main results

We first record the approximation input in the corrected form used below\.

###### Theorem 2\(Bias\-corrected bounded\-coefficient approximation\)\.

There exist universal constantsCapp,D0\>0C\_\{\\rm app\},D\_\{0\}\>0such that, for all integersm,D≥D0m,D\\geq D\_\{0\}and every continuousg:\[0,1\]→ℝg:\[0,1\]\\to\\mathbb\{R\}satisfying‖g‖∞≤1\\left\\lVert g\\right\\rVert\_\{\\infty\}\\leq 1andLip⁡\(g\)≤1\\operatorname\{Lip\}\(g\)\\leq 1, there isN∈𝒩⁡\(m,D,1\)N\\in\\mathcal\{N\}\(m,D,1\)with

‖N−g‖L∞​\(\[0,1\]\)≤Cappm2​D2​log⁡m\.\\left\\lVert N\-g\\right\\rVert\_\{L^\{\\infty\}\(\[0,1\]\)\}\\leq\\frac\{C\_\{\\rm app\}\}\{m^\{2\}D^\{2\}\\log m\}\.\(14\)

The bit\-extraction construction is due to[Ou et al\. 2024](https://arxiv.org/html/2608.17434#bib.bib12)\. Appendix[B](https://arxiv.org/html/2608.17434#A2)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 approximantN∈𝒩⁡\(W,D,B\)N\\in\\mathcal\{N\}\(W,D,B\), a homogeneous lift augments each hidden state by one constant coordinate and realizesB−D​NB^\{\-D\}Nwith unit coefficients\. A width\-\(W\+1\)\(W\+1\)fan\-out construction then trades coefficient magnitude for additional depth, restoring the output amplitude usingJ=⌈D​log⁡B/log⁡⌊\(W\+1\)/2⌋⌉J=\\lceil D\\log B/\\log\\lfloor\(W\+1\)/2\\rfloor\\rceiladditional layers\. In the required caseB=W2B=W^\{2\}, one hasJ=O⁡\(D\)J=O\(D\); replacing the two bias\-sensitive spline\-scaling calls by this construction preserves the width/depth asymptotics and yields \([14](https://arxiv.org/html/2608.17434#S3.E14)\)\.

Let

D=L−1,m=w−1,M=⌊c0​m2​D2​log⁡m⌋,D=L\-1,\\qquad m=w\-1,\\qquad M=\\left\\lfloor c\_\{0\}m^\{2\}D^\{2\}\\log m\\right\\rfloor,\(15\)wherec0\>0c\_\{0\}\>0is 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 constantsc,C0,Ctr,c0\>0c,C\_\{0\},C\_\{\\rm tr\},c\_\{0\}\>0and integersL0,w0L\_\{0\},w\_\{0\}such that, forL≥L0\+1L\\geq L\_\{0\}\+1,w≥w0\+1w\\geq w\_\{0\}\+1, everyA,B,σ\>0A,B,\\sigma\>0, and everyn≥1n\\geq 1,

ℜn∗​\(A,B,σ\)≥c​\[min⁡\{B,σ​Mn,1M​\(\(A−C0\)\+Ctr​D​w2\)D\}\]2\.\\mathfrak\{R\}\_\{n\}^\{\*\}\(A,B,\\sigma\)\\geq c\\left\[\\min\\left\\\{B,\\sigma\\sqrt\{\\frac\{M\}\{n\}\},\\frac\{1\}\{M\}\\left\(\\frac\{\(A\-C\_\{0\}\)\_\{\+\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\\right\\\}\\right\]^\{2\}\.\(16\)The packing is local: at its active amplitudeλ\\lambda, every codeword hasL2L^\{2\}norm at mostC​λC\\lambda, and distinct codewords are at leastc​λc\\lambdaapart\.

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 constants0<cσ≤Cσ<∞0<c\_\{\\sigma\}\\leq C\_\{\\sigma\}<\\infty\. There exist constantsc,c′,Crad\>0c,c^\{\\prime\},C\_\{\\rm rad\}\>0, depending at most oncσc\_\{\\sigma\}andCσC\_\{\\sigma\}, such that the following holds\. AssumeA=B=RA=B=R,cσ​R≤σ≤Cσ​Rc\_\{\\sigma\}R\\leq\\sigma\\leq C\_\{\\sigma\}R,n≥Mn\\geq M, andR≥2​C0R\\geq 2C\_\{0\}\. If

RD−1≥\(Crad​D​w2\)D​M3/2n,R^\{D\-1\}\\geq\\left\(C\_\{\\rm rad\}Dw^\{2\}\\right\)^\{D\}\\frac\{M^\{3/2\}\}\{\\sqrt\{n\}\},\(17\)then

ℜn∗​\(R,R,σ\)≥c​R2​Mn≥c′​L2​w2​log⁡w​R2n\.\\mathfrak\{R\}\_\{n\}^\{\*\}\(R,R,\\sigma\)\\geq c\\frac\{R^\{2\}M\}\{n\}\\geq c^\{\\prime\}\\frac\{L^\{2\}w^\{2\}\\log w\\,R^\{2\}\}\{n\}\.\(18\)

We call the parameter range in Corollary[4](https://arxiv.org/html/2608.17434#Thmtheorem4), in which the Gaussian testing scale is active, the*statistical regime*\.

A convenient condition uniform over alln≥Mn\\geq Mis

RD−1≥\(Crad​D​w2\)D​M\.R^\{D\-1\}\\geq\\left\(C\_\{\\rm rad\}Dw^\{2\}\\right\)^\{D\}M\.\(19\)Equivalently,

R\\displaystyle R≥\(Crad​D​w2\)D/\(D−1\)​M1/\(D−1\)\\displaystyle\\geq\(C\_\{\\rm rad\}Dw^\{2\}\)^\{D/\(D\-1\)\}M^\{1/\(D\-1\)\}=Crad​D​w2​exp⁡\(log⁡\(Crad​D​w2\)\+log⁡MD−1\)\\displaystyle=C\_\{\\rm rad\}Dw^\{2\}\\exp\\\!\\left\(\\frac\{\\log\(C\_\{\\rm rad\}Dw^\{2\}\)\+\\log M\}\{D\-1\}\\right\)=Crad​D​w2​exp⁡\(O⁡\(log⁡\(L​w\)L\)\)\.\\displaystyle=C\_\{\\rm rad\}Dw^\{2\}\\exp\\\!\\left\(O\\\!\\left\(\\frac\{\\log\(Lw\)\}\{L\}\\right\)\\right\)\.\(20\)
###### Theorem 5\(Gaussian pseudodimension upper bound\)\.

There exists a universalC\>0C\>0such that, for all integersL,w≥1L,w\\geq 1, allA,B,σ\>0A,B,\\sigma\>0, and all integersn≥2n\\geq 2,

ℜn∗​\(A,B,σ\)≤C​min⁡\{B2,\(σ2\+B2\)​L2​w2​log⁡\(2​L​w\)​log⁡\(e​n\)n\}\.\\mathfrak\{R\}\_\{n\}^\{\*\}\(A,B,\\sigma\)\\leq C\\min\\left\\\{B^\{2\},\\frac\{\(\\sigma^\{2\}\+B^\{2\}\)L^\{2\}w^\{2\}\\log\(2Lw\)\\log\(en\)\}\{n\}\\right\\\}\.\(21\)

Consequently, under Corollary[4](https://arxiv.org/html/2608.17434#Thmtheorem4),

c​L2​w2​log⁡w​R2n≤ℜn∗≤C​L2​w2​log⁡\(L​w\)​log⁡\(e​n\)​R2n\.c\\frac\{L^\{2\}w^\{2\}\\log w\\,R^\{2\}\}\{n\}\\leq\\mathfrak\{R\}\_\{n\}^\{\*\}\\leq C\\frac\{L^\{2\}w^\{2\}\\log\(Lw\)\\log\(en\)\\,R^\{2\}\}\{n\}\.\(22\)Thus the polynomial depth exponent is quadratic; the remaining discrepancy is logarithmic\.

## 4Where the extra depth factor lives

The lower and upper bounds in Section[3](https://arxiv.org/html/2608.17434#S3)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⁡\(L​w2\),Pdim=O⁡\(Wpar​L​log⁡Wpar\)\.W\_\{\\rm par\}=O\(Lw^\{2\}\),\\qquad\\operatorname\{Pdim\}=O\(W\_\{\\rm par\}L\\log W\_\{\\rm par\}\)\.Norm\-based capacity bounds provide a different parameter\-space route to depth\-dependent generalization estimates\([Neyshabur et al\. 2015](https://arxiv.org/html/2608.17434#bib.bib9);[Golowich et al\. 2018](https://arxiv.org/html/2608.17434#bib.bib7)\)\. 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ℓ\\ellhas entropyHℓ​\(δℓ\)≲pℓ​log⁡\(Cℓ/δℓ\)H\_\{\\ell\}\(\\delta\_\{\\ell\}\)\\lesssim p\_\{\\ell\}\\log\(C\_\{\\ell\}/\\delta\_\{\\ell\}\)and downstream Lipschitz amplificationAℓ=∏j\>ℓajA\_\{\\ell\}=\\prod\_\{j\>\\ell\}a\_\{j\}\. A telescoping decomposition gives

‖sL∘⋯∘s1−s~L∘⋯∘s~1‖≤∑ℓ=1LAℓδℓ\.\\left\\lVert s\_\{L\}\\circ\\cdots\\circ s\_\{1\}\-\\widetilde\{s\}\_\{L\}\\circ\\cdots\\circ\\widetilde\{s\}\_\{1\}\\right\\rVert\\leq\\sum\_\{\\ell=1\}^\{L\}A\_\{\\ell\}\\delta\_\{\\ell\}\.\(23\)The entropy\-minimizing allocation under total errorε\\varepsilonisδℓ=ε​pℓ/\(P​Aℓ\)\\delta\_\{\\ell\}=\\varepsilon p\_\{\\ell\}/\(PA\_\{\\ell\}\),P=∑ℓpℓP=\\sum\_\{\\ell\}p\_\{\\ell\}, and produces

∑ℓ=1Lpℓ​log⁡Aℓ\\displaystyle\\sum\_\{\\ell=1\}^\{L\}p\_\{\\ell\}\\log A\_\{\\ell\}=∑ℓ=1Lpℓ​∑j\>ℓlog⁡aj\\displaystyle=\\sum\_\{\\ell=1\}^\{L\}p\_\{\\ell\}\\sum\_\{j\>\\ell\}\\log a\_\{j\}\(24\)=∑j=2L\(∑ℓ<jpℓ\)​log⁡aj\.\\displaystyle=\\sum\_\{j=2\}^\{L\}\\left\(\\sum\_\{\\ell<j\}p\_\{\\ell\}\\right\)\\log a\_\{j\}\.\(25\)In the homogeneous casepℓ=pp\_\{\\ell\}=pandaj=a\>1a\_\{j\}=a\>1, this becomes

∑j=2L\(∑ℓ<jp\)​log⁡a=p​log⁡a​∑j=2L\(j−1\)=p​L​\(L−1\)2​log⁡a\.\\sum\_\{j=2\}^\{L\}\\left\(\\sum\_\{\\ell<j\}p\\right\)\\log a=p\\log a\\sum\_\{j=2\}^\{L\}\(j\-1\)=\\frac\{pL\(L\-1\)\}\{2\}\\log a\.\(26\)Thus the second factor of depth counts ordered pairs consisting of a perturbed layer and a downstream amplification layer\. Forp≍w2p\\asymp w^\{2\}, the resulting contribution isΘ⁡\(L2​w2\)\\Theta\(L^\{2\}w^\{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λ\\lambda, it lies in anO⁡\(λ\)O\(\\lambda\)ball, hasΩ⁡\(λ\)\\Omega\(\\lambda\)pairwise separation, and has log\-cardinalityΩ⁡\(L2​w2​log⁡w\)\\Omega\(L^\{2\}w^\{2\}\\log w\)\. Consequently, the localized covering entropy at this scale is at leastΩ⁡\(L2​w2​log⁡w\)\\Omega\(L^\{2\}w^\{2\}\\log w\), precluding a uniform covering\-entropy upper bound of orderO⁡\(L​w2\)O\(Lw^\{2\}\)in the statistical regime\.

Binary grid codelog⁡\|𝒵\|=Ω⁡\(M\)\\log\|\\mathcal\{Z\}\|=\\Omega\(M\)Bias\-corrected unit\-coefficient approximation‖Nz−hz/M‖∞≲M−1\\\|N\_\{z\}\-h\_\{z\}/M\\\|\_\{\\infty\}\\lesssim M^\{\-1\}Balanced amplificationcost≲D​w2​\(λ​M\)1/D\\lesssim Dw^\{2\}\(\\lambda M\)^\{1/D\}Gaussian Fanorisk≳λ2\\gtrsim\\lambda^\{2\}M=Θ⁡\(D2​m2​log⁡m\)M=\\Theta\(D^\{2\}m^\{2\}\\log 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\.
## 5A depth\-enabled local code

Letxj=j/Mx\_\{j\}=j/M,j=0,…,Mj=0,\\ldots,M\. Forz∈\{0,1\}M−1z\\in\\\{0,1\\\}^\{M\-1\}, setz0=zM=0z\_\{0\}=z\_\{M\}=0and lethzh\_\{z\}linearly interpolate\(xj,zj\)\(x\_\{j\},z\_\{j\}\)\. Then‖hz‖∞≤1\\left\\lVert h\_\{z\}\\right\\rVert\_\{\\infty\}\\leq 1,Lip⁡\(hz\)≤M\\operatorname\{Lip\}\(h\_\{z\}\)\\leq M, andgz=hz/Mg\_\{z\}=h\_\{z\}/Mis bounded and11\-Lipschitz\. Theorem[2](https://arxiv.org/html/2608.17434#Thmtheorem2)givesNz∈𝒩⁡\(m,D,1\)N\_\{z\}\\in\\mathcal\{N\}\(m,D,1\)with

‖Nz−gz‖∞≤Cappm2​D2​log⁡m\.\\left\\lVert N\_\{z\}\-g\_\{z\}\\right\\rVert\_\{\\infty\}\\leq\\frac\{C\_\{\\rm app\}\}\{m^\{2\}D^\{2\}\\log m\}\.\(27\)ForM=⌊c0​m2​D2​log⁡m⌋M=\\lfloor c\_\{0\}m^\{2\}D^\{2\}\\log m\\rfloorand sufficiently smallc0c\_\{0\}, the rescaled functionsQz=M​NzQ\_\{z\}=MN\_\{z\}obey

‖Qz−hz‖∞≤η\\left\\lVert Q\_\{z\}\-h\_\{z\}\\right\\rVert\_\{\\infty\}\\leq\\eta\(28\)for a fixed small universalη\\eta\.

Ifdj=zj−zj′d\_\{j\}=z\_\{j\}\-z\_\{j\}^\{\\prime\}, direct integration on thejjth cell gives

∫j/M\(j\+1\)/M\(hz−hz′\)2​𝑑x=dj2\+dj​dj\+1\+dj\+123​M\.\\int\_\{j/M\}^\{\(j\+1\)/M\}\(h\_\{z\}\-h\_\{z^\{\\prime\}\}\)^\{2\}\\,\\mathrm\{d\}x=\\frac\{d\_\{j\}^\{2\}\+d\_\{j\}d\_\{j\+1\}\+d\_\{j\+1\}^\{2\}\}\{3M\}\.\(29\)Sincea2\+a​b\+b2≥\(a2\+b2\)/2a^\{2\}\+ab\+b^\{2\}\\geq\(a^\{2\}\+b^\{2\}\)/2andd0=dM=0d\_\{0\}=d\_\{M\}=0,

‖hz−hz′‖22≥dH​\(z,z′\)3​M\.\\left\\lVert h\_\{z\}\-h\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}^\{2\}\\geq\\frac\{d\_\{H\}\(z,z^\{\\prime\}\)\}\{3M\}\.\(30\)The Varshamov–Gilbert bound\([Tsybakov 2009](https://arxiv.org/html/2608.17434#bib.bib23)\)therefore yields𝒵⊆\{0,1\}M−1\\mathcal\{Z\}\\subseteq\\\{0,1\\\}^\{M\-1\}such that

log\|𝒵\|≥cM,c≤‖Qz−Qz′‖2≤C\(z≠z′\)\.\\log\|\\mathcal\{Z\}\|\\geq cM,\\qquad c\\leq\\left\\lVert Q\_\{z\}\-Q\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}\\leq C\\quad\(z\\neq z^\{\\prime\}\)\.\(31\)The code therefore has the required cardinality and local geometry\. The remaining task is to amplify it to scaleλ\\lambdawithout exhausting the layer\-sum budget\.

## 6Balanced amplification andℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{2\}translation

SinceQz=M​NzQ\_\{z\}=MN\_\{z\}, reaching separation of orderλ\\lambdarequires a gainq=λ​Mq=\\lambda Mrelative to the unit\-coefficient approximant\. Applying this gain entirely in the final layer would charge orderqqto one block\. Balanced amplification distributes the same gain across depth while a constant homogeneous coordinate transports every bias exactly\.

###### Lemma 7\(Balanced amplification\)\.

LetN∈𝒩⁡\(m,D,1\)N\\in\\mathcal\{N\}\(m,D,1\)have exact depthD≥2D\\geq 2\. For everyq\>0q\>0,q​NqNhas a depth\-DD, width\-at\-most\-\(m\+1\)\(m\+1\)realization with coefficient magnitude at mostq1/Dq^\{1/D\}\.

Writings=q1/Ds=q^\{1/D\}, the augmented state ish~ℓ=\(sℓ​hℓ,sℓ\)\\widetilde\{h\}\_\{\\ell\}=\(s^\{\\ell\}h\_\{\\ell\},s^\{\\ell\}\)\. The extra coordinate transports the scaled biases, and the final affine map returnssD​N=q​Ns^\{D\}N=qN\. Appendix[D](https://arxiv.org/html/2608.17434#A4)gives the matrices and exact\-depth padding\.

###### Lemma 8\(Layer translation\)\.

LetT⁡\(x\)=ρ⁡\(A​x\+b\)T\(x\)=\\rho\(Ax\+b\)coordinatewise, with input and output dimensions at mostwwand\|Ai​j\|,\|bi\|≤s\|A\_\{ij\}\|,\|b\_\{i\}\|\\leq s\. ThenTTis an allowed vector\-valued block with at mostwwatoms and

‖T‖ℛ​BV2≤C​w2​s\.\\left\\lVert T\\right\\rVert\_\{\\mathcal\{R\}\\mathrm\{BV\}^\{2\}\}\\leq Cw^\{2\}s\.\(32\)The same estimate holds for an affine output map\.

Thus, forN∈𝒩⁡\(m,D,1\)N\\in\\mathcal\{N\}\(m,D,1\),

𝔙D,m\+1​\(q​N\)≤Ctr​D​\(m\+1\)2​q1/D\.\\mathfrak\{V\}\_\{D,m\+1\}\(qN\)\\leq C\_\{\\rm tr\}D\(m\+1\)^\{2\}q^\{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\\rho\(t\-1\),\\qquad 0\\leq t\\leq 2\.\(34\)It has univariateℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{2\}normC0=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\)=\\lambda Q\_\{z\}\(r\(t\)\),\(35\)we have

‖Fz−Fz′‖L2​\(\[0,2\),d​t/2\)=λ​‖Qz−Qz′‖L2​\(\[0,1\]\)\\left\\lVert F\_\{z\}\-F\_\{z^\{\\prime\}\}\\right\\rVert\_\{L^\{2\}\(\[0,2\),\\,\\mathrm\{d\}t/2\)\}=\\lambda\\left\\lVert Q\_\{z\}\-Q\_\{z^\{\\prime\}\}\\right\\rVert\_\{L^\{2\}\(\[0,1\]\)\}\(36\)and, usingD=L−1D=L\-1,m\+1=wm\+1=w,

𝔙L,w​\(Fz\)≤C0\+Ctr​D​w2​\(λ​M\)1/D\.\\mathfrak\{V\}\_\{L,w\}\(F\_\{z\}\)\\leq C\_\{0\}\+C\_\{\\rm tr\}Dw^\{2\}\(\\lambda M\)^\{1/D\}\.\(37\)Equation \([37](https://arxiv.org/html/2608.17434#S6.E37)\) completes the representation step\. We now combine this bound with the output and Gaussian testing constraints\.

## 7From the local code to the minimax lower bound

Three constraints determine the admissible amplitude\. First, \([28](https://arxiv.org/html/2608.17434#S5.E28)\) gives‖Qz‖∞≤1\+η\\left\\lVert Q\_\{z\}\\right\\rVert\_\{\\infty\}\\leq 1\+\\eta, so the output cap is satisfied whenever

λ≲B\.\\lambda\\lesssim B\.\(38\)Second, \([37](https://arxiv.org/html/2608.17434#S6.E37)\) places the code in the layer\-sum ball whenA\>C0A\>C\_\{0\}and

λ≲1M​\(A−C0Ctr​D​w2\)D\.\\lambda\\lesssim\\frac\{1\}\{M\}\\left\(\\frac\{A\-C\_\{0\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\.\(39\)WhenA≤C0A\\leq 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\. Sincelog⁡\|𝒵\|≳M\\log\|\\mathcal\{Z\}\|\\gtrsim Mand the pairwise divergence is of ordern​λ2/σ2n\\lambda^\{2\}/\\sigma^\{2\}, Fano’s inequality requires

λ≲σ​Mn\.\\lambda\\lesssim\\sigma\\sqrt\{\\frac\{M\}\{n\}\}\.\(40\)We therefore choose

λ=cλ​min⁡\{B,σ​Mn,1M​\(\(A−C0\)\+Ctr​D​w2\)D\}\.\\lambda=c\_\{\\lambda\}\\min\\left\\\{B,\\sigma\\sqrt\{\\frac\{M\}\{n\}\},\\frac\{1\}\{M\}\\left\(\\frac\{\(A\-C\_\{0\}\)\_\{\+\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\\right\\\}\.\(41\)Up to universal constants, \([41](https://arxiv.org/html/2608.17434#S7.E41)\) is the largest amplitude compatible with all three restrictions\.

After reducingcλc\_\{\\lambda\}, equations \([28](https://arxiv.org/html/2608.17434#S5.E28)\) and \([37](https://arxiv.org/html/2608.17434#S6.E37)\) implyFz∈𝒞L,w​\(A,B\)F\_\{z\}\\in\\mathcal\{C\}\_\{L,w\}\(A,B\)\. Equations \([31](https://arxiv.org/html/2608.17434#S5.E31)\) and \([36](https://arxiv.org/html/2608.17434#S6.E36)\) give

c​λ≤‖Fz−Fz′‖2≤C​λ,‖Fz‖2≤C​λ\.c\\lambda\\leq\\left\\lVert F\_\{z\}\-F\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}\\leq C\\lambda,\\qquad\\left\\lVert F\_\{z\}\\right\\rVert\_\{2\}\\leq C\\lambda\.\(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\_\{\\mathrm\{KL\}\}\(P\_\{z\}^\{\\otimes n\}\\\|P\_\{z^\{\\prime\}\}^\{\\otimes n\}\)=\\frac\{n\}\{2\\sigma^\{2\}\}\\left\\lVert F\_\{z\}\-F\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}^\{2\}\\leq C\\frac\{n\\lambda^\{2\}\}\{\\sigma^\{2\}\}\.\(43\)The testing restriction \([40](https://arxiv.org/html/2608.17434#S7.E40)\) makes this a sufficiently small multiple ofM≲log⁡\|𝒵\|M\\lesssim\\log\|\\mathcal\{Z\}\|\. Nearest\-neighbor decoding and Fano’s inequality\([Tsybakov 2009](https://arxiv.org/html/2608.17434#bib.bib23)\)then yield riskΩ⁡\(λ2\)\\Omega\(\\lambda^\{2\}\), proving Theorem[3](https://arxiv.org/html/2608.17434#Thmtheorem3)\.

For Corollary[4](https://arxiv.org/html/2608.17434#Thmtheorem4),n≥Mn\\geq Mmakes the testing amplitude at most a constant multiple ofRR\. IfR≥2​C0R\\geq 2C\_\{0\}, thenR−C0≥R/2R\-C\_\{0\}\\geq R/2, and \([17](https://arxiv.org/html/2608.17434#S3.E17)\) implies

1M​\(R−C0Ctr​D​w2\)D≥c​R​Mn\.\\frac\{1\}\{M\}\\left\(\\frac\{R\-C\_\{0\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\\geq cR\\sqrt\{\\frac\{M\}\{n\}\}\.Henceλ2≍R2​M/n\\lambda^\{2\}\\asymp R^\{2\}M/n\. The uniform condition \([19](https://arxiv.org/html/2608.17434#S3.E19)\) follows becauseM3/2/n≤MM^\{3/2\}/\\sqrt\{n\}\\leq Mforn≥Mn\\geq M\. Complete constants appear in Appendix[F](https://arxiv.org/html/2608.17434#A6)\.

## 8A 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\)\\mathcal\{C\}\_\{L,w\}\(A,B\)is realized by a piecewise\-linear computation graph with at mostC​L​w2CLw^\{2\}real parameters and computational depth at mostC​LCL\. Consequently,

Pdim⁡\(𝒞L,w​\(A,B\)\)≤C​L2​w2​log⁡\(2​L​w\)\.\\operatorname\{Pdim\}\(\\mathcal\{C\}\_\{L,w\}\(A,B\)\)\\leq CL^\{2\}w^\{2\}\\log\(2Lw\)\.\(44\)

The proof in Appendix[A](https://arxiv.org/html/2608.17434#A1)explicitly handles vector\-valued blocks, affine skips, and variable intermediate dimensions\. It then applies the piecewise\-linear pseudodimension theorem of[Bartlett et al\. 2019](https://arxiv.org/html/2608.17434#bib.bib5)\. For every design distributionPP, a\[−B,B\]\[\-B,B\]\-valued class of pseudodimensionVVsatisfies

log⁡N⁡\(ε,𝒞L,w​\(A,B\),L2​\(P\)\)≤C​V​log⁡C​Bε\.\\log N\(\\varepsilon,\\mathcal\{C\}\_\{L,w\}\(A,B\),L^\{2\}\(P\)\)\\leq CV\\log\\frac\{CB\}\{\\varepsilon\}\.\(45\)
For a finite𝒢⊂\[−B,B\]\\mathcal\{G\}\\subset\[\-B,B\], least squares underY=f⋆​\(X\)\+ξY=f^\{\\star\}\(X\)\+\\xi,ξ∼N⁡\(0,σ2\)\\xi\\sim N\(0,\\sigma^\{2\}\), obeys

𝔼​‖g^−f⋆‖22≤C​infg∈𝒢‖g−f⋆‖22\+C​\(σ2\+B2\)​log⁡\(2​\|𝒢\|\)n\.\\mathbb\{E\}\\left\\lVert\\widehat\{g\}\-f^\{\\star\}\\right\\rVert\_\{2\}^\{2\}\\leq C\\inf\_\{g\\in\\mathcal\{G\}\}\\left\\lVert g\-f^\{\\star\}\\right\\rVert\_\{2\}^\{2\}\+C\\frac\{\(\\sigma^\{2\}\+B^\{2\}\)\\log\(2\|\\mathcal\{G\}\|\)\}\{n\}\.\(46\)The Gaussian multiplier/Bernstein argument applies directly to unbounded Gaussian responses\. Taking a population\-L2L^\{2\}ε\\varepsilon\-net, using \([45](https://arxiv.org/html/2608.17434#S8.E45)\), and optimizingε\\varepsilonyields Theorem[5](https://arxiv.org/html/2608.17434#Thmtheorem5); Appendix[G](https://arxiv.org/html/2608.17434#A7)gives the full proof\. Together with Corollary[4](https://arxiv.org/html/2608.17434#Thmtheorem4), Theorem[5](https://arxiv.org/html/2608.17434#Thmtheorem5)fixes the polynomial depth exponent\. We next interpret the resulting local entropy bound and the competition among the output, testing, and representation scales\.

## 9Consequences and open directions

The packing also yields an explicit localized covering lower bound\. At the amplitude selected in \([41](https://arxiv.org/html/2608.17434#S7.E41)\), all codewords lie in anL2L^\{2\}ball of radiusC​λC\\lambda, distinct codewords are at leastc​λc\\lambdaapart, and

log⁡N⁡\(c​λ,𝒞L,w​\(A,B\)∩\{f:‖f‖2≤C​λ\},L2\)≥c​M=Ω⁡\(L2​w2​log⁡w\)\.\\log N\\\!\\left\(c\\lambda,\\mathcal\{C\}\_\{L,w\}\(A,B\)\\cap\\\{f:\\left\\lVert f\\right\\rVert\_\{2\}\\leq C\\lambda\\\},L^\{2\}\\right\)\\geq cM=\\Omega\(L^\{2\}w^\{2\}\\log w\)\.Hence the localized entropy at the testing scale is quadratic in depth, precluding a uniform covering\-entropy upper bound of orderO⁡\(L​w2\)O\(Lw^\{2\}\)in the statistical regime\. This local statement complements sharp entropy results for shallow neural variation spaces\([Siegel and Xu 2024](https://arxiv.org/html/2608.17434#bib.bib20)\)and the general entropy–minimax correspondence\([Yang and Barron 1999](https://arxiv.org/html/2608.17434#bib.bib24)\)\.

### 9\.1Radius dependence of the lower bound

Theorem[3](https://arxiv.org/html/2608.17434#Thmtheorem3)can be read as a competition among three amplitudes:

λout=B,λstat=σ​M/n,λrep=1M​\(\(A−C0\)\+Ctr​D​w2\)D\.\\lambda\_\{\\rm out\}=B,\\qquad\\lambda\_\{\\rm stat\}=\\sigma\\sqrt\{M/n\},\\qquad\\lambda\_\{\\rm rep\}=\\frac\{1\}\{M\}\\left\(\\frac\{\(A\-C\_\{0\}\)\_\{\+\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\.\(47\)Ifλout\\lambda\_\{\\rm out\}is smallest, the lower bound saturates at the output\-diameter scaleB2B^\{2\}\. Ifλstat\\lambda\_\{\\rm stat\}is smallest, ordinary Gaussian testing is active and the risk isΩ⁡\(σ2​M/n\)\\Omega\(\\sigma^\{2\}M/n\)\. UnderA=B=RA=B=Randσ≍R\\sigma\\asymp R, this is the quadratic\-depth regime of Corollary[4](https://arxiv.org/html/2608.17434#Thmtheorem4), namely the statistical regime\.

Ifλrep\\lambda\_\{\\rm rep\}is smallest, the same construction gives

ℜn∗​\(A,B,σ\)≳1M2​\(\(A−C0\)\+Ctr​D​w2\)2​D\.\\mathfrak\{R\}\_\{n\}^\{\*\}\(A,B,\\sigma\)\\gtrsim\\frac\{1\}\{M^\{2\}\}\\left\(\\frac\{\(A\-C\_\{0\}\)\_\{\+\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{2D\}\.\(48\)Equation \([48](https://arxiv.org/html/2608.17434#S9.E48)\) 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,\\operatorname\{Lip\}\(f\)\\leq\\prod\_\{\\ell=1\}^\{L\}\\left\\lVert s\_\{\\ell\}\\right\\rVert\_\{\\mathcal\{R\}\\mathrm\{BV\}^\{2\}\}\\leq\\left\(\\frac\{A\}\{L\}\\right\)^\{L\},\(49\)so a small ratioA/LA/Lcan collapse the class exponentially with depth\. The radius transition therefore reflects the geometry of the class rather than only the proof technique\.

### 9\.2Limitations and open questions

Several questions remain\. The lower bound containslog⁡w\\log w, whereas the upper bound containslog⁡\(L​w\)​log⁡n\\log\(Lw\)\\log 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 theO⁡\(L​w2\)O\(Lw^\{2\}\)parameterization in the motivating work; a literal scalar\-to\-scalar chain has onlyO⁡\(L​w\)O\(Lw\)parameters and defines a different minimax problem\. A sharpAA\-dependent upper bound across all three regimes in \([47](https://arxiv.org/html/2608.17434#S9.E47)\) remains open\. The local packing of entropyΩ⁡\(L2​w2​log⁡w\)\\Omega\(L^\{2\}w^\{2\}\\log w\)therefore survives the layer\-sum variation constraint at the Gaussian testing scale\. Under the radius condition of Corollary[4](https://arxiv.org/html/2608.17434#Thmtheorem4), 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](https://arxiv.org/html/2608.17434#S2)–[3](https://arxiv.org/html/2608.17434#S3), and complete proofs are provided in the appendices, including the corrected approximation reduction, balanced amplification andℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{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://www\.jmlr\.org/papers/v22/20\-583\.html](https://www.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://www\.jmlr\.org/papers/v25/23\-0677\.html](https://www.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, andnn\-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 AArchitecture conventions and computation\-graph realization

### A\.1Vector\-valued class and relation to the motivating formulation

Fors⁡\(x\)=∑k=1Kvk​ρ​\(wk⊤​x−bk\)\+C​x\+c0s\(x\)=\\sum\_\{k=1\}^\{K\}v\_\{k\}\\rho\(w\_\{k\}^\{\\top\}x\-b\_\{k\}\)\+Cx\+c\_\{0\}, we use \([8](https://arxiv.org/html/2608.17434#S2.E8)\)\. The Parhi–Nowak deep space composes vector\-valued maps across dimensionsd0,…,dLd\_\{0\},\\ldots,d\_\{L\}\([Parhi and Nowak 2022](https://arxiv.org/html/2608.17434#bib.bib14)\)\. The motivating work uses anO⁡\(L​w2\)O\(Lw^\{2\}\)parameter count, while its displayed base\-block formula does not explicitly display these dimensions\([Ganguli and Constantinescu 2026](https://arxiv.org/html/2608.17434#bib.bib6)\)\. Throughout this paper, all class inclusions refer to the explicit architecture

d0=dL=1,dℓ≤w,Kℓ≤w\.d\_\{0\}=d\_\{L\}=1,\\qquad d\_\{\\ell\}\\leq w,\\qquad K\_\{\\ell\}\\leq w\.

### A\.2Exact parameter count

A block with input dimensiondd, output dimensionD′D^\{\\prime\}, andKKatoms has

D′​K\+K​d\+K\+D′​d\+D′D^\{\\prime\}K\+Kd\+K\+D^\{\\prime\}d\+D^\{\\prime\}scalar parameters\. Ifd,D′,K≤wd,D^\{\\prime\},K\\leq w, this is at most3​w2\+2​w3w^\{2\}\+2w\. Hence

Wpar≤L⁡\(3​w2\+2​w\)\.W\_\{\\rm par\}\\leq L\(3w^\{2\}\+2w\)\.\(50\)

### A\.3Proof of Lemma[9](https://arxiv.org/html/2608.17434#Thmtheorem9)

For each block, compute theKKpreactivationswk⊤​x−bkw\_\{k\}^\{\\top\}x\-b\_\{k\}in one affine stage, applyKKReLUs, and compute∑kvk​ρ​\(⋅\)\+C​x\+c0\\sum\_\{k\}v\_\{k\}\\rho\(\\cdot\)\+Cx\+c\_\{0\}in a second affine stage\. The skipC​xCxis carried in parallel through the same block and adds no nonlinear depth\. Thus anLL\-block composition is a piecewise\-linear computation graph with at most the parameters in \([50](https://arxiv.org/html/2608.17434#A1.E50)\), at mostL​wLwReLU gates, and computational depth at most2​L2L\.

If a theorem is stated for ordinary feed\-forward ReLU networks without affine skips, represent a scalaruuby\(ρ⁡\(u\),ρ⁡\(−u\)\)\(\\rho\(u\),\\rho\(\-u\)\)and propagate both signs\. This converts every affine skip into a constant\-factor larger ReLU graph, preservingO⁡\(L​w2\)O\(Lw^\{2\}\)parameters andO⁡\(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](https://arxiv.org/html/2608.17434#bib.bib5), applied to this maximal graph, gives

Pdim≤C​Wpar​L​log⁡\(2​Wpar\)≤C​L2​w2​log⁡\(2​L​w\)\.\\operatorname\{Pdim\}\\leq CW\_\{\\rm par\}L\\log\(2W\_\{\\rm par\}\)\\leq CL^\{2\}w^\{2\}\\log\(2Lw\)\.The layer\-cost and output constraints only restrict the graph class and cannot increase pseudodimension\.

### A\.4Circle coordinate and representation cost

The coordinatet∈\[0,2\)t\\in\[0,2\)is the motivating coordinatet=θ/πt=\\theta/\\piwith normalized measured​t/2\\,\\mathrm\{d\}t/2\. The tent map \([34](https://arxiv.org/html/2608.17434#S6.E34)\) satisfiesr⁡\(0\)=r⁡\(2\)=0r\(0\)=r\(2\)=0, so the packed functions periodize continuously\.

The infimum \([10](https://arxiv.org/html/2608.17434#S2.E10)\) is generally not one\-homogeneous as a functional of the composed map: a scalar gain can be distributed acrossDDstages at cost proportional toD​q1/DDq^\{1/D\}\. Accordingly, all arguments use only the representation\-cost definition\.

## Appendix BA bias\-corrected bounded\-coefficient approximation theorem

This appendix proves Theorem[2](https://arxiv.org/html/2608.17434#Thmtheorem2)\. The bit decoder and approximation estimates are imported from the constructive proof of[Ou et al\. 2024](https://arxiv.org/html/2608.17434#bib.bib12)\. The coefficient\-scaling steps needed to pass from that construction to the unit\-coefficient theorem are rederived below under the affine\-layer convention \([13](https://arxiv.org/html/2608.17434#S2.E13)\)\.

### B\.1The affine\-bias obstruction and its repair

Uniformly multiplying every affine pair\(Aℓ,bℓ\)\(A\_\{\\ell\},b\_\{\\ell\}\)bya\>0a\>0scales homogeneous terms and biases by different powers across depth\. For example, the depth\-two realization

N⁡\(x\)=ρ⁡\(x\)\+1N\(x\)=\\rho\(x\)\+1becomesa2​ρ​\(x\)\+aa^\{2\}\\rho\(x\)\+a, nota2​N​\(x\)a^\{2\}N\(x\)\. The last\-layer bias receives only one factor ofaa\. A constant homogeneous coordinate repairs this mismatch\.

###### Lemma 10\(Homogeneous lift\)\.

LetB≥1B\\geq 1and letN∈𝒩⁡\(W,D,B\)N\\in\\mathcal\{N\}\(W,D,B\)have exact depthD≥2D\\geq 2\. For everyq\>0q\>0,

q​N∈𝒩⁡\(W\+1,D,B​q1/D\)\.qN\\in\\mathcal\{N\}\(W\+1,D,Bq^\{1/D\}\)\.\(51\)

###### Proof\.

Puts=q1/Ds=q^\{1/D\}and write the hidden states as in \([13](https://arxiv.org/html/2608.17434#S2.E13)\)\. Define

h~1=ρ⁡\(\[s​A10\]​x\+\[s​b1s\]\)=\[s​h1s\],\\widetilde\{h\}\_\{1\}=\\rho\\\!\\left\(\\begin\{bmatrix\}sA\_\{1\}\\\\ 0\\end\{bmatrix\}x\+\\begin\{bmatrix\}sb\_\{1\}\\\\ s\\end\{bmatrix\}\\right\)=\\begin\{bmatrix\}sh\_\{1\}\\\\ s\\end\{bmatrix\},\(52\)and, for2≤ℓ<D2\\leq\\ell<D,

h~ℓ=ρ⁡\(\[s​Aℓs​bℓ0s\]​h~ℓ−1\)\.\\widetilde\{h\}\_\{\\ell\}=\\rho\\\!\\left\(\\begin\{bmatrix\}sA\_\{\\ell\}&sb\_\{\\ell\}\\\\ 0&s\\end\{bmatrix\}\\widetilde\{h\}\_\{\\ell\-1\}\\right\)\.\(53\)Induction givesh~ℓ=\(sℓ​hℓ,sℓ\)\\widetilde\{h\}\_\{\\ell\}=\(s^\{\\ell\}h\_\{\\ell\},s^\{\\ell\}\)\. The final affine map is

N~​\(x\)=\[s​ADs​bD\]​h~D−1=sD​\(AD​hD−1\+bD\)=q​N​\(x\)\.\\widetilde\{N\}\(x\)=\\begin\{bmatrix\}sA\_\{D\}&sb\_\{D\}\\end\{bmatrix\}\\widetilde\{h\}\_\{D\-1\}=s^\{D\}\(A\_\{D\}h\_\{D\-1\}\+b\_\{D\}\)=qN\(x\)\.\(54\)The width increases by one\. Every old coefficient is multiplied byss, and the only new nonzero coefficient isss; sinceB≥1B\\geq 1, the new coefficient magnitude is at mosts​BsB\. ∎

### B\.2Trading coefficient magnitude for depth

We next use a unit\-coefficient fan\-out construction\.

###### Lemma 11\(Unit\-coefficient fan\-out\)\.

LetW≥2W\\geq 2, letN∈𝒩⁡\(W,D,1\)N\\in\\mathcal\{N\}\(W,D,1\), and letJ≥0J\\geq 0\. Putr=⌊W/2⌋r=\\lfloor W/2\\rfloor\. Then

rJ​N∈𝒩⁡\(W,D\+J,1\)\.r^\{J\}N\\in\\mathcal\{N\}\(W,D\+J,1\)\.\(55\)

###### Proof\.

The caseJ=0J=0is immediate\. ForJ≥1J\\geq 1, pad the input realization to exact depthDDand write its scalar output asy=AD​hD−1\+bDy=A\_\{D\}h\_\{D\-1\}\+b\_\{D\}\. Replace this final affine map by the hidden vector

u1=\(ρ⁡\(y\)​𝟏r,ρ⁡\(−y\)​𝟏r\)∈ℝ2​r\.u\_\{1\}=\(\\rho\(y\)\\mathbf\{1\}\_\{r\},\\rho\(\-y\)\\mathbf\{1\}\_\{r\}\)\\in\\mathbb\{R\}^\{2r\}\.For each of the nextJ−1J\-1hidden layers, applydiag⁡\(𝟏r×r,𝟏r×r\)\\operatorname\{diag\}\(\\mathbf\{1\}\_\{r\\times r\},\\mathbf\{1\}\_\{r\\times r\}\)with zero bias\. The final row\(𝟏r⊤,−𝟏r⊤\)\(\\mathbf\{1\}\_\{r\}^\{\\top\},\-\\mathbf\{1\}\_\{r\}^\{\\top\}\)returnsrJ​\(ρ⁡\(y\)−ρ⁡\(−y\)\)=rJ​yr^\{J\}\(\\rho\(y\)\-\\rho\(\-y\)\)=r^\{J\}y\. All coefficients belong to\{−1,0,1\}\\\{\-1,0,1\\\}and2​r≤W2r\\leq W\. ∎

###### Corollary 12\(Bias\-correct depth–coefficient conversion\)\.

LetW≥4W\\geq 4,D≥2D\\geq 2, andB≥1B\\geq 1\. Put

r=⌊W\+12⌋,J=⌈D​log⁡Blog⁡r⌉,r=\\left\\lfloor\\frac\{W\+1\}\{2\}\\right\\rfloor,\\qquad J=\\left\\lceil\\frac\{D\\log B\}\{\\log r\}\\right\\rceil,\(56\)withJ=0J=0whenB=1B=1\. Then

𝒩⁡\(W,D,B\)⊆𝒩⁡\(W\+1,D\+J,1\)\.\\mathcal\{N\}\(W,D,B\)\\subseteq\\mathcal\{N\}\(W\+1,D\+J,1\)\.\(57\)IfB=WKB=W^\{K\}for fixedKK, thenJ≤2​K​D\+1J\\leq 2KD\+1\.

###### Proof\.

ForN∈𝒩⁡\(W,D,B\)N\\in\\mathcal\{N\}\(W,D,B\), Lemma[10](https://arxiv.org/html/2608.17434#Thmtheorem10)withq=B−Dq=B^\{\-D\}givesB−D​N∈𝒩⁡\(W\+1,D,1\)B^\{\-D\}N\\in\\mathcal\{N\}\(W\+1,D,1\)\. Apply Lemma[11](https://arxiv.org/html/2608.17434#Thmtheorem11)at widthW\+1W\+1to obtainrJ​B−D​Nr^\{J\}B^\{\-D\}N\. SincerJ≥BDr^\{J\}\\geq B^\{D\}, multiplying the final affine map byBD/rJ≤1B^\{D\}/r^\{J\}\\leq 1recoversNNwithout violating the unit coefficient bound\. Finally,r2≥Wr^\{2\}\\geq WforW≥4W\\geq 4, solog⁡r≥12​log⁡W\\log r\\geq\\frac\{1\}\{2\}\\log Wand the stated bound onJJfollows\. ∎

### B\.3Repairing the bounded\-spline realization

For a strictly increasing breakpoint sequenceX=\(xi\)i=0MX−1⊂\[0,1\]X=\(x\_\{i\}\)\_\{i=0\}^\{M\_\{X\}\-1\}\\subset\[0,1\], letΣ⁡\(X,E\)\\Sigma\(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 byEE\. Put

Rm​\(X\)=max1≤i≤MX−1⁡\(xi−xi−1\)−1\.R\_\{m\}\(X\)=\\max\_\{1\\leq i\\leq M\_\{X\}\-1\}\(x\_\{i\}\-x\_\{i\-1\}\)^\{\-1\}\.The direct construction of[Ou et al\. 2024](https://arxiv.org/html/2608.17434#bib.bib12), which is independent of the bias\-sensitive layerwise scaling identity discussed above, implies that wheneveru2​v≥MXu^\{2\}v\\geq M\_\{X\},

Σ⁡\(X,1Ck​MX6​Rm​\(X\)4\)⊆𝒩⁡\(20​u,30​v,1\),\\Sigma\\\!\\left\(X,\\frac\{1\}\{C\_\{k\}M\_\{X\}^\{6\}R\_\{m\}\(X\)^\{4\}\}\\right\)\\subseteq\\mathcal\{N\}\(20u,30v,1\),\(58\)where2≤Ck≤1052\\leq C\_\{k\}\\leq 10^\{5\}is universal\.

###### Lemma 13\(Bias\-correct bounded\-spline realization\)\.

Assumeu2​v≥MXu^\{2\}v\\geq M\_\{X\},v≥1v\\geq 1,ws≥1w\_\{s\}\\geq 1, and

ws30​v≥MX6​Rm​\(X\)4​E\.w\_\{s\}^\{30v\}\\geq M\_\{X\}^\{6\}R\_\{m\}\(X\)^\{4\}E\.\(59\)Then

Σ⁡\(X,E\)⊆𝒩⁡\(20​u\+1,30​v,2​ws\)\.\\Sigma\(X,E\)\\subseteq\\mathcal\{N\}\(20u\+1,30v,2w\_\{s\}\)\.\(60\)

###### Proof\.

Forf∈Σ⁡\(X,E\)f\\in\\Sigma\(X,E\), setf0=\(2​ws\)−30​v​ff\_\{0\}=\(2w\_\{s\}\)^\{\-30v\}f\. By \([59](https://arxiv.org/html/2608.17434#A2.E59)\) and230​v≥230\>105≥Ck2^\{30v\}\\geq 2^\{30\}\>10^\{5\}\\geq C\_\{k\},

‖f0‖∞≤1Ck​MX6​Rm​\(X\)4\.\\left\\lVert f\_\{0\}\\right\\rVert\_\{\\infty\}\\leq\\frac\{1\}\{C\_\{k\}M\_\{X\}^\{6\}R\_\{m\}\(X\)^\{4\}\}\.Thusf0f\_\{0\}belongs to the left side of \([58](https://arxiv.org/html/2608.17434#A2.E58)\)\. Lemma[10](https://arxiv.org/html/2608.17434#Thmtheorem10), withq=\(2​ws\)30​vq=\(2w\_\{s\}\)^\{30v\}, realizes\(2​ws\)30​v​f0=f\(2w\_\{s\}\)^\{30v\}f\_\{0\}=fat the same depth, width at most20​u\+120u\+1, and coefficient magnitude at most2​ws2w\_\{s\}\. ∎

### B\.4Width and depth bookkeeping

The remaining decoder identities and approximation estimates in[Ou et al\. 2024](https://arxiv.org/html/2608.17434#bib.bib12)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](https://arxiv.org/html/2608.17434#Thmtheorem13)changes the two spline widths from40​m40mand40​n40nto40​m\+140m\+1and40​n\+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\)≤200​m\+2n\+5\+5\.\\operatorname\{width\}\(f\_\{1\}\)\\leq 200m\+2^\{n\+5\}\+5\.In the second stage,

width⁡\(u\)≤max⁡\{40​m\+1,40​n\+1\}\+2\.\\operatorname\{width\}\(u\)\\leq\\max\\\{40m\+1,40n\+1\\\}\+2\.Form,n≥2m,n\\geq 2, the first display dominates the second, so the composition off1f\_\{1\}withuuretains the first width bound\. Three parallel copies followed by the fixed median network have width at most

600​m\+3⋅2n\+5\+15≤600​m\+2n\+7\.600m\+3\\cdot 2^\{n\+5\}\+15\\leq 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 constantsC,D1\>0C,D\_\{1\}\>0such that, for all integersW,U≥D1W,U\\geq D\_\{1\}and every continuousg:\[0,1\]→ℝg:\[0,1\]\\to\\mathbb\{R\}with‖g‖∞≤1\\left\\lVert g\\right\\rVert\_\{\\infty\}\\leq 1andLip⁡\(g\)≤1\\operatorname\{Lip\}\(g\)\\leq 1, there isN∈𝒩⁡\(W,U,W2\)N\\in\\mathcal\{N\}\(W,U,W^\{2\}\)satisfying

‖N−g‖∞≤CW2​U2​log⁡W\.\\left\\lVert N\-g\\right\\rVert\_\{\\infty\}\\leq\\frac\{C\}\{W^\{2\}U^\{2\}\\log W\}\.\(61\)

###### Proof\.

The corrected construction just described yields, for integersm,n,ℓ≥2m,n,\\ell\\geq 2,

width⁡\(N\)\\displaystyle\\operatorname\{width\}\(N\)≤600​m\+2n\+7,\\displaystyle\\leq 600m\+2^\{n\+7\},depth⁡\(N\)\\displaystyle\\operatorname\{depth\}\(N\)≤101​ℓ,\\displaystyle\\leq 101\\ell,coeff⁡\(N\)\\displaystyle\\operatorname\{coeff\}\(N\)≤max⁡\{8​m​n,3n\+2\},\\displaystyle\\leq\\max\\\{8mn,3^\{n\+2\}\\\},‖N−g‖∞\\displaystyle\\left\\lVert N\-g\\right\\rVert\_\{\\infty\}≤3m2​ℓ2​n\.\\displaystyle\\leq\\frac\{3\}\{m^\{2\}\\ell^\{2\}n\}\.\(62\)Choose

m=⌊W1000⌋,ℓ=⌊U101⌋,m=\\left\\lfloor\\frac\{W\}\{1000\}\\right\\rfloor,\\qquad\\ell=\\left\\lfloor\\frac\{U\}\{101\}\\right\\rfloor,and letn≥2n\\geq 2be the largest integer such that2n\+7≤W/52^\{n\+7\}\\leq W/5\. For sufficiently largeW,UW,U, one hasm≍Wm\\asymp W,ℓ≍U\\ell\\asymp U, andn≍log⁡Wn\\asymp\\log W\. Moreover,

600​m\+2n\+7≤45​W,101​ℓ≤U,600m\+2^\{n\+7\}\\leq\\frac\{4\}\{5\}W,\\qquad 101\\ell\\leq U,and

8​m​n≤W2,3n\+2≤W28mn\\leq W^\{2\},\\qquad 3^\{n\+2\}\\leq W^\{2\}for all sufficiently largeWW\. Padding unused width and depth places the network in𝒩⁡\(W,U,W2\)\\mathcal\{N\}\(W,U,W^\{2\}\)\. Substituting the parameter choices into \([62](https://arxiv.org/html/2608.17434#A2.E62)\) proves \([61](https://arxiv.org/html/2608.17434#A2.E61)\)\. ∎

### B\.5Proof of Theorem[2](https://arxiv.org/html/2608.17434#Thmtheorem2)

Letm,Dm,Dbe sufficiently large, setm¯=m−1\\overline\{m\}=m\-1, and put

U=⌊D−15⌋\.U=\\left\\lfloor\\frac\{D\-1\}\{5\}\\right\\rfloor\.Proposition[14](https://arxiv.org/html/2608.17434#Thmtheorem14)gives a networkN0∈𝒩⁡\(m¯,U,m¯2\)N\_\{0\}\\in\\mathcal\{N\}\(\\overline\{m\},U,\\overline\{m\}^\{2\}\)with error at mostC/\(m¯2​U2​log⁡m¯\)C/\(\\overline\{m\}^\{2\}U^\{2\}\\log\\overline\{m\}\)\. Apply Corollary[12](https://arxiv.org/html/2608.17434#Thmtheorem12)\. Withr=⌊m/2⌋r=\\lfloor m/2\\rfloorandr2≥m¯r^\{2\}\\geq\\overline\{m\}for sufficiently largemm, the additional depth obeys

J=⌈U​log⁡\(m¯2\)log⁡r⌉≤4​U\+1\.J=\\left\\lceil\\frac\{U\\log\(\\overline\{m\}^\{2\}\)\}\{\\log r\}\\right\\rceil\\leq 4U\+1\.Hence the same function has a unit\-coefficient realization of width at mostmmand depth at mostU\+J≤5​U\+1≤DU\+J\\leq 5U\+1\\leq D\. Sincem¯≍m\\overline\{m\}\\asymp mandU≍DU\\asymp D, the error is at mostCapp/\(m2​D2​log⁡m\)C\_\{\\rm app\}/\(m^\{2\}D^\{2\}\\log m\), proving Theorem[2](https://arxiv.org/html/2608.17434#Thmtheorem2)\.

The fine\-scale bit decoder and its approximation estimate are taken from[Ou et al\. 2024](https://arxiv.org/html/2608.17434#bib.bib12)\. The coefficient\-rescaling steps used to obtain the unit\-coefficient realization have been rederived above under the affine\-layer convention in \([13](https://arxiv.org/html/2608.17434#S2.E13)\)\.

## Appendix CThe grid code and its local geometry

LetM≥8M\\geq 8\. Forz∈\{0,1\}M−1z\\in\\\{0,1\\\}^\{M\-1\}, setz0=zM=0z\_\{0\}=z\_\{M\}=0and lethzh\_\{z\}linearly interpolate\(j/M,zj\)\(j/M,z\_\{j\}\)\. OnIj=\[j/M,\(j\+1\)/M\]I\_\{j\}=\[j/M,\(j\+1\)/M\], writingu=M​x−ju=Mx\-janddj=zj−zj′d\_\{j\}=z\_\{j\}\-z\_\{j\}^\{\\prime\}, we have

hz​\(x\)−hz′​\(x\)=\(1−u\)​dj\+u​dj\+1\.h\_\{z\}\(x\)\-h\_\{z^\{\\prime\}\}\(x\)=\(1\-u\)d\_\{j\}\+ud\_\{j\+1\}\.Therefore

∫Ij\(hz−hz′\)2​𝑑x\\displaystyle\\int\_\{I\_\{j\}\}\(h\_\{z\}\-h\_\{z^\{\\prime\}\}\)^\{2\}\\,\\mathrm\{d\}x=1M​∫01\(\(1−u\)​dj\+u​dj\+1\)2​𝑑u\\displaystyle=\\frac\{1\}\{M\}\\int\_\{0\}^\{1\}\(\(1\-u\)d\_\{j\}\+ud\_\{j\+1\}\)^\{2\}\\,\\mathrm\{d\}u\(63\)=dj2\+dj​dj\+1\+dj\+123​M\.\\displaystyle=\\frac\{d\_\{j\}^\{2\}\+d\_\{j\}d\_\{j\+1\}\+d\_\{j\+1\}^\{2\}\}\{3M\}\.\(64\)Sincea2\+a​b\+b2=12​\(a2\+b2\)\+12​\(a\+b\)2a^\{2\}\+ab\+b^\{2\}=\\tfrac\{1\}\{2\}\(a^\{2\}\+b^\{2\}\)\+\\tfrac\{1\}\{2\}\(a\+b\)^\{2\}, summing and usingd0=dM=0d\_\{0\}=d\_\{M\}=0yields

‖hz−hz′‖22≥dH​\(z,z′\)3​M\.\\left\\lVert h\_\{z\}\-h\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}^\{2\}\\geq\\frac\{d\_\{H\}\(z,z^\{\\prime\}\)\}\{3M\}\.\(65\)
The Varshamov–Gilbert bound\([Tsybakov 2009](https://arxiv.org/html/2608.17434#bib.bib23)\)gives𝒵⊆\{0,1\}M−1\\mathcal\{Z\}\\subseteq\\\{0,1\\\}^\{M\-1\}and universalcVG,cH\>0c\_\{\\rm VG\},c\_\{H\}\>0with

log\|𝒵\|≥cVGM,dH\(z,z′\)≥cHM\(z≠z′\)\.\\log\|\\mathcal\{Z\}\|\\geq c\_\{\\rm VG\}M,\\qquad d\_\{H\}\(z,z^\{\\prime\}\)\\geq c\_\{H\}M\\quad\(z\\neq z^\{\\prime\}\)\.\(66\)
Nowgz=hz/Mg\_\{z\}=h\_\{z\}/Msatisfies‖gz‖∞≤1\\left\\lVert g\_\{z\}\\right\\rVert\_\{\\infty\}\\leq 1andLip⁡\(gz\)≤1\\operatorname\{Lip\}\(g\_\{z\}\)\\leq 1\. Theorem[2](https://arxiv.org/html/2608.17434#Thmtheorem2)givesNzN\_\{z\}\. WithM=⌊c0​m2​D2​log⁡m⌋M=\\lfloor c\_\{0\}m^\{2\}D^\{2\}\\log m\\rfloorandc0≤η/\(2​Capp\)c\_\{0\}\\leq\\eta/\(2C\_\{\\rm app\}\),

‖Qz−hz‖∞=M​‖Nz−gz‖∞≤η,Qz=M​Nz\.\\left\\lVert Q\_\{z\}\-h\_\{z\}\\right\\rVert\_\{\\infty\}=M\\left\\lVert N\_\{z\}\-g\_\{z\}\\right\\rVert\_\{\\infty\}\\leq\\eta,\\qquad Q\_\{z\}=MN\_\{z\}\.Thus, for fixedη<cH/3/4\\eta<\\sqrt\{c\_\{H\}/3\}/4,

‖Qz−Qz′‖2\\displaystyle\\left\\lVert Q\_\{z\}\-Q\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}≥cH/3−2​η,\\displaystyle\\geq\\sqrt\{c\_\{H\}/3\}\-2\\eta,‖Qz−Qz′‖2\\displaystyle\\left\\lVert Q\_\{z\}\-Q\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}≤1\+2​η,‖Qz‖∞≤1\+η\.\\displaystyle\\leq 1\+2\\eta,\\qquad\\left\\lVert Q\_\{z\}\\right\\rVert\_\{\\infty\}\\leq 1\+\\eta\.This proves \([31](https://arxiv.org/html/2608.17434#S5.E31)\) and locality after scaling byλ\\lambda\.

## Appendix DBalanced amplification for the statistical code

Lemma[7](https://arxiv.org/html/2608.17434#Thmtheorem7)is the coefficient\-one specialization of Lemma[10](https://arxiv.org/html/2608.17434#Thmtheorem10); we repeat the matrices to make the lower\-bound dependency self\-contained\.

### D\.1Exact\-depth padding

If an approximating network has depthd<Dd<D, insertD−dD\-didentity hidden layers immediately before the final affine map\. The hidden state is nonnegative, henceh↦ρ⁡\(I​h\)=hh\\mapsto\\rho\(Ih\)=h\. These layers have coefficient magnitude one and do not increase width\.

### D\.2Exact amplification matrices

Write

h1=ρ⁡\(A1​x\+b1\),hℓ=ρ⁡\(Aℓ​hℓ−1\+bℓ\),N=AD​hD−1\+bD\.h\_\{1\}=\\rho\(A\_\{1\}x\+b\_\{1\}\),\\quad h\_\{\\ell\}=\\rho\(A\_\{\\ell\}h\_\{\\ell\-1\}\+b\_\{\\ell\}\),\\quad N=A\_\{D\}h\_\{D\-1\}\+b\_\{D\}\.Forq\>0q\>0, puts=q1/Ds=q^\{1/D\}and define

h~1=ρ⁡\(\[s​A10\]​x\+\[s​b1s\]\)=\[s​h1s\],\\widetilde\{h\}\_\{1\}=\\rho\\\!\\left\(\\begin\{bmatrix\}sA\_\{1\}\\\\ 0\\end\{bmatrix\}x\+\\begin\{bmatrix\}sb\_\{1\}\\\\ s\\end\{bmatrix\}\\right\)=\\begin\{bmatrix\}sh\_\{1\}\\\\ s\\end\{bmatrix\},\(67\)h~ℓ=ρ⁡\(\[s​Aℓs​bℓ0s\]​h~ℓ−1\)=\[sℓ​hℓsℓ\],\\widetilde\{h\}\_\{\\ell\}=\\rho\\\!\\left\(\\begin\{bmatrix\}sA\_\{\\ell\}&sb\_\{\\ell\}\\\\ 0&s\\end\{bmatrix\}\\widetilde\{h\}\_\{\\ell\-1\}\\right\)=\\begin\{bmatrix\}s^\{\\ell\}h\_\{\\ell\}\\\\ s^\{\\ell\}\\end\{bmatrix\},\(68\)for2≤ℓ<D2\\leq\\ell<D, and

N~=\[s​ADs​bD\]​h~D−1=sD​N=q​N\.\\widetilde\{N\}=\\begin\{bmatrix\}sA\_\{D\}&sb\_\{D\}\\end\{bmatrix\}\\widetilde\{h\}\_\{D\-1\}=s^\{D\}N=qN\.\(69\)The width increases by one, depth is unchanged, and the coefficient bound isss, including whenq<1q<1\.

## Appendix ETranslation into deepℛ​BV2\\mathcal\{R\}\\mathrm\{BV\}^\{2\}blocks

### E\.1Coordinatewise ReLU layers

LetT⁡\(x\)=ρ⁡\(A​x\+b\)T\(x\)=\\rho\(Ax\+b\), with rowsai⊤a\_\{i\}^\{\\top\}ofAA\. In the block notation \([6](https://arxiv.org/html/2608.17434#S2.E6)\),

T⁡\(x\)=∑i=1d′ei​ρ​\(ai⊤​x−\(−bi\)\),T\(x\)=\\sum\_\{i=1\}^\{d^\{\\prime\}\}e\_\{i\}\\rho\(a\_\{i\}^\{\\top\}x\-\(\-b\_\{i\}\)\),soK=d′K=d^\{\\prime\}and the variation term is

∑i=1d′‖ei‖1​‖ai‖2=∑i=1d′‖ai‖2≤d′​d​s\.\\sum\_\{i=1\}^\{d^\{\\prime\}\}\\left\\lVert e\_\{i\}\\right\\rVert\_\{1\}\\left\\lVert a\_\{i\}\\right\\rVert\_\{2\}=\\sum\_\{i=1\}^\{d^\{\\prime\}\}\\left\\lVert a\_\{i\}\\right\\rVert\_\{2\}\\leq d^\{\\prime\}\\sqrt\{d\}\\,s\.For the anchor term,

\|Ti​\(0\)\|=\|ρ⁡\(bi\)\|≤s\|T\_\{i\}\(0\)\|=\|\\rho\(b\_\{i\}\)\|\\leq sand, since ReLU is11\-Lipschitz,

\|Ti​\(ej\)−Ti​\(0\)\|≤\|ai​j\|≤s\.\|T\_\{i\}\(e\_\{j\}\)\-T\_\{i\}\(0\)\|\\leq\|a\_\{ij\}\|\\leq s\.Hence

‖T‖ℛ​BV2​\(d,d′\)≤d′​d​s\+d′​\(d\+1\)​s≤3​w2​s\\left\\lVert T\\right\\rVert\_\{\\mathcal\{R\}\\mathrm\{BV\}^\{2\}\(d;d^\{\\prime\}\)\}\\leq d^\{\\prime\}\\sqrt\{d\}\\,s\+d^\{\\prime\}\(d\+1\)s\\leq 3w^\{2\}sford,d′≤wd,d^\{\\prime\}\\leq wandw≥1w\\geq 1\.

For an affine mapT⁡\(x\)=A​x\+bT\(x\)=Ax\+b, takeK=0K=0,C=AC=A, andc0=bc\_\{0\}=b\. Then

‖T‖ℛ​BV2​\(d,d′\)=∑i=1d′\(\|bi\|\+∑j=1d\|ai​j\|\)≤d′​\(d\+1\)​s≤2​w2​s\.\\left\\lVert T\\right\\rVert\_\{\\mathcal\{R\}\\mathrm\{BV\}^\{2\}\(d;d^\{\\prime\}\)\}=\\sum\_\{i=1\}^\{d^\{\\prime\}\}\\left\(\|b\_\{i\}\|\+\\sum\_\{j=1\}^\{d\}\|a\_\{ij\}\|\\right\)\\leq d^\{\\prime\}\(d\+1\)s\\leq 2w^\{2\}s\.Applying these estimates to theD−1D\-1hidden maps and final affine map in Appendix[D](https://arxiv.org/html/2608.17434#A4)proves

𝔙D,m\+1​\(q​N\)≤Ctr​D​\(m\+1\)2​q1/D\\mathfrak\{V\}\_\{D,m\+1\}\(qN\)\\leq C\_\{\\rm tr\}D\(m\+1\)^\{2\}q^\{1/D\}with, for example,Ctr=3C\_\{\\rm tr\}=3under the displayed conventions\.

### E\.2Tent map and circle isometry

The mapr⁡\(t\)=t−2​ρ​\(t−1\)r\(t\)=t\-2\\rho\(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\.\\left\\lVert r\\right\\rVert\_\{\\mathcal\{R\}\\mathrm\{BV\}^\{2\}\(1;1\)\}=\|\-2\|\\,\|1\|\+\|r\(0\)\|\+\|r\(1\)\-r\(0\)\|=3\.Thus one may takeC0=3C\_\{0\}=3\. It satisfies

r⁡\(t\)=t\(0≤t≤1\),r⁡\(t\)=2−t\(1≤t≤2\)\.r\(t\)=t\\quad\(0\\leq t\\leq 1\),\\qquad r\(t\)=2\-t\\quad\(1\\leq t\\leq 2\)\.For any measurableu:\[0,1\]→ℝu:\[0,1\]\\to\\mathbb\{R\},

∫02\|u⁡\(r⁡\(t\)\)\|2​d​t2\\displaystyle\\int\_\{0\}^\{2\}\|u\(r\(t\)\)\|^\{2\}\\frac\{\\,\\mathrm\{d\}t\}\{2\}=12​∫01\|u⁡\(t\)\|2​𝑑t\+12​∫12\|u⁡\(2−t\)\|2​𝑑t\\displaystyle=\\frac\{1\}\{2\}\\int\_\{0\}^\{1\}\|u\(t\)\|^\{2\}\\,\\mathrm\{d\}t\+\\frac\{1\}\{2\}\\int\_\{1\}^\{2\}\|u\(2\-t\)\|^\{2\}\\,\\mathrm\{d\}t=∫01\|u⁡\(x\)\|2​𝑑x\.\\displaystyle=\\int\_\{0\}^\{1\}\|u\(x\)\|^\{2\}\\,\\mathrm\{d\}x\.This proves \([36](https://arxiv.org/html/2608.17434#S6.E36)\)\. Combining the tent block with theDDtranslated blocks gives total depthD\+1=LD\+1=Land width at mostm\+1=wm\+1=w\.

### E\.3Membership of the packed functions

ForFz=λ​M​Nz∘rF\_\{z\}=\\lambda MN\_\{z\}\\circ r, Lemma[7](https://arxiv.org/html/2608.17434#Thmtheorem7)and the preceding block calculation give

𝔙L,w​\(Fz\)≤C0\+Ctr​D​w2​\(λ​M\)1/D\.\\mathfrak\{V\}\_\{L,w\}\(F\_\{z\}\)\\leq C\_\{0\}\+C\_\{\\rm tr\}Dw^\{2\}\(\\lambda M\)^\{1/D\}\.Also

‖Fz‖∞≤λ⁡\(1\+η\)\.\\left\\lVert F\_\{z\}\\right\\rVert\_\{\\infty\}\\leq\\lambda\(1\+\\eta\)\.ThereforeFz∈𝒞L,w​\(A,B\)F\_\{z\}\\in\\mathcal\{C\}\_\{L,w\}\(A,B\)whenever

λ≤B1\+η,λ≤1M​\(\(A−C0\)\+Ctr​D​w2\)D\.\\lambda\\leq\\frac\{B\}\{1\+\\eta\},\\qquad\\lambda\\leq\\frac\{1\}\{M\}\\left\(\\frac\{\(A\-C\_\{0\}\)\_\{\+\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\.\(70\)Universal constant losses in these inequalities are absorbed bycλc\_\{\\lambda\}in \([41](https://arxiv.org/html/2608.17434#S7.E41)\)\.

## Appendix FFano proof of the lower bound

Let𝒵\\mathcal\{Z\}be the code from Appendix[C](https://arxiv.org/html/2608.17434#A3), and defineFzF\_\{z\}by \([35](https://arxiv.org/html/2608.17434#S6.E35)\)\. There are universal constantsa0,a1,a2\>0a\_\{0\},a\_\{1\},a\_\{2\}\>0such that

log⁡\|𝒵\|≥a0​M,a1​λ≤‖Fz−Fz′‖2≤a2​λ,‖Fz‖2≤a2​λ\.\\log\|\\mathcal\{Z\}\|\\geq a\_\{0\}M,\\qquad a\_\{1\}\\lambda\\leq\\left\\lVert F\_\{z\}\-F\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}\\leq a\_\{2\}\\lambda,\\qquad\\left\\lVert F\_\{z\}\\right\\rVert\_\{2\}\\leq a\_\{2\}\\lambda\.\(71\)Choose

λ=cλ​min⁡\{B,σ​Mn,1M​\(\(A−C0\)\+Ctr​D​w2\)D\},\\lambda=c\_\{\\lambda\}\\min\\left\\\{B,\\sigma\\sqrt\{\\frac\{M\}\{n\}\},\\frac\{1\}\{M\}\\left\(\\frac\{\(A\-C\_\{0\}\)\_\{\+\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\\right\\\},wherecλc\_\{\\lambda\}is sufficiently small for \([70](https://arxiv.org/html/2608.17434#A5.E70)\)\. Under thenn\-sample lawPz\(n\)P\_\{z\}^\{\(n\)\}, the design law is common and the conditional responses are independent Gaussians of varianceσ2\\sigma^\{2\}\. Hence

DKL\(Pz\(n\)∥Pz′\(n\)\)\\displaystyle D\_\{\\mathrm\{KL\}\}\(P\_\{z\}^\{\(n\)\}\\\|P\_\{z^\{\\prime\}\}^\{\(n\)\}\)=n𝔼TDKL\(N\(Fz\(T\),σ2\)∥N\(Fz′\(T\),σ2\)\)\\displaystyle=n\\mathbb\{E\}\_\{T\}D\_\{\\mathrm\{KL\}\}\\\!\\left\(N\(F\_\{z\}\(T\),\\sigma^\{2\}\)\\\|N\(F\_\{z^\{\\prime\}\}\(T\),\\sigma^\{2\}\)\\right\)\(72\)=n2​σ2​‖Fz−Fz′‖22≤a22​cλ22​M\.\\displaystyle=\\frac\{n\}\{2\\sigma^\{2\}\}\\left\\lVert F\_\{z\}\-F\_\{z^\{\\prime\}\}\\right\\rVert\_\{2\}^\{2\}\\leq\\frac\{a\_\{2\}^\{2\}c\_\{\\lambda\}^\{2\}\}\{2\}M\.\(73\)Choosecλc\_\{\\lambda\}so the last term is at most\(1/16\)​log⁡\|𝒵\|\(1/16\)\\log\|\\mathcal\{Z\}\|\. With the uniform prior, mutual information is bounded by the average pairwise divergence, and Fano’s inequality\([Tsybakov 2009](https://arxiv.org/html/2608.17434#bib.bib23)\)gives a universal lower bound on the worst\-case codeword error probability\.

Given an arbitrary estimatorf^\\widehat\{f\}, decode by nearest neighbor inL2​\(μ\)L^\{2\}\(\\mu\)\. Whenever‖f^−Fz‖2<a1​λ/2\\left\\lVert\\widehat\{f\}\-F\_\{z\}\\right\\rVert\_\{2\}<a\_\{1\}\\lambda/2, the decoded index iszz\. Markov’s inequality therefore yields

supz∈𝒵𝔼z​‖f^−Fz‖22≥c​λ2\.\\sup\_\{z\\in\\mathcal\{Z\}\}\\mathbb\{E\}\_\{z\}\\left\\lVert\\widehat\{f\}\-F\_\{z\}\\right\\rVert\_\{2\}^\{2\}\\geq c\\lambda^\{2\}\.Taking the infimum over estimators proves Theorem[3](https://arxiv.org/html/2608.17434#Thmtheorem3)\.

### F\.1The sample\-size\-dependent radius corollary

Fix constants0<cσ≤Cσ<∞0<c\_\{\\sigma\}\\leq C\_\{\\sigma\}<\\infty, and letA=B=RA=B=R,cσ​R≤σ≤Cσ​Rc\_\{\\sigma\}R\\leq\\sigma\\leq C\_\{\\sigma\}R,n≥Mn\\geq M, andR≥2​C0R\\geq 2C\_\{0\}\. The output cap is at least a constant multiple ofR​M/nR\\sqrt\{M/n\}\. Further,

λrep≥1M​\(R2​Ctr​D​w2\)D\.\\lambda\_\{\\rm rep\}\\geq\\frac\{1\}\{M\}\\left\(\\frac\{R\}\{2C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\.Condition \([17](https://arxiv.org/html/2608.17434#S3.E17)\), withCradC\_\{\\rm rad\}sufficiently large inside the base of theDDth power, impliesλrep≥c​R​M/n\\lambda\_\{\\rm rep\}\\geq cR\\sqrt\{M/n\}\. Thereforeλ2≍R2​M/n\\lambda^\{2\}\\asymp R^\{2\}M/nand

ℜn∗​\(R,R,σ\)≥c​R2​M/n\.\\mathfrak\{R\}\_\{n\}^\{\*\}\(R,R,\\sigma\)\\geq cR^\{2\}M/n\.ForL,wL,wabove absolute thresholds,D=L−1D=L\-1,m=w−1m=w\-1, and \([15](https://arxiv.org/html/2608.17434#S3.E15)\) implyM≥c​L2​w2​log⁡wM\\geq cL^\{2\}w^\{2\}\\log w\. This proves Corollary[4](https://arxiv.org/html/2608.17434#Thmtheorem4)\.

SinceM3/2/n≤MM^\{3/2\}/\\sqrt\{n\}\\leq Mfor everyn≥Mn\\geq M, condition \([19](https://arxiv.org/html/2608.17434#S3.E19)\) is sufficient uniformly over that sample\-size range\. Taking\(D−1\)\(D\-1\)st roots gives \([20](https://arxiv.org/html/2608.17434#S3.E20)\)\.

## Appendix GProof of the Gaussian upper bound

### G\.1Pseudodimension and covering numbers

The computation graph described in Appendix[A](https://arxiv.org/html/2608.17434#A1)hasWpar=O⁡\(L​w2\)W\_\{\\rm par\}=O\(Lw^\{2\}\)real parameters,O⁡\(L​w\)O\(Lw\)piecewise\-linear units, and computational depthO⁡\(L\)O\(L\)\. The piecewise\-linear network theorem of[Bartlett et al\. 2019](https://arxiv.org/html/2608.17434#bib.bib5)therefore yields

Pdim⁡\(𝒞L,w​\(A,B\)\)≤C​Wpar​L​log⁡\(2​Wpar\)≤C​L2​w2​log⁡\(2​L​w\)\.\\operatorname\{Pdim\}\(\\mathcal\{C\}\_\{L,w\}\(A,B\)\)\\leq CW\_\{\\rm par\}L\\log\(2W\_\{\\rm par\}\)\\leq CL^\{2\}w^\{2\}\\log\(2Lw\)\.\(74\)The norm and output constraints only restrict the unconstrained architecture and hence cannot increase pseudodimension\.

A standard pseudodimension covering theorem\([Haussler 1992](https://arxiv.org/html/2608.17434#bib.bib8);[Anthony and Bartlett 1999](https://arxiv.org/html/2608.17434#bib.bib1)\)states that for every probability measurePPand every\[−B,B\]\[\-B,B\]\-valued class of pseudodimension at mostVV,

log⁡N⁡\(ε,ℱ,L2​\(P\)\)≤C​V​log⁡C​Bε,0<ε≤B\.\\log N\(\\varepsilon,\\mathcal\{F\},L^\{2\}\(P\)\)\\leq CV\\log\\frac\{CB\}\{\\varepsilon\},\\qquad 0<\\varepsilon\\leq B\.\(75\)

### G\.2A finite\-class Gaussian oracle inequality

###### Lemma 15\.

Let𝒢\\mathcal\{G\}be a finite class of functionsg:𝒳→\[−B,B\]g:\\mathcal\{X\}\\to\[\-B,B\], and supposeY=f⋆​\(X\)\+ξY=f^\{\\star\}\(X\)\+\\xiwith\|f⋆\|≤B\|f^\{\\star\}\|\\leq Bandξ∼N⁡\(0,σ2\)\\xi\\sim N\(0,\\sigma^\{2\}\)independent ofXX\. Let

g^∈arg⁡ming∈𝒢​1n​∑i=1n\(Yi−g⁡\(Xi\)\)2\.\\widehat\{g\}\\in\\arg\\min\_\{g\\in\\mathcal\{G\}\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\(Y\_\{i\}\-g\(X\_\{i\}\)\)^\{2\}\.Then

𝔼​‖g^−f⋆‖L2​\(PX\)2≤C​infg∈𝒢‖g−f⋆‖L2​\(PX\)2\+C​\(σ2\+B2\)​log⁡\(2​\|𝒢\|\)n\.\\mathbb\{E\}\\left\\lVert\\widehat\{g\}\-f^\{\\star\}\\right\\rVert\_\{L^\{2\}\(P\_\{X\}\)\}^\{2\}\\leq C\\inf\_\{g\\in\\mathcal\{G\}\}\\left\\lVert g\-f^\{\\star\}\\right\\rVert\_\{L^\{2\}\(P\_\{X\}\)\}^\{2\}\+C\\frac\{\(\\sigma^\{2\}\+B^\{2\}\)\\log\(2\|\\mathcal\{G\}\|\)\}\{n\}\.\(76\)

###### Proof\.

Forg∈𝒢g\\in\\mathcal\{G\}, putdg=g−f⋆d\_\{g\}=g\-f^\{\\star\},rg=P​dg2r\_\{g\}=Pd\_\{g\}^\{2\}, and

Zi​\(g\)=dg​\(Xi\)2−2​ξi​dg​\(Xi\),Zn​\(g\)=1n​∑i=1nZi​\(g\)\.Z\_\{i\}\(g\)=d\_\{g\}\(X\_\{i\}\)^\{2\}\-2\\xi\_\{i\}d\_\{g\}\(X\_\{i\}\),\\qquad Z\_\{n\}\(g\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}Z\_\{i\}\(g\)\.Then𝔼​Zi​\(g\)=rg\\mathbb\{E\}Z\_\{i\}\(g\)=r\_\{g\}, and empirical risk minimization impliesZn​\(g^\)≤Zn​\(g\)Z\_\{n\}\(\\widehat\{g\}\)\\leq Z\_\{n\}\(g\)for everyg∈𝒢g\\in\\mathcal\{G\}\.

Because\|dg\|≤2​B\|d\_\{g\}\|\\leq 2B, the centered random variableZi​\(g\)−rgZ\_\{i\}\(g\)\-r\_\{g\}is sub\-exponential with Bernstein variance proxy

νg2≤C⁡\(σ2\+B2\)​rg\\nu\_\{g\}^\{2\}\\leq C\(\\sigma^\{2\}\+B^\{2\}\)r\_\{g\}\(77\)and scale at mostC⁡\(σ​B\+B2\)C\(\\sigma B\+B^\{2\}\)\. To see \([77](https://arxiv.org/html/2608.17434#A7.E77)\), use𝔼​dg4≤4​B2​rg\\mathbb\{E\}d\_\{g\}^\{4\}\\leq 4B^\{2\}r\_\{g\}for the design term and𝔼​\(2​ξ​dg\)2=4​σ2​rg\\mathbb\{E\}\(2\\xi d\_\{g\}\)^\{2\}=4\\sigma^\{2\}r\_\{g\}for the multiplier term\. The Gaussian conditional moment\-generating function, together with\|dg\|≤2​B\|d\_\{g\}\|\\leq 2B, gives the corresponding sub\-exponential scale\. Bernstein’s inequality and2​u​v≤u/2\+2​v2\\sqrt\{uv\}\\leq u/2\+2vimply that, for eachu\>0u\>0, with probability at least1−2​e−u1\-2e^\{\-u\},

12​rg−C​a​un≤Zn​\(g\)≤32​rg\+C​a​un,a=σ2\+B2\.\\frac\{1\}\{2\}r\_\{g\}\-Ca\\frac\{u\}\{n\}\\leq Z\_\{n\}\(g\)\\leq\\frac\{3\}\{2\}r\_\{g\}\+Ca\\frac\{u\}\{n\},\\qquad a=\\sigma^\{2\}\+B^\{2\}\.\(78\)IncreasingCCabsorbs the scale term becauseσ​B\+B2≤C⁡\(σ2\+B2\)=C​a\\sigma B\+B^\{2\}\\leq C\(\\sigma^\{2\}\+B^\{2\}\)=Ca\.

Apply the lower inequality in \([78](https://arxiv.org/html/2608.17434#A7.E78)\) simultaneously to everyg∈𝒢g\\in\\mathcal\{G\}withu=t\+log⁡\(2​\|𝒢\|\)u=t\+\\log\(2\|\\mathcal\{G\}\|\), and apply the upper inequality to a fixed comparatorg0g\_\{0\}withu=tu=t\. With probability at least1−3​e−t1\-3e^\{\-t\},

12​rg^\\displaystyle\\frac\{1\}\{2\}r\_\{\\widehat\{g\}\}≤Zn​\(g^\)\+C​a​t\+log⁡\(2​\|𝒢\|\)n\\displaystyle\\leq Z\_\{n\}\(\\widehat\{g\}\)\+Ca\\frac\{t\+\\log\(2\|\\mathcal\{G\}\|\)\}\{n\}≤Zn​\(g0\)\+C​a​t\+log⁡\(2​\|𝒢\|\)n\\displaystyle\\leq Z\_\{n\}\(g\_\{0\}\)\+Ca\\frac\{t\+\\log\(2\|\\mathcal\{G\}\|\)\}\{n\}≤32​rg0\+C​a​2​t\+log⁡\(2​\|𝒢\|\)n\.\\displaystyle\\leq\\frac\{3\}\{2\}r\_\{g\_\{0\}\}\+Ca\\frac\{2t\+\\log\(2\|\\mathcal\{G\}\|\)\}\{n\}\.Thus

rg^≤3​rg0\+C​a​2​t\+log⁡\(2​\|𝒢\|\)n\.r\_\{\\widehat\{g\}\}\\leq 3r\_\{g\_\{0\}\}\+Ca\\frac\{2t\+\\log\(2\|\\mathcal\{G\}\|\)\}\{n\}\.Integrating the exponential tail overt≥0t\\geq 0and minimizing overg0g\_\{0\}proves \([76](https://arxiv.org/html/2608.17434#A7.E76)\)\. ∎

### G\.3Completion of Theorem[5](https://arxiv.org/html/2608.17434#Thmtheorem5)

LetVVdenote the right\-hand side of \([74](https://arxiv.org/html/2608.17434#A7.E74)\)\. If\(σ2\+B2\)​V/n≥B2\(\\sigma^\{2\}\+B^\{2\}\)V/n\\geq B^\{2\}, the zero estimator has risk at mostB2B^\{2\}, proving the first branch of \([21](https://arxiv.org/html/2608.17434#S3.E21)\)\. Otherwise set

ε2=\(σ2\+B2\)​Vn<B2\\varepsilon^\{2\}=\\frac\{\(\\sigma^\{2\}\+B^\{2\}\)V\}\{n\}<B^\{2\}and let𝒢\\mathcal\{G\}be anε\\varepsilon\-net inL2​\(μ\)L^\{2\}\(\\mu\)\. By \([75](https://arxiv.org/html/2608.17434#A7.E75)\),

log⁡\|𝒢\|≤C​V​log⁡C​Bε≤C​V​log⁡\(e​n\),\\log\|\\mathcal\{G\}\|\\leq CV\\log\\frac\{CB\}\{\\varepsilon\}\\leq CV\\log\(en\),where the last inequality usesε2≥B2​V/n\\varepsilon^\{2\}\\geq B^\{2\}V/nandV≥1V\\geq 1\. Lemma[15](https://arxiv.org/html/2608.17434#Thmtheorem15)gives

ℜn∗​\(A,B,σ\)≤C​ε2\+C​\(σ2\+B2\)​V​log⁡\(e​n\)n≤C​\(σ2\+B2\)​V​log⁡\(e​n\)n\.\\mathfrak\{R\}\_\{n\}^\{\*\}\(A,B,\\sigma\)\\leq C\\varepsilon^\{2\}\+C\\frac\{\(\\sigma^\{2\}\+B^\{2\}\)V\\log\(en\)\}\{n\}\\leq C\\frac\{\(\\sigma^\{2\}\+B^\{2\}\)V\\log\(en\)\}\{n\}\.Substitute \([74](https://arxiv.org/html/2608.17434#A7.E74)\) to obtain Theorem[5](https://arxiv.org/html/2608.17434#Thmtheorem5)\.

## Appendix HRadius geometry and phase regimes

The lower bound is governed by

λout=B,λstat=σ​M/n,λrep=1M​\(\(A−C0\)\+Ctr​D​w2\)D\.\\lambda\_\{\\rm out\}=B,\\qquad\\lambda\_\{\\rm stat\}=\\sigma\\sqrt\{M/n\},\\qquad\\lambda\_\{\\rm rep\}=\\frac\{1\}\{M\}\\left\(\\frac\{\(A\-C\_\{0\}\)\_\{\+\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\.
### H\.1The sample\-size\-dependent statistical regime

Fix constants0<cσ≤Cσ<∞0<c\_\{\\sigma\}\\leq C\_\{\\sigma\}<\\infty, and letA=B=RA=B=R,cσ​R≤σ≤Cσ​Rc\_\{\\sigma\}R\\leq\\sigma\\leq C\_\{\\sigma\}R,R≥2​C0R\\geq 2C\_\{0\}, andn≥Mn\\geq M\. SinceR−C0≥R/2R\-C\_\{0\}\\geq R/2,

λrep≥1M​\(R2​Ctr​D​w2\)D\.\\lambda\_\{\\rm rep\}\\geq\\frac\{1\}\{M\}\\left\(\\frac\{R\}\{2C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{D\}\.A sufficient condition forλrep≥c​R​M/n\\lambda\_\{\\rm rep\}\\geq cR\\sqrt\{M/n\}is

RD−1≥\(Crad​D​w2\)D​M3/2n,R^\{D\-1\}\\geq\(C\_\{\\rm rad\}Dw^\{2\}\)^\{D\}\\frac\{M^\{3/2\}\}\{\\sqrt\{n\}\},\(79\)where the base constantCradC\_\{\\rm rad\}absorbs2​Ctr2C\_\{\\rm tr\}and the fixed noise\-comparison constants\. This proves Corollary[4](https://arxiv.org/html/2608.17434#Thmtheorem4)\.

For a condition valid simultaneously for everyn≥Mn\\geq M, useM3/2/n≤MM^\{3/2\}/\\sqrt\{n\}\\leq M, obtaining \([19](https://arxiv.org/html/2608.17434#S3.E19)\)\. Taking\(D−1\)\(D\-1\)st roots yields \([20](https://arxiv.org/html/2608.17434#S3.E20)\)\.

### H\.2Representation\-limited behavior

WhenAAis small, the present code gives

ℜn∗≳1M2​\(\(A−C0\)\+Ctr​D​w2\)2​D\.\\mathfrak\{R\}\_\{n\}^\{\*\}\\gtrsim\\frac\{1\}\{M^\{2\}\}\\left\(\\frac\{\(A\-C\_\{0\}\)\_\{\+\}\}\{C\_\{\\rm tr\}Dw^\{2\}\}\\right\)^\{2D\}\.By the block Lipschitz estimate of[Parhi and Nowak 2022](https://arxiv.org/html/2608.17434#bib.bib14),

Lip⁡\(f\)≤∏ℓ=1L‖sℓ‖ℛ​BV2≤\(A/L\)L\.\\operatorname\{Lip\}\(f\)\\leq\\prod\_\{\\ell=1\}^\{L\}\\left\\lVert s\_\{\\ell\}\\right\\rVert\_\{\\mathcal\{R\}\\mathrm\{BV\}^\{2\}\}\\leq\(A/L\)^\{L\}\.Thus smallA/LA/Lcan collapse the class exponentially in depth, showing that a radius condition is structural rather than merely technical\.