Abstract Deep learning has demonstrated remarkable success across various machine learning tasks, often outperforming traditional kernel methods. To understand this success theoretically, we analyze the performance of deep learning in nonparametric regression settings involving Gaussian noise. While most theoretical studies focus on smooth function classes like Hölder or Besov spaces, this work investigates function classes with discontinuity and sparsity—characteristics common in real-world data. We demonstrate that deep neural networks achieve minimax-optimal rates on these classes, whereas linear estimators remain suboptimal. Furthermore, we show how parameter sharing in deep networks significantly reduces model complexity.
Introduction: Beyond Smoothness
Traditional statistical learning theory often relies on the assumption of smoothness, typically modeled via Hölder or Besov classes. However, real-world signals—such as images with sharp edges or speech with transient patterns—are frequently discontinuous and sparse. This paper by Satoshi Hayakawa and Taiji Suzuki addresses the gap between deep learning's empirical success on such "messy" data and its theoretical foundations.
The central question is: Why does deep learning converge faster than linear methods on sparse datasets? The authors argue that the answer lies in the fundamental inability of linear estimators to exploit non-convexity and sparsity.
Theoretical Framework: Sparse Function Classes
The authors utilize the framework of nonparametric regression to estimate an unknown function $f^\circ$ from noisy observations. They define specific function classes that capture the essence of sparsity:
- $\mathcal{I}^0_\Phi$ ($\ell^0$-bounded affine class): Functions composed of a finite number of affine-transformed basis functions.
- $\mathcal{K}^p_\Psi$ (Weak $\ell^p$-approximated wavelet class): Functions where wavelet coefficients exhibit rapid decay, representing high sparsity.
By analyzing the $\epsilon$-entropy of these classes, the authors establish minimax lower bounds, representing the theoretical limit of performance for any estimator.
The Suboptimality of Linear Estimators
A critical insight of this work is the "Convex Hull Trap." Linear estimators—including many kernel-based methods—are mathematically constrained by the convex hull of the target function class. In high-dimensional sparse settings, the target class is often a non-convex set. Because linear methods cannot distinguish between a set and its convex hull, they are forced to search a much larger space, leading to significantly slower convergence rates. Deep neural networks, being non-linear and non-convex, can effectively "shrink-wrap" the sparse target set, avoiding this complexity penalty.
Main Results: Minimax Optimality of Deep Learning
The study proves that deep ReLU networks are minimax-optimal for these sparse and discontinuous classes. The table below summarizes the convergence rates, showing a clear advantage for deep learning over linear methods.
Key quantitative findings include:
- Piecewise Constant Functions: Deep learning achieves a near-optimal rate of $\tilde{O}(n^{-1})$, while linear methods are limited to $\Omega(n^{-1/2})$.
- Sparse Wavelet Classes: Deep learning attains the minimax rate $\tilde{O}(n^{-\frac{2\alpha}{2\alpha+1}})$. Linear methods remain suboptimal at $\Omega(n^{-1/2})$, and their performance can become "arbitrarily slow" as the sparsity becomes more extreme.
The Power of Parameter Sharing
Beyond non-convexity, the paper highlights parameter sharing as a theoretical advantage. In architectures like Convolutional Neural Networks (CNNs), parameter sharing reduces the "covering entropy" of the model. The authors prove that this mechanism allows the model to reach optimal rates with significantly lower complexity, explaining why shared-weight architectures generalize so well from limited data.
Conclusion and Future Directions
This work provides a rigorous justification for the superiority of deep learning in sparse parameter spaces. While the results are compelling, the authors note that future research should address the constraints of orthonormal bases in wavelet classes and the specific optimization dynamics of Stochastic Gradient Descent (SGD). Extending these bounds to specific CNN architectures also remains a promising area for further study.
Summary updated