PaperlayerView exact revision on arXiv

Source-linked AI summary

A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case

Greg Ongie, Rebecca Willett, Daniel Soudry, Nathan Srebro

arXiv:1910.01635v1cs.LGstat.ML

TL;DR

The paper addresses how to characterize the norm and function class induced by infinite-width, single-hidden-layer ReLU networks when weight magnitude—not width—controls complexity. It develops a Radon-transform-based function-space characterization, showing which multivariate functions have finite representational cost and deriving consequences for smoothness, depth, and the distinction from kernel learning.

  • Problem

    Existing approximation theory often emphasizes network size, while the relevant model class for overparameterized networks may instead be determined by the minimal weight norm needed to represent a function.

  • Method

    The paper defines a rigorous representational-cost seminorm for multivariate functions using the Radon transform and a Laplacian-based functional, extending the infinite-width ReLU framework beyond classical smooth cases.

  • Results

    The characterization shows that W^(d+1),1(R^d) functions have finite cost, finite-support radial bumps can have finite cost, generic compactly supported piecewise-linear functions have infinite cost, and a depth separation exists in norm.

  • Takeaways & Limitations

    Representational cost captures the inductive bias of bounded-norm infinite-width ReLU learning and differs fundamentally from any kernel RKHS norm.

  • Takeaways & Limitations

    The multivariate characterization is less simple than the univariate one, and the paper does not rule out every compactly supported piecewise-linear function having finite R-norm.

Abstract

from arXiv · show

A key element of understanding the efficacy of overparameterized neural networks is characterizing how they represent functions as the number of weights in the network approaches infinity. In this paper, we characterize the norm required to realize a function $f:\mathbb{R}^d\rightarrow\mathbb{R}$ as a single hidden-layer ReLU network with an unbounded number of units (infinite width), but where the Euclidean norm of the weights is bounded, including precisely characterizing which functions can be realized with finite norm. This was settled for univariate univariate functions in Savarese et al. (2019), where it was shown that the required norm is determined by the L1-norm of the second derivative of the function. We extend the characterization to multivariate functions (i.e., networks with d input units), relating the required norm to the L1-norm of the Radon transform of a (d+1)/2-power Laplacian of the function. This characterization allows us to show that all functions in Sobolev spaces $W^{s,1}(\mathbb{R})$, $s\geq d+1$, can be represented with bounded norm, to calculate the required norm for several specific functions, and to obtain a depth separation result. These results have important implications for understanding generalization performance and the distinction between neural networks and more traditional kernel learning.

1 INTRODUCTION

The paper reframes complexity and generalization for effectively infinite-width networks in terms of weight magnitude and representational cost rather than parameter count. It extends the univariate characterization of bounded-norm ReLU networks to multivariate functions using the Radon transform and derives consequences for smoothness, bumps, piecewise-linear functions, depth, and kernel comparisons.

  • Motivation: Weight magnitude, rather than network size, is presented as the relevant complexity control for generalization and inductive bias.The paper motivates studying the minimal weight norm required to represent a function in effectively infinite-width networks.
  • Problem: The paper asks how large a norm is necessary to represent target functions when network width is unbounded.This reframes approximation theory around the magnitude of weights instead of the number of units.
  • Method: The multivariate characterization uses a Radon-transform-based functional that rigorously captures representational cost, including when classical derivatives are not well-defined.The construction defines a seminorm that can be finite or infinite and precisely captures the cost.
  • Implications: The multivariate characterization shows that bounded-norm neural-network learning is fundamentally different from kernel learning because no RKHS norm matches the proposed cost.The cited prior work connects Radon transforms to approximation theory and ridgelet analysis, while the paper extends the representational-cost perspective to multivariate networks.
  • Consequences: W^(d+1),1(R^d) functions have finite representational cost, with the required smoothness increasing with dimension.The cost can be bounded using the Sobolev norm.
  • Consequences: Finite-support radial bumps can have finite cost, sharp fixed-height bumps cost 1/ε, and generic compactly supported piecewise-linear functions have infinite cost.The paper also gives a two-dimensional depth separation: a depth-three ReLU network has small finite norm, whereas no bounded-norm depth-two network represents the same function.

2 INFINITE WIDTH RELU NETWORKS

