PaperlayerView exact revision on arXiv

Source-linked AI summary

Banach Space Representer Theorems for Neural Networks and Ridge Splines

Rahul Parhi, Robert D. Nowak

arXiv:2006.05626v3stat.MLcs.LG

TL;DR

The paper asks how to characterize functions learned when fitting single-hidden-layer networks to data. It formulates continuous-domain inverse problems with Radon-domain TV regularization and proves a sparse representer theorem; the resulting seminorms also support generalization bounds.

  • Problem

    The paper seeks a function-space account of what happens when single-hidden-layer neural networks are fit to finite-dimensional data.

    Source: §1 · p. 2

  • Method

    It studies continuous-domain inverse problems with Radon-domain TV seminorms and proves sparse solutions are single-hidden-layer networks plus low-degree polynomials.

    Source: §1 · p. 2, §1.1 · p. 2, §2.1 · p. 7

  • Results

    The seminorms characterize optimal network solutions and bound Rademacher complexity, yielding generalization bounds for networks with uniformly bounded seminorm.

    Source: §1.1 · p. 3, §7 · p. 31

  • Takeaways & Limitations

    The framework recasts data fitting as finite-dimensional network training with regularizers related to weight decay and path norm, while linking small seminorm to good predictions on new data.

    Source: §1.1 · p. 3

    Extending the variational framework to deep networks remains an open, challenging question because deep networks involve compositions of ridge functions.

    Source: §7.2 · p. 31

Abstract

from arXiv · show

We develop a variational framework to understand the properties of the functions learned by neural networks fit to data. We propose and study a family of continuous-domain linear inverse problems with total variation-like regularization in the Radon domain subject to data fitting constraints. We derive a representer theorem showing that finite-width, single-hidden layer neural networks are solutions to these inverse problems. We draw on many techniques from variational spline theory and so we propose the notion of polynomial ridge splines, which correspond to single-hidden layer neural networks with truncated power functions as the activation function. The representer theorem is reminiscent of the classical reproducing kernel Hilbert space representer theorem, but we show that the neural network problem is posed over a non-Hilbertian Banach space. While the learning problems are posed in the continuous-domain, similar to kernel methods, the problems can be recast as finite-dimensional neural network training problems. These neural network training problems have regularizers which are related to the well-known weight decay and path-norm regularizers. Thus, our result gives insight into functional characteristics of trained neural networks and also into the design neural network regularizers. We also show that these regularizers promote neural network solutions with desirable generalization properties.

1. Introduction

The paper frames fitting finite-width, single-hidden-layer neural networks as continuous-domain function recovery, using Radon-domain TV-like regularization to characterize learned functions. Its contributions connect representer theorems, ridge splines, practical network training, and generalization.

1.1 Contributions

  • The proposed Radon-domain seminorms yield truncated-power network solutions; for m = 2, these are ReLU networks.The seminorm is total variation of a filtered mth offset derivative in the Radon domain.Source: §1.1 · p. 2
  • Polynomial ridge splines are multivariate piecewise-polynomial superpositions of ridge functions, and specialize to ordinary polynomial splines in one dimension.They are presented as intermediate between univariate splines and traditional multivariate splines.Source: §1.1 · pp. 2–3
  • For point-sampled data, the inverse problem becomes finite-dimensional network training with regularizers related to weight decay and path norm, and width K can be at most the data size N.The resulting network is optimal with respect to the seminorm characterizing the learned function.Source: §1.1 · p. 3
  • For binary classification, bounded seminorm controls Rademacher complexity and yields generalization bounds, so small-seminorm networks make good predictions on new data.The argument relates Rademacher complexity to generalization error using standard learning-theory results.Source: §1.1 · p. 3

1.2 Related work

  • The paper extends prior Radon-domain TV work from representing bounded-norm infinite-width ReLU networks to fitting scattered data, while characterizing the resulting spaces as non-Hilbertian Banach spaces.Unlike compact-domain approaches, the unbounded Radon domain requires techniques addressing existence of solutions.Source: §1.2 · pp. 4–5

