PaperlayerView exact revision on arXiv

Source-linked AI summary

The gap between theory and practice in function approximation with deep neural networks

Ben Adcock, Nick Dexter

arXiv:2001.07523v3cs.LGcs.NAmath.NAstat.ML

TL;DR

This paper examines the gap between DNNs’ expressive power and their practical performance in scientific computing. Experiments find trained DNNs can perform poorly on smooth functions yet compete with compressed-sensing methods on other examples, while a theoretical strategy matches their guarantees up to constants.

  • Problem

    A gap remains between DNNs’ expressive power and the performance achieved with standard training, while sample costs can dominate high-dimensional approximation problems.

    Source: §1.1 · p. 3, §1.3 · p. 4

  • Method

    The paper studies fully connected ReLU networks empirically and proves that a DNN architecture and training procedure can match compressed-sensing performance guarantees up to constants.

    Source: §6 · p. 27, §5.3 · p. 27

  • Results

    Trained DNNs perform poorly on smooth functions but are competitive with compressed-sensing schemes on other examples; standard methods generally miss theoretical convergence rates on smooth approximation problems.

    Source: §1.3 · p. 4, §6 · p. 27

  • Takeaways & Limitations

    A theoretical DNN strategy can match best-in-class compressed-sensing guarantees up to constants, but the proof-based procedure is not claimed to be practical or numerically stable.

    Source: §1.3 · p. 5, §5.3 · p. 27

    The empirical study covers fully connected ReLU networks with constant hidden-layer widths and ℓ2 loss; the existence proof is not claimed to be practical or numerically stable.

    Source: §1.4 · p. 5, §5.3 · p. 27

Abstract

from arXiv · show

Deep learning (DL) is transforming industry as decision-making processes are being automated by deep neural networks (DNNs) trained on real-world data. Driven partly by rapidly-expanding literature on DNN approximation theory showing they can approximate a rich variety of functions, such tools are increasingly being considered for problems in scientific computing. Yet, unlike traditional algorithms in this field, little is known about DNNs from the principles of numerical analysis, e.g., stability, accuracy, computational efficiency and sample complexity. In this paper we introduce a computational framework for examining DNNs in practice, and use it to study empirical performance with regard to these issues. We study performance of DNNs of different widths & depths on test functions in various dimensions, including smooth and piecewise smooth functions. We also compare DL against best-in-class methods for smooth function approx. based on compressed sensing (CS). Our main conclusion from these experiments is that there is a crucial gap between the approximation theory of DNNs and their practical performance, with trained DNNs performing relatively poorly on functions for which there are strong approximation results (e.g. smooth functions), yet performing well in comparison to best-in-class methods for other functions. To analyze this gap further, we provide some theoretical insights. We establish a practical existence theorem, asserting existence of a DNN architecture and training procedure that offers the same performance as CS. This establishes a key theoretical benchmark, showing the gap can be closed, albeit via a strategy guaranteed to perform as well as, but no better than, current best-in-class schemes. Nevertheless, it demonstrates the promise of practical DNN approx., by highlighting potential for better schemes through careful design of DNN architectures and training strategies.

1. Introduction.

Although DNNs have strong approximation-theory results and growing use in scientific computing, their practical performance under training remains insufficiently understood. The paper evaluates trained networks using numerical-analysis criteria and finds a gap between expressivity and practical results, while establishing a theoretical benchmark for matching compressed sensing (CS).

1.1. Challenges.

  • The study examines DNN approximation through stability, accuracy, sample complexity, dimensionality, and computational cost because expressivity results do not establish reliable training to scientific-computing tolerances.The authors note that convergence guarantees often show existence of a suitable network, not a training method that reliably achieves the required tolerances.Source: §1.1 · pp. 2–3

1.2. Contributions.

  • The authors develop a numerical-analysis-based framework and empirically study fully connected feedforward ReLU networks on smooth and piecewise smooth functions across dimensions, comparing smooth-function results with CS.The study also examines effects of architecture and training choices.Source: §1.2 · p. 4

1.4. Outlook.

  • A DNN architecture and training procedure can attain CS’s exponential convergence rate for analytic functions, but the authors do not claim the proof-based strategy is practical, numerically stable, or superior to CS.The benchmark’s flexibility across function classes remains an open challenge.Source: §1.2 · p. 4, §1.4 · p. 6

