Abstract
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.
Introduction
Deep Neural Networks (DNNs) with ReLU activation functions are essentially engines for creating piecewise linear functions. However, statisticians have used other piecewise linear methods for decades—most notably Multivariate Adaptive Regression Splines (MARS) and Faber-Schauder series expansions.
If both approaches produce the same "type" of output (piecewise linear), why have deep networks become the dominant force in modern AI while splines remain a niche tool for specific statistical tasks? This research investigates the "expressive power" gap: determining if a deep network can replicate spline-based functions and identifying where deep networks offer superior efficiency.
Methodology
The study employs a mix of constructive mathematical proofs and statistical risk analysis to compare these frameworks:
- Constructive Approximation: The authors prove that for any function represented by a MARS model with $M$ parameters, there exists a deep ReLU network with $O(M \log(M/\epsilon))$ parameters that approximates it within an error of $\epsilon$. This demonstrates that DNNs "improperly learn" splines—they can simulate them almost perfectly with only a logarithmic increase in complexity.
- Lower Bound Analysis: Specific functions are identified where splines fail to maintain efficiency. By analyzing the approximation of $f(x) = x^2$, the authors reveal a massive efficiency gap.
- Oracle Inequalities: The paper derives "risk comparison inequalities" that bound the statistical risk (expected error on new data) of a fitted neural network by the risk of spline-based methods. This provides a theoretical guarantee that DNNs will perform at least as well as (or better than) splines in regression settings.
Key Insights: The Efficiency Gap and Tensorization
The $x^2$ Efficiency Gap
A striking finding is the comparison for $f(x) = x^2$. To achieve an error $\epsilon$, a spline method requires $O(\epsilon^{-1/2})$ parameters. In contrast, a deep ReLU network only needs $O(\log(1/\epsilon))$ parameters. This represents an exponential improvement in efficiency for approximating smooth, curved functions.
The Weakness of Tensorization
Spline methods like MARS are built using "tensorization"—the process of multiplying univariate functions together to create multivariate basis functions. This approach is illustrated in the various interaction patterns shown below.
While these basis functions can cover the space, they are poorly suited for functions involving linear combinations of inputs (like $x_1 + x_2$). DNNs handle these interactions naturally in their first layer, whereas splines require a massive number of parameters to approximate the same logic.
Results and Performance
- Theoretical Dominance: The authors prove that deep networks perform better or only slightly worse than the considered spline methods across the board.
- High-Dimensional Adaptivity: In simulations with 1,000 input dimensions where only 10 are relevant, DNNs consistently achieved smaller prediction risks than higher-order MARS. This suggests that DNNs are better at "finding the needle in the haystack" in high-dimensional data.
- Jump Functions: For functions with sharp jumps, DNNs were found to produce fewer "spurious artifacts" (unwanted oscillations or wiggles) around the jump compared to spline methods.
- Optimization Bottlenecks: While a DNN can represent these functions, standard optimization (like SGD) often fails to find them. The authors introduced an "increasing Glorot" initialization to help the network capture the shape of the target function more effectively, highlighting that the gap between theory and practice often lies in the optimization path.
Conclusion
This research bridges the gap between classical statistics and modern deep learning. By proving that deep ReLU networks can efficiently mimic and often surpass the expressive power of spline-based methods like MARS, it provides a rigorous foundation for the empirical success of deep learning in high-dimensional regression tasks. While optimization remains a practical challenge, the theoretical potential of DNNs to handle complex interactions and smooth functions with logarithmic parameter growth explains their superiority over traditional tensor-product methods.
Summary updated