The paper defines representational cost for unbounded-width two-layer ReLU networks through limiting approximations and an equivalent measure-based formulation. Adding an unregularized linear unit isolates the costly nonlinear component and yields a unique measure characterization of the cost.

  • Normalization: ReLU homogeneity converts the Euclidean weight-cost problem into unit-norm inner weights with an ℓ1 penalty on outer weights.This normalization is the basis for the measure representation.
  • Representational cost: The finite-width cost is insufficient for general functions, so the paper defines cost through sequences of networks converging uniformly on expanding balls while matching the target at zero.This extends the representation class beyond finite piecewise-linear networks.
  • Measure formulation: An infinite-width ReLU network is represented by a signed measure over unit directions and biases, with finite total variation acting as the outer-weight norm.The measure formulation corresponds to integrating ReLU units over weight-bias pairs.
  • Interpretation: The resulting function-space cost captures the inductive bias of learning with unbounded-width ReLU networks under weight regularization.Controlling the network’s weight norm is thereby equivalent to controlling the function-level representational cost.
  • Linear unit: An unregularized linear unit absorbs the linear component, allowing the representational cost to focus on absolute-value or nonlinear units.The same construction is used in the infinite-width formulation hα,v,c(x)=hα,c(x)+v⊤x.
  • Uniqueness: The minimizer of the measure-based cost is unique and is given by the total variation norm of the unique even measure representing the function.The paper states that this measure, together with the linear and constant terms, uniquely characterizes the representation.

3 THE RADON TRANSFORM AND ITS DUAL

The Radon transform represents a function through integrals over hyperplanes indexed by direction and offset, while its dual integrates over hyperplanes passing through each point. In the paper, Radon inversion and Fourier-domain Laplacian identities provide the analytic machinery for characterizing representational cost.

  • Radon transform: The Radon transform integrates f over hyperplanes w⊤x=b, parameterized by unit normal w and signed offset b.The transform is even because (w,b) and (−w,−b) describe the same hyperplane.
  • Dual transform: The dual Radon transform maps a function of direction and offset back to x-space by integrating over all hyperplanes passing through x.This is the adjoint operation used in the inversion framework.
  • Inversion: Radon inversion combines the dual transform with a (d−1)/2-power of the negative Laplacian in Fourier domain.For odd dimensions this fractional power reduces to repeated applications of the usual Laplacian; for even dimensions it is pseudodifferential.
  • Geometric interpretation: The Radon transform of point masses traces curves in direction-offset space, and superpositions produce sinograms by summing those curves.Figure 1 illustrates this construction in two dimensions.
  • Fourier relations: The Fourier slice theorem links one-dimensional Fourier transforms in the offset variable to the d-dimensional Fourier transform of the original function.This identity yields the intertwining relation between the Laplacian and derivatives with respect to the offset.
  • Conditions: The inversion identities require function-space assumptions such as integrability, evenness, or Schwartz regularity, depending on the formula used.For odd dimensions, offset derivatives can also be expressed using the Hilbert transform.

4 REPRESENTATIONAL COST IN FUNCTION SPACE: THE R-NORM

The paper defines the R-norm to extend representational-cost analysis to nonsmooth multivariate functions and proves that it equals the infinite-width ReLU representational cost. It relates this cost to a filtered Radon transform, establishes finiteness criteria and bounds, and derives scaling and smoothness consequences.

  • Computing representational cost: For sufficiently regular functions, the representational cost is γ_d times the L1-norm of the Radon transform of (−∆)^(d+1)/2f.For odd dimensions, the result applies when f and ∆^(d+1)/2f are integrable; even dimensions require the corresponding pseudo-differential operators.
  • Defining the R-norm: The authors define the R-norm by duality for all Lipschitz functions, including cases where classical derivatives or Radon transforms are undefined.The functional is a seminorm rather than a norm, and it is finite only on a subset of Lipschitz functions.
  • Characterization: Theorem 1 proves that R1(f) = ∥f∥R for every function, so finite representational cost is equivalent to Lipschitz continuity with finite R-norm.The construction is illustrated by applying the fractional negative Laplacian, then the Radon transform, whose scaled L1-norm gives the R-norm.
  • Unregularized linear units: Theorem 2 shows that the cost without an unregularized linear unit is finite exactly when the R-norm is finite, with bounds involving ∥f∥R and the gradient at infinity.The upper bound can be attained nontrivially, so the lower-bound expression does not always give the exact cost.
  • Scaling and smoothness: The R-norm scales as ε^-1 under the contraction fε(x) = f(x/ε), causing fixed-height sharp bumps to have diverging representational cost as ε approaches zero.This scaling supports the role of the norm in discouraging spike-like minimum-norm fits and reflects dependence on derivatives of order d + 1.
  • Scaling and smoothness: Finite R-norm additionally requires rapid Fourier decay along every ray for a broad class of functions.This gives a Fourier-domain expression of the smoothness requirements imposed by the representational-cost characterization.

