PaperlayerView exact revision on arXiv

Source-linked AI summary

A comparison of deep networks with ReLU activation function and linear spline-type methods

Konstantin Eckle, Johannes Schmidt-Hieber

arXiv:1804.02253v2stat.MLcs.LGstat.ME

TL;DR

The paper asks whether deep ReLU networks are comparable in expressive power and statistical performance to piecewise-linear spline methods. It constructs network approximations to MARS and Faber-Schauder functions, derives risk comparisons, and reports finite-sample behavior alongside an initialization-related limitation.

  • Problem

    Deep networks are richer than shallow networks, but this alone does not explain their success; their expressive power should also be compared with piecewise-linear spline methods.

  • Method

    The paper constructively approximates MARS and Faber-Schauder functions with multilayer ReLU networks and derives statistical risk comparison inequalities.

  • Results

    O(M log(M/ε)) network parameters approximate either spline-class function with M parameters to sup-norm error ε, while some network-efficient functions are costly for both spline classes.

  • Takeaways & Limitations

    DNN fitting has no much larger statistical risk than MARS or Faber-Schauder estimation, and constructive proofs permit spline-based network initialization.

  • Takeaways & Limitations

    Finite-sample performance can be worse than spline methods because standard initialization may deactivate units or lead to suboptimal local minima.

Abstract

from arXiv · show

Deep neural networks (DNNs) generate much richer function spaces than shallow networks. Since the function spaces induced by shallow networks have several approximation theoretic drawbacks, this explains, however, not necessarily the success of deep networks. In this article we take another route by comparing the expressive power of DNNs with ReLU activation function to piecewise linear spline methods. We show that MARS (multivariate adaptive regression splines) is improper learnable by DNNs in the sense that for any given function that can be expressed as a function in MARS with $M$ parameters there exists a multilayer neural network with $O(M \log (M/\varepsilon))$ parameters that approximates this function up to sup-norm error $\varepsilon.$ We show a similar result for expansions with respect to the Faber-Schauder system. Based on this, we derive risk comparison inequalities that bound the statistical risk of fitting a neural network by the statistical risk of spline-based methods. This shows that deep networks perform better or only slightly worse than the considered spline methods. We provide a constructive proof for the function approximations.

1 Introduction

The paper compares deep ReLU networks with piecewise-linear spline methods, asking whether their expressive power and statistical performance are comparable. It shows that spline functions can be efficiently approximated by DNNs and that corresponding risk comparisons follow.

  • Motivation: ReLU networks produce piecewise linear functions, making them structurally comparable to several spline-based nonparametric methods.The paper focuses on methods built from piecewise linear function classes.
  • Motivation: Deep networks avoid some shallow-network drawbacks, including inefficient localization and multiplication, motivating comparisons beyond shallow architectures.The paper frames spline methods as structurally similar alternatives that may not share these shortcomings.
  • Scope: The comparison targets MARS and Faber-Schauder expansions, both based on piecewise linear functions.MARS uses tensorization for multivariate functions, while Faber-Schauder functions arise from integrated Haar wavelets.
  • Main results: For either spline class with M parameters, a multilayer network with O(M log(M/ε)) parameters achieves sup-norm error ε.The paper also reports that the converse fails for some functions, which are much more efficiently represented by networks.
  • Statistical comparison: Risk comparison inequalities show that fitting a DNN does not incur much larger statistical risk than MARS or Faber-Schauder series estimation.The results are presented as applying directly to the two considered spline methods, with possible extension to related multivariate spline systems.
  • Constructive proof: The constructive approximation proof permits initializing a DNN from a previously fitted MARS or Faber-Schauder function.This yields a two-step procedure: first estimate the spline function, then use it to initialize the network.

2 Spline type methods for function estimation