1.3. Conclusions.

  • Trained DNNs can perform poorly on smooth functions despite strong expressivity results, yet can be competitive with CS on other examples.The conclusions identify a gap between DNN expressivity and performance achieved with standard training.Source: §1.3 · p. 4
  • On smooth-function approximation, standard training typically reaches at most four digits of accuracy, while weighted ℓ1-minimization with Legendre polynomials can reliably reach six or seven digits.The authors report that DNNs should be capable of the latter results under a different initialization and training procedure.Source: §1.3 · p. 4

1.5. Outline.

  • The paper proceeds from approximation problem and method definitions to experimental setup and numerical results, then presents theoretical results.The authors point to supplementary materials and accompanying computational-framework code.Source: §1.5 · p. 6

2. Framework.

Section 2 formulates function approximation from samples on a unit cube and introduces deep learning, polynomial approximation, and compressed-sensing schemes for comparison.

2.1. Problem formulation.

  • The task is to approximate an unknown f∈L2(U), with U=(−1,1)^d and uniform measure, from independently drawn Monte Carlo samples (x_i, f(x_i)).The setup is adopted for ease of presentation; the authors note extensions to more general domains, sampling strategies, and vector-valued functions.Source: §2.1 · p. 6

2.2. Deep Learning.

  • DNNs are trained from sampled values by minimizing a loss; the study uses fully connected ReLU networks whose architecture is specified by activation, depth, and layer widths.Selecting an appropriate architecture for a problem is identified as a significant challenge.Source: §2.2 · p. 7

2.3. Polynomial approximation of smooth functions.

  • Best s-term Legendre approximation selects the largest coefficients to capture anisotropy; for analytic functions it converges exponentially in s and improves on fixed isotropic schemes in high dimensions.In dimensions d≥2, choosing an index set a priori may fail to capture anisotropic behavior.Source: §2.3 · p. 8
  • Computing a best s-term approximation can be infeasible because it may require finding infinitely many coefficients before selecting the largest s.The text notes that this can remain computationally infeasible even when only a large finite set of coefficients is considered.Source: §2.3 · p. 9

2.4. Polynomial approximation with compressed sensing.

  • Compressed sensing restricts Legendre coefficients to a finite hyperbolic-cross set, then recovers an approximately sparse vector using weighted ℓ1 minimization to avoid potentially exponential-in-dimension sample bounds.The paper considers either the weighted problem or the unweighted ℓ1 problem for comparison.Source: §2.4 · p. 9

3. Testing setup.

The testing setup compares fully connected ReLU networks across architectures and training choices using repeated trials and numerical-analysis error measures. Adam with an exponentially decaying learning rate performs best among tested solvers, but training loss tolerance does not ensure stable or accurate pointwise predictions.

3.1. Setup.

  • The experiments used fully connected ReLU networks, and the authors found small β = L/N effective for training; they fixed the initialization seed at 0, noting that broader seed averaging remained future work.They used Adam with an exponentially decaying learning rate and checkpointed networks as training loss fell.Source: §3.1 · pp. 10–11
  • The study ran 20 trials per architecture and data set, typically using at most about 1,000 uniformly sampled training points, then averaged test errors and run statistics.Testing used large sparse-grid point sets and deterministic relative L2 error estimates; the framework was implemented as MLFA in TensorFlow.Source: §3.1 · pp. 10–11

3.2. Solvers.

  • Adam achieved the best accuracy with the least computational cost among tested methods; AdamW matched but did not outperform it at low weight decay, while larger decay worsened accuracy and runtime.Figure 1 compares average relative L2 error and training time for 20 ReLU 10 × 100 networks.Source: §3.2 · p. 12, Figure 1 · p. 12
  • All 20 Adam trials reached the 5 × 10^-7 loss tolerance in under 14,000 epochs, whereas neither constant-rate nor exponentially decaying-rate SGD trials reached tolerance within 50,000 epochs.The comparison uses the same problem and an exponentially decaying schedule for Adam and one SGD condition.Source: §3.2 · pp. 12–13, Figure 2 · p. 13
  • Batch sizes that were too small increased training time with only marginal performance benefit; their effects in higher-dimensional problems were left for future study.Source: §3.2 · p. 13

