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

Area of Science:

• Machine Learning
• Computational Theory
• Numerical Analysis

Background:

• Deep neural networks (DNNs) possess richer function spaces than shallow networks, but the theoretical reasons for their success remain debated.
• Shallow network function spaces exhibit approximation-theoretic drawbacks, necessitating further investigation into the advantages of deep architectures.
• Understanding the expressive power of DNNs is crucial for advancing machine learning theory and practice.

Purpose of the Study:

• To compare the function approximation capabilities of deep neural networks (DNNs) with ReLU activation to linear spline methods.
• To establish theoretical bounds on the learnability of functions represented by MARS and Faber-Schauder systems using DNNs.
• To derive risk comparison inequalities between DNNs and spline-based methods to quantify their relative statistical performance.

Main Methods:

• Demonstrated that multivariate adaptive regression splines (MARS) are 'improperly learnable' by DNNs, showing DNNs can approximate MARS functions with a specific parameter complexity.
• Extended this learnability result to functions expanded with respect to the Faber-Schauder system.
• Derived risk comparison inequalities to bound the statistical risk of fitting neural networks relative to spline-based methods.

Main Results:

• A constructive proof shows that for any MARS function with M parameters, a DNN with O(Mlog(M∕ε)) parameters can approximate it within sup-norm error ε.
• Similar approximation guarantees were established for Faber-Schauder system expansions.
• Derived risk inequalities indicate that deep networks perform comparably to or better than the analyzed spline methods in terms of statistical risk.

Conclusions:

• Deep neural networks (DNNs) possess significant function approximation power, theoretically matching or surpassing traditional spline-based methods.
• The study provides a theoretical foundation for the success of deep learning by linking its expressive power to established approximation theory.
• These findings suggest that deep networks offer a competitive or superior alternative to spline methods for complex function approximation tasks.