PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tao Jiang, Minbo Gao, Shaowei Cai

arXiv:2608.17434v1cs.AI

TL;DR

The paper asks whether depth’s apparent second contribution to statistical complexity is intrinsic or merely a proof artifact. It constructs a localized packing for deep-RBV^2 networks and shows quadratic depth dependence in minimax risk, up to logarithmic factors, under a radius condition.

  • Problem

    The paper investigates whether the depth factor in complexity bounds for norm-constrained ReLU classes reflects information depth can decode or only a proof artifact.

  • Method

    The authors build a local packing using bias-corrected bounded-coefficient approximation and balanced amplification within the explicit vector-valued deep-RBV^2 architecture.

  • Results

    Under the stated radius condition, the minimax risk has quadratic rather than linear polynomial dependence on depth, up to logarithmic factors.

  • Takeaways & Limitations

    The local entropy packing survives the layer-sum variation constraint at the Gaussian testing scale, establishing intrinsic quadratic depth dependence for this architecture.

  • Takeaways & Limitations

    The result targets the explicit vector-valued Parhi–Nowak architecture, while a sharp A-dependent upper bound across all three regimes remains open.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper shows that depth can contribute a genuine second factor to local statistical complexity in a norm-constrained deep-RBV^2 ReLU class. It constructs a localized quadratic-depth packing and derives matching depth dependence in Gaussian regression bounds up to logarithmic factors.

  • Motivation: The central question is whether the second depth factor in generic complexity bounds is an artifact or information that depth can actually decode.The paper distinguishes depth-driven statistical complexity from established representation benefits of deep networks.
  • Construction: A corrected homogeneous-lift construction handles biases exactly while preserving the bounded-coefficient approximation rate up to universal constants.Augmenting hidden states with a constant channel enables homogeneous scaling under affine layers with biases.
  • Lower bound: The radius-explicit minimax lower bound separates output, Gaussian testing, and representation-limited scales, with a sample-size-dependent corollary.The localized code is designed to satisfy both the representation constraint and the Gaussian testing scale.
  • Upper bound: A Gaussian-regression upper bound combines architecture-to-computation-graph control, pseudodimension, population covering, and a finite-class least-squares oracle inequality.The oracle inequality handles Gaussian responses directly.

2 STATISTICAL AND FUNCTION-CLASS SETTING

The section formulates Gaussian regression on the circle using the Parhi–Nowak vector-valued variation-space convention and a depth- and width-indexed ReLU function class. It also fixes the bounded-coefficient standard-network convention used later for approximation.

  • Statistical model: Observations satisfy T_i ∼ µ, Y_i = f⋆(T_i) + ξ_i, with independent ξ_i ∼ N(0, σ^2) and normalized uniform measure on the circle.The circle is identified with t ∈ [0, 2) under µ(dt) = dt/2.
  • Function-class convention: The representation cost uses vector-valued Radon-domain variation-space blocks with K_ℓ ≤ w and permits scalar gains to distribute across layers.Because of this distribution, the resulting functional is not one-homogeneous.
  • Function-class convention: The deep variation architecture class is C_L,w(A, B) = {f : [0, 2) → R : V_L,w(f) ≤ A, ∥f∥∞ ≤ B}.Continuous endpoint identification is imposed when the functions are periodized.
  • Statistical model: The motivating normalization sets A = B = R and σ ≍ R.The section frames the target risk as R*_n(C_L,w(A, B), σ).
  • Network convention: Standard networks N(W, D, B) count depth through affine maps including the final output layer, with hidden width at most W and coefficients bounded by B.This is the convention used in the bounded-coefficient approximation result.

3 MAIN RESULTS

The main results establish a radius-explicit local packing lower bound with quadratic depth dependence and match it, up to logarithmic factors, with a Gaussian pseudodimension upper bound. The lower bound is statistical-regime dependent because small layer-sum budgets can collapse the class.

  • Radius-explicit lower bound: Theorem 3 gives a radius-explicit lower bound based on output, Gaussian testing, and representation-limited amplification scales.The three terms correspond respectively to the output cap, Gaussian testing scale, and representation-limited amplification scale.
  • Radius-explicit lower bound: The local packing has codewords with L2 norm at most Cλ and pairwise separation at least cλ.This establishes locality and separation at the packing amplitude λ.
  • Quadratic-depth regime: Corollary 4 identifies a sample-size-dependent statistical regime under A = B = R and σ proportional to R, yielding the quadratic-depth lower-bound behavior.The regime assumes n ≥ M, R ≥ 2C0, and cσR ≤ σ ≤ CσR.
  • Upper bound and comparison: Theorem 5 supplies a Gaussian pseudodimension upper bound, and under Corollary 4 the remaining discrepancy is logarithmic.The stated conclusion is that the polynomial depth exponent is quadratic.
  • Radius condition: The radius condition is structural: a small layer-sum budget can collapse the nonconstant part of the class, invalidating an all-radius lower bound proportional to L^2w^2B^2/n.The limitation follows from the Parhi–Nowak Lipschitz estimate and AM–GM.