3.3. Initialization and Precision.

  • Small-variance initialization mattered: mean-zero normal weights and biases with variance 0.01 performed near best on the smaller architectures and about as well as variance 2/N on the largest tested architecture.The comparison used Adam on the piecewise continuous function problem; making β = L/N too small could produce numerical instabilities despite meeting training-loss tolerance.Source: §3.3 · p. 13
  • For some problems, initializing and training DNNs in double precision improved test generalization accuracy, with larger gains for deeper networks; computation time increased substantially, so comparisons covered only a handful of problems and architectures.Double precision required more epochs to reach tolerance 5 × 10^-16 and incurred additional arithmetic time.Source: §3.3 · p. 14

3.4. Convergence of Adam on function approximation problems.

  • Adam’s average performance was often good despite some trials missing the epoch budget or producing unstable networks; error spread was larger for the discontinuous function than for smoother functions.The 10-layer, 100-node example’s boxplot summarizes average relative L2 errors over 20 trials.Source: §3.3 · p. 14, §3.4 · p. 15, Figure 6 · p. 15

4. Numerical experiments.

The experiments compare trained ReLU DNNs with compressed-sensing (CS) approximations on smooth and piecewise continuous test functions, varying function regularity, dimension, and network architecture. Performance depends strongly on the target and architecture: smooth-function tests expose a gap between approximation theory and practice, while DNNs outperform CS on the tested discontinuous halfspace.

4.1. Smooth one-dimensional functions.

  • For the smooth one-dimensional target with K = 1, shallow networks fail, while larger networks become competitive with unweighted and weighted CS.The target has rapidly decaying Legendre coefficients; increasing network size from 10 to 20 hidden layers yields diminishing returns.Source: §4.1 · p. 16, Figure 8 · p. 17
  • For the one-dimensional oscillatory target, the 20-hidden-layer network gives the best tested DNN accuracy after about 600 samples and matches weighted CS around 700 samples.Increasing depth and width improves accuracy, but wider architectures can show diminishing returns or diverge with numerical artifacts.Source: §4.1 · pp. 16–17
  • For K = 10, trained networks have larger-magnitude weights and biases on average than for K = 1, while wide-network artifacts occur despite weight magnitudes similar to narrower networks.The authors note that double precision can improve results on this function, but did not improve the 20-hidden-layer network’s accuracy.Source: §4.1 · pp. 16–17

4.2. Smooth higher-dimensional functions.

  • Despite analyticity, DNNs do not exceed three digits of accuracy on the smooth isotropic test, while both CS approaches achieve nearly eight digits.The authors identify this as a practical gap from theoretical results suggesting DNNs can match CS on this problem.Source: §4.2 · p. 18, Figure 13 · p. 20
  • On the smooth higher-dimensional test, best results use 10^3–10^5 trainable parameters; deeper networks help narrower designs, while shallower ones help wider designs.Wider and deeper networks can diverge, and weights grow with depth for the wider architectures as sample counts increase.Source: §4.2 · pp. 18–19, Figure 13 · p. 20
  • For the less-smooth anisotropic higher-dimensional target, CS reaches roughly 0.02 error, while the best ReLU DNNs achieve about five times smaller error.The target’s less-rapid Legendre-coefficient decay accompanies the weaker CS result.Source: §4.2 · p. 19, Figure 15 · p. 22

4.3. Piecewise continuous functions.

  • On the piecewise continuous halfspace, DNNs outperform CS in dimensions above one, but neither method achieves more than two digits of accuracy.CS fails to converge for d > 1; trained DNN weights remain bounded and do not reach the large values associated with the cited high-accuracy existence result.Source: §4.3 · pp. 21–22

5. Theoretical insights.

The theoretical section establishes exponential approximation rates for holomorphic functions, shows compressed sensing (CS) can attain them, and constructs a DNN training procedure with comparable guarantees. The DNN result is an existence benchmark, not a claim of practical or numerically stable performance.

5. Theoretical insights.

  • The section’s theoretical results proceed from best s-term polynomial approximation rates to CS recovery guarantees and then to a DNN existence result with corresponding guarantees.The DNN proof rewrites CS recovery as weighted square-root LASSO training and uses uniform neural-network approximation of a finite set of Legendre polynomials.Source: §5 · p. 22, §5.3 · p. 27

5.1. Exponential convergence of polynomial approximations.

  • For functions holomorphic on a Bernstein polyellipse, a lower set of at most s indices achieves exponential best s-term convergence at a rate adapting to anisotropy without prior knowledge of the ellipse parameters.The rate depends on the product of log(ρ_j), rather than log(ρ_min) as with a fixed isotropic index set; constants may scale poorly with d.Source: §5.1 · pp. 23–25