5 CONSEQUENCES, APPLICATIONS AND DISCUSSION

The paper develops consequences of the multivariate R-norm characterization, including smoothness conditions for finite cost, radial-bump scaling, piecewise-linear obstructions, and a qualitative depth separation. It also shows that the R-norm is not an RKHS norm.

  • Multivariate R-norm characterization is often easy to evaluate, but is less simple than the univariate characterization.
  • Functions in W^{d+1,1}(R^d) have finite R-norm, bounded by a dimension-dependent constant times their Sobolev norm.For odd d, the bound is ∥f∥R ≤ c_dγ_d∥f∥W^{d+1,1}.
  • Radial bump functions: For radial functions, finite R-norm follows when the weak derivative of order (d+1)/2 of the radial profile exists and has bounded variation.
  • Radial bump functions: Radial bumps with profile (1−r^2)^k have finite R-norm exactly when k ≥ (d+1)/2, with a contraction to radius ε scaling as approximately d^2/ε for a specified choice of k.
  • Piecewise-linear functions: A compactly supported continuous piecewise-linear function has infinite R-norm under specified nonparallel-boundary or convexity conditions.The paper states that condition (a) is generic under small perturbations, while not ruling out every exceptional case.
  • Depth separation: The pyramid function has infinite two-layer representational cost but an exact finite-width three-layer representation, yielding qualitative depth separation.The two-layer norm is infinite rather than merely large, whereas the three-layer representation has finite norm.
  • The R-norm is not an RKHS norm, so bounded-norm neural-network training is fundamentally different from kernel learning.

A INFINITE-WIDTH NETS

The paper models infinite-width two-layer ReLU networks using finite-total-variation measures over directions and offsets. Even-measure reductions and a Lipschitz bound establish the basic function-space structure.

  • An infinite-width ReLU network is defined by integrating a shifted ReLU over a signed measure on S^{d−1}×R with finite total variation.
  • The shifted-ReLU definition is always well-defined for finite-total-variation measures, unlike the original formulation’s finite-first-moment restriction.
  • Every measure decomposes uniquely into even and odd parts, and the odd component can be absorbed into the network’s affine term.
  • Restricting to even measures loses no generality for representing infinite-width networks.
  • Every infinite-width network is Lipschitz, with Lipschitz constant at most the measure’s total variation norm plus the affine slope norm.The bound is ∥f∥L ≤ ∥α∥1 + ∥v∥.

B OPTIMIZATION CHARACTERIZATION OF REPRESENTATIONAL COST

The paper identifies representational costs with optimization over measure-based infinite-width networks and connects them to limits of finite-width networks. These formulations establish equivalent cost characterizations.

  • The paper derives optimization-equivalent expressions for the representational costs R(f) and R1(f).
  • Finite-width two-layer ReLU networks correspond one-to-one with discrete measures, with the network cost matching the measure’s total variation.
  • R(f) equals the infimum limiting total variation among pointwise-convergent finite-width network sequences with tight measures.
  • Every infinite-width network is a pointwise limit of finite-width networks whose total variation norms do not exceed that of the original measure.
  • The R1(f) minimizer is characterized by a unique even measure representing f, and its total variation gives R1(f).

C EXTENSION OF R-NORM TO LIPSCHITZ FUNCTIONS AND PROOF OF THEOREM 1

The paper extends the R-norm to Lipschitz functions through a dual Radon-transform construction and proves that finite R-norm is equivalent to representation by a unique even measure plus an affine function. It then identifies this norm with the optimization cost.

  • The R-norm is defined through a dual functional involving a (d+1)/2-power Laplacian and the dual Radon transform.
  • For Lipschitz f, the defining functional is finite because f has at most linear growth while the transformed test function decays sufficiently fast.
  • The distributional identity linking the Laplacian of a network to the Radon transform of its measure extends from smooth densities to arbitrary finite-total-variation measures.
  • Finite R-norm is equivalent to representing f as an infinite-width ReLU network with a unique even measure and unique affine terms.
  • The main theorem proves that the R-norm equals the optimization cost R1(f).
  • For suitable functions, the R-norm can be computed from the L1 norm of a Radon transform of a fractional Laplacian or an integer-order derivative expression.