4 WHERE THE EXTRA DEPTH FACTOR LIVES

The quadratic depth term arises from ordered pairs of a perturbed layer and a downstream amplification layer in layerwise entropy calculations. A function-space packing shows this complexity is necessary locally, with entropy scaling as Ω(L^2w^2 log w).

  • Ordered-pair structure: Θ(L^2w^2) arises from ordered pairs of a perturbed layer and a downstream amplification layer when p ≍ w^2.This identifies where the second depth factor enters the layerwise covering calculation.
  • Function-space lower bound: The packing supplies a function-space lower bound because global parametrization could otherwise avoid the ordered-pair bookkeeping of layerwise covering arguments.The construction establishes necessity rather than merely reproducing the upper-bound calculation.
  • Function-space lower bound: Ω(L^2w^2 log w) packing entropy occurs at active amplitude λ, with codewords in an O(λ) ball and pairwise Ω(λ) separation.This rules out a uniform localized covering-entropy upper bound of order O(Lw^2) in the statistical regime.
  • Proof mechanism: The constant channel repairs coefficient rescaling and amplifies the statistical code without concentrating gain in one layer.It is used twice in the proof mechanism.

5 A DEPTH-ENABLED LOCAL CODE

This section constructs a local code from piecewise-linear interpolants and establishes its required cardinality and local geometry. The remaining step is amplification to scale λ while preserving the layer-sum budget.

  • Code construction: The construction interpolates binary codewords on a grid to obtain bounded, 1-Lipschitz functions.For z ∈ {0,1}^{M−1}, the interpolant satisfies ∥h_z∥∞ ≤ 1 and Lip(h_z) ≤ M, while g_z = h_z/M is bounded and 1-Lipschitz.
  • Code construction: M = ⌊c_0m^2D^2 log m⌋ specifies the code scale for the rescaled functions Q_z.The statement assumes sufficiently small c_0; a fixed small universal η also appears in the construction.
  • Amplification: The code has the required cardinality and local geometry, but must still be amplified to scale λ without exhausting the layer-sum budget.This explicitly identifies amplification as the remaining task after the local code construction.

6 BALANCED AMPLIFICATION AND RBV2 TRANSLATION

Balanced amplification realizes qN at depth D with coefficient magnitude at most q^(1/D), while translating each ReLU layer into an allowed vector-valued RBV^2 block costs O(w^2s). These representation bounds are then combined with output and Gaussian testing constraints.

  • Balanced amplification: q = λM distributes the required gain across depth instead of charging order q to one final-layer block.The augmented state transports the scaled biases, and the final affine map returns qN.
  • Balanced amplification: qN admits a depth-D, width-at-most-(m + 1) realization with coefficient magnitude at most q^(1/D).The construction uses a constant homogeneous coordinate to transport scaled biases while preserving exact depth.
  • RBV2 translation: A width-at-most-w ReLU layer with coefficient bound s translates into an allowed vector-valued block with at most w atoms and ∥T∥RBV2 ≤ Cw^2s.The same estimate holds for an affine output map.
  • RBV2 translation: The representation step is combined with the output and Gaussian testing constraints.Equation (37) completes the representation step before these constraints are applied.

7 FROM THE LOCAL CODE TO THE MINIMAX LOWER BOUND