5.2. Exponential convergence via compressed sensing.

  • CS attains the best s-term approximation rates with sample complexity quadratic in s up to logarithmic factors, with scaling that depends only logarithmically on dimension d.The weighted ℓ1 norm promotes sparse lower sets; the authors state that unweighted ℓ1 would yield a higher algebraic power of s.Source: §5.2 · p. 26

5.3. Existence of good training for DNN approximation.

  • For holomorphic functions, Theorem 5.5 guarantees DNN approximations match CS convergence rates and sample complexity up to a constant, using an architecture with relatively few trainable parameters.The construction uses a weighted ℓ1 penalty on output-layer weights; the authors do not claim the procedure is practical or numerically stable.Source: §5.3 · pp. 26–27

6. Conclusions.

The paper concludes that standard trained DNNs often fall short of CS on smooth functions but are more promising on less-smooth and discontinuous functions. The appendices report implementation choices and show that learning-rate schedule effects vary with architecture.

6. Conclusions.

  • Standard DNN training generally fails to reach theoretical convergence rates on smooth functions, while DNNs are more promising on less-smooth functions and functions with jump discontinuities.The authors identify future work on architecture, cost-function, and training-algorithm design, alongside practical existence theory.Source: §6 · p. 27

Appendix A. Testing setup – further information.

  • The appendix describes hardware and precision comparisons, further Adam training details, learning-rate schedules, batch-size experiments, and CS truncation-parameter selection.It notes that double-precision GPU calculations can be substantially more demanding than single precision.Source: Appendix A · p. 28, §A.1 · p. 28

A.2. The Adam optimizer.

  • Adam uses β1 = 0.9, β2 = 0.999, δ = 10^-7, and an initial learning rate of 10^-3; training runs to a tolerance or a fixed epoch limit.The reported limits are 50,000 epochs or 5 × 10^-7 in single precision, and 200,000 epochs or 5 × 10^-16 in double precision.Source: §A.2 · p. 28

A.3. Learning rate schedules for Adam.

  • For the tested discontinuous two-dimensional function, exponential learning-rate decay marginally helps shallower networks, while its effect is insignificant for deeper networks.Bases below 0.85 may decay too quickly and stall; larger bases may decay too slowly for rapid training of larger models.Source: §A.3 · p. 28, Figure 20 · p. 29

A.4. Batch size comparison.

On the tested smooth eight-dimensional function, smaller Adam batches marginally improve error, but their increased training time is not proportional to that gain.

A.4. Batch size comparison.

  • Smaller batches marginally improve generalization error on the tested smooth 8-dimensional function, but their training-time increase is not proportional to the improvement.The comparison spans full, half, and quarter batches; performance at higher dimensions remains for future study.Source: §A.4 · p. 29, Figure 21 · p. 29

A.5. Stability of training with respect to noise.

In the reported experiments, both CS and the best-performing DNNs remain stable under additive Gaussian measurement noise: their L2 error scales with noiseless approximation error plus noise standard deviation.

A.5. Stability of training with respect to noise.

  • For noise levels σ ∈ {10^-1, 10^-2, 10^-3}, CS and the best-performing DNNs have L2 error proportional to noiseless approximation error plus noise standard deviation.The experiments add Gaussian noise to function measurements supplied to both methods.Source: §A.5 · pp. 29–30, Figure 22 · p. 30

Appendix B. Additional numerical results.

The additional experiments relate DNN training time to architecture and function smoothness, and report how compressed-sensing problems were configured.

Appendix B. Additional numerical results.

  • For function (4.2), architectures with better accuracy often trained faster than shallower or narrower alternatives, while some larger divergent architectures took longer.Figure 23 compares training time with sample count for ReLU architectures at different β values.Source: Appendix B · p. 30
  • Training DNNs on the less smooth function (4.3) took longer than on function (4.2).The passage reports this comparison from average run times.Source: Appendix B · p. 30
  • The numerical experiments use weighted or unweighted quadratically-constrained basis problems with the truncation parameter chosen as in (3.2).Source: Appendix B · p. 30

B.1. Truncation parameters in compressed sensing.

This section contrasts the parameter choice for compressed-sensing experiments with theoretical concerns about noise-dependent error estimates and a square-root LASSO alternative.