D PROOF OF THEOREM 2

The section characterizes the norm R(f) through an optimization that separates the even measure representing nonlinear structure from the linear component encoded by ∇f(∞). Without the unregularized linear unit, the higher-dimensional norm generally lacks a simple closed form.

  • Theorem 2: Without the unregularized linear unit, R(f) has no simple closed-form expression in higher dimensions, although bounds are available for every Lipschitz function.
  • Theorem 2: When f vanishes at infinity, ∇f(∞)=0 and the representational cost reduces to R(f)=∥f∥R=R1(f).
  • Theorem 2: R(f) is optimized over a measure representation and a linear component, with the R-norm ∥f∥R capturing the even part and ∇f(∞) capturing the function’s linear behavior at infinity.The gradient at infinity equals V(α), the linear operator applied to the representing measure.
  • Theorem 2: The lower bound R(f)≥max{∥f∥R, 2∥v0∥} follows from separate dual feasible choices for the nonlinear measure and the linear component.
  • Theorem 2: Examples attain the upper bound, including functions whose cost equals ∥f∥R+2∥w−∥ when ∇f(∞)=w−.

E PROPERTIES OF THE R-NORM

The R-norm is a seminorm on Lipschitz functions that ignores affine components and is invariant under translations and rotations. Its finiteness imposes smoothness and Fourier-decay constraints, while its scaling under dilation is explicit.

  • Basic properties: The R-norm is absolutely homogeneous and subadditive, so it is a seminorm rather than a norm.
  • Basic properties: ∥f∥R=0 exactly for affine functions f(x)=v⊤x+c, meaning affine components are annihilated.
  • Invariances and scaling: Translations and orthogonal rotations preserve the R-norm, while fε(x)=f(x/ε) gives ∥fε∥R=ε^-1∥f∥R.
  • Analytic characterization: For odd d under classical integrability conditions, the R-norm is represented by the L1 norm of the Radon transform of (−∆)^((d+1)/2)f.
  • Fourier characterization: Finite R-norm requires Fourier decay of ∆f along every ray, with c∆f(σ·w)=O(|σ|^−(d−1)) as |σ|→∞.

G RADIAL BUMP FUNCTIONS

For radial functions, the Radon transform reduces the R-norm calculation to derivatives of a one-dimensional profile. The resulting smoothness threshold and dimension dependence can be evaluated explicitly for compactly supported radial bumps.

  • Radial reduction: For a radially symmetric f, R{f}(w,b)=ρ(b) is independent of the direction w, reducing the calculation to the profile ρ.
  • Finite-cost condition: The R-norm is finite exactly when the relevant (d+1)-st derivative of ρ has bounded variation, yielding a smoothness threshold on the bump exponent k.
  • Finite-cost condition: For d=3, finiteness requires k≥2 for the radial bump family.
  • Dimension dependence: For the choice k=(d+5)/2, the explicit bump family satisfies ∥f∥R∼d^2 for odd d≥3.

H PIECEWISE LINEAR FUNCTIONS

For compactly supported continuous piecewise linear functions, the distributional Laplacian is concentrated on region boundaries. Its Fourier transform can remain asymptotically constant along a ray, violating the decay required for finite R-norm.

  • Boundary decomposition: The distributional Laplacian of a continuous piecewise linear function decomposes into surface measures on its region boundaries, weighted by gradient jumps.At a boundary, the coefficient is ±∥gp−gq∥, with the sign determined by local concavity or convexity.
  • Failure of finite norm: Finite R-norm requires Fourier decay of c∆f along every ray, but these piecewise linear functions violate that requirement.
  • Failure of finite norm: Under the stated boundary configurations, there exists a direction w such that c∆f(σ·w) is asymptotically constant as |σ|→∞.
  • Fourier argument: For a boundary normal w1 distinct from the others, the corresponding surface integral contributes a nonzero constant while the remaining boundary terms decay.
Loading 1910.01635v1…