The section selects the largest amplitude satisfying output, layer-sum, and Gaussian-testing constraints, then uses the resulting local separated code with Fano’s inequality to prove the minimax lower bound. Under Corollary 4’s conditions, the bound specializes to λ^2 ≍ R^2M/n.

  • Amplitude selection: Three restrictions jointly determine the admissible amplitude: output cap, layer-sum budget, and Gaussian testing scale.The output constraint requires λ ≲ B, while the layer-sum constraint applies when A > C0; for A ≤ C0, the theorem records a trivial lower bound.
  • Minimax lower bound: Fano’s inequality and nearest-neighbor decoding yield risk Ω(λ^2), proving Theorem 3.The testing restriction makes the divergence sufficiently small relative to M ≲ log |Z|.
  • Amplitude selection: Up to universal constants, equation (41) gives the largest amplitude compatible with all three restrictions.This amplitude is obtained after combining the output, representation, and testing constraints.
  • Local packing: The constructed family is local and pairwise separated at the chosen amplitude, while the reduced functions belong to CL,w(A, B).Equations (28), (31), (36), and (37) establish the output, representation, locality, and separation properties.
  • Corollary 4: Under Corollary 4’s conditions, λ^2 ≍ R^2M/n.For n ≥ M and R ≥ 2C0, the testing amplitude is at most a constant multiple of R, and the uniform condition (19) follows.

8 A GAUSSIAN UPPER BOUND WITHOUT BOUNDED RESPONSES

This section derives a Gaussian upper bound for the same architecture to match the lower bound’s polynomial depth dependence. It uses computation-graph and pseudodimension controls together with Gaussian multiplier/Bernstein analysis, including unbounded responses.

  • The upper-bound argument targets the same architecture to match the lower bound in polynomial dependence on depth.
  • Every function is represented by a piecewise-linear computation graph with O(Lw^2) real parameters and computational depth O(L).
  • The proof handles vector-valued blocks, affine skips, and variable intermediate dimensions before applying the piecewise-linear pseudodimension theorem.
  • Least-squares estimation over a finite [−B, B]-valued class is analyzed under Gaussian regression using a population-L2 ε-net.
  • The Gaussian multiplier/Bernstein argument applies directly to unbounded Gaussian responses, and optimizing the net radius yields Theorem 5.Together with Corollary 4, Theorem 5 fixes the polynomial depth exponent and motivates interpreting output, testing, and representation scales.

9 CONSEQUENCES AND OPEN DIRECTIONS … B.4 Width and depth bookkeeping

The paper establishes quadratic-in-depth localized entropy for the explicit vector-valued architecture and explains its radius-dependent statistical and representation-limited regimes. Appendices justify the architecture bookkeeping and repair bounded-coefficient approximation without changing the asymptotic width bounds.

  • 9.1 Radius dependence of the lower bound: Under A = B = R and σ ≍ R, the statistical regime yields risk Ω(σ^2M/n), while output limitation instead saturates at B^2.Theorem 3 compares output, statistical, and representation amplitudes.
  • 9.1 Radius dependence of the lower bound: A small A/L can collapse the class exponentially with depth, making the radius transition reflect class geometry rather than only proof technique.Equation (48) identifies where the layer-sum budget blocks the code from reaching Gaussian testing scale.
  • 9.2 Limitations and open questions; A ARCHITECTURE CONVENTIONS AND COMPUTATION-GRAPH REALIZATION: The main open problems are closing the log w versus log(Lw) log n gap, treating smallest widths, understanding finite-precision transitions, and obtaining sharp A-dependent upper bounds.The architecture distinction also matters: the explicit vector-valued model has O(Lw^2) parameters, unlike a scalar chain with O(Lw).
  • A.1 Vector-valued class and relation to the motivating formulation: The explicit Parhi–Nowak construction composes vector-valued maps with d0 = dL = 1, dℓ≤w, and Kℓ≤w, matching the motivating O(Lw^2) parameterization.This distinguishes the analyzed architecture from the scalar-to-scalar chain.
  • A.2 Exact parameter count; A.3 Proof of Lemma 9: Each block uses at most 3w^2 + 2w scalar parameters, yielding an O(Lw^2) computation graph with at most Lw ReLU gates and computational depth at most 2L.Affine skips can be represented with constant-factor overhead, preserving these asymptotic bounds.
  • A.4 Circle coordinate and representation cost: Representation cost is not generally one-homogeneous: distributing scalar gain q across D stages costs proportional to Dq^(1/D), so arguments use the representation-cost definition.The circle coordinate periodizes continuously through the tent map.
  • B A BIAS-CORRECTED BOUNDED-COEFFICIENT APPROXIMATION THEOREM; B.1 The affine-bias obstruction and its repair; B.2 Trading coefficient magnitude for depth; B.3 Repairing the bounded-spline realization; B.4 Width and depth bookkeeping: A constant homogeneous channel repairs affine-bias scaling, while balanced amplification and corrected spline calls preserve coefficient control and the original asymptotic width bound.The width changes from 40m and 40n to 40m + 1 and 40n + 1, and the terminal estimate remains valid.