B.1. Truncation parameters in compressed sensing.

  • The experiments use weighted or unweighted quadratically-constrained basis pursuit, with η chosen as small as possible while keeping the exact coefficients feasible.The authors describe this as an optimal choice in some sense; cross-validation is an alternative when coefficients cannot be computed feasibly.Source: §B.1 · pp. 30–31
  • The quadratically-constrained basis-pursuit accuracy declines when η is too large or too small.Source: §B.1 · p. 30
  • Earlier theoretical error estimates for polynomial approximation via compressed sensing often require unrealistic assumptions on the expansion tail, a concern also applying to LASSO variants.The tail depends on unknown expansion coefficients, motivating the weighted square-root LASSO, whose optimal parameter μ depends on s rather than the noise term and permits explicit convergence rates without those assumptions.Source: §B.1 · pp. 30–31
  • Figure 23 compares training time with sample count for function (4.2) across ReLU architectures parameterized by β = L/N.The plotted β values range from 0.5 to 0.025.Source: Figure 23 · p. 31

Appendix C. Proofs.

Appendix C contains proofs of Theorems 5.2, 5.4, and 5.5.

Appendix C. Proofs.

C.1. Proof of Theorem 5.2.

The appendix proves results for compressed sensing recovery over lower sets, including conditions that guarantee recovery and a random-sampling condition for the Legendre measurement matrix.

C.1. Proof of Theorem 5.2.

  • Theorem 5.2’s proof uses techniques from [68, Sec. 3] and constructs a lower set using a threshold before bounding its size in terms of s.The construction is Λ = {ν : ρ^−ν ≥ ϵ}.Source: §C.1 · pp. 31–33

C.2. Compressed sensing for lower set recovery.

  • For lower-set recovery, the compressed-sensing setup differs from standard recovery of arbitrary s-sparse vectors and uses a hyperbolic-cross index set.Source: §C.2 · p. 33
  • Intrinsic lower sparsity K(s) is the maximum weighted cardinality over lower subsets of size at most s.The definition uses the weights u.Source: §C.2 · pp. 33–34
  • The lower robust null space property guarantees recovery for weighted square-root LASSO, while the lower restricted isometry property is a sufficient condition for that null-space property.The authors note that working directly with the lower rNSP is difficult in practice.Source: §C.2 · pp. 34–35
  • For the tensor Legendre polynomial measurement matrix, uniform independent samples yield the lower restricted isometry property with probability at least 1 − ε under the stated conditions.Source: §C.2 · p. 35

C.3. Proof of Theorem 5.4.

The proof of Theorem 5.4 establishes its error guarantee by showing that the sampling matrix has a lower restricted isometry property, which yields a lower robust null space property. It also derives a sufficient lower bound on the sample count.

C.3. Proof of Theorem 5.4.

  • The proof’s first and third bounds use Theorems 3.7 and 3.5 of, while its second uses [54, Thm. 4.9].Source: §C.3 · p. 36
  • With probability at least 1 − ε, the matrix A has lower restricted isometry of order 2s with constant δ ≤ δ2s,L = 1/6, which implies a lower rNSP via Lemma C.4.Source: §C.3 · p. 36
  • m ≥ c·s^2·L(2s, δ2s,L, ε) is the derived sufficient sample-count condition.Source: §C.3 · p. 37

C.4. Proof of Theorem 5.5.

Theorem 5.5’s proof approximates compressed-sensing matrix-vector multiplication with a ReLU network, then uses robustness of the lower rNSP to control the resulting error. It also establishes network complexity bounds.

C.4. Proof of Theorem 5.5.

  • The proof approximates Az with a neural network evaluated at sample points, then uses compressed-sensing results to derive an error bound.Because this approximation introduces an error, the proof first establishes robustness of the lower rNSP to small matrix perturbations.Source: §C.4 · p. 37
  • Lemma C.7 transfers the lower rNSP from A to its perturbed matrix A′, with adjusted constant ρ′ and the same τ.Source: §C.4 · p. 37
  • The constructed network family has n trainable parameters, with depth increased by 1 and size by n relative to ΦΛ,δ.Source: §C.4 · p. 38
  • The error estimate uses the assumption ∥f∥L∞(U) ≤ 1 and bounds on the coefficient norm and σs,L(c)1,u.Source: §C.4 · p. 39
  • The depth bound for ΦΛ,δ scales with (1 + d log(d))(1 + log(s))(s + log(s) + log(n) + γs1/d).Source: §C.4 · p. 40

Related papers

Loading 2001.07523v3…