1.3 Roadmap

  • The roadmap assigns the main theorem to Section 4, ridge-spline connections to Section 5, and training, regularization, and generalization applications to Section 6.Sections 2 and 3 state results and introduce notation and formulation.Source: §1.3 · p. 5

2. Main Results

The section develops a representer theorem linking Radon-domain total-variation inverse problems to sparse neural-network solutions and finite-dimensional training formulations. It also bounds generalization via Rademacher complexity, relating control of the Radon-domain seminorm to the learned function’s complexity and error probability.

2.1 The representer theorem

  • Under the stated convexity, measurement, and null-space conditions, a sparse minimizer exists as a single-hidden-layer neural network plus a polynomial, with K ≤ N − dim Nm.The solution need not be unique, and nonsparse solutions may also exist.Source: §2.1 · p. 7
  • The native space Fm is a Banach space under a suitable direct-sum topology, constructed using a stable right inverse; the authors identify this as the first such structure on a non-Euclidean domain.Source: §2.1 · p. 8

2.2 Ridge splines

  • The operator Rm sparsifies cubic ridge splines into Radon-domain Dirac impulses, and in one dimension order-m polynomial ridge splines coincide with classical polynomial splines.Source: §2.2 · pp. 10–11

2.3 Scattered data approximation and neural network training

  • Theorem 8 recasts the continuous problem as finite-dimensional neural-network training when K ≥ N − dim Nm; for ReLU, the equivalent regularizers are the ℓ1-path norm and weight decay.For either training problem, a global minimizer at a smaller width remains a global minimizer at any larger width.Source: §2.3 · pp. 11–12

2.4 Statistical generalization bounds

  • For binary classification with iid examples, the authors formulate a bounded-regularizer Ivanov estimator and state that they provide a generalization bound for it.Source: §2.4 · pp. 13–14
  • Bounding the Radon-domain seminorm by B controls Rademacher complexity and, hence, the generalization error of the minimizer of (21).The section uses a standard Rademacher-complexity approach; when expected loss upper-bounds error probability, the resulting generalization bound also bounds that probability.Source: §2.4 · pp. 14–15
  • Under the stated almost-sure input bound, Theorem 10 bounds the Rademacher complexity of FΘ, with a contribution from the polynomial terms c(x).The bound applies to the neural-network hypothesis space under the section's bounded-input condition.Source: §2.4 · pp. 14–15
  • For neural networks implemented without the polynomial term c(x), the same complexity and generalization bound holds without R(c).The remark ties the bound to control of the seminorm ∥Rm f∥M(Sd−1×R) ≤ B.Source: §2.4 · p. 15

3. Preliminaries & Notation

The preliminaries set up the function and measure spaces used to formulate transforms in the Radon domain. They establish the distributional framework needed for the paper’s later arguments.

3.1 Spaces of functions and distributions

  • Schwartz and Lizorkin test functions, together with their continuous duals, provide the function and distribution spaces used on Euclidean and Radon domains.Lizorkin distributions on Rd can be viewed as tempered distributions modulo polynomials.Source: §3.1 · p. 15
  • Finite Radon measures are dual to continuous functions vanishing at infinity, and their total variation norm gives the measure norm used in the paper.The even Radon-domain measure space can also be viewed as measures on the manifold of hyperplanes.Source: §3.1 · p. 16

3.2 The Fourier transform

  • The Fourier transform and its inverse preserve Schwartz functions and extend to tempered distributions by duality.Source: §3.2 · pp. 16–17

3.3 The Hilbert transform

  • The Hilbert transform extends to distributions by duality and satisfies H H f = f.Its Fourier multiplier is sgn ω.Source: §3.3 · p. 17

3.4 The Radon transform

  • Defining Radon transforms of distributions requires Lizorkin test functions, since the dual Radon transform need not map Schwartz functions to Schwartz functions.The Radon transform is even, and the distributional transforms are defined by duality using the continuous bijections on Lizorkin spaces.Source: §3.4 · pp. 17–18

4. The Representer Theorem

The representer theorem reduces the continuous-domain inverse problem to a sparse Radon-measure recovery problem. Under the stated assumptions, a solution can be represented by finitely many neural-network atoms, while the native space is a Banach space.

