PaperlayerView exact revision on arXiv

Source-linked AI summary

The Barron Space and the Flow-induced Function Spaces for Neural Network Models

Weinan E, Chao Ma, Lei Wu

arXiv:1906.08039v2cs.LGmath.PRstat.ML

TL;DR

The paper asks which function spaces and norms suit neural-network approximation, since classical Sobolev/Besov spaces are tied to schemes that suffer from the curse of dimensionality. It constructs Barron space for two-layer networks and flow-induced space for residual networks, establishing approximation theorems and complexity bounds. The paper reports optimal upper bounds for Rademacher complexity on bounded sets under the associated norms.

  • Problem

    Sobolev/Besov spaces are tied to piecewise-polynomial schemes that suffer from the curse of dimensionality, motivating function spaces suited to neural-network models.

    Source: §1 · p. 2

  • Method

    The paper constructs Barron space for two-layer networks and flow-induced function space for residual networks, using direct and inverse approximation theorems to relate them to their models.

    Source: §1 · p. 2, §3 · p. 11

  • Results

    The identified spaces admit direct and inverse approximation theorems, and bounded sets under the associated norms have optimal upper bounds for Rademacher complexity.

    Source: §1 · p. 2, §3 · p. 11, §4 · p. 30

  • Takeaways & Limitations

    The paper treats function spaces as approximation-scheme-specific frameworks, with Barron and flow-induced spaces corresponding to two-layer and deep residual networks.

    Source: §1 · p. 2

    The terms “space” and “norm” are used loosely; the paper does not establish that the flow-induced quantities are true norms.

    Source: §1 · p. 2

Abstract

from arXiv · show

One of the key issues in the analysis of machine learning models is to identify the appropriate function space and norm for the model. This is the set of functions endowed with a quantity which can control the approximation and estimation errors by a particular machine learning model. In this paper, we address this issue for two representative neural network models: the two-layer networks and the residual neural networks. We define the Barron space and show that it is the right space for two-layer neural network models in the sense that optimal direct and inverse approximation theorems hold for functions in the Barron space. For residual neural network models, we construct the so-called flow-induced function space, and prove direct and inverse approximation theorems for this space. In addition, we show that the Rademacher complexity for bounded sets under these norms has the optimal upper bounds.

1 Introduction

Classical approximation theory links function spaces and norms to approximation error, but Sobolev/Besov spaces are tied to piecewise-polynomial schemes that suffer from the curse of dimensionality. The paper proposes Barron and flow-induced spaces as corresponding frameworks for two-layer and residual neural networks.

1 Introduction

  • Classical approximation theory uses function-space norms to control error, and direct and inverse theorems connect approximation rates with membership in Sobolev/Besov spaces.These spaces also describe functions of interest such as PDE solutions, though the paper notes their neural-network mismatch separately.Source: §1 · pp. 1–2
  • Sobolev/Besov spaces are tied to piecewise-polynomial approximation, whose parameter count grows exponentially with dimension, limiting their suitability for neural-network models.The paper motivates finding spaces aligned with models that may address the curse of dimensionality.Source: §1 · p. 2
  • The paper also cites RKHS as a kernel-method function space associated with dimension-independent error estimates.This is presented as inspiration for identifying analogous spaces for neural-network models.Source: §1 · p. 2
  • The paper identifies Barron space for two-layer networks and flow-induced function space for residual networks as analogs of spaces associated with their approximation schemes.The introduction frames these spaces through direct and inverse approximation theorems.Source: §1 · p. 2
  • In high dimensions, the best attainable approximation error rate may be the Monte Carlo rate, making function spaces and their norms useful alternatives to error rate alone for characterizing schemes.The paper views a function space as defined by approximation properties under a particular scheme.Source: §1 · p. 2

2 The Barron space

The section defines Barron spaces as function spaces tailored to two-layer networks and studies their approximation and complexity properties. It extends the framework to non-ReLU activations and relates Barron spaces to RKHSs and the space F1.

2.1 Definition of the Barron space

  • Barron spaces consist of continuous functions representable as probability-distribution averages of ReLU units with finite Barron norm.The paper notes that its Barron norm differs from the spectral norm in Barron’s original papers.Source: §2.1 · pp. 3–4

2.5.1 Proof of Proposition 1

  • For ReLU, the Barron norms indexed by p coincide, so the paper uses one Barron space and norm.The proof passage also derives equality between the 1- and infinity-indexed norms.Source: §2.1 · p. 4, §2.5.1 · p. 8

2.2 Direct and inverse approximation theorems

  • The direct approximation theorem constructs finite two-layer approximants for every Barron function, with the path norm serving as the network-side analogue of the Barron norm.The section also states an inverse approximation theorem for sequences of approximants with bounded path norm.Source: §2.2 · p. 5

