PaperlayerView exact revision on arXiv

Source-linked AI summary

Smaller generalization error derived for a deep residual neural network compared to shallow networks

Aku Kammonen, Jonas Kiessling, Petr Plecháč, Mattias Sandberg, Anders Szepessy, Raúl Tempone

arXiv:2010.01887v2math.NAcs.NAmath.OC

TL;DR

The paper studies generalization error for deep residual networks using random Fourier features. It derives an optimal frequency distribution through an optimal-control analysis, and reports error scaling with total feature count alongside a conditional advantage over a shallow-network bound.

  • Problem

    The paper asks whether deep residual networks with random Fourier features can have a smaller generalization-error estimate than shallow networks with the same total node count.

    Source: §1.1 · p. 1, §2 · p. 9

  • Method

    The analysis approximates an infinite-layer, infinite-node optimal-control problem with Monte Carlo features and uses its solution to derive optimal time-frequency densities.

    Source: §2 · pp. 7, 10

  • Results

    O((KL)^-1) generalization error is reported, with Method 1 giving lower error at L = 5 than L = 1 for fixed KL.

    Source: §7.4 · p. 33

  • Takeaways & Limitations

    For functions with ||f||L∞ sufficiently small relative to ||fhat||L1, the deep-network estimate can be lower than the standard shallow-network estimate.

    Source: §2 · p. 9

    In the reported run, training stops at 100 epochs to limit computational time although the error continues to decrease.

    Source: §7.4 · p. 33

Abstract

from arXiv · show