4. The Representer Theorem

  • Under the stated convexity and measurement assumptions, Radon-measure recovery has a sparse minimizer with at most N atoms.The atoms are parameterized by z_k = (w_k, b_k), with nonzero coefficients v_k.Source: §4 · p. 20
  • The Radon derivative operator sparsifies single-hidden-layer network atoms, allowing the inverse problem to be reduced to Radon-measure recovery.The sparsified atoms are truncated-power ridge functions ρ_m(w^T x − b).Source: §4 · pp. 19–20
  • The null space of R_m consists of polynomials of degree strictly less than m, and the native space F_m forms a Banach space under a suitable norm.Its structure splits into a component represented through a right inverse and the null space; the right inverse is isometric on the corresponding even or odd measure space.Source: §4 · pp. 22–23

4.1 Proof of Theorem 1

  • The proof first fixes the measurement values shared by solutions, then reduces the problem to interpolation constraints and applies sparse measure recovery.The resulting minimizer has the neural-network-plus-polynomial form, with the odd-order case handled analogously.Source: §4 · p. 19, §4.1 · pp. 24–25

5. Ridge Splines and Polynomial Splines

The paper connects polynomial ridge splines to classical splines and to univariate splines indexed by directions in the Radon domain. These connections identify the univariate solutions and constrain the biases of sparse ridge-spline solutions under ideal sampling.

5.1 Univariate ridge splines are univariate polynomial splines

  • For d = 1, polynomial ridge splines of order m coincide with classical univariate polynomial splines of order m.With suitable path-norm or weight-decay regularization, a sufficiently wide univariate network fit to data yields a locally adaptive regression spline.Source: §5.1 · p. 26

5.2 Ridge splines correspond to univariate splines in the Radon domain

  • A ridge spline can be viewed in the Radon domain as a continuum of univariate splines, one for each direction γ.For a fixed direction, the corresponding function is an mth-order polynomial spline.Source: §5.2 · pp. 26–27
  • In the ideal sampling setting, each directional spline has adaptive knots with at most N − m locations, and no knots outside the sampling locations.The knot locations may depend on direction.Source: §5.2 · p. 27
  • The biases of a sparse ridge-spline solution under ideal sampling are bounded by the largest absolute sampling projection across directions.The bias terms correspond to the directional spline knot locations.Source: §5.2 · p. 27

6. Applications to Neural Networks

The applications section connects the representer framework to finite-dimensional neural-network training and binary-classification generalization. The supplied proof passages describe the regularizer equivalence and steps used to bound complexity.

6. Applications to Neural Networks

  • The applications extend the representer theorem to neural-network training, regularization, and generalization.Source: §6 · p. 28

6.1 Finite-dimensional neural network training problems

  • The finite-dimensional training result is proved by recasting the variational problem and relating the network regularizer to the Radon-domain seminorm.The proof uses the weight-bias representation and the homogeneity of ρ_m.Source: §6.1 · p. 28, §6.1.1 · p. 28

6.1.1 Proof of Theorem 8

  • At a minimizer, rescaling homogeneous activations balances the output coefficient and input-weight norm, yielding the stated regularizer.The proof identifies each regularizer term as minimized when |v_k| = ||w_k||_2^(m−1).Source: §6.1.1 · p. 29

6.2 Generalization bounds for binary classification

  • For binary-classification bounds, the proof normalizes neuron weights and bounds empirical Rademacher complexity, beginning with a single neuron.It uses the symmetry of the Rademacher variables to equate complexities for functions that differ only by sign.Source: §6.2 · p. 29, §6.2.1 · pp. 29–30

6.2.1 Proof of Theorem 10

  • The complexity argument proceeds through single-neuron bounds and then applies expectation to obtain the theorem’s bound.Source: §6.2.1 · p. 30

7. Conclusion

The paper connects single-hidden-layer network training to continuous-domain inverse problems with Radon-domain total-variation-like regularization, and relates the resulting seminorms to generalizability, weight decay, and path norms. It identifies unresolved computational questions for finding sparse solutions and extending the framework to deep networks.

