Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories

Zixuan Zhang, Minshuo Chen, Mengdi Wang, Wenjing Liao, Tuo Zhao

Research output: Contribution to journalConference articlepeer-review


Existing theories on deep nonparametric regression have shown that when the input data lie on a low-dimensional manifold, deep neural networks can adapt to the intrinsic data structures. In real world applications, such an assumption of data lying exactly on a low dimensional manifold is stringent. This paper introduces a relaxed assumption that the input data are concentrated around a subset of Rd denoted by S, and the intrinsic dimension of S can be characterized by a new complexity notation - effective Minkowski dimension. We prove that, the sample complexity of deep nonparametric regression only depends on the effective Minkowski dimension of S denoted by p. We further illustrate our theoretical findings by considering nonparametric regression with an anisotropic Gaussian random design N(0, Σ), where Σ is full rank. When the eigenvalues of Σ have an exponential or polynomial decay, the effective Minkowski dimension of such an Gaussian random design is p = O(√log n) or p = O(nγ), respectively, where n is the sample size and γ ∈ (0, 1) is a small constant depending on the polynomial decay rate. Our theory shows that, when the manifold assumption does not hold, deep neural networks can still adapt to the effective Minkowski dimension of the data, and circumvent the curse of the ambient dimensionality for moderate sample sizes.

Original languageAmerican English
Pages (from-to)40911-40931
Number of pages21
JournalProceedings of Machine Learning Research
StatePublished - 2023
Event40th International Conference on Machine Learning, ICML 2023 - Honolulu, United States
Duration: Jul 23 2023Jul 29 2023

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Cite this