Estimates of the generalization error are proved for a residual neural network with $L$ random Fourier features layers $\bar z_{\ell+1}=\bar z_\ell + \mathrm{Re}\sum_{k=1}^K\bar b_{\ell k}e^{\mathrm{i}\omega_{\ell k}\bar z_\ell}+ \mathrm{Re}\sum_{k=1}^K\bar c_{\ell k}e^{\mathrm{i}\omega'_{\ell k}\cdot x}$. An optimal distribution for the frequencies $(\omega_{\ell k},\omega'_{\ell k})$ of the random Fourier features $e^{\mathrm{i}\omega_{\ell k}\bar z_\ell}$ and $e^{\mathrm{i}\omega'_{\ell k}\cdot x}$ is derived. This derivation is based on the corresponding generalization error for the approximation of the function values $f(x)$. The generalization error turns out to be smaller than the estimate ${\|\hat f\|^2_{L^1(\mathbb{R}^d)}}/{(KL)}$ of the generalization error for random Fourier features with one hidden layer and the same total number of nodes $KL$, in the case the $L^\infty$-norm of $f$ is much less than the $L^1$-norm of its Fourier transform $\hat f$. This understanding of an optimal distribution for random features is used to construct a new training method for a deep residual network. Promising performance of the proposed new algorithm is demonstrated in computational experiments.

1. Introduction

The paper studies generalization error for supervised learning with noisy data and functions whose Fourier transforms are L1-bounded. It extends random Fourier features to deep residual networks and derives error estimates and parameter distributions for this setting.

1. Introduction

  • The analysis considers noisy supervised data and target functions with Fourier transforms bounded in L1.The inputs are independent samples from an unknown probability distribution.Source: §1.1 · p. 1

1.1. Residual neural network formulation.

  • The paper extends random Fourier features to multiple hidden layers and derives generalization-error estimates and an optimal parameter distribution.The distribution motivates a generalization of adaptive Metropolis sampling to deep random-feature networks [11].Source: §1.1 · p. 2
  • With the same total of KL nodes, the deep-network error estimate is intended to improve on the one-hidden-layer bound.The authors also seek choices of depth, width, frequency distributions, and regularization that minimize the deep-network estimate.Source: §1.1 · p. 4
  • The analysis uses an infinite-dimensional optimal-control problem to split the control into data-dependent and state-dependent parts, then minimize Monte Carlo variance.The resulting error representation integrates the difference between exact and approximate value functions along the exact solution path.Source: §1.2 · p. 6

1.2. Relation to previous work.

  • The theorem concerns generalization error for functions with L1-bounded Fourier transforms, and its upper bounds do not establish that deep networks always outperform shallow ones.This distinguishes the result from earlier approximation results [18] and composition-based examples.Source: §1.2 · p. 6

2. Statement and discussion of the main result

Theorem 2.1 bounds the generalization error of a deep residual network and identifies optimal time-dependent frequency densities. The section explains how stratified Monte Carlo sampling uses these densities and discusses when the bound can be smaller than the shallow-network estimate.

2. Statement and discussion of the main result

  • Under boundedness and optimal-solution assumptions, Theorem 2.1 and Corollary 2.3 provide a generalization-error bound with constant C.The theorem assumes an optimal solution to (1.9) and an optimal β*(x) for (1.7).Source: §2 · pp. 8, 10
  • The minimal C is attained by optimal time-dependent densities; with constant densities and sufficiently small A, C ≃ 2(AB)^1/2 ≪ A.The section also gives optimal densities for the time-independent case.Source: §2 · pp. 8–9
  • When ∥f∥L∞ is sufficiently small relative to ∥f̂∥L1, the residual-network error estimate can be smaller than the shallow bound with KL nodes.The comparison is to a one-hidden-layer network with the same total number of nodes.Source: §2 · p. 9
  • The proof approximates an infinite-layer, infinite-node optimal-control solution by Monte Carlo; linear dependence across levels lets it split into identity-map and data terms.Stratified time sampling and the optimal densities minimize the variances of the two approximations.Source: §2 · pp. 7, 10
  • In practice, a layer-by-layer approximation uses adaptive Metropolis sampling to approximately draw frequencies from the optimal densities.The proposed method follows [11].Source: §2 · p. 10

3. Random feature Monte Carlo approximation

This section establishes Monte Carlo quadrature as the basis for analyzing random Fourier feature approximation, first for a single hidden layer and then as a step toward the deep residual network.

3. Random feature Monte Carlo approximation

  • For a single hidden layer, the Fourier representation yields the random-feature density p′(ω) = |f̂(ω)|/∥f̂∥L1(R^d).The deep-network analysis requires an optimal-control construction and an analogous Monte Carlo approximation.Source: §3 · p. 10
  • The section states Monte Carlo quadrature results for the mean, variance, and kurtosis of an approximation formed from iid frequencies.The stated results assume frequencies are sampled from a density.Source: §3 · p. 11
  • Optimal importance sampling formulates density selection as a minimization problem for the Monte Carlo approximation error.The section applies this framework to motivate optimal frequency densities for random Fourier features.Source: §3 · pp. 10–12

4. An optimal control solution

The section connects the finite residual-network optimization to a continuous-time optimal-control problem. Its explicit path and Monte Carlo approximation motivate the sampling and control choices used in the error bounds.

4. An optimal control solution

  • The finite residual-network problem is linked to the continuous-time control solution through Monte Carlo quadrature of its integrals.The control solution is feasible for the related differential-equation constraint.Source: §4 · pp. 12–13
  • The infinite-node optimal-control solution follows a linear path from the initial state to the target value for each data point.The paper uses this explicit solution to derive the bounds for the residual network.Source: §4 · pp. 13–14
  • A bang-bang control minimizes the variance objective, with the switching time determined by the chosen densities.For constant densities, the stated choice is τ = min(1, (B/A)^1/2).Source: §4 · p. 16
  • The control first approximates f(x) − β(x), then later approximates the scaled identity; choosing γ(t)=1 throughout recovers a one-hidden-layer network with E ≤ (KL)^−1A.The staged choice is motivated by the singularity at t=0 in the scaled-identity term.Source: §4 · pp. 15–16

5. Proof of Theorem 2.1

The proof compares the discrete residual network with a continuous optimal path and controls the resulting errors using Monte Carlo estimates and a discrete Gronwall inequality. It derives bounds for the state approximation and quadrature error.

5. Proof of Theorem 2.1

  • The proof organizes the estimate into an error representation, derivative bounds, a discrete Gronwall estimate for state differences, and a Monte Carlo quadrature bound.The discrete amplitudes are chosen from the feasible optimal-control solution and the corresponding optimal partition.Source: §5 · p. 17
  • E_tω[|ε_ℓ|²] = O(L^−2 + K^−1 + L e^−cK) uniformly over layers, where ε_ℓ is the difference between the exact and discrete states.The estimate follows by controlling layerwise fluctuations and applying a discrete Gronwall bound.Source: §5 · pp. 20, 22
  • When L ≪ K ≪ L³, the generalization error is dominated by the term identified in the proof’s quadrature-error step.The passage gives this regime as the condition for that dominance.Source: §5 · p. 24
  • For these Monte Carlo approximations, the variance yields R0 = O(L^-1 K^-1 + L^-4), as in Lemma 3.1 and Lemma 4.2.Source: §5 · p. 26

6. Numerical algorithms

The numerical algorithms approximate the residual network layer by layer, adaptively sample frequencies, and then use the resulting network to initialize global optimization. Pretraining may use substantially fewer data points than the full training set.

6. Numerical algorithms

  • The numerical algorithm combines explicit layer-wise approximation, adaptive frequency sampling, and global optimization of the resulting residual network.The paper presents this procedure as an approximation to the residual-network optimization problem for given frequency distributions.Source: §6 · p. 28, §6.1 · p. 29, §6.3 · p. 29

6.1. A layer by layer approximation of amplitudes

  • The layer-by-layer amplitude method motivates an explicit least-squares approximation by assuming residuals shrink by a factor δ across levels.The amplitudes are determined using the Pontryagin principle and finite training data.Source: §6.1 · pp. 28–29

6.2. Layer by layer training of amplitudes and frequencies

  • Adaptive Metropolis updates use computed amplitude magnitudes to sample frequencies approximately from the optimal distribution.The amplitudes are solved by least squares for each frequency update; deeper layers fit residual targets using both input-based and layer-state features.Source: §6.2 · p. 29, §6.1 · p. 29

6.3. Global post-training

  • The final residual network is globally optimized after layer-by-layer pretraining, using the pre-trained network as the optimizer’s initialization.The pretraining data count N1 can be significantly smaller than N, according to the experiments.Source: §6.3 · pp. 29–31

7. Numerical experiments

The experiments compare generalization error across node counts, layer counts, and training methods. Layer-by-layer pretraining followed by Adam yields smaller errors than Xavier-initialized Adam for both targets at the chosen epoch count, with training time limiting that count.

7. Numerical experiments

  • Experiments use normally distributed inputs, normalized training and test data, and examine generalization error versus total nodes and training method.The study uses target functions f1 and f2 and reports error bars for Method 1.Source: §7 · pp. 31–32

7.2. Method 2: The residual networks are trained by a global optimizer

  • Method 2 uses Adam with Xavier-normal initialization for frequencies and amplitudes, motivated partly by uncertainty about suitable initial distributions.Its learning rate decreases as Δte/te; the proposed layer-by-layer method supplies an alternative initialization for global optimization.Source: §7.2 · p. 32

7.3. The residual networks are trained by Algorithm 3

  • Method 3 produces smaller generalization errors than Xavier-initialized Adam for both targets at the chosen epoch count, though Method 2 may eventually reach similar error.Method 3 combines layer-by-layer construction with Adam; both methods could improve with larger K and more epochs.Source: §7.4 · p. 33, §7.3 · p. 33

7.4. Summary of experimental results

  • For Method 1, generalization error decreases as O((KL)^-1), and at fixed KL it is lower for five layers than for one.The five-layer Method 3 runs also have lower error per run than one-layer runs, while one-layer outcomes show less spread.Source: §7.4 · pp. 33–34
  • Adam’s error continued to decrease beyond the 100-epoch runs, which were capped to balance approximation error against computational time.The epoch count was chosen to limit computational time despite the continuing decrease.Source: §7.4 · p. 33

8. Conclusions

The paper derives an optimal random-feature distribution for deep residual networks and uses it to construct a layer-by-layer training method. The error estimate can be smaller than the shallow-network estimate under the stated function-norm condition.

8. Conclusions

  • The analysis derives an optimal random-feature distribution and shows deep residual networks can have smaller generalization error than shallow networks with the same total node count.The comparison is supported for functions whose L∞ norm is much smaller than the L1 norm of their Fourier transform.Source: §8 · pp. 34–35
  • The layer-by-layer method uses adaptive Metropolis sampling with computed amplitudes in the proposal step, then initializes a global optimizer such as Adam.The paper presents this as a training method built from the optimal-distribution insight.Source: §8 · p. 35
  • The experiments demonstrate the proposed algorithm’s performance, with the plotted Method 3 approximation of f2 coinciding with target values at plot resolution.The conclusion passage characterizes the computational performance as promising.Source: §8 · p. 35, Figure 13 · p. 35
Loading 2010.01887v2…