2.3 Estimates of the Rademacher complexity

  • For bounded Barron-space sets, the section estimates Rademacher complexity and states that the result implies efficient learnability.The estimate is presented as an upper bound for functions whose Barron norm is at most Q.Source: §2.3 · p. 6

2.4 Barron space for Non-ReLU functions and the space F1

  • For non-ReLU activations, the extended Barron norms support direct approximation and Rademacher-complexity control under a condition on the activation.Unlike ReLU, a general activation lacks the homogeneity that makes the different p-indexed Barron spaces equal.Source: §2.4 · p. 6
  • For general activations, F1 and the extended Barron space can differ: F1 may require compact features and can give loose bounds for simple functions, while the extended norm distinguishes features.For ReLU, F1 is equivalent to the Barron space and their norms are equal [12].Source: §2.4 · p. 7

2.5.2 Proof of Theorem 3

  • The paper identifies the B2 Barron space with the union of RKHSs induced by the kernels kπ.The proof establishes both inclusions between B2 and that union.Source: §2.5.2 · p. 8

3 Flow-induced function spaces

The section develops flow-induced spaces and norms for residual networks, motivated by their continuous-time flow limit. It establishes direct and inverse approximation theorems and a complexity bound.

3 Flow-induced function spaces

  • The section establishes direct and inverse approximation theorems connecting residual networks with flow-induced spaces.It also proves a complexity bound for the flow-induced space.Source: §3 · p. 11
  • The flow-induced spaces and norms are motivated by the continuous-time flows arising as limits of residual networks.Source: §3 · p. 11
  • The section postpones its proofs until the end of the section.Source: §3 · p. 11

3.1 The compositional law of large numbers

The section studies deep residual networks as compositions of random near-identity maps and relates their limit to an ODE. It reports uniform-in-input convergence and notes that the result extends to time-dependent distributions.

3.1 The compositional law of large numbers

  • The analysis treats deep residual networks as repeated compositions of i.i.d. random near-identity maps and defines their compositional mean through an ODE.Source: §3.1 · pp. 11–12
  • The compositional law of large numbers gives convergence uniform in x for the residual-network sequence and its ODE limit.The ODE has a unique solution.Source: §3.1 · p. 12
  • The result extends to time-dependent distributions, which the paper identifies as the setting relevant in applications.Source: §3.1 · p. 12

3.2 The flow-induced function spaces

The section defines flow-induced function spaces through residual-network representations and associated quantities that control their complexity. It also relates these spaces to Barron functions and residual-network path norms.

3.2 The flow-induced function spaces

  • Dp consists of continuous functions represented by fα,{ρt} with finite Dp quantity.The representation uses a linear system of equations.Source: §3.2 · p. 13
  • The refined space ˜Dp controls both Np(1) and the Lipschitz norm of {ρt}, addressing continuity needed by the approximation argument.The distributions need not be continuous under the initial representation condition.Source: §3.2 · pp. 13–14
  • The residual-network l1 path norm is a discrete analog of the flow-induced quantity, and the paper uses only the l1 version.The authors note that other p-norm analogs can also be defined.Source: §3.2 · p. 14
  • ˜Dp is contained in Dp, and Barron functions belong to ˜D1 under the stated dimension and width conditions.For ˜Dp functions, the Dp quantity is no larger than the ˜Dp quantity; Proposition 9 assumes D ≥ d + 2 and m ≥ 1.Source: §3.2 · p. 14
  • Composing two Barron functions yields a function in D1 with norm bounded polynomially in their norms.For the cited high-dimensional example, the D1 quantities grow polynomially while spectral norms grow exponentially with dimension, suggesting residual networks can better approximate some functions.Source: §3.2 · p. 15

3.3 Direct and inverse approximation theorems

The section gives direct and inverse approximation results for residual networks, linking approximation by controlled networks to membership in flow-induced spaces.

3.3 Direct and inverse approximation theorems

  • Functions in ˜D2 admit residual-network approximations with error rate 1/L^(1−δ) for any δ ∈ (0, 1), using networks with uniformly bounded path norm.The theorem states this for sufficiently large network depth L.Source: §3.3 · p. 15
  • Conversely, a pointwise-convergent sequence of residual networks with the theorem’s parameter bounds and uniformly bounded D1 quantities yields the stated inverse approximation conclusion.The supplied passages specify the assumptions but omit the conclusion’s displayed formula.Source: §3.3 · p. 15

3.4 Bounds for the Rademacher complexity

The section introduces a modified flow-induced quantity for its Rademacher-complexity upper bound, noting that its relation to the original flow-induced space is unresolved.

3.4 Bounds for the Rademacher complexity

  • The Rademacher-complexity result uses a modified norm ˆDp because of technical difficulties.The supplied passages do not state the bound itself.Source: §3.4 · p. 16
  • The modified definition differs by a factor of 2, and the relationship between ˆDp and Dp is unclear in the vectorial case.The authors say they are unable to remove the factor; the scalar comparison does not always extend to the vectorial case.Source: §3.4 · p. 16

