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

Satoshi Hayakawa, Taiji Suzuki

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.
Conceptual framework illustrating how complex function classes are constructed from sparse combinations of basis functions.

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.

Comparison of convergence rates for deep learning versus linear methods across different function classes.

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

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\"{o}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.
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},
}
Figure