How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning

• URL: http://arxiv.org/abs/2407.05664v1
• Date: Mon, 8 Jul 2024 06:59:29 GMT
• Title: How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning
• Authors: Arthur Jacot, Seok Hoan Choi, Yuxiao Wen,
• Abstract summary: We show that deep neural networks (DNNs) can efficiently learn any composition of functions with bounded $F_1$-norm. We compute scaling laws empirically and observe phase transitions depending on whether $g$ or $h$ is harder to learn.
• Score: 9.302851743819339
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We show that deep neural networks (DNNs) can efficiently learn any composition of functions with bounded $F_{1}$-norm, which allows DNNs to break the curse of dimensionality in ways that shallow networks cannot. More specifically, we derive a generalization bound that combines a covering number argument for compositionality, and the $F_{1}$-norm (or the related Barron norm) for large width adaptivity. We show that the global minimizer of the regularized loss of DNNs can fit for example the composition of two functions $f^{*}=h\circ g$ from a small number of observations, assuming $g$ is smooth/regular and reduces the dimensionality (e.g. $g$ could be the modulo map of the symmetries of $f^{*}$), so that $h$ can be learned in spite of its low regularity. The measures of regularity we consider is the Sobolev norm with different levels of differentiability, which is well adapted to the $F_{1}$ norm. We compute scaling laws empirically and observe phase transitions depending on whether $g$ or $h$ is harder to learn, as predicted by our theory.

Related papers

• Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
  We show that gradient descent with a fixed learning rate $eta$ can only find local minima that represent smooth functions. We also prove a nearly-optimal MSE bound of $widetildeO(n-4/5)$ within the strict interior of the support of the $n$ data points.
  arXiv  Detail & Related papers  (2024-06-10T22:57:27Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  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 intrinsic data structures. This paper introduces a relaxed assumption that input data are concentrated around a subset of $mathbbRd$ denoted by $mathcalS$, and the intrinsic dimension $mathcalS$ can be characterized by a new complexity notation -- effective Minkowski dimension.
  arXiv  Detail & Related papers  (2023-06-26T17:13:31Z)
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
  Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. We propose an extension, $(k,t)$-FWL, which considers any equivariant set as neighbors instead of all nodes. N$2$-GNN achieves record-breaking results on ZINC-Subset (0.059), outperforming previous SOTA results by 10.6%.
  arXiv  Detail & Related papers  (2023-06-05T21:35:32Z)
• Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff [12.351756386062291]
  We formalize a balance between learning low-dimensional representations and minimizing complexity/irregularity in the feature maps. For large depths, almost all hidden representations are approximately $R(0)(f)$-dimensional, and almost all weight matrices $W_ell$ have $R(0)(f)$ singular values close to 1. Interestingly, the use of large learning rates is required to guarantee an order $O(L)$ NTK which in turns guarantees infinite depth convergence of the representations of almost all layers.
  arXiv  Detail & Related papers  (2023-05-30T13:06:26Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• The Onset of Variance-Limited Behavior for Networks in the Lazy and Rich Regimes [75.59720049837459]
  We study the transition from infinite-width behavior to this variance limited regime as a function of sample size $P$ and network width $N$. We find that finite-size effects can become relevant for very small datasets on the order of $P* sim sqrtN$ for regression with ReLU networks.
  arXiv  Detail & Related papers  (2022-12-23T04:48:04Z)
• Neural Networks Efficiently Learn Low-Dimensional Representations with SGD [22.703825902761405]
  We show that SGD-trained ReLU NNs can learn a single-index target of the form $y=f(langleboldsymbolu,boldsymbolxrangle) + epsilon$ by recovering the principal direction. We also provide compress guarantees for NNs using the approximate low-rank structure produced by SGD.
  arXiv  Detail & Related papers  (2022-09-29T15:29:10Z)
• Feature Learning in $L_{2}$-regularized DNNs: Attraction/Repulsion and Sparsity [9.077741848403791]
  We show that the loss in terms of the parameters can be reformulated into a loss in terms of the layerwise activations $Z_ell$ of the training set. This reformulation reveals the dynamics behind feature learning.
  arXiv  Detail & Related papers  (2022-05-31T14:10:15Z)
• Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances [9.390008801320024]
  We show that adding one extra neuron to each is sufficient to connect all previously discrete minima into a single manifold. We show that the number of symmetry-induced critical subspaces dominates the number of affine subspaces forming the global minima manifold.
  arXiv  Detail & Related papers  (2021-05-25T21:19:07Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation. We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
  arXiv  Detail & Related papers  (2020-08-06T09:50:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.