Source-linked AI summary
How do infinite width bounded norm networks look in function space?
Pedro Savarese, Itay Evron, Daniel Soudry, Nathan Srebro
TL;DR
The paper asks which functions infinite-width ReLU networks can represent under bounded overall weight norm, and how that norm shapes learning. It formulates representation cost through norm minimization and characterizes the univariate case. The minimal norm is max(∫ |f''(x)| dx, |f'(-∞) + f'(+∞)|), and minimum-norm sample fitting yields linear spline interpolation.
Problem
The paper asks what functions can be represented or approximated by infinite-width ReLU networks with bounded norm, addressing norm requirements that size-based approximation results do not characterize.
Method
The paper studies single-hidden-layer infinite-width ReLU networks by minimizing the overall Euclidean norm of their non-bias weights and analyzing the resulting representation cost in function space.
Results
For univariate functions, the minimal network norm is max(∫ |f''(x)| dx, |f'(-∞) + f'(+∞)|), and minimum-norm fitting yields linear spline interpolation.
Takeaways & Limitations
The induced complexity control connects infinite-width ReLU learning to linear spline interpolation and interpolation-learning predictors.
Takeaways & Limitations
The analysis leaves multivariate extensions as future work, conjecturing a connection to the integral of the nuclear norm of the Hessian.
Abstract
from arXiv · showhide
We consider the question of what functions can be captured by ReLU networks with an unbounded number of units (infinite width), but where the overall network Euclidean norm (sum of squares of all weights in the system, except for an unregularized bias term for each unit) is bounded; or equivalently what is the minimal norm required to approximate a given function. For functions $f : \mathbb R \rightarrow \mathbb R$ and a single hidden layer, we show that the minimal network norm for representing $f$ is $\max(\int |f''(x)| dx, |f'(-\infty) + f'(+\infty)|)$, and hence the minimal norm fit for a sample is given by a linear spline interpolation.
1 Introduction
The paper studies how bounded weight norms, rather than network size, control complexity in infinite-width ReLU networks. For univariate functions, this control yields a rich function-space bias, with minimum-norm fitting producing linear spline interpolation.
- Motivation: Weight magnitude may control neural-network complexity even when model size is effectively unbounded.The paper frames norm control as either explicit or implicit in practical neural networks.
- Motivation: Infinite-width networks shift learning from selecting among finite models toward searching the function space for low-representation-cost functions.Representation cost is the minimal norm needed to represent a function in the chosen architecture.
- Motivation: Unlike classical size-based approximation, bounded-norm networks can approximate broad classes of smooth functions arbitrarily well without increasing the norm.Classical analyses often study how network size grows as approximation error decreases.
- Setup: The paper studies single-hidden-layer infinite-width ReLU networks with controlled overall Euclidean weight norm.The architecture uses an unbounded number of rectified linear units.
- Results: For univariate functions, norm-minimizing fitting yields linear spline interpolation and connects neural-network learning to interpolation-learning analyses.The paper identifies these splines with predictors studied by Belkin et al.
- Method: The induced function-space complexity can be derived using the Green’s function of the second derivative and interpreted through a variational problem.The Green’s-function perspective is developed for fitting two-layer networks.
2 Infinite Width ReLU Networks
The paper defines representation cost for unbounded-width ReLU networks through minimum squared non-bias weight norm and reformulates learning as a convex function-space problem. With sufficiently many units, the infinite-width formulation already describes finite networks used for empirical fitting.
- Network definition: The model is a two-layer network with one hidden layer containing an unbounded number of ReLU units.The framework targets functions f: R^d → R.
- Representation cost: The network complexity is the minimum squared Euclidean norm of non-bias weights required to implement a function.Hidden-layer biases remain unregularized, while the output bias can be removed without changing the definitions or results.
- Representation cost: Representation cost extends exact finite-network implementability to arbitrary approximation as the number of units increases.This makes norm, rather than unit count, the central object of study.
- Function-space formulation: The sub-level sets of representation cost are closures of symmetric convex hulls of ReLU features, yielding an infinite-dimensional L1-regularized formulation.The formulation uses signed measures over feature parameters.
- Optimization: Learning with controlled network norm is equivalent to minimizing a loss over functions while controlling their representation cost, and this problem is convex.The equivalence follows from rewriting parameter-space norm control in function space.
- Finite-width equivalence: N data points require at most N weight vectors, or N + 1 units, for a minimizer of the function-space problem.Thus a finite network with at least as many units as data points precisely captures the stated infinite-width optimization.
3 One-dimensional Functions
For univariate functions, the paper exactly characterizes the minimum norm of infinite-width ReLU representations and shows that norm-regularized fitting reduces to controlling the total variation of the derivative. On finite samples, a global minimizer is a linear spline interpolation, although other equally optimal, smoother functions may also exist.
- Exact norm characterization: Theorem 3.1 exactly characterizes the minimum representation norm R(f) for every univariate function f.The characterization uses the weak second derivative and endpoint derivative limits.
- Representation structure: The representation measure is nearly unique: its total signed component is fixed by f′′, while only the forward-versus-backward ReLU mass can vary.That remaining component contributes only an affine term and is constrained by the endpoint slopes.
- Exact norm characterization: The norm is determined by the larger of the total variation of f′ and the absolute sum of its derivative limits at −∞ and +∞.The total variation term is ∫|f′′(x)|dx, while the endpoint term is |f′(−∞)+f′(+∞)|.
- Regularized learning: Norm-regularized infinite-width ReLU learning is equivalent to minimizing the total variation of the derivative over functions.This equivalence applies to fitting with any lower semi-continuous loss and positive regularization.
- Finite-sample solutions: For finite data, a global minimizer is the linear spline interpolation with breakpoints at the data points and at most N + 1 pieces.The interpolation minimizes the relevant objective, though the minimizer need not be unique; trained networks can implement smoother functions with the same optimal cost.
- Finite-sample solutions: The same optimal function-space cost can be attained by distinct networks and distinct functions, including networks with 20 and 100 hidden units.In the illustrated ten-point example, all three functions achieve R(f*) = 4.35, while the trained networks reach optimal parameter-space cost.
4 An Interpertation in Terms of Green’s Functions
The paper interprets two-layer ReLU fitting through Green’s functions: the network represents a second-derivative variable, while an undetermined affine term accounts for the kernel of the second derivative. This connects norm-controlled fitting to an L1-regularized variational problem.
- ReLU acts as a Green’s function for the second derivative, so fitting f can be viewed as recovering u = f′′.The second derivative can be read directly from the representing measure or network weights.
- The representing measure yields u(x) through the combined mass of forward- and backward-sloping ReLUs at the relevant threshold.Discrete networks approximate this representation with weighted ReLU units; smoother approximations can replace point masses with smooth bumps.
- Introducing an auxiliary variable u rewrites the norm-controlled network problem as a variational problem over the second derivative.The affine term ax + c remains undetermined by the second derivative and must be handled separately.
- The resulting top-layer L1 regularization is equivalent to Euclidean norm regularization across both layers.The additional boundary term arises because the linear component is constrained as well.
5 Approximating Higher Dimensional Functions
The higher-dimensional extension uses the Hessian and its eigenstructure to seek a function-space characterization of the representation cost. The paper finds that a naive Hessian-nuclear-norm formula works only in restricted cases and fails generally.
- The higher-dimensional analysis extends the Green’s-function viewpoint to inputs x in R^d and examines the Hessian of represented functions.The representation is expressed through measures over directions and thresholds.
- When the representing measure is nonnegative, the paper gives a special-case expression linking representation cost to the Hessian and boundary geometry.The derivation uses the divergence theorem and assumes α(w,b) ≥ 0.
- A naive generalization is the integral of the Hessian’s nuclear norm, the sum of the absolute eigenvalues rather than the signed Laplacian.This conjecture is motivated by the one-dimensional integral of |f′′| but is not generally valid.
- Functions with vanishing Hessian show that no normalized Hessian norm alone can characterize the general representation cost.Such functions can nevertheless have finite, nonzero network norm.
- The paper leaves the correct higher-dimensional function-space cost for general L1 representation minimization as an open problem.Finite interpolation remains possible using scaled and shifted radial bump functions, while the corresponding cost is not captured by the naive Hessian formula.
6 Discussion
The discussion argues that infinite-width architectures should be understood through the function-space complexity controls induced by weight norms. It also proposes studying depth through changes in norm-based representation cost and inductive bias rather than unit-count efficiency.
- Norm regularization in infinite-width networks induces rich and non-obvious complexity control over function space.The architecture’s role is characterized as shaping this control rather than merely determining representational size.
- The paper advocates approximation theory based on bounded norm rather than bounded numbers of units.This reframes the central resource from network size to representation cost.
- Depth should be evaluated by whether it permits lower-norm representations and changes the inductive bias induced by weight control.For infinitely many deep parallel ReLU networks, the paper reports ℓ2/L bridge penalties replacing the two-layer ℓ1 penalty.
- The paper proposes extending the representation-cost framework to infinitely wide fully connected L-layer ReLU networks with arbitrary units per layer.The resulting depth-dependent function-space cost is posed as a topic for further study.
- An anecdotal experiment with deeper networks did not appear to change the inductive bias, since all depths recovered a function minimizing the one-dimensional representation cost.The comparison used deeper networks with fixed hidden-unit counts and the same regularization setting.
- The discussion also identifies multiple outputs as a natural extension, connecting the question to matrix factorization and nuclear-norm regularization.The corresponding function-space behavior for vector-valued ReLU networks remains open.
B Relationship to Barron’s Analysis
The paper distinguishes its overall two-layer ReLU norm from Barron’s norm, which primarily controls the output layer and has domain-dependent approximation guarantees. It argues that Barron’s quantity is generally sufficient but not necessary for the approximation questions considered here.
- Barron’s analysis uses a measure over weights to approximate functions with sigmoidal networks while bounding the number of units and output-layer ℓ1 norm.The associated Barron Norm is a seminorm over the functions for which it is finite.
- Unlike the paper’s ReLU norm, Barron’s norm does not control the weights across both layers.For ReLU networks, positive homogeneity makes separate control of one layer inadequate because layer scales interact.
- Barron’s norm is not tight for step or sigmoidal activations, so it does not exactly capture the induced function-space complexity.The paper therefore treats it as an upper bound rather than a necessary characterization of approximability.
- Barron-based depth-separation results do not translate into meaningful depth-separation results for sigmoidal, and especially ReLU, networks.The mismatch follows because the relevant induced complexity is not characterized exactly by Barron’s norm.
- Barron’s approximation guarantees apply within bounded Euclidean balls and depend strongly on the ball radius.For bounded-domain approximation, the relevant quantity would involve minimizing Barron norm over extensions to the full space, whose behavior is unclear.
C The effect of neural networks depth on the inductive bias
The section studies how depth changes the inductive bias of parallel infinite-width networks under Euclidean norm control. It shows an equivalent last-layer bridge penalty, parameter alignment, and depth-dependent sparsity of parallel subnetworks.
- The parallel architecture sums k subnetworks with L−1 layers and parameterizes their weights together with a final linear-combination layer.
- The controlled squared Euclidean weight norm can be reformulated using a last-layer ℓp bridge penalty with p = 2/L < 1 and normalized subnetwork weights.
- Equivalent formulations preserve the represented network function and objective value, linking the original norm-constrained problem to the bridge-penalized formulation.
- At a norm-minimizing solution, each subnetwork’s inner-layer ℓ2 norms equal its corresponding final-layer coefficient.
- For finite samples, an optimal solution exists with at most N nonzero final-layer coefficients, and when L ≥ 3 every optimum has this sparsity.
- As depth increases, the bridge penalty approaches an ℓ0 penalty, implicitly zeroing as many parallel subnetworks as possible and inducing stronger sparsity.
Proof for Theorem C.1
The proof establishes equivalence between the original implementation-cost formulation and a bridge-penalized problem by rescaling positively homogeneous subnetworks in both directions.
- The proof starts from an optimal bridge-penalized solution and rescales each positively homogeneous subnetwork to satisfy the normalized weight constraints.
- Conversely, an implementation-cost solution is normalized through the same homogeneity argument, producing a feasible bridge-penalized solution.
- The reverse construction yields the required inequality, completing the equivalence between the two optimization formulations.
- Positive homogeneity preserves every subnetwork’s function while redistributing scale across its layers and final coefficient.
- The constructed implementation-cost solution has the same objective value as the original bridge-penalized solution.
Proof for Theorem C.3
The proof shows that when L ≥ 3, the nonconvex bridge penalty admits only finitely supported optimal solutions on finite samples, with support size at most N.
- For L = 1, related finite-support arguments instead yield an optimal support bound of at most N + 1 through Carathéodory-based reasoning.
- For L ≥ 3, the objective’s 2/L-power penalty is nonconvex but quasi-convex, and every optimal solution has finite support of size at most N.
- Assuming an optimum has N+1 active coefficients, the proof constructs a nonzero perturbation preserving all N sample outputs.
- Concavity of the 2/L-power function and strict Jensen inequality imply that one of two perturbed solutions has a strictly smaller penalty.
- Because the perturbations have identical loss, the lower-penalty solution has a smaller objective, contradicting optimality.
D Proof of Claim 5.2
The proof evaluates a spherical integral by aligning the input direction with a coordinate axis and reducing the calculation through rotational symmetry and one-dimensional integration.
- For d > 1, the input is aligned without loss of generality with the first coordinate axis before integrating over the sphere.
- The spherical integral is reduced by integrating over the surface area of a (d−2)-dimensional sphere and using the surface area S_d.
- When ∥x∥ > b, the remaining integral is expressed with the lower limit −b/∥x∥.
- The final expression separates into a constant term plus an odd function, using the fact that integrating an even function yields this decomposition.
- The resulting form is then used to establish the claimed expression for suitable constants r0 and C under any norm.