7. Conclusion

  • Training with an appropriate regularizer yields a single-hidden-layer network function optimal for a Radon-domain total-variation-like seminorm, which the paper says directly controls generalizability.The framework encompasses ReLU networks, whose corresponding regularizers relate to weight decay and path norms.Source: §7 · p. 31

7.1 Computational issues

  • Finding sparse solutions remains an open computational question because algorithms that provably find global minimizers are not yet established.The paper notes that gradient descent seems to find global minima, but full theoretical justifications are lacking.Source: §7.1 · p. 31

7.2 Deep networks

  • Extending the variational framework to deep networks would require a continuous-domain inverse problem and a representer theorem, which the authors expect to be challenging because deep networks compose ridge functions.Source: §7.2 · p. 31

A.1 Proof of Lemma 9

The proof establishes boundedness of point evaluation by decomposing a function into an inverse-Radon component and a null-space polynomial component.

A.1 Proof of Lemma 9

  • To prove boundedness, the argument reduces the problem to showing that evaluation at a fixed x0 is a bounded operator.Source: §A.1 · p. 32
  • The representation f = R_m,φ^-1 u + q separates the inverse-Radon component from a polynomial q in the null space.The inverse operator's boundedness and continuity of its kernel support bounding the inverse-Radon contribution to evaluation.Source: §A.1 · p. 32
  • Point evaluation is continuous on the null space, and its norm bound combines with the kernel bound to bound evaluation of f.The proof identifies the null space as polynomials of degree strictly less than m.Source: §A.1 · p. 32

A.2 Proof of Lemma 19

The proof uses the Fourier slice theorem to characterize the null space of the mth Radon-domain derivative as polynomials of degree less than m.

A.2 Proof of Lemma 19

  • The Fourier slice theorem relates the Fourier transform of the Radon-domain derivative to the multivariate Fourier transform of f along directions γ.Source: §A.2 · pp. 32–33
  • If f lies in the null space, the displayed derivative vanishes for all (γ, ω), implying that f's Fourier transform is supported only at zero and f is a polynomial.Source: §A.2 · p. 33
  • The condition f ∈ L∞,m−1(Rd) restricts that polynomial to degree strictly less than m.Source: §A.2 · p. 33

A.3 Proof of Lemma 21

The proof uses Green functions and null-space polynomials in a calculation that checks boundary conditions and establishes boundedness of the inverse operator on measures.

A.3 Proof of Lemma 21

  • The calculation uses translated Green functions r_z and polynomials p_n from the null space to obtain the test-function expression.Source: §A.3 · p. 33
  • Boundary conditions are checked against even test functions when m is even; the odd case is analogous.The preceding calculation gives the corresponding expression for even or odd test functions according to the parity of m.Source: §A.3 · p. 33
  • The biorthogonal system ensures a unique representation of elements of the null space.Source: §A.3 · p. 33
  • Assuming the inverse is stable, density arguments extend it to measures; the theorem establishes that it is bounded on measures.Source: §A.3 · p. 33

A.4 Proof of Theorem 22

The proof equips the boundary-constrained space with a Banach norm by identifying it isometrically with an even or odd measure space. It then splits functions into boundary-constrained and null-space components while preserving their Radon transform.

A.4 Proof of Theorem 22

  • Boundary conditions remove the null-space component, making Fm,φ isometrically isomorphic to the corresponding even or odd measure space under the Radon transform norm.The bounded inverse theorem gives a bounded inverse, identified with the unique inverse satisfying the boundary conditions.Source: §A.4 · p. 34
  • Projecting onto Nm writes each f as a boundary-constrained component plus a null-space component, with the constrained component retaining the same Radon transform as f.The construction imposes φ(ef) = 0, so ef belongs to Fm,φ.Source: §A.4 · p. 34
  • The direct-sum decomposition Fm = Fm,φ ⊕ Nm yields a composite Banach norm combining the Radon transform measure norm and the null-space coefficient norm.The null-space norm is defined through the Euclidean norm of its expansion coefficients.Source: §A.4 · pp. 34–35

Related papers

Loading 2006.05626v3…