TL;DR
This paper provides a rigorous mathematical comparison between deep ReLU neural networks and traditional linear spline methods like MARS. The authors prove that deep networks can efficiently "mimic" these spline methods with minimal overhead, while also demonstrating that deep networks are exponentially more efficient at approximating certain smooth functions and multivariate interactions.
What Problem Does This Paper Address?
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? The authors tackle this by investigating the "expressive power" gap: can a deep network do everything a spline can do, and can it do things splines can’t?
Methods
The authors employ a mix of constructive mathematical proofs and statistical risk analysis:
- Constructive Approximation: They 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 shows that DNNs "improperly learn" splines—they can simulate them almost perfectly with only a logarithmic increase in complexity.
- Lower Bound Analysis: They identify specific functions where splines fail to keep up. By analyzing the approximation of $f(x) = x^2$, they show a massive efficiency gap.
- Oracle Inequalities: The paper derives "risk comparison inequalities." These bound the statistical risk (the expected error on new data) of a fitted neural network by the risk of spline-based methods, providing a theoretical guarantee that DNNs will perform at least as well as (or better than) splines in a regression setting.
Datasets
As a theoretical paper, the authors do not use standard image or text benchmarks. Instead, they use synthetic datasets generated from specific mathematical functions to test their theories:
- Univariate smooth functions: $f(x) = x^2$ and $f(x) = \sin(5 \cdot 2\pi x)$.
- Discontinuous functions: A jump function to test how methods handle non-smoothness.
- Multivariate interactions: $f(x_1, x_2) = (x_1 + x_2 - 1)_+$.
- High-dimensional models: Simulations where the input dimension $d$ ranges from 1 to 1000, but only a few variables are "active."
Key Insights and Ideas
- The $x^2$ Efficiency Gap: One of the most striking "aha moments" is the comparison for $f(x) = x^2$. To achieve an error $\epsilon$, a spline method requires $O(\epsilon^{-1/2})$ parameters. A deep ReLU network, however, only needs $O(\log(1/\epsilon))$ parameters. This is an exponential improvement in efficiency for approximating smooth, curved functions.
- The Weakness of Tensorization: Spline methods like MARS are built using "tensorization"—multiplying univariate functions together. This makes them 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.
- Initialization is the Bottleneck: The authors note that while a DNN can represent these functions, standard optimization (like SGD) often fails to find them. They introduce 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.
Key Results
- 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.
Limitations and Future Work
- Optimization vs. Approximation: The paper focuses heavily on what a network can represent (approximation theory). However, the authors acknowledge that in practice, deep networks often get stuck in local minima or flat regions. Their theory assumes we can find the "good" network, which isn't always true.
- Sparsity Assumptions: The theoretical results rely on the "sparsity paradigm"—the idea that most network parameters are zero. While this is a common theoretical tool, it doesn't perfectly match how most practitioners train dense, overparameterized networks.
- Scope of Splines: The study is limited to MARS and Faber-Schauder systems. While the authors believe the results generalize to other multivariate splines, those specific proofs are left for future work.
Summary updated