3.5 Proofs

The proofs establish the approximation and embedding claims by estimating discretization errors, exploiting distribution regularity, and constructing controlled representations.

3.5.1 Proof of Theorem 7

  • Theorem 7’s proof bounds the expectation of the error terms using boundedness, independence, and Lipschitz control, then obtains the result for sufficiently large L.The estimates include terms involving z(t), Ul, Wl, and the discretization error.Source: §3.5.1 · pp. 17–18

3.5.2 Proof of Theorem 8

  • Theorem 8’s proof changes the Kl,L estimate; the stated conditions keep z(t) Lipschitz, making that term the same order as in Theorem 7.The proof then follows the same arguments as Theorem 7.Source: §3.5.2 · p. 19

3.5.3 Proof of Proposition 9

  • For Proposition 9, the proof chooses a Barron representation and uses a distribution fixed across t, whose Lipschitz coefficient is zero.Source: §3.5.3 · pp. 19–20

3.5.4 Proof of Theorem 11

  • Theorem 11’s construction samples residual-network weights from ρl/L and uses a compact-support lemma to control the representation.The proof also considers a smoothed activation function.Source: §3.5.4 · p. 20

Proof of Lemma 1

  • Lemma 1 permits compactly supported distributions with bounded entries while keeping the ˜D2 quantity arbitrarily close to its infimum.The proof normalizes distributions on a set defined by constraints on W and |U||W|.Source: Proof of Lemma 1 · p. 21

Proof of Lemma 2

The proof steps compare ODE solutions after replacing the activation and use moment bounds in the continued approximation argument.

Proof of Lemma 2

  • The proof compares solutions of the same ODE before and after replacing σ with σε, starting from equal initial values.The random-weight expectation appears in the comparison argument.Source: Proof of Lemma 2 · pp. 21–22

Proof of Lemma 3

  • The proof of Lemma 3 integrates a bound over x to obtain its result.The estimate uses Theorem 8.Source: Proof of Lemma 3 · p. 22

Proof of Theorem 11 (Continued)

Proof of Lemma 4

These proof sections establish moment bounds, probabilistic approximation estimates, and a limiting residual-network representation using Young measures.

Proof of Lemma 4

  • Hoeffding’s inequality is used to bound entries of Sl,L, supporting bounds on the third and fourth moments of ∥el,L∥.The proof introduces an event A and uses sharper bounds under that event.Source: Proof of Lemma 4 · pp. 24–25

Proof of Theorem 11 (Continued)

  • Using Markov’s inequality, the proof controls the distance between f and fL with probability no less than 2/3, although the cited passage does not state the control bound.Source: Proof of Theorem 11 (Continued) · p. 26

3.5.5 Proof of Theorem 12

  • Uniformly bounded network parameters yield a subsequence and a family of probability measures ρt via the fundamental theorem for Young measures.The proof identifies the resulting function with f and establishes bounds on its D∞ and D1 norms.Source: §3.5.5 · pp. 27, 29

3.5.6 Proof of Theorem 13

The proof connects residual networks with bounded weighted path norms to approximation in the associated function space.

3.5.6 Proof of Theorem 13

  • The proof says it uses the same techniques as the direct approximation theorem to establish the residual-network approximation claim.The supplied passage introduces the claim for functions in ˆD_Q^2.Source: §3.5.6 · p. 29
  • Functions in ˆD_Q^2 can be approximated by residual networks as depth L tends to infinity, with weighted path norm at most 9Q.The passage states this approximation result for functions in ˆD_Q^2.Source: §3.5.6 · p. 29
  • F_Q consists of residual networks whose weighted path norms are bounded by Q.The proof considers the closure of F_Q in connecting this network class to the function-space approximation result.Source: §3.5.6 · pp. 29–30

4 Concluding remarks

The concluding remarks connect function-space norms to approximation and estimation error, then compare the resulting generalization scaling across methods.

4 Concluding remarks

  • The remarks frame high-dimensional model comparison around the size of the associated function space and its norm, rather than approximation error rate alone.They note that conventional Sobolev/Besov spaces are tied to piecewise-polynomial schemes that suffer from the curse of dimensionality.Source: §4 · p. 30
  • Finite datasets introduce estimation error, which the remarks say is controlled by the Rademacher complexity of the hypothesis space.The paper reports optimal estimates for the identified spaces.Source: §4 · p. 30
  • The kernel method, two-layer networks, and residual networks have generalization-error scaling O(1/m) + O(1/√n), with coefficients determined by target-function norms.The remarks characterize the move across these methods as decreasing norms and expanding function spaces.Source: §4 · p. 30

Related papers

Loading 1906.08039v2…