On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces

Area of Science:

• Machine Learning
• Theoretical Computer Science
• Statistical Learning Theory

Background:

• Deep learning demonstrates superior performance in machine learning tasks compared to methods like kernel methods.
• Existing theoretical studies often focus on smooth function classes (e.g., Hölder, Besov), not capturing practical complexities.
• Understanding the theoretical underpinnings of deep learning's success, particularly for non-smooth functions, remains crucial.

Purpose of the Study:

• To provide a theoretical understanding of deep learning's effectiveness in nonparametric regression.
• To analyze deep learning performance on function classes with discontinuity and sparsity.
• To compare deep learning against linear (shallow) estimators in challenging function settings.

Main Methods:

• Theoretical analysis of deep learning and linear estimators on nonparametric regression problems with Gaussian noise.
• Focus on function classes characterized by discontinuity and sparsity.
• Comparison of minimax risks for deep learning and linear methods on specific function classes.

Main Results:

• Linear methods are suboptimal on non-convex function classes where deep learning achieves near-minimax-optimal rates.
• Deep learning attains minimax rates (up to log factors) on function classes with sparse wavelet coefficients.
• Linear methods remain suboptimal for strongly sparse function classes.
• Parameter sharing in deep neural networks effectively reduces model complexity in this context.

Conclusions:

• Deep learning offers significant advantages over linear methods for nonparametric regression, especially with discontinuous and sparse data.
• The theoretical framework supports deep learning's ability to handle complex function classes more effectively.
• Parameter sharing is identified as a key mechanism contributing to deep learning's efficiency.