B.5 Proof of Theorem 2 … F FANO PROOF OF THE LOWER BOUND

The proof builds a depth-dependent packing by combining grid-code geometry, balanced network amplification, and translation into deep RBV^2 blocks. Gaussian Fano then converts the packing’s separation and divergence control into the lower bound of Theorem 3.

  • B.5 Proof of Theorem 2: Theorem 2 obtains error at most C_app/(m^2D^2 log m) with unit-coefficient width at most m and depth at most D.The construction uses Proposition 14, Corollary 12, and the comparisons m ≍ m and U ≍ D.
  • C THE GRID CODE AND ITS LOCAL GEOMETRY: The grid code uses M = ⌊c0m^2D^2 log m⌋ and, after scaling by λ, produces local codewords with controlled norms and pairwise separation.The preceding estimates give ∥Q_z − Q_z′∥_2 ≤ 1 + 2η and ∥Q_z∥_∞ ≤ 1 + η before scaling.
  • D.1 Exact-depth padding: Exact-depth padding inserts D − d identity ReLU layers without increasing width or introducing coefficients larger than one.Nonnegative hidden states make ρ(Ih) = h.
  • D BALANCED AMPLIFICATION FOR THE STATISTICAL CODE / D.2 Exact amplification matrices: Balanced amplification implements qN using coefficient bound s = q^(1/D), increasing width by one while leaving depth unchanged.The construction remains valid when q < 1.
  • E TRANSLATION INTO DEEP RBV2 BLOCKS / E.1 Coordinatewise ReLU layers: Affine maps translate into coordinatewise ReLU blocks under the stated block notation, with a representative translation constant C_tr = 3.For T(x) = Ax + b, the block parameters take K = 0, C = A, and c_0 = b.
  • E.2 Tent map and circle isometry: The tent map r(t) = t − 2ρ(t − 1) combines with D translated blocks to give total depth D + 1 = L and width at most m + 1 = w.On [0,1], r(t) = t; on [1,2], r(t) = 2 − t.
  • E.3 Membership of the packed functions: The packed functions F_z = λM N_z ◦ r satisfy the required block bounds after universal constant losses are absorbed into c_λ.The construction uses the code from Appendix C and chooses c_λ sufficiently small for the stated membership condition.
  • F FANO PROOF OF THE LOWER BOUND: Gaussian Fano bounds the lower error probability by controlling pairwise divergence and decoding arbitrary estimators by nearest neighbor in L2(µ).The divergence is bounded by a2^2 c_λ^2 M, and c_λ is chosen so it is at most (1/16) log |Z|.

F.1 The sample-size-dependent radius corollary … H.2 Representation-limited behavior

The paper establishes a sample-size-dependent regime where the deep-RBV^2 lower bound is valid and derives a pseudodimension-based Gaussian upper bound. It also identifies a representation-limited regime in which small variation budgets can collapse the class exponentially with depth.

  • F.1 The sample-size-dependent radius corollary: The radius condition implies λ_rep ≥ cR when A = B = R and the noise scale is proportional to R.The assumptions include cσR ≤ σ ≤ CσR, n ≥ M, and R ≥ 2C0.
  • F.1 The sample-size-dependent radius corollary: M ≥ cL^2w^2 log w is sufficient for the sample-size-dependent radius corollary.This follows for L and w above absolute thresholds with D = L − 1 and m = w − 1.
  • G.1 Pseudodimension and covering numbers: The architecture has W_par = O(Lw^2) parameters, O(Lw) piecewise-linear units, and computational depth O(L).These quantities feed the Bartlett et al. piecewise-linear network theorem used for pseudodimension control.
  • G.1 Pseudodimension and covering numbers: Norm and output constraints cannot increase the pseudodimension, so covering bounds apply to the constrained architecture through the unconstrained class.The covering theorem is stated for bounded function classes with finite pseudodimension.
  • G.2 A finite-class Gaussian oracle inequality: Lemma 15 provides a finite-class Gaussian oracle inequality for bounded predictors under independent N(0, σ^2) noise.Its proof combines sub-exponential control, Bernstein’s inequality, simultaneous comparison over the finite class, and optimization over a comparator.
  • H.2 Representation-limited behavior: Small A/L can collapse the representation class exponentially in depth, making the radius condition structural rather than merely technical.This is shown using the present code and the Parhi–Nowak block Lipschitz estimate.
Loading 2608.17434v1…