This section introduces MARS and Faber-Schauder methods as piecewise-linear function estimators, describing their bases, fitting procedures, and approximation properties. Faber-Schauder expansions interpolate on dyadic grids and connect to MARS through finite representations.

  • MARS: MARS builds multivariate piecewise-linear basis functions by multiplying hinge factors, whose supports are hyperrectangles.The basis uses index sets, signs, and shifts to construct products of factors such as (x_j−t_j)+.
  • MARS: MARS greedily selects basis functions that improve least-squares fit, beginning with a constant and adding two functions at each step.A backward deletion procedure may subsequently remove selected functions with small predictive power.
  • MARS: Higher-order MARS replaces linear hinge factors with piecewise-polynomial basis functions, while retaining the same general procedure.The paper denotes this extension HO-MARS.
  • Faber-Schauder: Faber-Schauder functions are piecewise linear and arise as integrals of Haar wavelets; multivariate systems are obtained by tensorization.Their expansions therefore produce componentwise piecewise-linear approximations.
  • Faber-Schauder: At resolution level j, univariate Faber-Schauder reconstruction linearly interpolates the function on the dyadic grid x = k/2^(j+1).The lowest level interpolates at 0 and 1, and higher levels add dyadic knot points.
  • Faber-Schauder: Multivariate Faber-Schauder reconstruction equals the linear interpolating spline at dyadic knot points and supports universal approximation.The reconstruction matches the function on the relevant grid and remains piecewise linear in each component.
  • Connection between methods: Each tensor-product Faber-Schauder function can be represented as a linear combination of 3^d MARS functions.Consequently, the truncated Faber-Schauder class is contained in a corresponding MARS class with transformed complexity and coefficient bounds.
  • Approximation properties: The MARS function class also satisfies a universal approximation theorem.This follows from the representation relationship between Faber-Schauder functions and MARS functions.

3 Deep neural networks (DNNs)

The paper models deep ReLU networks algebraically through layered affine maps and shifted ReLU activations. It also defines sparsity and bounded-parameter network classes to support theoretical analysis.

  • Network definition: A deep ReLU network uses the activation σ(x) = max(x, 0) between successive affine transformations.The network is represented as a composition of weight matrices, shifted activations, and an output map.
  • Network architecture: Network depth is L, while the width vector p records the number of units at each layer and begins with input dimension d.Real-valued outputs require the final width to equal one.
  • Sparsity: Sparsity counts active or nonzero network parameters across weight matrices and shift vectors.Sparse-network assumptions are used as a theoretical analogue for regularized reconstructions.
  • Network class: The theoretical network class bounds every weight and shift parameter by one and imposes a supremum-norm bound on the output.The class is indexed by depth, architecture, and sparsity.
  • Training and regularization: Practical DNN fitting typically uses stochastic gradient descent on empirical loss, alongside methods such as weight decay, batch normalization, and dropout.The paper notes that a complete theoretical treatment of these combined techniques remains out of reach.

4 Deep networks vs. spline type methods

The paper constructs ReLU networks that approximate MARS and Faber-Schauder functions with only a logarithmic parameter overhead, then shows converse separations where DNNs are substantially more parameter-efficient.

  • 4.1 Improper learning of spline type methods by deep networks: A ReLU network approximates every MARS function with M parameters to sup-norm error ε using O(M log(M/ε)) parameters.The network architecture exists for fixed input dimension and ε ∈ (0, 1].
  • 4.1 Improper learning of spline type methods by deep networks: Faber-Schauder functions with I parameters likewise require network size of order I up to a logarithmic factor for ε-approximation.This follows by embedding Faber-Schauder functions into the MARS class.
  • 4.1 Improper learning of spline type methods by deep networks: The constructive proofs support a two-step procedure that learns a spline function first and converts it into a DNN initialization.The resulting network approximates the learned function up to error ε and can initialize an iterative method.
  • 4.1 Improper learning of spline type methods by deep networks: The product approximation used in the construction achieves error at most 3r2^-N with at most 42r2(1 + (N + 5)⌈log2 r⌉) parameters.This multiplication network is the key building block for approximating the spline classes.
  • 4.2 Lower bounds: DNNs approximate x2 with O(log(1/ε)) parameters, whereas MARS and Faber-Schauder require at least order ε^-1/2 parameters; DNNs also efficiently represent (x1+x2−1)+.The latter function uses one neural-network layer and four parameters, while tensorized spline classes require far more parameters for cross-input linear combinations.
  • 4.2 Lower bounds: For f(x)=x2, MARS and Faber-Schauder classes have approximation error lower bounded by 1/(36M2) for MARS and the corresponding piecewise-linear bound for Faber-Schauder functions.The lower bound follows because these classes are piecewise linear with at most M+1 or 2M+2 pieces.

5 Risk comparison for nonparametric regression

