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

Thanks for the thorough review, and for explaining your concerns clearly.

Regarding Theorem 4: The fact that the final rate only depends on the worst ratio is in line with previous results, e.g. (Schmidt-Hieber, 2020). The intuition is that the errors of approximating each function sum up (roughly speaking) therefore only the function with the worst rate matters as $N$ grows. Now things might get a bit more complicated if one considers a number of compositions $L^*$ that grows to infinity. But in this paper we assume $L^*$ to be finite. Also it should not be possible to change $r_{max}$ by adding more layers, because it is determined by the number of times $\nu$ the function can be differentiated, and if $f=g\circ h$ then it is not possible for both $g$ and $h$ to be more times differentiable than $f$ (since the $k$-th derivative of $f$ can be computed from the $1$ to $k$-th derivatives of $g$ and $h$ using Faa di Bruno's formula).

Also thanks for pointing out line 1343 to us, there was indeed an error where we forgot to put the sum over $L$ terms as a constant in front. This constant depends on the $\rho_\ell$s, $r_\ell$s and on the depth $L$ (it scales as $L^{1+r^*}$ in the proof).

• Regarding Figure 1, the focus of our paper is the scaling of generalization bounds $N^{-\gamma}$ as $N$ grows. We felt it made sense to have one plot in terms of $N$ so that one could see that the test error does indeed behave roughly as $N^{-\gamma}$ for some $\gamma$. Figure 2 is the figure that focuses on how $\gamma$ itself is affected by the regularity of the functions $g,h$ that make up the true function $f^* = h \circ g$.

• Thank you for pointing out these typos, we have fixed them.

Regarding your second question: Even though it might be true that one can take small initialization for each individual weight (i.e. a variance of $1/w$ for $w$ the width in LeCun initialization), for large widths $w$ there are more and more parameters. This results in the expected squared parameter norm scaling as $w$, which implies an $F_1$ norm of order $w$, whereas at the end of training the optimal parameter norm should be independent of width.

Thank you for the thoughtful review and interesting questions.

Regarding the weaknesses:

• Our experiments were designed to illustrate the results, so we chose a family of tasks where the compositionality can be tuned to reveal the phase changes and other predictions of our theory. We agree that it would be interesting to test our theory on larger text or image datasets, though our intuition is that we would first have to extend our theory to CNNs/transformers to meaningfully train on such tasks.

• Actually the point of the composition of Sobolev functions structure is that much less regularity is required for efficient learning: the true function could be the composition of a first smooth function that maps to a one dimensional feature space followed by a function that is only Lipschitz; such a composition can have non-differentiable points (if the second function is non-differentiable) and still be learnable efficiently. Without compositionality, the only learnable functions are those that are roughly as many times differentiable as the input dimension.

• That's a very good point, we should make clearer recommendations. However our recommendation is to train DNNs as usual (using traditional weight decay/L2 regularization) and this what we do in our experiments. As we explain at the lines 458-466, we believe that the use of large learning rates implicitly controls the Lipschitzness, so only the F1 norms need to be minimized using weight decay. The problem is that at the moment, there is only partial theoretical support for this implicit control, so it is difficult push for this choice.

We plan to study this implicit control in more details and hopefully prove it in future work. The intuition is simple: if the functions that map from some hidden representations to the outputs are not Lipschitz, then the gradients will blow up, leading to unstability under large learning rates. This control can easily be proven in Linear networks, so we could add this in the appendix as further proof.

Nevertheless we have reworked the above mentioned paragraph to more explicitely advocate for the use of L2 regularization together with large learning rates.

Regarding your questions:

• When you say regularity assumption, do you mean Lipschitzness or the Sobolev norms? The Sobolev norms are not strictly necessary, they are just a common functional norm that can be used to bound the F1 norm, one could instead work with functions with bounded F1 norms directly (i.e. Theorem 2). For the Lipschitzness assumption, it seems pretty clear that one needs to control how errors in the middle of the network propagate to the outputs, but something weaker than Lipschitzness might be sufficient (e.g. a bound on the Jacobian on the training data only, as in (Wei & Ma, 2019) which can be computed), we hope to investigate these ideas in the future.

• See our response to the third weakness.

• We mention above the implicit bias of large learning rates, or weakening Lipschitzness to a maximum over the training data as in (Wei & Ma, 2019).

Thanks for the positive review.

We have added a note to give an example of a function with a large gap between its $F\_1$ norm and Lipschitz constant "A simple example of a function whose Lipschitz constant is much smaller than its $F_1$ norm (and thus its operator norms since $\\|W \\|\_{op} \geq \frac{\\|W \\|\_F}{\mathrm{Rank} W}$) is is the `zig-zag' function $f(x)=|x - a^{-1}\mathrm{round}(ax)|$ on the interval $[0,1]$: we have $Lip(f)=1$ but $\|f\|_{F_1} = \Omega(a)$ since one neuron is needed for each up or down, each contributing a constant to the parameter norm."

Thanks for pointing out these typos/unclarities, we fixed them.

We already try to give some motivation for why this type of structure might be common (e.g. the presence of symmetries). Another motivation is the section 4.2.2 "Computational Graphs" which suggests that compositional structure might arise on any task that could be described by a computational graph/algorithm, so if we assume that our brain does perform some kind of algorithm to understand text or images or logical problems, then these tasks must have some form of compositional structure. But this is a very fuzzy intuition at the moment, one of our future goal is to formalize this intuition.

Our postulate in this paper. is to view deep networks as a composition of shallow ones, and so if each shallow networks is biased towards minimizing its $F_1$ norm, then the network will be biased towards minimizing the sum of the $F_1$ norm. With weight decay, one is explicitely trying to minimize this sum of the $F_1$ norms, but we hope that in the absence of weight-decay the implicit bias observed in shallow networks would translate to an implicit bias towards small sum of $F_1$ norm. Now the training dynamics of deep networks are really out of reach of theoretical analysis today (outside of the NTK regime of course), so it is difficult to say anything with high confidence. Interestingly, our analysis suggests that it is important to control the Lipschitz constant of each shallow subnetwork too, which seems to not be necessary when working with shallow networks. We cite previous work that suggests that the Lipschitz constant might be controled implicitely by large learning rates, but this is just the beginning.

Yes, we actually already leverage (implicitely) this structure in our proof of theorem 5, where we use the fact that the $F_1$ norms in Theorem 2 can adapt to the inner dimension. This is what allow us to allow the inner dimensions $d\_\ell$ of the network to be larger or equal the true dimensions $d^*_\ell$ (and not exactly match it) without affecting the exponent (though by looking at the proofs one can see that the constant does depend on $d_\ell$ so it is best for $d_\ell$ to not be too large).

Thanks for your thorough review and the many relevant references.

We agree that the literature on generalization bounds is extensive and that we can do a better job of comparing to existing works. But these comparison are often difficult since one bound is rarely strictly better than another one, we feel like doing too many comparison could hurt the readability/accessibility of the paper. We propose to add detailed comparison to a few selected results whose comparison is easier (e.g. Bartlett et al. 2017), but more importantly we will write a high level comparison, which views our work as a combination of two lines of work:

On one hand, our work is inspired by approximation results such as (Schimidt-Hieber, 2020) which show that compositions of Sobolev/Hölder functions can be approximated by neural networks with few parameters, so few that the generalization error can be bounded and shown to match the known optimal rates for learning such compositions. But these results require training networks with few neurons, since they rely on a small number of parameters as capacity control, and we know that having many neurons helps the optimization of DNNs (e.g. mean-field/NTK limits). The work (Galanti et al. 2023, and Poggio et Fraser, 2024) can show similar optimal rates under the assumption that sufficiently many parameters are zero, which directly constraints the dimensionality of the space.

Another approach are norm-based generalization bounds (rather than based on dimensionality), which show how the capacity of DNNs can be controlled by different complexity measures $R(\theta)$ of the parameter that are (almost) independent of the width and depths of the network. Many such bounds have been proven in the recent years (such as the ones you refer too in your review), but it can be difficult to compare them. Also, we are not aware of any result showing that these norm-based bounds can achieve tight or close to tight rates on compositions of Sobolev functions. To achieve this we make a few changes to bound of (Bartlett et al. 2017): switching from operator norms to Lipschitz constant, from the (2,1) norm to the $F_{1}$-norm (and getting rid of the $2/3$ and $3/2$ exponents, but this has a smaller impact). The second change allows us to reuse approximation results from (Bach, 2017) to show that compositions of Sobolev functions can be approximated by AccNets with almost optimal rates. The first change (relying on Lipschitz constant) allows us to retain almost optimal rates even in hard settings when multiple functions in the compositions are Sobolev with low-differentiability. While it is difficult to prove that these changes are necessary to obtain almost optimal rates, these two changes allow for a relatively natural construction when approximating the composition of Sobolev functions.

In general, we believe that this family of functions could be a good baseline to compare generalization bounds, their compositional structure seems well-adapted to DNNs, and they contain enough variety to have a complex structure to allow for a fair comparison: the complexity of the model can either be increased by composing more functions, or by increasing the complexity of each function.

We have reworked the introduction to better explain this, and better differentiate our work from previous ones (and have also added citations to the papers your reference).

We also added a short paragraph after the statement of Theorem 2 comparing our bound to the bound of (Bartlett et al. 2017) which is most similar to our bound:

"This allows us compare our complexity measure to the one in (Bartlett et al. 2017), whose complexity measure $\\prod\_{\\ell}\\|W\_{\\ell}\\|\_{op}\\left(\\sum\_{\\ell}\\frac{\\|W\_{\\ell}\\|\_{2,1}\^{2\/3}}{\\|W_{\\ell}\\|\_{op}\^{2\/3}}\\right)^{3\/2}$ is closest to ours. We obtain three improvements: replacing the operator norm by the Lipschitz constant of $f_{\ell}$, replacing the $(2,1)$-norm ($\|A\|\_{2,1}=\|(\|A\_{:,1}\|\_{2},\dots,\|A\_{:,d}\|\_{2})\|\_{1}$) by the nuclear norm, and removing the $2/3$ and $3/2$ exponents. These three changes play a significant role in Theorem 4, as we discuss later. Note however that since our bound relies on the rank of the weight matrices being bounded, we cannot say that it is a strict improvement over (Bartlett et al. 2017)."

Finally the main change we did is rework the discussion following Theorem 4, where we focus on 4 points: the power of already existing approximation results for the $F_{1}$-norm; sparsity-based bounds vs our norm based bounds (comparison to (Schimidt-Hieber, 2020) and others); how the Lipschitz constant vs operator norms affect the final rates; the large depth behavior of our bound in comparison to (Bartlett et al. 2017) and (Golowich et al. 2020) which can in some case lead to an exponential dependence on depth. You can check the updated version for details of this discussion.

We have made a final change, adding a figure which compares our bound to previous bound. We see a significant improvement, though it still remains far from being tight. The new figure is in the appendix, Figure 4.