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

Satoshi Hayakawa, Taiji Suzuki

Deep learning has revolutionized fields like computer vision and speech recognition, often outperforming traditional "linear" methods like kernel ridge regression. While we know deep learning works, the mathematical "why" is still being mapped out.

In this paper, Satoshi Hayakawa and Taiji Suzuki provide a rigorous theoretical explanation for this superiority. They show that deep neural networks are fundamentally better at learning from sparse parameter spaces—settings where the target function is composed of only a few active components, a common trait in real-world data.

TL;DR

This paper proves that deep ReLU networks are minimax-optimal for sparse and discontinuous function classes where traditional linear estimators (like kernels) are fundamentally suboptimal. By leveraging non-convexity and parameter sharing, deep learning "breaks" the performance barriers that limit linear methods in high-dimensional, sparse settings.

What Problem Does This Paper Address?

Most classical statistical theory assumes that the functions we want to learn are "smooth" (belonging to Hölder or Besov classes). However, real-world data is often "messy": images have sharp edges (discontinuities), and speech signals are composed of sparse combinations of basic patterns.

The authors tackle the gap between deep learning's practical success and its theoretical understanding. Specifically, they ask: Why does deep learning converge faster than linear methods on these "natural" sparse datasets?

The core challenge is that linear estimators—a broad class including many kernel methods—cannot distinguish between a function class and its convex hull. If a function class is sparse (and thus non-convex), its convex hull is much larger and more complex. Linear methods are forced to "pay" for this extra complexity, leading to slower convergence rates.

Methods

The authors use the framework of nonparametric regression, where the goal is to estimate an unknown function $f^\circ$ from noisy data. They compare deep ReLU networks against "linear estimators" (estimators that are linear combinations of the observed outputs).

To prove their point, they define several "sparse" function classes:

  • $\mathcal{I}^0_\Phi$ ($\ell^0$-bounded affine class): Functions built from a finite number of affine-transformed basis functions (like a few shifted and scaled pulses).
  • $\mathcal{K}^p_\Psi$ (Weak $\ell^p$-approximated wavelet class): Functions where the wavelet coefficients decay quickly, representing a high degree of sparsity.

They use $\epsilon$-entropy (a measure of how many "bits" are needed to describe a function class) to derive minimax lower bounds. This allows them to determine the absolute best possible error rate any algorithm could achieve and then show that deep learning hits that limit while linear methods do not.

This figure illustrates how complex functions can be built from sparse combinations of basis functions $\psi_1$ and $\psi_2$.

Datasets

As a theoretical study, this paper does not use empirical datasets. Instead, it evaluates performance on mathematically defined function classes that serve as proxies for real-world data characteristics, such as:

  • Piecewise constant functions ($J_k$): Modeling sharp transitions in signals.
  • Sparse Wavelet spaces: Modeling the "natural" sparsity found in images and audio.

Key Insights and Ideas

  • The Convex Hull Trap: Linear estimators are mathematically "blind" to the gaps in non-convex sets. If your target functions are sparse points in a high-dimensional space, a linear method treats the entire volume between those points as part of the search space. Deep learning, being non-convex, can "shrink-wrap" the sparse set.
  • ReLU as a Universal Approximator for Sparsity: The authors show that deep ReLU networks are exceptionally efficient at approximating wavelets and piecewise polynomials.
  • Parameter Sharing: The paper highlights that parameter sharing (a hallmark of CNNs) is not just an engineering trick; it's a theoretical powerhouse. It drastically reduces the "covering entropy" of the model, allowing it to generalize better from fewer samples.
A comparison of the mathematical features of the study and their real-world counterparts.

Key Results

The main quantitative takeaway is the comparison of convergence rates (how fast the error drops as you add more data $n$).

Summary of error bounds for deep learning vs. linear methods across different function classes.
  • Piecewise Constant Functions: Deep learning achieves a near-optimal rate of $\tilde{O}(n^{-1})$, while linear methods are stuck at $\Omega(n^{-1/2})$.
  • Sparse Wavelet Classes ($\mathcal{K}^p_\Psi$): Deep learning attains the minimax rate $\tilde{O}(n^{-\frac{2\alpha}{2\alpha+1}})$. In contrast, linear methods remain suboptimal at $\Omega(n^{-1/2})$, and their performance can become "arbitrarily slow" as the sparsity becomes more extreme.
  • Complexity Reduction: The authors prove that parameter sharing can remarkably reduce the model complexity required to reach these optimal rates.

Limitations and Future Work

  • Orthogonality Constraints: Much of the proof for wavelet classes relies on the basis being orthonormal. The authors suggest that future work should explore removing this restriction to better model "overcomplete" dictionaries used in practice.
  • Optimization Dynamics: The paper assumes "ideal optimization"—that we can actually find the best neural network. It doesn't account for the "messiness" of Stochastic Gradient Descent (SGD) or local minima.
  • CNN Specifics: While parameter sharing is discussed, the results are general. Applying these bounds specifically to standard Convolutional Neural Network architectures remains an open challenge.

Summary updated

Abstract

Deep learning has been applied to various tasks in the field of machine learning and has shown superiority to other common procedures such as kernel methods. To provide a better theoretical understanding of the reasons for its success, we discuss the performance of deep learning and other methods on a nonparametric regression problem with a Gaussian noise. Whereas existing theoretical studies of deep learning have been based mainly on mathematical theories of well-known function classes such as Hölder and Besov classes, we focus on function classes with discontinuity and sparsity, which are those naturally assumed in practice. To highlight the effectiveness of deep learning, we compare deep learning with a class of linear estimators representative of a class of shallow estimators. It is shown that the minimax risk of a linear estimator on the convex hull of a target function class does not differ from that of the original target function class. This results in the suboptimality of linear methods over a simple but non-convex function class, on which deep learning can attain nearly the minimax-optimal rate. In addition to this extreme case, we consider function classes with sparse wavelet coefficients. On these function classes, deep learning also attains the minimax rate up to log factors of the sample size, and linear methods are still suboptimal if the assumed sparsity is strong. We also point out that the parameter sharing of deep neural networks can remarkably reduce the complexity of the model in our setting. Previous article in issue Next article in issue
BibTeX
@article{hayakawa2020minimax,
  author = {Satoshi Hayakawa and Taiji Suzuki},
  title = {{On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces}},
  journal = {Neural Networks},
  year = {2020},
  doi = {10.1016/j.neunet.2019.12.014},
}

Loading related content...

Figure