The paper studies prediction risk in nonparametric regression and bounds neural-network risk using spline approximation quality plus optimization and complexity-related remainders.

  • The regression model estimates a bounded function f0 from independent observations Yi = f0(Xi) + εi with standard-normal noise.
  • Prediction risk evaluates an estimator on an independent test covariate X having the same distribution as the training covariates.
  • The analysis separates statistical risk from optimization error through Δn, the excess loss relative to the empirical risk minimizer over the network class.Δn is nonnegative and equals zero for an empirical risk minimizer.
  • Theorem 5.1 bounds neural-network risk by the best approximation over MARS functions plus a remainder.The remainder is roughly Δn + M/n, where M is the maximal number of MARS basis functions.
  • Theorem 5.2 constructs a network class with depth O(log n), width O(I), and parameter count O(I log n) for comparison with the approximation scheme.

6 Finite sample results

The simulations compare DNNs, MARS, higher-order MARS, and Faber–Schauder reconstructions across smooth, oscillatory, discontinuous, and high-dimensional regression settings. Results depend on function structure and network initialization: spline methods often excel for oscillations, while DNNs avoid jump artifacts and achieve lower risk in the dimensional experiments.

  • Experimental setup: The study compares DNNs, MARS, higher-order MARS, and Faber–Schauder expansions through simulation-based reconstruction experiments.DNNs use Adam; the experiments also vary network depth, width, spline order, and parameter counts.
  • Smooth function: For f0(x) = x^2, higher-order MARS exactly represents the regression function, while DNNs and Faber–Schauder estimation have comparable quality and MARS performs worse.The noisy and noiseless models both show substantially smaller prediction risk than the noisy case.
  • Oscillatory function: For the highly oscillating sine function, the Faber–Schauder series expansion performs best, although all methods require many parameters.The comparison uses MARS with M = 50, HO-MARS with K = 5 and M = 50, Faber–Schauder with M = 6, and a ten-hidden-layer network.
  • Discontinuous function: For the jump function, the neural network reconstruction does not add spurious artifacts around the jump location compared with the other methods.This experiment examines approximation when standard smoothness assumptions are violated.
  • High-dimensional functions: Across dimensions d = 1, 2, 5, 10, neural networks achieve consistently smaller risk than higher-order MARS, although both methods suffer from the curse of dimensionality.The experiment uses HO-MARS with K = 10, M = 30 and a network with L = 15 and width 10 in hidden layers.
  • High-dimensional functions: With 10 active parameters and d = 1000, neural-network and higher-order-MARS risks remain comparable to the final row of Table 4, indicating adaptation to active parameters.Here the input dimension equals the sample size.

7 Proofs

The proofs construct ReLU networks that approximate spline basis functions and combine them into approximations of MARS or Faber–Schauder expansions. They then use covering-number and oracle-inequality arguments to transfer these approximation bounds into statistical risk bounds.

  • Approximation construction: Each MARS or Faber–Schauder basis function is approximated by a constructed ReLU network before the basis approximations are combined.For Faber–Schauder functions, the construction builds hinge factors and applies a multiplication network.
  • Approximation construction: The Faber–Schauder construction yields a network Hm,N with sup-norm error at most 3d2^-N and active-parameter count at most 42d^2((N + 5)⌈log2 d⌉ + 2).The network architecture has depth (N + 5)⌈log2 d⌉ + 1 and hidden widths based on 6d.
  • Approximation construction: To approximate a linear combination, the proof adds a constant coordinate, scales basis outputs by bounded coefficients, and uses a final layer containing the coefficients.The scaling subnetworks use logarithmic depth and parameter counts in the coefficient bound C.
  • Risk analysis: The risk proofs bound neural-network estimation error using an oracle inequality together with covering-number bounds for the network class.ReLU Lipschitz continuity supplies the covering-number control.
  • Risk analysis: For fixed C, the resulting network class has depth O(log Mn), maximum width O(M), and active-parameter count O(M log Mn), with approximation error at most 1/n.This class is used in the proof of the MARS risk theorem.
  • Risk analysis: Theorem 5.2 follows by replacing M and the index set in the corresponding bounds and repeating the proof strategy used for Theorem 5.1.The same approximation-and-entropy framework is reused for the second spline class.
Loading 1804.02253v2…