Optimal approximation of piecewise smooth functions using deep ReLU neural networks

Area of Science:

• Machine Learning Theory
• Neural Network Approximation
• Computational Complexity

Background:

• Understanding the representational power of neural networks is crucial for deep learning.
• Piecewise smooth functions are common in real-world data and require efficient approximation.
• The complexity of neural networks, in terms of depth and weights, dictates their approximation capabilities.

Purpose of the Study:

• To establish the necessary and sufficient complexity (depth and weights) of ReLU networks for approximating piecewise C^β functions in L^p-sense.
• To determine the optimal approximation rates and the role of network depth in achieving them.
• To analyze approximation in high-dimensional spaces with factorizable functions.

Main Methods:

• Construction of ReLU neural networks to approximate functions in the E^β(R^d) class.
• Derivation of lower bounds on the description complexity of E^β(R^d) to prove optimality.
• Analysis of network depth requirements and approximation rates in factorized high-dimensional settings.

Main Results:

• Constructed ReLU networks achieve optimal L^2 approximation error ε for E^β(R^d) functions.
• The number of non-zero weights is proven to be optimal at O(ε^(-2(d-1)/β)).
• Minimal network depth is shown to be proportional to β/d, demonstrating the necessity of depth for efficient approximation.

Conclusions:

• Deep ReLU networks are necessary for efficiently approximating piecewise smooth functions.
• The study provides tight bounds on network complexity, offering theoretical insights into deep learning.
• In high-dimensional settings with factorizable functions, approximation complexity depends on feature space dimension, not input dimension.