Technical Summary: Deep Neural Variation Spaces

Problem Statement

The theoretical understanding of depth in deep neural networks remains incomplete. While empirical evidence suggests that depth enhances representational capacity, existing theoretical frameworks largely rely on parameter-based complexity measures (e.g., width, total parameter count, or sum-of-squared-weights). These measures often fail to capture the effective complexity of learned predictors, particularly in overparameterized regimes where the number of parameters exceeds the data size. Furthermore, existing function space theories for deep networks are fragmented, often specialized to homogeneous activations (like ReLU), and utilize disparate notions of complexity that are difficult to compare. A unified perspective is needed to distinguish between functional complexity arising from the repeated composition of nonlinearities versus complexity arising merely from compounded linear rescaling across layers.

Methodology

The authors develop a unified function space theory for deep fully connected neural networks, termed Deep Neural Variation Spaces ($V_L$). The core methodology involves the following steps:

1. Normalized Activation Functions: To handle both homogeneous (e.g., ReLU) and non-homogeneous (e.g., GELU, SiLU) activations uniformly, the authors introduce a family of normalized activation functions $\sigma_s(t) = \sigma(st)/s$ (or $\sigma(st)/s^m$ for degree-$m$ homogeneous functions). This separates the "shape" of the feature from its "size," ensuring that features with different scales incur a norm cost proportional to their Lipschitz constant.
2. Recursive Construction: The function spaces are defined recursively. The base layer $B_1$ consists of a dictionary of affine functions. Subsequent layers $B_L$ are defined as the closed absolutely convex hull of compositions $\sigma_s \circ f$, where $f \in B_{L-1}$.
3. Variational Norms: The space $V_L$ is equipped with an atomic (or gauge) norm $\|f\|_{V_L}$, defined as the infimum of $c > 0$ such that $f \in cB_L$. This norm measures the "cost" of representing a function as a convex combination of activated functions from the previous layer.
4. Integral Representations: The authors establish that functions in $V_L$ admit integral representations with respect to finite measures over the space of previous-layer functions and scaling parameters. This connects the deep spaces to generalized Barron spaces and neural tree spaces.
5. Comparison with Existing Costs: The proposed norm is compared against other representation costs, including the sum-of-squared-weights (SOSW) and various group norms ($\ell_{2,1}$, $\ell_{1,1}$). The authors demonstrate that their norm is a true Banach norm on the function space, whereas many existing costs act as quasi-norms or additive penalties that do not properly account for the exponential amplification of function output due to layerwise rescaling.

Key Contributions

1. Unified Framework for General Activations: The paper provides a single function-space framework applicable to a broad family of continuous activation functions, including non-homogeneous ones. It proves that for many "ReLU-like" activations (Leaky ReLU, GELU, SiLU, etc.), the induced function spaces are norm-equivalent to the ReLU space, with explicit depth-dependent bounds on the equivalence constants.
2. Novel Representer Theorem: The authors prove a representer theorem showing that solutions to norm-penalized data-fitting problems over $V_L$ are realized by width-bounded neural networks. Specifically, for homogeneous activations, the solution is a finite-width network; for non-homogeneous activations, the solution may involve limiting atoms ($\sigma_0, \sigma_\infty$) but remains width-bounded.
3. Function-Space Complexity Bounds: Novel bounds are derived for the worst-case empirical Rademacher complexity and $L_p(\mu)$ metric entropies of the unit balls $B_L$. These bounds grow only mildly with depth (often polynomially or linearly in $L$, and in many cases independent of $L$ for 1-Lipschitz activations), contrasting with the exponential growth often implied by parameter-count-based analyses.
4. Depth Saturation Result: In the univariate ReLU case, the authors prove a "depth saturation" theorem: the deep unit balls satisfy $B_2 \subset B_L \subset 2B_2$ for all $L \ge 2$. This implies that depth adds no new functional diversity beyond a constant rescaling of the shallow class.
5. Frequency Control: As a consequence of the univariate saturation result, the authors show that multivariate functions in deep norm-constrained ReLU classes cannot exhibit high frequencies along any individual direction of the input domain.

Key Results

• Norm Equivalence: For a wide range of activations (Leaky ReLU, GELU, SiLU, Mish, etc.), the deep variation spaces $V_L^\sigma$ are norm-equivalent to the ReLU space $V_L^{\text{ReLU}}$. However, the equivalence constants may grow with depth for non-homogeneous activations.
• Complexity Bounds:
  • Rademacher Complexity: The complexity grows at most as $\sqrt{L}$ (or $L$ for non-1-Lipschitz activations) up to polylogarithmic factors, and is independent of network width.
  • Metric Entropy: The metric entropy of the unit balls $B_L$ is bounded similarly, growing mildly with depth. Lower bounds derived from shallow classes ($B_2$) show that the gap between upper and lower bounds is small for high input dimensions.
• Depth Saturation (Univariate ReLU): The paper proves that for univariate ReLU networks, increasing depth does not expand the set of representable functions beyond a constant factor (specifically, a factor of 2) of the shallow class $B_2$. Functions like the Telgarsky sawtooth function, often cited as evidence of depth's power, require exponentially large weights (in the function space norm) to be represented, effectively negating the benefit of depth when complexity is controlled by norm rather than neuron count.
• Frequency Constraints: Functions in multivariate deep ReLU classes must exhibit low frequencies along any line in the input domain. If a function's restriction to a line has a second-derivative total variation exceeding a specific constant, it cannot be represented in any deep norm-bounded ReLU class.

Significance and Claims

The paper claims that a function-space perspective yields new structural insights into the relationship between depth and complexity. The primary significance lies in demonstrating that many "depth separation" results—where deep networks are claimed to represent high-frequency or complex functions more efficiently than shallow ones—rely on representational cost measures (like parameter count or SOSW) that fail to penalize the compounded rescaling of weights across layers.

When complexity is controlled by a true function-space norm (which accounts for the magnitude of the function output), the authors argue that the structural advantages of depth are far more limited than previously thought. Specifically:

• Depth does not inherently generate new functional shapes in the univariate ReLU case; it only allows for rescaling.
• The ability of deep networks to represent high-frequency functions is contingent on allowing weights to grow exponentially with depth, which is penalized by the proposed norm.
• The inductive bias of norm-controlled deep networks is one of frequency control along all directions, rather than the ability to generate arbitrary high-frequency oscillations.

The authors conclude that while depth may offer benefits in specific contexts, these benefits disappear when the network's complexity is measured by a norm that properly controls the function's magnitude, suggesting that the "expressivity" of depth is often an artifact of unconstrained parameter scaling rather than the repeated application of nonlinearity.