How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning
Authors: Arthur Jacot
Seok Hoan Choi
Yuxiao Wen
Venue: ICLR 2025 Poster (2025)
Keywords: Generalization bound
covering numbers
compositionality
Primary area: learning theory
TL;DR: A new generalization bound for DNNs that illustrates how DNNs can leverage compositionality to break the curse of dimensionality.

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 quotient 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.

Published as a conference paper at ICLR 2025
How DNNS BREAK THE CURSE OF DIMENSIONALITY: COMPOSITIONALITY AND SYMMETRY LEARNING
Arthur Jacot, Seok Hoan Choi & Yuxiao Wen
Courant Institute New York University New York, NY 10012
(arthur. jacot, jacor, shc443, yuxiaowen eny.:eewennnnueeeeee edu
ABSTRACT
We show that deep neural networks (DNNs) can efficiently learn any composition functions with bounded F1 Fi-norm, which allows DNNs 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 Fi-norm (or the related Barron norm) for large width adaptivity. We show that the global minimizer of the regularized loss DNNs can fit for example the composition of two functions f h o g from small number of observations, assuming is smooth/regular and reduces the dimensionality (e.g. 9 could be the quotient map of the symmetries of f*), so that à can be learned in spite of its low regularity. The measures of regularity we consider is the Sobolev norm with different levels of differentiabilityy which is well adapted to the Fi 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.
INTRODUCTION
One of the fundamental features of DNNs is their ability to generalize even when the number of neurons (and of parameters) is so large that the network could fit almost any function (Zhang et al.) 2017). Actually DNNs have been observed to generalize best when the number of neurons is infinite (Belkin et al. 2019: Geiger et al.) 2019 2020). The now quite generally accepted explanation to this phenomenon is that DNNs have implicit bias coming from the training dynamic where properties of the training algorithm lead to networks that generalize well. This implicit bias is quite well understood in shallow networks (Chizat & Bach 2018 Rotskoff & Vanden-Eijnden 2018). in linear networks (Gunasekar et al.) 2018 Li et al. 2000), or in the NTK regime (Jacot et al. 2018). but remains ill-understood in the general deep nonlinear case.
In both shallow networks and linear networks, one observes a bias towards small parameter norm (either implicit (Chizat & Bach 2020) or explicit in the presence of weight decay (Wang & Jacot 2024)). Thanks to tools such as the Fi-norm (Bach 2017). or the related Barron norm (Weinan et al. 2019), or more generally the representation cost (Dai of functions that can be represented by shallow networks or linear networks with finite parameter norm. This was then leveraged to prove uniform generalization bounds (based on Rademacher complexity) over these sets (Bach, 2017). which depend only on the parameter norm, not on the number of neurons or parameters.
2021). is possible describe the family
Similar bounds have been proposed for DNNs (Bartlett et al. Klusowskij 2019 Schhidtt-Hehher/ 2020 Nitanda Suzuki 2020 Hsu al. 2021 Sellke 2024).
2017
Golowich et al. 2020 Barron &
relying different types of norms on the parameters of the network. Analogues of these bounds have been extended to other architectures, such as CNNs (Ledent et al. [221]] Graf et al., 2022
Truong 2022 Galanti al. 2023). But there remains many issues: these bounds are typically orders of magnitude too large (Jiang et al. 2019 Gonon et al. 2023), and they tend to explode as the depth L grows (Sellke) 2024).
is difficult to compare these bounds, since they involve many terms that have complex behavior the depth increases. To justify our new complexity measure R(O) and bound, pair it with an

---

Published as a conference paper at ICLR 2025
approximation result on composition of Sobolev functions (functions with certain decay of their Fourier or spherical harmonics coefficients), which implies that DNNs can learn such composite functions with almost optimal rates, allowing to break the curse of dimensionality in certain cases.
Previous works has shown that DNNs with either bounded width/depth (Schmidt-Hieber 2020
or with bounded number of non-zero parameters (Galanti al. 2023 Poggio & Fraser 2024)
can effectively learn such compositional functions. This paper shows that these strong sparsity assumptions are not strictly necessary for DNNs learn such compositional functions.
The family of composite Sobolev functions is also useful theoretical baseline to compare different norm-based bounds, by checking which complexity measure lead to tighter rates. This allows to show the importance of replacing operator norms by Lipschitz constants and other design choices.
1.1 CONTRIBUTION
We consider Accordion Networks (AccNets), which are the composition FL.1 fL o.... fi of multiple shallow networks fe(x)) Wea VEE + be), we prove uniform generalization bound for R(0) S V VN"
the MSE (((fa)) (EN(fen)
for complexity measure
R(0) [I Lip(fe) ) (Σ
Ifell dd de-1 Lip(fe)
that depends on the Fi firros llfell (which is upper bounded by the parameter norm of the corresponding shallow network [|We IVeel + [bell3) and Lipschitz constanst Lip(fe) of the subnetworks, and the intermediate dimensions .o..... dz. This use of the Fi-norms makes this bound independent of the widths W...... wy, of the subnetworks, though it does depend on the depth T. (it typically grows linearly I, which still better than the exponential growth often observed).
Any traditional DNN can be mapped to an AccNet (and vice versa), by spliting the middle weight matrices We with SVD USV into two matrices U UVS and VSVTT to obtain an AccNet with dimensions de = Rank Wr, so that the bound can be applied to traditional DNNs with bounded rank.
We then show an approximation result: any composition of Sobolev functions f fī. .... can approximated with a network with either a bounded complexity R(0) or slowly growing one. Thus under certain assumptions Sobolev functions (i.e. functions whose first v E N derivatives are bounded in Le norm). This ability be interpreted DNNs being able learn symmetries, allowing them to avoid the curse of dimensionality in settings where kernel methods or even shallow networks suffer heavily from it.
can show that DNNs can learn general compositions of
Empirically, observe good match between the scaling laws of learning and our theory, well as qualitative features such as transitions between regimes depending on whether it is harder to learn the symmetries of task, or learn the task given its symmetries.
2 ACCORDION NEURAL NETWORKS AND RESNETS
Our analysis is most natural for slight variation on the traditional fully-connected neural networks (FCNNs), which we call Accordion Networks, which we define here. Nevertheless, all of our results can easily be adapted to FCNNs.
Accordion Networks (AccNets) are simply the composition of L shallow networks, that fra JT. Si where fz(=) Weo(Viz + be) for the nonlinearity We, We x de-1 matrix Ve, and di-d vector be, and for the widths wi,... Wt and dimensions do.... .... dz. We will focus the ReLU or (zz) max(0, x for the nonlinearity. The parameters 0 are made up of the concatenation of all (We, Ve. by). More generally, we denote fras, = ft, ... fe. for any < & < la < L.
R IR the de x we matrix
We will typically be interested in settings where the widths wy is large (or even infinitely large), while the dimensions d, remain finite or much smaller in comparison, hence the name accordion.
If we add residual connections, i.c. free = (fr. + id) o ... o (fi + id) for the same shallow nets f fr. we recover the typical ResNets.
2

---

Published as a conference paper at ICLR 2025
Remark. The only difference between AccNets and FCNNs is that each weight matrix Mr of the FCNN is replaced by a product two matrices Mr
V.W+-1 in the middle of the network (such a
structure has already been proposed (Ongie & Willett 2022 Parkinson et al. 2023)). Given AccNet one can recover an equivalent FCNN by choosing M, We Mo Vo and ML+1 WT. In
the other direction there could be multiple ways to split Me into the product of two matrices, but
will focus on taking V2 U U and Wt-1 VSV for the SVD decomposition Mr- USV"
along with the choice dz = Ra One can thus think of AccNets as rank-constrained FCNNs.
2.1 LEARNING SETUP
We consider a traditional MSE regression setup, where we want to find function / C BR Rdout that minimizes the population loss [(f) Rew Il (x) (z))l for the 'true function' f³, and input distribution т. Given training set .1....,,2. NN of size N we approximate the population loss by the empirical loss (f) = & M [lf(z.) - (x that can be minimized.
To ensure that the empirical loss remains representative of the population loss, we will prove high
probability bounds on the generalization gap v CCf) v (f) = RNVE) uniformly over function families with complexity bounded by R. Thus as long as the train error is small enough ORRN $). This type of bound on the gap between squared roots of the losses is more natural for the MSE loss and allows for so-called fast rates under the assumption that the train error is itself small. Note that our generalization bounds rely on covering number arguments, so they could easily be applied to Lipschitz losses using Dudley's s theorem.
(f( = O =). will the test error L(f)
For simplicity of analysis, we will assume that the true function f and estimator f are uniformly bounded ||o |l S B. This can be guaranteed easily by adding a renormalizing nonlinearity Since this is contraction it does not affect the Bi
at the end of the network (x) = [IIII1 covering number argument that we rely on.
GENERALIZATION BOUND FOR DNNS
The reason we focus on accordion networks is that there exists generalization bounds for shallow networks (Bach) 2017 Weinan al. 2019). that are (to our knowledge) widely considered to be tight, which is in contrast to the deep case, where many bounds exist but no clear optimal bound has been identified. Our strategy is extend the results for shallow nets the composition of multiple shallow nets, i.e. AccNets. Roughly speaking, we will show that the complexity of an AccNet fo is bounded by the sum of the complexities of the shallow nets fi....,J St. it is made of.
We will therefore first review (and slightly adapt) the existing generalization bounds for shallow networks in terms of their so-called Fn-norm (Bach 2017). and then prove a generalization bound for deep AccNets.
3.1 SHALLOW NETWORKS
The complexity of shallow net f(x) = Wo(Vx + b), with weights V Ruxdin and
W E Re X10 can be bounded in terms of the quantity C En [aal / /Iv + D.. First note that the rescaled function f can be written as a convex combination f =
W V. Σ. [W.l / [I. W.to b,) for W., [W.
V.
and b, VIV, 2
since the coefficients IW..Il//l...I + are positive and sum up to 1. Thus belongs to C' times the convex hull
BF, Conv { I wa + 6): ||l]| ||/|| + 6² PP=1 =1].
This set can be thought as the unit ball w.r.t. to the norm Bach 2017). The Fi-norn I| itself then be defined as the smallest positive scalar such that f E Bp,- Note that by the AM-GM
3

---

Published as a conference paper at ICLR 2025
inequality, we have
30
1 1 Wlalll V [IV 2 + 1/2 S
11l SC= Σ
Σ [w.] 2 |V + D2
The generalization gap over any Fi-ball can be uniformly bounded with high probability: Theorem For any input distribution πT supported on the L2 ball ((O, b) with radius b, we have with probability 1 - p, over the training samples , N,, that for all f E {f [l S R, 1f S B}
-EU)-VEN(O) S cov BRN Bo.BV
1/2
N
Therefore if (N(() O(BRN-3) then L(f) O(BRN
This theorem is a slight variation of the one found in (Bach) 20177: we simply generalize it to multiple outputs, and apply to the -on-LLipshhitz) MSE loss instead of general Lipschitz loss. The proof technique however relies on covering numbers rather than Rademacher complexity, which will be key to obtaining generalization bound for the deep case.
Notice how this bound does not depend on the width w, because the Fi-norm (and the Fi-ball) themselves do not depend on the width. This matches with empirical evidence that shows that increasing the width does not hurt generalization (Belkin et al. 2019, Geiger et al.) 2019 2020).
To use Theorem I efffetively
need be able to guarantee that the learned function will have small enough F Form. The Fi-morm is hard to compute exactly, but is bounded by the parameter
norm: if (x) Wo(Vx + b), then I|, S (IWI2 + I + [[b]))) and this bound tight if the width is large enough and the parameters are chosen optimally. Adding weight decay/I.2- regularization to the cost then leads to bias towards learning with small Fi norm.
3.2 DEEP NETWORKS
Since an AccNet is simply the composition of multiple shallow nets, the functions represented by an AccNet is included in the set of composition of Fi balls. More precisely, if [|& 12 +|V||| |/V//|=+|/00 +|bbe|1 <
2R, then LLa belongs to the set [9z c o 91 gt E Br, (0, Re)} for some Re.-
As noticed in (Bartlett et al. 2017). the covering number is well- behaved under composition, therefore the complexity of AccNets can be bounded in terms of the individual shallow nets it is made of:
Theorem 2. Consider accordion net of depth L and widths di....,de dg. with corresponding set of functions F = {fi. [l I Re, Lip(ft) S Pt, llf I B} with input space S = B(,, r). Then with probability - p over the sampling of the training set X from the distribution we have
for all f E F
L
Re
loge/2
VC() (x(()) & c Bptar 1
Σ
dd + de
VN (1 + +1)) + aa Bv
pe
N
2==1
for co R0 14.6 and e₁ se 7.4. Thus if [x(J) O(BPLar Et C()) O(BrL. Ek Bg Pe
Rg
Pe dd + de - then
dde de de-
Theorem 2 can be extended to ResNets (fr + id) (f1 + id) by simply replacing the Lipschitz constant Lep(fe) by Lip(ft + id).
The Lipschitz constants Lip(fe) are difficult compute exactly, so is casiest to simply bound it by the product of the operator norms Lip(ft) < [[Wellop [|Ve but we see in Theorem how this bound can be very loosd operator norms W VVVellop is thus a significant advantage.
[ The fact that our bound depends the Lipschitz constants rather than the
A simple example of function whose Lipschitz constant is much smaller than its F, norm (and thus Wir its operator norms since || 2 Rankw) is is the 'zig-zag' function f(x) = Ix a "round((z)) on the interval [0, 1}: we have Táp(f)= but [r, (a))) since one neuron is needed for each up or down, each contributing a constant the parameter norm.
4

---

Published as a conference paper at ICLR 2025
Vy -
U) 1 My
MNIST and WESAD
10
Model FCNN
SIAST
Geraralbation Sound
Cerrenaliaation Iisaard
WESAD
Accivets
10a
10h
301
10h
2x
301
10"
1e5 enerr
10"4
10
Model
6x
PCHN
10
Accliets
3
Shalloos
30
3-
Kemel
20
Figure 1: Visualization of scaling laws. We observe that deep networks (either AccNets or DNNs) achieve better scaling laws than kernel methods or shallow networks on certain compositional tasks, in agreement with our theory. We also see that our new generalization bounds approximately recover the right scaling laws (even though they are orders of magnitude too large overall). We consider compositional true function f h g where maps from dimension 15 to 3 while h maps from to 20, and we denote U,, Ph. for the number of times g, h are differentiable. In the first plot "n 8, Ph 2 so that g is easy to learn while h is hard, whereas in the second plot Vg = 9, pn 10, so both g and are relatively easier. The third plot presents the test error and generalization bounds for MNIST and WESAD (Schmidt et al. 2018
This bound can be applied a FCNNs with weight matrices MI...., M, 1, by replacing the middle Mr with SVD decomposition U S in the middle by two matrices W = vSV and V = U UVS, with dimensions de = Rank 1 The Frobenius norm of the new matrices equals the nuclear norm of the original one ||W,-1|l 1| |
||Vil || Recent results have shown that weight-decay
leads to a low-rank bias on the weight matrices of the network (Jacoi 2023a b Galanti et al. 2022).
This allows us compare our complexity measure to the in (Bartlett et al. 201 whose
3/2
complexity measure II. [[ellopp
Σe
is closest to ours. We obtain three improve-
ments: replacing the operator norm by the Lipschitz constant of fe, replacing the (2, 1) -orm (||A||2,1 = [1]] ... .| a1l2))))) by the nuclear norm, and removing the 2/3 and 3/2 expo- nents. These three changes play significant role in Theorem 4 as we discuss later. Note however that since bound relies the rank of the weight matrices being bounded, we cannot say that it is a strict improvement over (Bartlett et al. 2017).
We compute in Figure the upper bound of Theorem 2 for both AccNets and DNNs, and even though we observe a very large gap (roughly of order 10"), we do observe that it captures rate/scaling of the test error (the log-log slope) well. So this generalization bound could be well adapted to predicting rates, which is what we will do in the next section.
Remark. Note that if one wants to compute this upper bound in practical setting, it is important to train with La regularization until the parameter norm also converges (this often happens after the train and test loss have converged). The intuition is that at initialization, the weights are initialized randomly, and they contribute lot the parameter norm, and thus lead to larger generalization bound. During training with weight decay, these random initial weights slowly vanish, thus leading smaller parameter norm and better generalization bound. It might be possible to improve our generalization bounds to take into account the randomness at initialization to obtain better bounds throughout training, but we leave this future work.
5

---

Published as a conference paper at ICLR 2025
4 BREAKING THE CURSE OF DIMENSIONALITY WITH COMPOSITIONALITY
In this section we study a large family of functions spaces, obtained by taking compositions of Sobolev balls. We focus this family of tasks because they well adapted the complexity measure we have identified, and because kernel methods and even shallow networks do suffer from the curse of dimensionality on such tasks, whereas deep networks avoid (e.g. Figure
More precisely, we will show that these sets of functions can be approximated by a AccNets with bounded (or in some cases slowly growing) complexity measure
lffell,
R(O)- II Lip(Se) Σ
dd de-1- Lip(fe)
This will then allow us show that AccNets can (assuming global convergence) avoid the curse of dimensionality, even in settings that should suffer from the curse of dimensionality, when the input dimension is large and the function is not very smooth (only few times differentiable).
Since the regularization term R(0) is difficult to optimize directly because of the Lipschitz constants, we also consider the upper bound R(0) obtained by replacing each Lip(fe) with [Velopp|\Welle
4.1 COMPOSITION OF SOBOLEV BALLS
The family of Sobolev norms capture the regularity of function, by measuring the size of its derivatives. Consider a function f Rio -> with derivatives 0 for some dia-multi-inee a, the WoP( (r)--oboley norm with integer and p 2 1 is defined as
I = Σ 100 [12,
lalSo
Note that the derivative 0 I only needs to be defined in the "weak" sense, which means that even non-differentiable functions such as the ReLU functions can actually have finite Sobolev norm.
The Sobolev balls (=) (0, R) {f [Illl R) are a family of function spaces with range of regularity (the larger v, the more regular). This regularity makes these spaces of functions learnable purely from the fact that they enforce the function f to vary slowly as the input changes. Indeed we can prove the following generalization bound:
Proposition 3. Given distribution π with support in B(0, b), we have that with probability 1 for all functions f F (ff llll S R. fl. S B}
(2x(f) = c0 vE() (CUn-VEx1T
B B²RR" N
log 9/2
taBB
N
where din, Therefore if Σx(f) )((BB))t)) then C(f) O(( B²R" )oîr).
But this result also illustrates the curse of dimensionality: the diffcrentiability needs to scale with the input dimension d, obtain a reasonable rate. If instead
constant and d grows, then the number of datapoints N needed to guarantee a test error of at most c² scales exponentially in din- i.c.
(2+ =e=) One way to interpret this issue is that regularity becomes less and less useful the larger the dimension: knowing that similar inputs have similar outputs is useless in high dimension where the closest training point æ; to test point x typically very far away.
N - (2+r)
4.1.1 BREAKING THE CURSE OF DIMENSIONALITY WITH COMPOSITIONALITY
To break the curse of dimensionality, we need assume some additional structure on the data or task which introduces an 'intrinsic dimension that can be much lower than the input dimension d
Manifold hypothesis: If the input distribution lies on a deur Searr-ti ddimensional manifold, the error rates typically depends on d instead of din
2019 Chen et al. 2022).
Known Symmetries: If (g x) = fx) for group action w.r.t. a group G, then f can be written the composition of quotient map g" Rdin - 34in /a which maps pairs of inputs which

---

empirical Published as a conference paper at ICLR 2025
ACCMES
RCW trra Pate
Thoretka Onte Rote
Kran Mettll Fros
Salii Ape
ArdMes
25
-45
Figure A comparison of empirical and theoretical error rates. The frist two columns show the log decay rate of the test error with respect to the dataset size N based simulations for 4 different models. The top right plot depicts the theoretical decay rate of the test 2v, error wwor-minff 2' 2uy+ 4dmed The bottom right plot displays the difference between the rates of AccNets and shallow nets. The lower left region represents the area where g easier to learn than h, the upper right where h easier to learn than g. and the lower right region where both f and g are easy. We see that the biggest gain of AccNets shallow are in the. lower left regions, where learning h is hard.
2vn
equivalent up to symmetries the same value (pairs x. y s.t. 9-20 for some g G), and then a second function h* R + Rdaau, then the complexity of the task will depend on the dimension of the quotient space /////G which can be much lower. the symmetry is known, then one can for example fix g and only learn h² (though other techniques exist, such as designing kernels features that respect the same symmetries) (Mallat 2012).
Symmetry Learning: However if the symmetry is not known then both g" and h have to be learned, and this is where we require feature learning and/or compositionality. Shallow networks are able learn translation symmetries, since they can learn so-called low-index functions which satisfy (x(xx f (Px) for some projection (with statistical complexity that depends on the dimension of the space one projects into, the full dimension (Bach) 2017 Abbe et al.) (02T)) ). Low-index functions correspond exactly to the set of functions that are invariant under translation along the kernel ker P. To learn general symmetries, one needs to learn both h² and the quotient map g" simultaneously. hence the importance of feature learning.
For g" be learnable efficiently, needs be regular enough not suffer from the curse of dimensionality, but many traditional symmetries actually have smooth quotient maps, for example the quotient map g" (I) ||=||² for rotation invariance. This can be understood as special case of composition Sobolev functions, whose generalization gap can be bounded:
Theorem 4. Let F
Fr. [/ S R, 11llll S B, Lip(fe) S pe), and let Tmax max, Tt. for
Fi where Ft
{Se Rd + Rdd s.I.
de-1 then with probability p have for all f EF
ue
VD(f) -N(F)
B2Remma
24rmax
log
+ c BV
N
where Co depends only on rt, Pc. Thus if Ex(J) S O(N T-rmas then L(J) O(N T
7

---

Published as a conference paper at ICLR 2025
We see that only the largest ratio Tmax matters when it comes to the rate of learning. Coming back to the symmetry learning example, we see that the hardness of learning a function of the type f = h with inner dimension dmud and regularities V9 and P4 leading to ratios rg test error will of order (assuming the train error is small enough)
du and th Amid the "
L= 0 NN min min Larg 2tth
= (N=
20g min[ 2ng Tdon 2on tilmidd
This suggests the existence two regimes depending on whether or is harder to learn, which is determined by which ratio rg 1h is larger.
In contrast, without taking advantage of the compositional structure, we expect f to be only min 1h) times differentiable, so trying to learn it as a single Sobolev function would lead to an er- 2 ror rate of N 2min 24, = N min { sug tden 2un maan which is no better than the compositional rate assuming dimiid S din. and can in some cases be arbitrarily worse.
2n1
Furthermore, since multiple compositions are possible, one can imagine a hierarchy of symmetries that slowly reduce the dimensionality with less and less regular quotient maps. For example one could imagine a composition fL o ..... fi with dimensions de = do2 and regularities = do2 so that the ratios remain constant rg du2 d-2- = 3. leading to an almost parametric rate of N 3 log N,
improving significantly over to the non-compositional rate of N-2""
Remark. A naive argument suggests that the rate of N should be optimal: assume that the maximum Ty is attained at a layer É, then one can consider the subset of functions such that the image fe-1a1 r)) contains a ball (22,r') r') C Bdd-1 and that the function f1.0+1 is 8-non-contracting [lfL:e+1 (z) - fL:++1 (3)ll 2 B || 3/1. then learning fL.1 should be as hard as learning fe over the ball B(z, r'), thus forcing rate of least N 2Tvmax An analysis of minimax rates in similar
setting has been done in (Giordano et al. 2022).
4.2 BREAKING THE CURSE OF DIMENSIONALITY WITH ACCNETS
Now that we know that composition of Sobolev functions can be easily learnable, even in settings where the curse of dimensionality should make it hard to learn them, we need to find model that can achieve those rates. Though many models are possible Fl we focus on DNNs, in particular AceNets. Assuming convergence to a global minimum of the loss of sufficiently wide AccNets with two types of regularization, one can guarantee close to optimal rates:
Theorem 5. Given true function fī.: = Ji- o...o Ji going through the dimensions dā. di.. along with a continuous input distribution To supported in B(0, bn), such that the distributions me of ft (x) (for x ~ To) are continuous too and supported inside B(0, be) C RRd.. Further assume that there are differentiabiltties ve and radii Re such that II. (Bll= S RR, and pt such that Tip(Ji) S Pt- For an infinite width AccNet with L, 2 I." and dimensions de 2 di.....dh
.......... we
have for the ratios it = maxx di 1t 23:
(I) At a global min fix of (N(ft)) + AR(O), we have L(fra) = O(N 24 for Fmax ma..........
(2) At a global min fLa of (x(fta) + Ai(()), we have C(fra) = O(N I+Teum ) for Feum
2 E 2).
In the proof, we build a network fr. that approximates fi in the following manner: we adapt approximation results from (Bach) 2017) to approximate each Sobolev function S by shallow network fo and if L > L* we add L L- L identity layers where the dimensionality di is minimal (the parameter norm required to represent the identity
d-dimensional representation is proportional to d, so it is optimal to add identity layers at the smallest dimension).
'nne could argue that it would be more natural to consider compositions of kernel method models, for example a composition of random feature models. But this would lead to very similar model: this would be equivalent to AccNet where only the We weights are leamed, while the V2, be weights remain constant. Another family of models that should have similar properties is Deep Gaussian Processes (Damianou & Lawrence 2013
8

---

Published as a conference paper at ICLR 2025
F1 F1-norm/Barron norm: This shows the power of replacing other parameter norm measures (such as the (2, 1)-norm from Bartlett et al. (2017)) with the Fi-norm, by allowing us to repurpose the already existing approximation results for shallow networks. While we do not prove that similar approximations cannot be achieved with small (2, 1 )-norm too, it seems unlikely, since generic Sobolev functions require a high variety of active neurons (a natural way to approximate them is to use a random feature approach (Rahimi & Recht 2008)) which seems in contradiction with the (2, 1)-morm which imposes sparsity on the neurons.
Norm based vs Sparsity based: In (Schmidt-Hieber 2020 Poggio & Fraser 2024 a similar class of functions is considered and optimal rates N 21-mm with Tmar = max
di--1 instead of PC-
Fmaz= max{ di+3 - 2) are proven. The presence off the +3 comes from the shallow P2.
21 network approximation results and could potentially be removed. The bigger gap happens for easy tasks, where the 'fast' rates can be achieved N-1 when mmaz R O, whereas our result can never predict rates faster than N because maz 2 2. This might be a fundamental gap, because norm- based complexity measures are known to be unable to yield fast rates (Srebro et al.) 2010), control on the dimensionality of the model might be required to obtain these fast rates. Real world tasks are probably rarely easy enough to achieve rates faster than N e.g. LLMs scaling laws have been observed to be roughly - in (Kaplan et al. 2020).
e.g.
By evaluating the complexities R. R on this approximation, we obtain two bounds illustrating the tradeoff between these two complexities. The first complexity measure based Lipschitz constant Lip(ff) leads to almost optimal rates, whereas the second
Lipschitz constant operator norm:
complexity measure can lead to arbitrarily suboptimal rates when two or more ratios 42-1+3 larger than 2. This is due to the fact to approximate general Sobolev functions with large ratio di d7-1+3 with a shallow network, the parameter norm || |1? + Veell needs to grow to infinity as 0, leading to exploding operator norms, even though the Lipschitz constant remains bounded.
'y are
Obviously, the Lipschitz constants Lip(fe) are difficult to optimize over. For finite width networks it is in theory possible to take the max over all linear regions, but the complexity might be unrcasonable. It might be more reasonable to leverage implicit bias instead, such large learning rate, because a large Lipschitz constant implies that the network is sensible to small changes in its parameters, so GD with large learning rate should only converge to minima with a small Lipschitz constant (such a bias is described in (Jacol 2023b)). For this reason, we apply standard weight-decay to minimize the Fi Finnorss, and rely on the implicit bias to control the Lipschitz constants. Going further, techniques from /Wei & Ma 2019) could be used to replace the Lipschitz constant in the bound with the maximum Jacobian over the dataset, which could then be optimized directly.
Impact of Depth: As can be seen in the proof of Theorem 5 when the depth L is strictly larger than the true depth I,", one needs to add identity layers, leading to a so-called Bottleneck structure, which was proven emerge as result of weight decay in (Tacot. 2023a by Wen & Jacot 2024). These identity layers add term that scales linearly in the additional depth (T.-1" Jd to the first regularization.
v/
(and multiplicative factor of order L to the second), see the proof for more details. The removal of the 2/3 and 3/2 exponents in our bounds in comparison previous bounds Bartlett et al. (2017) allow us to get such a OLL) bound instead of O(L ). Interestingly. the first bound proposed in Golowich et al. (020) to obtain a better depth dependence depends on the product of the Frobenius norms, which would grow exponentially as ming(dj- .diieddd....dd di, d (2-2") if the minimum dimension is 2 or more. Finally, note that by switching to a ResNet, there is no need for those identity layers, and the generalization becomes constant in depth.
There are a number of limitations this result. First we assume that one able to recover the global minimizer of the regularized loss, which should be hard in genera E (we already know from (Bach) (017)) that this NP-hard for shallow networks and simple Fi Fi-reaularization) Note that it is sufficient to recover a network fta1 whose regularized loss is within a constant of the
Limitations:
We achieve this by applying chaining accross the layers instead of applying to each layer separately. 'Note that the unregularized loss can be optimized polynomially, e.g. in the NTK regime (Jacot et al. 2018 Allen-Zhu et al. 2019 Du et al. (201)) but this is an easier task than finding the global minimum of the regularized loss where one needs both fit the data, and do it with an minimal regularization term.

---

Published as a conference paper at ICLR 2025
global minimum, which might be easier to guarantee, but should still be hard in general. The typical method of training with GD on the regularized loss is a greedy approach, which might fail in general but could recover almost optimal parameters under the right conditions (some results suggest that training relies on first order correlations to guide the network in the right direction (Abbe et al. 2021 Petrini et al. 2023)).
2022
Another limitation is that our proof requires an infinite width, because we were not able to prove that function with bounded Fi-morm and Lipschitz constant can be approximated by sufficiently wide shallow networks with the same (or close) Fi-norm and Lipschitz constant (we know from (Bach) (017)) that is possible without preserving the Lipschitzness). We are quite hopeful that this condition might be removed in future work.
4.2.1 EXPERIMENTS
We train our models on a synthetic dataset obtained by composing two Gaussian processes Y (x)))) with Matérn kernels Kg. K₁, chosen so that and h have the right differentiability. In Figure 2 we compare the empirical rates (by doing a linear fit on log-log plot of test error as a function of
2n, 2v tdm.c which seem to yield the best match. Note that this best fit N) and rates min 2 tdg+
20g
for the rates is mix of the theoretical lower bound min +d.+ 2ontd } and the upper bound 2v, min 2' +xn+ 2P +dmi++++33 suggesting that the appearance of the +3 in the denominator might be an artifact of the proofs, whereas the 1 might actually be optimal. But the amount of noise in our approximation of the rates does not allow us to give a definite answer for what the rates should be.
20g
2n
21/
Notice also that all experiments were done with simple In-regularization, which suggests the Lipshitz constants Lip(fe) do not need to be optimized directly. The use of large learning rates and the edge of stability phenomenon (Cohen al., 2021) could explain this implicit control of the Lipschitzness, because a large Lipschitz constant can lead to exploding gradients, and training with large learning rates could implicit avoid such parameters. Stability under large learning rate has been shown to control the regularity of the representations in previous works (Jacot 2023a b).
4.2.2 COMPUTATIONAL GRAPHS
Theorem 5 can be adapted to show that AccNets can also learn any 'computational graph' as in (Schmidt- Hieber 2020; Poggio & Fraser 2024). where a variables v1.... UK each with their own dimension dg. Each variable has a set of parents P(k) C {1..... K} on whom it depends 2 = f f( : m E P()))) for 74- Sobolev or F, function 9k- We assume that the variables can be ordered in such a way that all parents of variable belong have smaller indices, or equivalently that the directed graph with K vertices, with edges connecting parents to their child acyclic. The input variable is 1 and output one is K.
is then possible to organize the variables into 'layers' of variables that only have parents in the previous layers (possibly adding identities to keep certain variables from previous layers until they are needed). We say that the depth L' of the computational graph is the minimal number of layers required to find such a representation, and it matches the length of the longest directed path in the graph. Thus the complete function can be written as the composition of L functions fī.1. where each Jī is the product of few gkS,, e-g. f (v1, U2 has the property that Fj-norm of the product of multiple functions is upper bounded by the sum of the Fi norms, e.g. [[fi || F, [1 lI; + llgell + [[9|||5, as well as the Lipshchitz constant Lip(f?) = Lip(gr) + Lip(gz) + Lip(ga). One can then easily see that, assuming bounded Lipschitz constants, we can guarantee rate of learning of N ? for Pmaz max
U2) v3) = (g) (v1, v2),, 92 (va), ga (u1, v2)). The Fi-morm
3+) mpp du M4
5 CONCLUSION
We have given generalization bound for Accordion Networks and as extension Fully-Connected networks. It depends on the Fi-norms and Lipschitz constants of its shallow subnetworks. This allows us to prove under certain assumptions that AccNets can learn general compositions of Soboley functions efficiently, making them able to break the curse of dimensionality in certain settings, such as in the presence of unknown symmetries.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Emmanuel Abbe, Enric Boix-Adsert Matthew Stewart Brennan, Guy Bresler, and Dheeraj Mysore Nagaraj. The staircase property: How hierarchical structure can guide deep learning. In A. Beygelz- imer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
nww. http:p/eeeeeeeeeteooooooooooo/aa
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-stairease property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pp. 4782 4782-4887. PMLR, 2022.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Kendall Atkinson and Weimin Han. Spherical harmonics and approximations on the unit sphere: an introduction, volume 2044. Springer Science & Business Media, 2012.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-66)) 2017.
Andrew R Barron and Jason M Klusowski. Complexity, statistical risk, and metric entropy of deep nets using total path variation. stat, 1050:6, 2019.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Opectrally-normaliize margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical ilas-variane trade-off. Proceedings of the National Academy of Sciences, 116632):5549--15844 2019.
M. S. Birman and M. Z. Solomjak. Piecewise-polynomia approximations of functions of the classes Wo. Mathematics of The USSR-Sbornik, 2:295-317, 1967. URL https://api
semant cscho ar org/ Cotp///orpppaaaaap t 12:
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Nonparametric regression on low- dimensional manifolds using deep relu networks: Function approximation and statistical recovery. Information and Inference: A Journal of the IMA, 11(4):1203-1253) 2022.
Lénaïc Chizat and Francis Bach.
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport.
In Ad-
vances in Neural Information ran Associates, Inc.. 2018
Processing Systems 31, pp. 3040-3050. Cur-
URL http: www. wwws.cc/papprr
7567-on-the-globnn global pdf
of wwwp:e/ennee-..o-oaaee-ee------e org.:aeeeeeoo....eeerrrraaaeeeee
I Lénaïi Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 Proceedings of Machine Learning Research, pp. 1305-1338, PMLR, 09-12 Jul 2020. URL chizat20s.html
mlr. pre.prees//125/
Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations, 2021. BRLLhttss://opeeeee
net. forum jh-
Feng Dai. Approximation theory and harmonic analysis on spheres and balls. Springer, 2013.
Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural networks: Analysis and design. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.). Advances in Neural Information Processing Systems, 2021. URL /tttps:///peereevee
11

---

Published as a conference paper at ICLR 2025
Andreas Damianou and Neil D. Lawrence. Deep Gaussian processes. In Carlos M. Carvalho and Pradeep Ravikumar (eds.), Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, volume 31 of Proceedings of Machine Learning Research, pp. 207-215, Scottsdale, Arizona, USA, 29 Apr-01 May 2013. PMLR. press/ v/tp//31//aaaa anou 3a ht.m
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019.
net/ http:/ewweeeefeeeeeeeeeeeee forummiddodoooo eK 09YQ
I. Dumer, M.S. Pinsker, and V.V. Prelov. On coverings of ellipsoids in euclidean spaces. IEEE Transactions on Information Theory, 50(10))2348-2355 2356, 2004. doi: 10. 00.1109/T1T220048844755
Lawrence C Evans. Partial differential equations, volume 19. American Mathematical Society, 2022.
Tomer Galanti, Zachary S Siegel, Aparna Gupte, and Tomaso Poggio. Sgd and weight decay provably induce a low-rank bias in neural networks. arXiv preprint arXiv:2206.0555 05794, 2022.
Tomer Galanti, Mengjia Xu, Liane Galanti, and Tomaso Poggio. Norm-based generalization bounds for compositionally sparse neural networks. arXiv preprint arXiv:2301. 12033, 2023.
Mario Geiger, Stefano Spigler, Stéphane d' Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition as paradigm to understand the loss landscape of deep neural networks. Physical Review 100(1):012115, 2019.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' d'Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters in deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020()):023401, 2020.
Matteo Giordano, Kolyan Ray, and Johannes Schmidt-Hieber On the inability of gaussian process regression to optimally learn compositional functions. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), ), Advances Neural Information Processing Systems, 2022. URL
net http:r/eeeeeeeeeeeeooooo//////oo herrrmmmd=ffoooooGco
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Information and Inference: A Journal of the IMA, 9(2):473-504, 2020.
Antoine Gonon, Nicolas Brisebarre, Elisa Riccietti, and Rémi Gribonval. A path-norm toolkit for modern networks: consequences, promises and challenges. In The Twelfth International Conference Learning Representations, 2023.
Florian Graf, Sebastian Zeng, Bastian Rieck, Marc Niethammer, and Roland Kwitt. On measuring excess capacity in neural networks. Advances in Neural Information Processing Systems, 35:
10164-10178, 2022.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1832 1841. PMLR, 10-15 Jul 2018. URL httt:::/proceeedggg www.srres//e.... v80 https///////ungaeaaaaaaa hww.//ggnasaaaaaeaa 18a. html
Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang. Generalization bounds via distillation. In International Conference on Learning Representations, 2021. URL http:/ttss//opereeviiee
net/forum?icn Bed.iddddGFBBBmBmmme FeeeFFhBzmAss 1BZmAAB
Arthur Jacot. Implicit bias of large depth networks: notion of rank for nonlinear functions.
In The Eleventh International Conference on Learning Representations, 2023a. URL https
//ppenreview.o net. forte//ooummmm in 6iDicee
Arthur Jacot. Bottleneck structure in learned features: Low-dimension vs regularity tradeoff. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 23607-23629, Curran Associates, Inc., 2023b. URL ht /ttll/ttttt//oopeeiiiiiii wwwp::innnnnn..uu.uu.u.........e pappe http://pppppppeeeeeeoetteeeeaeee fttpeeeefleeeppaeeeeeeee / 0 71le://55555aaFF7e00025331333333
12

---

Published as a conference paper at ICLR 2025
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kemel: Convergence and
Generalization in Neural Networks. In Advances in Neural Information Processing Systems 31. pp. 8580-8589, Curran Associates, Inc., 2018. URL -ndee-aaa-gggeanaaeeeeeeeeae
www.perss.iiiiioo wwt.aipps..ccppppaam ccppappp/pppppcppcppppccpc.a.epe 6076-neural- -tangenttttnnnttttee kernel - conver woweeeeeeeeee-aadeeeeeeeeeeeeeee genera pdf
neu -al-networks.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv: 1912.02/78, 2019.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprini arXiv:2001.0885
2020.
Antoine Ledent, Waleed Mustafa, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 8279-8287, 2021.
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. In International Conference on Learning Representations, 2020.
Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65 (10):1331-138,, 2012.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. In International Conference on Learning Representations, 2020.
Greg Ongie and Rebecca Willett. The role of linear layers in nonlinear interpolating networks. arXiv preprint 2xXix:2202.00856 2022.
Suzanna Parkinson, Greg Ongie, and Rebecca Willett. Linear neural network layers promote learning single-and multiple-index models. arXiv preprint urXiv:2305. /5598, 2023.
Leonardo Petrini, Francesco Cagnetta, Umberto M Tomasini, Alessandro Favero, and Matthieu Wyart. How deep neural networks learn compositional data: The random hierarchy model. arXiv preprint arXiv:2307.022 129, 2023.
Tomaso Poggio and Maia Fraser. Compositional sparsity of learnable functions. Bulletin of the American Mathematical Sociery, 61(3):438 456, 2024.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008. URL TRLL/tttpp::/prrccedddns wewripssiss..... cc/
Grant Rotskoff and Eric Vanden-Eijnden. long time convergence and asymptotic егтоr
Parameters as interacting particles: scaling of neural networks. In Systems 31, pp. 7146-7155. Cur-
Advances in Neural Information Processing ran Associates, Inc., 2018.
URL
http::/pppprs.missscoo
7945 7945-paras 125-parameterssass as wagpaacciigaaratlleeee-ognneeeee
pdf
Philip Schmidt, Attila Reiss, Robert Duerichen, Claus Marberger, and Kristof Van Laerhoven. Introducing wesad, a multimodal dataset for wearable stress and affect detection. In Proceedings of the 20th ACM International Conference on Multimodal Interaction. ICMI '18, pp. 400-408. New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781 47781450356923, 10. 10.1145/3242999.322
doi: UtL.tttts:///dd /ttp://////o....//.../o// 11..0...115522222. 3249885
Johannes Schmidt-Hieber. Deep relu network approximation of functions on a manifold. arXiv preprint / 190.00099000 2019.
13

---

Published as a conference paper at ICLR 2025
Johannes Scheidt-Hieber. Nonparametric regression using deep neural networks with ReLU activa- tion function. The Annals of Staristics,, 48(4):1875 1897, 2020. doi: 10.1214/19-A0S1875 URL
https://doi www.lo.rrg1...0 wtt.:///...../1111111111
Mark Sellke. On size-independent sample complexity of relu networks. Information Processing Letters, pp. 106482, 2024.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates.
www.steeaaasnntoeeeee ArXiv, abs/1009.3896, 2010. URL http:///w.....aaatccccccc...ro/o wtw.accooaaa...oooorruuus..ua...
1984524
Lan V Truong. On rademacher complexity-basee generalization bounds for deep learning. arXiv e-prints, pp. arXiv-2208, 2022.
Rui Tuo and C. F. Jeff Wu. A theoretical framework for calibration in computer models: parametriza- tion, estimation and convergence properties, 2015. URL https: /ttpss///axvvvoo/ /a////b///// 1508 07155
Zihan Wang and Arthur Jacot. Implicit bias of SGD in Iz-regularized linear DNNs: One-way jumps from high to low rank. In The Twelfth International Conference on Learning Representations, 2024.
net Fot.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. Advances in Neural Information Processing Systems, 32, 2019.
Weinan, Chao Ma, and Lei Wu. Barron spaces and the compositional function spaces for neural network models. arXiv preprint arXiv:1906.00 08039, 2019.
Yuxiao Wen and Arthur Jacot. Which frequencies do cnns need? emergent bottleneck structure in feature learning. to appear at ICML, 2024.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR 20/7 proceedings, Feb 2017. URL /ttps://arxiv.. wttp:/iivvvgg/a///////abaa
14

---

Published as a conference paper at ICLR 2025
The Appendix is structured follows:
1. In Section A we describe the experimental setup and provide a few additional experiments.
2. in Section we introduce the notion of covering numbers and prove Theorem that we will use to obtain generalization bounds from covering numbers bound.
3. In Section
prove Theorems 1 [nd from the main.
4. In Section
we prove Proposition and Theorem
5. In Section we prove Theorem and other approximation results concerning Sobolev functions.
6. In Section prove few technical results on the covering number.
A EXPERIMENTAL SETUP
In this section, we review our numerical experiments and their setup both synthetic and real- world datasets in order to address theoretical results more clearly and intuitively. The code used for experiments is publicly available here
A.1 DATASET
A.1.1 EMPIRICAL DATASET
By Corollary A.6 from (Tuo & Wu 2015), the Reproducing kernel Hilbert space (RKHS) generated by Matérn kernel is norm equivalent to the Sobolev space (F)), so we utilized Matérn kernels generate the synthetic dataset which retains Sobolev properties.
The Matérn kernel is considered generalization of the radial basis function (RBF) kernel. It controls the differentiability, or smoothness, of the kernel through the parameter v. As - oc, the Matérn kernel converges to the RBF kernel, and as v 0, it converges to the Laplacian kernel, O-differentiable kernel. this study, we utilized the Matérn kernel to generate Gaussian Process (GP) samples based on the composition of two Matérn kernels, Kg and Kr., with varying differentiability the range 10.5,10]x(0.5,) (dmsd), and the output dimension (dou)) 15, 3, and 20, respectively.
The input dimension (din) of the kernel, the bottleneck mid-dimension
This outlines the general procedure of our sampling method for synthetic data:
1. Sample the training dataset X T RDdd,
2. From X, compute the D x kernel K, with given V/
3. From Kg, sample Z E Dxdmia with columns sampled from the Gaussian (0, Ky).
4. From Z, compute Kg with given V/.
5. From Ks, sample the test dataset Y E Dxdout with columns sampled from the Gaussian (0, K;)-
used 128 GB of RAM to generate our synthetic dataset. Due to Matérn Kernel's time complexity of Onn)) and the space complexity of O(n²), ), the maximum possible dataset size for 128 GB of memory is approximately 52,500. Among the 52,500 dataset points, 50,000 were allocated for training. and 2,500 were used for the test dataset.
A.1.2 REAL-WORLD DATASET: MNIST AND WESAD
In our study, we utilized both MNIST (Modified National Institute of Standards and Technology) and WESAD (Wearable Stress and Affect Detection) to train our AccNets for classification tasks. As standard benchmark for image classification tasks, MNIST consists of 60,000 grayscale images of 10 different handwritten digits. On the other hand, the WESAD dataset provides multimodal physiological and motion data collected from 15 subjects using devices chest. For the purpose of our experiment, we specifically employed the Empatica E4 wrist device to distinguish between non-stress (baseline) and stress conditions.
the wrist and
15

---

Published as a conference paper at ICLR 2025
10000 2.0.
Acchet 10000 2.0,
200 10.0, sh100
Acchee 200 whi0.0
Figure 3: A comparison: singular values of the weight matrices for DNN and AceNets models.
The first two plots represent cases where N = 10000 while the right two plots correspond to N 200. number of outliers at the top of each plot signifies the rank of each network. The plots with N 10000 datasets demonstrate clearer capture of the true rank compared those with N 200 indicating that higher dataset count provides more accurate rank determination.
After preprocessing, the dataset comprised total of 136,482 instances. We implemented train-test split ratio of approximately 75:25, resulting 100,000 dataset for the training set and the rest 36,482 dataset for the test set. The overall hyperparameters and architecture of the AccNets model applied to the WESAD dataset were largely consistent with those used for our synthetic data. The primary differences were the use of 100 epochs for each iteration of N, from N in the model setup and learning rate set to le-5.
A.2 MODEL SETUPS
For analyzing the scaling law of test error for our synthetic dataset, we trained mod- els with gradually increasing N; data points from our training data, where N [100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]. The models utilized for our analysis are the kernel method, shallow networks, fully connected deep neural networks (FCNN), and Ace- Nets. For FCNN and AccNets, we set the network depth to 12 layers, with the layer widths as [din, 500, 500, ..., 500, dout] for DNNs, and [d.n. 900, 100, 900, ......., 100, 900, dout] for AccNets.
In order to have comparable number of neurons between the shallow networks and other deeper networks, the width for the shallow networks was set to 50,000, resulting dimensions of [din, 50000, dour].
We utilized ReLU as the activation function and 2.2-norm as the cost function, with the Adam optimizer. The total number of batch was set 5, and the training process conducted over 3600 epochs, divided into three phases. The detailed optimizer parameters are as follows:
1. For the first 1200 epochs: learning rate (Ir) = 1.5 * 0.001, weight decay =
2. For the second 1200 epochs: Ir 0.4 0.001, weight decay = 0.002
3. For the final 1200 epochs: Ir 0.1 0.001, weight decay 0.005
We conducted experiments utilizing NVIDIA V100 GPUs (each with 32GB memory) over approximately 7 days to train all the synthetic datasets. In contrast, training the WESAD and MNIST dataset required only one hour on a single V100 GPU.
B COVERING NUMBERS
We will use covering number argument prove generalization bounds. Before start, must define a few notions.
The e-covering number (FF of set F of functions f [ ? Rd,, is the smallest integer such that for any distribution supported on Ω there is covering F. i.e. finite set with more than
16

---

Published as a conference paper at ICLR 2025
Figure 4: Comparison of our bounds to number of previous bounds on the composition of two functions dataset across different differeetiabilittes of g and h. For simplicity, prefactors in each bound, since they are mostly an artifact of the proofs. We see that our bound (Jacot24 Jacobian) obtains strictly better than previous ones, even when using upper bounding the Lipschitz constants by the operator norms (Jacot24 OP). Since we cannot compute the Lipschitz constant, we approximate them by max over 100 random points (taking more points does not significantly change the final bound). The lines appear flat because most of the variation is between different bounds rather than as N increases, but by zooming in, we can sec a downward trend, albeit a slow and noisy one. The case (2, 2) lies in the regime where both g and h are hard, in which case theory predicts that the operator norm bound should have a worse scaling exponent than the Lipschitz based bound. The experiments appear to match our prediction, because the Lipschitz-constan based bound seems to be the only one that is decreasing in N, while the operator norm bound, as well as all previous bounds, are increasing (the fact that uniform generalization bounds can be increasing in N has been observed in previous work (Nagarajan & Kolter (2019). Though these trends are interesting. there clearly lot of noise in the resulting curves, so is difficult to confidently conclude anything from these experiments.
drop the constant
elements, such that for all there is cover f E f with
-- Bnwn ((0)) [(0)- F(x))
Scc
We will also sometimes say that if covers ff in such case.
The covering number allows us to bound the difference between the errors of two datasets uniformly over the whole functions set F with high-probabilige
Theorem 6. Let F. be a space functions such that l|glloc S Bor all E F. Given true function
f such that l| S B, we have that with probability at least - p over the sampling of two datusets S, S' from distribution one has for all y E F:
log Nog,((Fe)) logp
1g - l lg 1l S min e + BY
N
Proof. We start with Chernoff bound:
Ps,s gEF
sup llg f' 11g I" 2 Es.sr
exp
tsup l|g - f'1ls- -11g -1---111 -1l--flls) e- gEF
Defining (() = Es.sr [exp (Isup 5F 11g - 1 - l1g - s [lsss]] this can be reformulated as saying that with probability p. have that for all g F
log M(t) log
1l9 f llg f'lls min
Let us now bound (t). For any pair of datasets S", we consider the c-overing F of F w.r.t. to the measure S+S5 which is the empirical measure corresponding to the dataset of size 2N made up of the union of S and S'. Thus for any function g E F, there a ğ E such that ||g - ğll s4sr S c
and ز v (FF,).
We now bound
17

---

Published as a conference paper at ICLR 2025
M(t)
Bs,s'
exp
suu gEF
11g
fl -11 f1sss
g|ls ll .llss -1 8 1lss 11 (m1ls) )
Es,s'
exp
suu gEF
S
E
exp
tsup 11@ gef
-f'lls: - و| -
Li=l 1ī(x;;) f (a:i)l 11x(x1) - f (x)))
Bs,s'
sup exp DEF
N (1l 11ss 110 1s)
Lisl (((()))) - f (xx))1 - 11 (afi))
e 24c
Bs,s'
sup exp gEF
V2N 11 f مويك
where we used the fact that ||A||s + |1bll S V |10lls 2 2|lls 2 ||/ gtyt S and conversely
||ll| + |s 2 VIAIl + ||A||s = 22 ||ll|
We may now introduce i..d. Rademacher 1.
random variables equal to 1 and -1 with prob.
2'
Em of (10(x.) - (x:))) -10(())))( (x))))
(t) S 2s,s
Egg
sup exp JEž
V2N 11ğ f-1l Ey
N
to: (1ā(x;)- - (xx))] (1ī(x() - (x4))))
< Es,s'
Es,
exp
V2N 11 M1
iEF
1=
To understand why adding the Rademacher random variables o, does not change the expectation, one can think of these random variables as randomly switching the i-th datapoints T; from S and xy from S' with each other (not that these switches leave the denominator unchanged too). Sampling two datasets S and S' followed by random switches is equivalent to sampling without the switches.
We now use Hoeffdings Lemma, which tells us that for any random var with E.X and X E [-b, b] a.s. one has E ExxptX t. & exp 2
f²b² to obtain
t
N 1i=1
(10(zx)
fz 19(())) (a)))))) 2
(ff)= < 2
Σ
exp
2N 1
f "و
jEF
e EN N |0( (x:))) (10(x()) (
<
2
Σ cxp
N2 | fz 1
GEEF
B2
[|g 101 + |l 113
= 25
Σ exp
N llğ - f P3a
LEFF
22B²
< 20
Σ
exp
N
LEEF
(22B2
< <N(F c) exp
22e
N
18

---

Published as a conference paper at ICLR 2025
This bound (t) then implies that with probability at least all g E
p the sampling of S, S for
log (t)
logp
11g 1-l -119
1ls S min
t
2
log log.V(F. log
S min 2e +
+
6
N
1
log Log,((FF logp
e + B
N
We then use the above bound the generalization error uniformly: Theorem 7. Under the same setup Theorem 6 have that with prob. 1 - p for all g F
log (JF, c)
log
11g- - 1- 1-- - Ils S min 2e + BV N
+ cBV
N
for == V2 5))
Proof. Our goal is approximate the population error || g||² by the test error I|
gll for
sample 5" independent of and this test error is itself close to the train error thanks to Theorem G
We use Bennett's inequality which relies on the fact that the function lxx)) = || (x) g(x)) | is bounded by 4B2:
N
[115 91 -11f 9lls
h(r,) NEE(E)) 2 Na
NE, [(((x) ((Ax)))E((2))? (4B2)²
4Ba
S exp
E. [(((z) - Eh(x)))
for ((u) = (1 + u) log(1 (1 + u) - u.
Lemma 8 gives us the bound + (v) S /2v + 2v, which implies that with probability p
En [h(zz) - [E(()))
(V
-2(4132 logp
-2(4B2)2 log
|| .ll -II -olss- S
4B2
NE, [(h(x) EN(x))
NE, [(h(s) Rh(x))
log
+8B² logg
- 2F ((1(x) - [b(x)))
N
N
We now use the facts that E,, [(h(z)) - [b(()))]] < Ex [h(x) < A, [h(z)] = 4B2 11g 11 obtain
log
+ 8B2 llog
1f - -15" - 011s. - B B f" -
8
N
Reordering this is implies
logp N
log
||f" -1 - 11 glle V 8B
1 8B2
<
N
which by the quadratic formula yields the inequality
- - glle - 2/822 logp N
/ 2B2
10p2-lopg logp
log p N
+ +If
911 + 8B2
N
log
< || All + (V2+ + v10) B
N
19

---

Published as a conference paper at ICLR 2025
This implies that with probability 1 2p have that for all g E F,
log P N
1g - fl - 11g - Ils 1 If gllss - 119 - f"lls + ( B
(og,N(F,e) 6) - -logp + +(V2+ VIO) B
log P
x min 2e + 2B
N
N
log NogN(F,e
llogg
$ min 2e + BV
+22333+ v
N
N
Let us now prove the lemma we used in the proof:
Lemma 8. The function d(u) = (1 + u) log( [1 + u) - u satisfies
u²
sbu)= -
1 + u 2
It is also invertible over the non-negative reals and its inverse satisfies
(v) S 22v + 2v.
Proof. To obtain the first inequality, we compute the derivatives of d: d'(u) log (1 + u) 1 log + u)
1
("(u)
1 +
which implies that
11
1
1
1 (0
{ dwdv
1 u²
<(u)
dwde
>
0
1
1 11 J
1
Solving for non-negative
u2
1 u
yields
1
2v
+ u
u
2 + u1
0
2v
-1
u
2
2/00
V2 Vo = =V
which implies that
Φ
(6) S Volv2+0+ & /2v 2v.
Example 1. As an example consider function space whose log covering number (this is also called the metric entropy) grows polynomially:
log,N((F,)) S -r
Therefore get that
|| - fll, - 11f" - flly min 2e + VBB Ve
log p/2
+ BBB
VeN
N
20

---

Published as a conference paper at ICLR 2025
Choosing = (2B² (2B²x) x) शोल ))xt (chosen so that the two terms depending on match), we obtain
|l - A11 115 flls s (2
2B C
log P/2
+ + B
N
which is of order N पीr.
Assuming that the train error is zero (or sufficiently small, i.c. O(N 2tr )), we get that
|| - =NN
C ACCNET GENERALIZATION BOUNDS
The proof of generalization for shallow networks (Theorem 1 is the special case of the proof of Theorem 2 so only prove the second:
Theorem 9. Consider an accordion net of depth L and widths dr..... da. with corresponding set of Lie( pe} with input space Q ((0, r) and with final nonlinearity that is 1-Lipschitz and uniformly bounded by B. Then with probability 1 over the sampling of the training set X from the distribution n. we have for all f
functions F far 9 Sta [e
Ry de de +11 + o(1)) + + tB. BV
log 1/2
VE( [x(l)) Se0 Bplar
Σ
pe
N
8=1
for co = 14.6 and c1 7.4. Thus if ((x(f) cuy BPLLAP Et Re
vde de -
Per
C B
1/2 N
we have
C(f) s BpLaT
Σ
Re
du de N +(1) Sef log
Pe
The strategy is: (1) prove a covering number bound F, use it bound the generalization error.
Proof.
(1) We define St V We that fo fLA1 fr .... f1. First notice that write each fe as convex combination of its neurons:
fe(x) Σ
ve = Re Σ 0e (wF,
1=1
for Wy,i
we,1 Twee. Uz.4
Me. |Re
Rs E/=1 || We, and Cr. |!agell /weell-
Let us now consider a sequence 2 for = 0.... ... K and define (b) wh to be the co-coers (0) of ūz Wy furthermore we may choose o/ = i.; = 0 since every unit vector is within 6p = distance of the origin. We will now show that one can approximate fo by approximating each of the fe by functions of the form
Ma.
fe(x)) Rs
Σ
(k)
x)
(.(k-1) (ro x))
MA,E
E,5(0)
k=1
for indices (Kk 8, = 1...., choosen adequately. Notice that the number of functions of this type
equals the number of MR.t quadruples (t) (
(R)T _(R-1) (Ik ((--)) where these vectors belong (,,(()) .
(,444) (.4(6) (,2(6)
the εĄ- resp. -goi-iies of the d resp. dour-dimensional unit sphere. Thus the number of such functions is bounded by
Kr II
( 15) 1 ( .4--)) Mac
21

---

Published as a conference paper at ICLR 2025
and we have this choice for all & 1,..... L. We will show that with sufficiently large Ma. this set of functions e-covers which then implies that
K2 Σ Ma (log N2 (2 (k- + log N2 ; .c--1))
log 1og.V((F,c) 2
1=1 k=1
We will use the probabilistic method to find the right indices fg,m approximate function fr
(k)
Re Ee ce,De,0(00 Φ) with function fe- We take all f. be i.d. equal to the index i 1. 1. we with probability Ce that in expectation
(R)
K₂ MP
Ef((z)= - Rs Σ Σ
UEs o x)
(100) (M)T
- -ig -i(t-1) -((t"")((utt- (1) x)
cei
My
R₂ Σ
(R)
(
(i(KK) x).
(K)T
We will show that this expectation is O(e (e )-lose Se and that the variance of īe goes to zero
the ME grow, allowing us to bound the expected error E [LA - Se.1 || S which then implies
that there must be at least one choice of indices (R) such that || - St.1 Se. Let us first bound the distance
mn)
[xx)
R
Σ Cei
Ve (
=(K) (K))
R
Ct.i [1(,11 (82, - (( (K)) o )
+ |لايار
(a(wī,z)
o o1 (K)T x)) )1)l)
1=1
81z
Ct,5 (0,5- 0e,4 - [(K)] | +
,. | - きن
(KYT xx
Rs
i=1
We
2R
Ce,tEKe ||-|||
2R
||a|||
22

---

Published as a conference paper at ICLR 2025
Then we bound the trace of the covariance of fe which equals the expected square distance between ft and its expectation:
[((()) - (((()))((((())
Ke
R2
Ma,E
((k) e. e.j0),
cl x) - o (w (0ol x)
i(k) (1 x)
( x)
E
E
M
Ke
R2
M
E
t.m or
(k)
(w x) of uptmm) 1)
o aw
1k-1 1
x))
MR.E
R2
Wy
U σ
Wi,i x) - ن
(k)T
(W(K-11)T 2 ||
212
||0||
2
(k)
2
(k)
(k-
2
(k) (k
1) 2
||
(k-
+
V2g 822
M
1=1
Ke
4R |,,|
(ex: + Ex-1)²
Ma.e
Ke
361?
|0|12
Ma,e
Putting both together, we obtain
B B - -((co) S AR
||0:1 2 +
Σ
Kr
36R2
||
2
MA.e
kmm
Ke o +
2x = 4R2 ||>||
Mr.e
We will now use this bound, together with the Lipschitzness of Se to bound the error
E [[[sa(()) - [La()) 2 We will do this by induction on the distances E - - Fea
We start by
T - s 4R | C 9
MR.1
k=1
And for the induction step, we condition on the first - 1 layers
E - [
E E - -ealts)))-Feat>> -f [ffe-a
E [[]Seat)) F [Tea( 11²= EE [Ee E
[Taa(t)] I| Ve-ia
E
=|]fe1(5)- (f((f))))e(f + EE
((((-m)))))) [5em1
(
Kr of
S S - + ARRB |
c + Σ
M
k=1
Now since
E Fe
s (x) + E -
fo
S Pi- ... pi ||] + E (e) - f -
23

---

Published as a conference paper at ICLR 2025
obtain that
E
fei(() - fta
$ <(p pž + AR3
E +9
Kr
Ma,e/ )) E
E
(t-)
k=1
Kr
2
+ AR Pi-1--1
1.. pi ||:111
6ke + Σ
Ma,e
We detine 83 = 0ž 11+4
R2 4
( + +9Σ k=l Mu.e/ ) and obtain
a2)
1/
1
Kt
E (na(())
Plaee 12 1.1 |1:1
2 cKe
+
MR.e
t=1
k=1
Thus for any distribution ı over the ball ((0, r), there is a choice of indices
zt. such that
Kr
| fea 2 S E Piae Riph-
c
+
MA,E
We now simply need to choose Kt and MA,e adequately. To reach an error of 2e, we choose
1 Ke loge e
ブ log 4pt.r2
4
Σ
L
Re PV
vde
de-
R
Pev de + de-1
where PL.1 = I Pe. Notice that that cx S
PEV Peydetde-1 2
40% 12
2
Rg Ete
per vao+do-1)
Rr
Given 8g = Eisl T2- 1.3473 < oo, we define
L Rr v de + de
2 x 1 pe de + de vk e
Rτ
Ma,E =
36pt.112 s0
So that for all
R2
Kr
Re / + de-1
4
Pi
2
Ke
+ 9
>
Ma.e
&
5
Pi.n r2
E pt
Pe
Bs dd de-1
2
k=1
de + di-1
Σ Ki
VR2-X k
+
2
k==1
P2.11
Σ Rs /dle do-1
80
Ri
/de + di-
$ 2
Pr.
2
PL.122 2
Σ
Rr
dde + de-1
pt
Now this also implies that
Ri / de + d
ie S exp
2
1
E Pe
Re
ddl + do-1
and thus
E1-e41
Rs pr
V de + de-1
2 Pi
PL S PL:111 exp
2
S
PLet1 exp
22
Rs
v de + do-1
pt
24

---

Published as a conference paper at ICLR 2025
Putting it all together, we obtain that
Ke
111 - FLN1 | S
Plate1
R
EKg +9
>
Mx.e
1=1
k=1
K2
2
c
exp
PLar"
Pł
Mr.0
k=1
2
S 2xx
2
6²
= 22 + O(E2).
Now since log Nog = de log (2 + 1) and
Rs
R₁ 2
Mr. S 36p2.1
v de + de-1
de de-i vk e² +
Pe
have
2
Ke
Nog,N((F, V2epp
e)
52 2
Ma. (logNN((5 ;x- + log N2 1-1 1-xx1))))__
(f.11"
L
Kr
2
MR.e (de + de-1)log( +1)
CK-1
8=1
Ke 2 log(
1 +
Ry
Rr de + de-1
< 1280pi.11" 122
v de + de-1
cc_1
pe
Pe
Vk
k=1
Kr
+
(de + de-1)
Σ log(
+ +1
CK-1
8m1
kml
L Re
$ P2 7
v de + de-1
+ 3). 6²
The diameter of J smaller than PL:1T, so for all PLAT, log N2 0. For all 8 S PL:17
choose $ so that v2 V2exp P2
S 8 and therefore
V28
2
log 1ogNN(F.0))
144s
Re pe
dde de + de
1
+
82
(2) We now apply Theorem
7 along the lines of Example]
T with r 2 and
L Re Vde + de--1
2
1
14483ep2 2
c
Pe:
82
to obtain
L
Rs v de + de (1 (10+)())
VEU - v [n(() s2
24Bso Veptar
Pe:
log
BcBB
N
L
Re v de +
log r/2
=00 C0N
BPL.T
de t1 + taB
N
25

---

Published as a conference paper at ICLR 2025
for cu = =2/ 14.6 and c .22(3 V5) ~ 7.4.
Therefore if / /Ex(I) S co BpLar Et=
Re PM
vde de - N
0q BBB
1/g
we have
N
1.
5 2 BpLAT
Σ
Rg
(1++ o(1)) + 20, BV de + do -N (1+
log 9/2
Pe
N
8==1
L
Re
-log dd + de - (1 (())((1) + 82 B2 log P/2
S BPL11
Σ
pe
N
D COMPOSITION OF SOBOLEV BALLS
Let us first prove a simple generalization bound for Sobolev balls:
Proposition 10 (Proposition 3 from the main.). Given a distribution л with support in B(0, b), we have that with probability p for all functions f F =f: IIfll S R. ll S B)
VC( (x(()= =
=
BRR"
+ BBB
log 1/2
N
where r d. Therefore if / (J) S.00
B²
c BaBy
log 1/2 N
we have
N
B2R"
2
log P/2
C()) s Soe
8c7 B²
N
Proof. (1) We know from Theorem 5.2 of (Birman & Solomjak 1967) that the Sobolev ball
90,2(0, R) over any d-dimensional hypercube 12 satisfies
R
log
e) Co
for a constant and any measure 7 supported in the hypercube.
(2) We apply Theorem 7 along the lines of Example with d and
CoTT", obtain that
Co
R'
Iτ +(V2 + ai B
log P/2
VD( v [x(1) $
2B²
N
N
B2R
2#7
log 9/2
co
+ +
B
N
N
The bound on the covering number Sobolev balls, can then be used to bound compositions of Sobolev balls, thanks to the following general result: Proposition 11. Let Fi.....FF. be set of functions mapping through the sets Do,..., St. then if all functions in F& are pe Lipschchi,,, we have
1gg2 ....c Fi.
PL.+19)) S Σ log (g
Proof. For any distribution on Ω there is ei-covering Fr F, with J s (2 then for any Jn E F choose eg-covering Fr w.r.t. the measure क which the measure of fi f1 if
26

---

Published as a conference paper at ICLR 2025
I ~ To of F2 with Fz - 22( c), and so on until we obtain coverings for all t. Then the set
F f..... fi fi E Fi......fr E F1) is a Ei= P of = FL o ... Fi.
indeed for any f fL.1 choose fi Fi....,fL FL that cover f1...., ,.....,fi. then fL. covers fL::
|12 - feal
$
Σ
fiie fe-1a flat1 o feal
8=1
Ffur - fliet1 f
PLit+1EE,
8=1
and log cardinality of the set F is bounded E log (2Fe,
We can now put the two previous results together to obtain a generalization bound for composition of Sobolev balls:
Theorem 12.
Let
=
Ft
o Fi where Fe
{fe: R + Rdd s.t. I1fellw",.2 S R. [lfell S SB Lip(fi) pe). and let r- ming re ve
for Te = de then with probability we have for all f E
VC( - V2N() S co
(B2R*
24.-
log
+ +c.By
2t.-
where co, Ci depend only on re, pe and Thus if v (Cx(f)= S co have
+ ccB/
log 9/2
N
B²R
log N
L()) S 808
+ B2
Proof. (1) We know from Theorem 5.2 of (Birman & Solomjak Bw (0, R) over any dy-dimensional hypercube satisfies
1967) that the Sobolev ball
(ci
R T2
log
(0, Rt, m)), <
for r: = de and constant Cs that depends on the size of hypercube and the dimension de and the regularity i/j and any measure т supported in the hypercube.
Thus Proposition I1 tells us that the composition of the Sobolev balls satisfies
R
logNN((F, ..... F1, PL <
C
t=1
E=1
Given /" = max, Tas we can bound it by R" Ete (cr
and by then choosing Gr =
1P C2)
e, we obtain that
Ee The
ltr
log NegLo Fi,e) FI,c)) S
Σ
Ce)
(2) Again, apply Theorem 7 along the lines of Example T we obtain that
(B2R²*
1og
VC(f) Cx(f) s co
+ BaBB
N
27

---

Published as a conference paper at ICLR 2025
E GENERALIZATION AT THE REGULARIZED GLOBAL MINIMUM
In this section, we first give the proof of Theorem 5 and then present detailed proof's of lemmas used in the proof. The lemmas are largely inspired by Bach 2017) and may be of independent interest.
E.1 THEOREM IN SECTION
Theorem 13 (Theorem S in the main). Given a true function fi-11 = ft. o...o going through the dimensions .g...., di., along with a continuous input distribution To supported in (00, bo), such that the distributions nı of fž (4) (for To) are continuous too and supported inside ( by) C Rd Further assume that there are differentiabilities and radii R& such that II.2 (( S Re, and pe such that Lip(ft) S Pt. For an infinite width AccNet with L LL and dimensions de di....,,GL-. have for the ratios ft max
433 VE ,2):
(1) At a global min FLA of (xtaa + AR(0), we have L(fra) O(N 21Tmaa for Fmax max(fi....,f1..
(2) At a global min fLA of LN(fLa) XR((), we have ((fia) O(N JTTTsmmmm for Fsum
2 Σe Ft 2.
o... fi with L I L, intermediate dimensions .g....,,f, di., along with Proof. f- ft.
continuous input distribution supported in B(0, bu), such that the distributions ne of fł (x) (for To) are continuous too and supported inside ((0, be) C Rd2, Further assume that there are differentiabilities Vs and radii R& such that [[ w ((B(O()))) I Rg.
We first focus on the L = L case and then extend to the L > L case.
Each fi can be approximated by another function fe with bounded Fi-norm and Lipschitz constant.
Actually 2v: 2 d;_1 +3 one can choose fe = fi since [lfi ll I C. by Lemma 16 and by
assumption Lip(fe) S pe. If 2v < di then by Lemma 15 we know that there fe with
fe F
S SCRRiC,
2
and Lip(Fe) S C.Lip(f)) S Cepp and error
10 Fe Lo((T-1)) (e S ce
- Fill I CEEE
Note that by setting 7: = max 4/-1+3 +3 2}, we can write
[1111 S SCeReee
+1 in both cases.
Therefore the composition fra satisfies
1|:2 Seal FeallZatte
hrat o Sēa fia si-1a L2(7)
(2(T))))
Lip(
1=1
For any L > L* dimensions de d7 and widths we 2 N, we can build an AccNet that fits exactly FL.I. by simply adding zero weights along the additional dimensions and widths, and by adding identity layers if L > L", since it is possible to represent the identity on Rd with a shallow network with 2d neurons and Fn-orrm 2d (by having two neurons (;a(e -) and (e;o(-e,-) for each basis e.). Since the cost in parameter norm of representing the identity scales with the dimension, it is best to add those identity layers the minimal dimension min (d) (d).... .i,,.....d.. J. We therefore end up with a AccNet with L L identity layers (with Fi norm 2 min .., di. }) and L layers that approximate each of the f with bounded Fi-morm function fe.
28

---

Published as a conference paper at ICLR 2025
Since fia has zero population loss, the population loss of the AccNet fL.1 is bounded by (p Dē=1 Pl:e- Using Bennett's inequality in the proof of Theorem 7 (though the 'other direction' since we want to bound LN in terms of L and not vice versa), we obtain that with probability p
logg
logp
(n(Jia) & ((fra) 1888 1 (B)L(()))))
8B²
N
-oop (lia)) + v /8B2
logp N
log p
p PL:-- PLAT-CCLet1CEe V8B2
8B2
N
(1) At the global minimizer fra1 = o.... o fi of the regularized loss (with the first regularization term), the regularized loss is upper bounded by
logp 1888 N
p
PLit+1 11E4100EE
8=1
L
L'
Req
2 Rz
+ Av 2d
Cepe
Σ
+ 2(L L2) mi). d?..
Cepe
2=1
Taking Et N 24r and X N this is upper bounded by
L
logp Tेe + +188 N
PL:t+1 PL:411CLe41cN
188B
22d Cape
Σ
RR Cepe
+ं + N
+(L L*) minfd....... ... di. NN- $
8=1
The above is of order NT 2 for Fmax max = 1,..., L}. which implies that at the global minimizer the regularized loss, the (unregularized) train loss of order N 24riaax and the complexity measure R(fi...., fL) is of order N s4rmux which implies that the test error will be of order N 2 well.
(2) Let us now focus on the R(0) regularizer instead. Taking the same approximation fL.1 we see that the global minimum fL.1 of the R-regularized loss is upper bounded by
log N
PLe+1CLetiCEE + 1
8B2
Pm1
1." AV + min di. 1) II
2- CeRec
2
t=1
where we used the bound |[Wellop Véllop S 11felle.
Choosing cg N 2+Foum for F.um = 2 Ee(Fe - 2) and A = N
is upper bounded by
2
log p N
PLaE+1 Cr.eHINNN AImmum + 8B2
+ (2d + (L L") min ................................ dz-})
II
Cr
N 21
E=1
29

---

Published as a conference paper at ICLR 2025
Which implies that both the train error is of order N 2Traum and the regularization term is of order
N 24
And since the R-regularized loss bounds the R-regularized loss, the test enror will be of order
N x-roum.
Note that if there is at a most one & where fzz > 2 then the rate is the same for both regularizers.
E.2 LEMMAS ON APPROXIMATING SOBOLEV FUNCTIONS
Now we present the lemmas used this proof above that concern the approximation errors and Lipschitz constants of Sobolev functions and compositions of them. We will bound the F2-norm and note that the F2-norm is larger than the Fi-morm, cf. (Bach) 2017 Section 3.1).
Lemma 14 (Approximation for Sobolev function with bounded error and Lipschitz constant). Sup- R with S d
pose 9 Sa - R. is an even function with bounded Sobolev norm l|gll with inputs on the unit d-dimensional sphere. Then for every > O, there is E G2 with small approximation error [|g - (...) C(d, R),,, bounded Lipschitzness Lip(g) S ('()))ip(g). and bounded norm
ll S (d,
413
Proof. Given our assumptions on the target function g, may decompose g(x) Σ 9h along the basis of spherical harmonics with go(x)) Ss, g(y)dra(y) being the mean of g(x) over the uniform distribution Ta over Sa. The k-th component can be written as
Px y) g = N(d, k)) / .(v) Ps
with ((d, k)) 2b-d-1 kk+d22 and Gegenbauer polynomial of degree and dimension d + 1: d-1
k
Pa(t)= - (-1/2) r(d/2)
- 12 dt [[k + d/2)
dik (1 (2)x+(d-2)/22
known as Rodrigues' formula. Given the assumption that the Sobolev norm Iigli upper bounded, we have Il S Cold, u for f = 2 where A is the Laplacian on S. (Eaans) 2022 Bach 2017). Note that Is are eigenfunctions of the Laplacian with eigenvalues k(k: + d (Atkinson & Han 2012). thus
Il (8, (k(k d)) < 1 I. k- S v)
where in the last inequality holds we use [l. (s.)) = Exzo ll (2g Note using the Hecke-Funk formula, we can also write Ia scaled pk for the underlying density p of the Fi and Fornorm::
(x = (x)
where A Wi-1 1 (t)) (2)(d-2) 2) at (d433/2)) (Bach 2017 Appendix D.2)
wy
and wa denotes the surface area of Sy. Then by definition of || |1 for some probability density p.
/ dr(e)
Σ l|p ((2))) oSk
Σ xx 11911191122
S.a
Now to approximate g, consider function 9 defined by truncating the "high frequencies" of g. i.c. setting ÿk = [kk 4 mlgk for some 0 specify later. Then we bound the norm with
|| = Σ
3 (B.g) = Σ
OSA:A 70
Ocksm A+#0
(d,
Σ
|| ( k d43-22
05kmm
< vd #43-2
05k5m
< v2(d, m23---2 d+3-2v
30

---

Published as a conference paper at ICLR 2025
where (a) uses Eq | and A 22( (2kk-((())))) (d+3)/2).
To bound the approximation error,
lgg 91l2a =
Σ 11 (Ba((
9k
km
(2(Bg)
kmm
Ilf l
(8,)
22
k2
Co(d, v) R2m
since Σ 11 S $11f1122(.)
kmm
Finally, choosing m 6_ ,, we obtain | (2(8)) S C(d,v) and
l I (d, -18 2z
Then it remains to bound Lip(ğ) for our constructed approximation. By construction and by Dai 2013 Theorem 2.1.3), we have g = g h with now
m
h(t) = Σ Px)),)), [E[-1,1]
k=U
by orthogonality of the Gegenbauer polynomial PE's and the convolution is defined as
(g hx))) wa Ss.
((v)h((z, v))
The coefficients for 0 < k < m given by Daai 2013 Theorem 2.1.3) are
Wd-1 [(d
Pa(1) ll + (d () 1)/2)² (b)
k r(d - 1
hx Wd I(d - 11++ k)
T22 T22-4I(d - 11+
where (a) follows from the (inverse of) weighted L2 norm of Px: (b) plugs in the unit constant
(a(1) T(d-1je and suppresses the dependence on d. Note that the constant factor M
r(k+d-1)
r(d-1)
comes from the difference in the definitions of the Gegenbauer polynomials here and in (Dai 2013 Then we can bound
[[Vp())lop
(n v)) Bo,
Lip(g) ( (b((,,)))ddy
s (ooLip(o) (f h((z, h((a,))) )
1/2
by Cauchy-Schward
1/2
m Σ
/waLip(g)
uk)
A=j=0
1/2
-waLip(o)
Σ
h1)) = dt
by Dai 2013 Eq A.5.1)
1/2
(waLip(o)
2
1-2 dt (2(t)(11
by orthogonality of P w.r.t. this measure
k=
-22-0T(d - k+)
(waLip(o)
h2 M(lk (d - 1)/2)[(((d -1)/222
k=
1/2
(agLip(o) 0(1) +
Σ
r(d- (r(d-1+1)1))
k
A=1
(wdLip(()CC()
for constant C(d) that only depends on d. Hence Lip(ø) C' (d)).ipp)))
31

---

Published as a conference paper at ICLR 2025
The next lemma adapts Lemma 14 inputs on balls instead of spheres following the construction in (Bach 2017 Proposition 5).
Lemma 15. Suppose f (0,0 b) - has bounded Sobolev norm Ilflw S R with v 2 (d+2)/2
even, where B() {ar E IR | b) is the radius-b ball. Then for every e > 0 there exists Se E F2 such that [[s fc fclle,(B(o.b)) = C(d, Re, Lip(fe) S (d)TTip(()) and
[e s (d, Re -4
Proof. Define g(2,a) = (2 a on (2,a) E Sa with a E Rd and S a E R. One may
verify that unit-norm (2,0) with a 2 v2
is sufficient to cover B(0, b) by setting x
and
solve for (z, a). Then we have bounded ||g w < 1" R and may apply Lemma 14 to get 9 with llg - (39.)) I C'd, v)b Re. Letting (z) = (% a) a for the corresponding b a) E Sa gives the desired upper bounds.
Lemma 16. Suppose f B)O,b) , has bounded Sobolev norm even. Then E F2 and |[fllr, I C(d, R.
I| S R with v 2 (d+ 3)/2
In particular, Wv.2 S Fefor 2 (d (d+33) 3)/2 even.
Proof. This lemma reproduces Bachh 2017 Proposition 5) functions with bounded Sobolev Le
norm instead of L norm. The proof follows that of Lemma 14]and and Lemma 15 and noticing that by Eq
E OS
X 1991 (l.2
Σ hdt3 20
11
05k
$
||A"/2// glli:2(04)
Udd
Finally, we remark that the above lemmas extend straightforward functions f B(O, - Rd with multi-dimeenional outputs, where the constants then depend on the output dimension d' too.
E.3 LEMMA ON APPROXIMATING COMPOSITIONS OF SOBOLEV FUNCTIONS
With the lemmas given above and the fact that the Fz-norm upper bounds the Fi-norm, find width DNN approximations for compositions of Sobolev functions, which is also pointed out in the proof of Theorem 5
Lemma 17. Assume the target function Ω + Rdoue, with Ω S B(0, b) C Rddi,, satisfies:
f = ga o.... 91 a composition of k Sobolev functions gi : Rdd - Rd+++ with bounded norms 1 < for 1,..., ... k. with dj = dini
f is Lipsehitz, i.e. Lip(g:) < oo for io..........
Ifv; S (d, + 2)/2 for any i.e. less smooth than needed. for depth L 2 k and any e >> 0, there an wnfinite-width DNN f such that
Lip(f)) < C. IT Lip(g.):
-1 Alle,
Rēe;
32

---

Published as a conference paper at ICLR 2025
with Vmax max,=1.....A V4, the constants C1 depends all of the input dimensions d, (1o gi) and dout, and C2 depends on d,, dout, V4, k. and Lip(ge) for all i.
If otherwise V4 2 (d, + 32/2 for all i, we can have f = where each layer has a parameter norm bounded by Czb m R², with C3 depending on di, dous, and
Proof. Note that by Lipschitzness.
(g: ................................ (1)( C B 0,b Lip(e;)
i.e. the pre-image of each component lies in ball. By Lemma
15 for each gi. if vs S (d, + 2)/2.
we have an approximation 9. on a slightly larger ball 6/ = b bII; (dd,,, d)+1)Lip(9)) such that
ll òille, I SC(d, di+1, vb.) RiC
llille, S C"',,, d d4,, (b,) * Rite" de 2
204
Lip(å:) S (di, di+i Lip((:);
where de the input dimension of gi Write the constants as C₁ C% and C.²' for notation simplicity. Note that the Lipschitzness of the approximations 9, guarantees that, when they are composed, (0i-1 ....o ()) (S2) lies in ball of radius by b blI;-1 CiLip(yj), hence the approximation error remains bounded while propagating. While each is (infinitewwddth) layer, for the other T. layers, we may have identity layers
Let be the composed DNN of these layers. Then we have
Lip(f) < II Lip(()) C" de. dout) II Lip(g))
and approximation emror
|l flle.
C.())) " Rie II Li)((())) O(b "max Rbe)
t=1
j>t
where Viaxx max; Vi, the last equality suppresses the dependence on di, dous Vis k, and Lip(g:) for ,,....k.. k.
In particular, by Lemma 16 uf (322 for any i = 1, k, we can take h 9s. If this holds for all i, then can have while each layer has F2-norm bounded by O(b - R$).
L
F TECHNICAL RESULTS
Here show number of technical results regarding the covering number.
First, here is a bound for the covering number of Ellipsoids, which is a simple reformulation of Theorem of (Dumer et al. (0004):
Theorem 18. The d-dimensional ellipsoid E = {a xT TTTT- k s 1) with radii v>a for d the i-th eigenvalue of K satisfies log N₂ (E,c) Mc (1 (11) for
Vx
M = Σ
log
if one has log vxi
M2 k. log
for K = ( vA
SSince the domain is always hounded here, can let the bias translate the domain to the first quadrant and let the weight be the identity matrix, cf. the construction in (Wen Jacot 2024 Proposition 1.1.3).
33

---

Published as a conference paper at ICLR 2025
For our purpose, we will want to cover unit ball B {w ||m||| - 1) w.r.t. non-isotropic norm ||=l w" Kw, but this equivalent to covering E with an isotropic norm:
Corollary 19. The covering number of the bull B = {w ||w|| S 1) w.r. the norm | w² K w
satisfies log.N (B, :c) = -Me (1 + o(1) for the same Me as in Theorem 18 and under the same condition.
Furthermore, log.N N (B, S
TrK (1 (1+ o(1) long as log o 2
(x
/Trk
(log <Trk
Proof. If E is an e-covering of E w.r.t. to the I2-norm, then B E is an e-covering of B w.r.t. the norm II- k: because if E B, then VKw and so there an E E. such that
r- -Kw S c, but then VK x covers w since || w = ( Sc
Since A; < TrK we have K < K for K the matrix obtained by replacing the i-th eigenvalue X; of K by TrK and therefore N (B, x| e) < N (B, II- k e) since 11-11 S II-Il We now have the approximation log.N (B, |1- K <) M. (1 + o(1) for
Y
K
TrK
M.
log
ie
i=1
TrK
K,
22
We now have the simplification
TrK
K
ke
log dd + o(1)) P/2 (1+ o(1))
k
Mc
log
log
Vie
2
0
1=1
where the o(1) term vanishes as e
0. Furthermore, this allows us to check that as long as
log d = 4e log 2TrK
TTrK the condition is satisfied
VTrk = 41og (1kkg
Ke li log
) =0 )==0
M
log
Second we prove how to obtain the covering number the convex hull a function set F:: Theorem 20. Let be a set of B-uniformly bounded functions. then for all εą = B2
Vlog Ng 26x) S V18
Σ 2
(FF,N
k=1
Proof. Define EN B2 and the corresponding c4-coverings F& (w.tt. some measure IT. For any f, we write [f] for the function fe([]] E F& that covers f. Then for any functions f in Conv we have
K
Σ
B.f.
Σ 1m1
3s fi- f fk((d) + +Σ B (fulAl - fi-alff) + folf)). i=ii
We may assume that folfal = 0 since the zero function co-covers the whole F since co = B.
We will now use the probabilistic method to show that the sums Em Bg (fAlfA
fa-I(fil) can
be approximated by finite averages. Consider the random functions g(()) gm sampled iid with
=(k)
34

---

Published as a conference paper at ICLR 2025
(k)
- fa-1lfi)]] = B. We have ||ggh|] = -ii= Bs (filfil - fi- and
gj
=
E
K
1
mi
K
m
3e
- -
k
Σ 1
m
||
mk
m
j=1
k= 1=1
k=1
j=1
K
3:
|
fn- [Lfi]]
K
3
m
[Allf fk fh-ilfill, I ck + ck-1 33k
where we used the fact that
If we choose my that
1 3ce (3ce) ex
)2 with Σ 0k = we know that there must exist a choice of g s such
K
me
K
m
3x (felfil - Fa-
Scx-
mi
1=1
This implies that the finite set C =
Ex
R== my j= 9j :9 E Fx - -F is an 2E covering
1 > m, (1)) (k)
of C = F, since we know that for all f = Σ 1= 3:ft there are 9.hh such that
K
Σ
Bife
Σ Bi (f+ -Fx(fi)
mi
k=
1=1
1 me
m
9
(b)
Σ 1=1
3,
(fulfl- -i----)-))))
mik
km
j=l
2
Since [d|
=
-II
K
Fx
m2 |
we have
3ch ya (log.N((F,es) + log log.N ND(FF
log (og.N(CConv(F) 2ck)
0k
EK
k=
< 18
2k) log N2F
0k
k=1
This is minimized for the choice
-k),
k), log (F,
0g
Σ 2(K-K) /og MoggN2(22 (2)
which yields the bound
K log Np(C, 2xx) S v18 Σ
2k-h k Vlg (2,,
k=1
35


Reviews:
[{"review_id": "VfsZGvaBqX", "reviewer": "Reviewer_od6v", "summary": "The paper explores how deep neural networks (DNNs) can overcome the curse of dimensionality through mechanisms of compositionality and symmetry learning. It introduces Accordion Networks (AccNets), which are structured as compositions of shallow subnetworks, and derives new generalization bounds based on the F1-norm and Lipschitz properties of these subnetworks. The authors prove that, under certain conditions, DNNs can efficiently learn complex functions, such as compositions of Sobolev functions, by leveraging these structural properties. Empirical experiments support the theoretical results, demonstrating phase transitions in learning behaviors and illustrating how compositionality helps avoid the exponential data requirements that typically plague high-dimensional learning tasks.", "questions": "- How sensitive are the theoretical results to violations of the regularity assumptions?\n- Can the authors provide clearer guidelines for when to use each regularization method?\n- Are there alternative methods to control Lipschitz constants that could simplify optimization?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces an innovative framework to explain how DNNs overcome the curse of dimensionality through compositionality and symmetry learning. Using Accordion Networks (AccNets) to model compositions of functions and deriving generalization bounds based on F1-norms and Lipschitz constants is a novel and insightful contribution.\n- The theoretical analysis is thorough, with detailed proofs and a solid foundation in functional analysis. The empirical results, though limited in scope, align well with the theory, demonstrating meaningful phase transitions and supporting the derived bounds.\n- The paper is well-organized and logically presented, though the advanced mathematical concepts may still be challenging for non-expert readers. Key ideas are well-articulated, but additional intuition would improve accessibility.\n- The paper has the potential to make a significant impact on our understanding of deep learning's success. By framing generalization in terms of compositionality and symmetry, the work could inspire new approaches to model design and optimization.", "weaknesses": "- The experiments are limited to small-scale models, and the applicability of the results to large-scale, real-world networks remains unclear. More extensive testing on modern architectures would strengthen the findings.\n- The reliance on smoothness and regularity assumptions (e.g., Sobolev norms) may limit the practical relevance of the results. The paper does not sufficiently address how deviations from these assumptions affect performance.\n- The work lacks clear guidelines for implementing the theoretical insights in real-world scenarios. The two regularization methods proposed are difficult to optimize and may not be straightforward to apply.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k6KG00NdAd", "reviewer": "Reviewer_p5Ym", "summary": "The paper investigates how deep neural networks (DNNs) can effectively tackle high-dimensional problems by leveraging compositionality and symmetry. Through a novel generalization bound, it demonstrates that DNNs with bounded F1 norms can avoid the curse of dimensionality—something shallow networks struggle with. Using a theoretical framework that combines the F1 norm (a complexity measure) and covering number arguments, the authors show how DNNs can learn compositions of functions by minimizing data requirements. This is particularly achievable when the network’s layers correspond to smooth functions that reduce dimensionality. Some empirical results illustrate phase transitions in learning based on the relative difficulty of learning different functions within the composition, validating the theory's scaling laws.", "questions": "1. Are there specific ways to directly compare the current bound with those from previous contributions? For example, how does this bound compare to those of Bartlett et al. (2017), Golowich et al. (2017), etc., for fully connected neural networks (FCNNs), and how does it compare with bounds for compositional architectures such as convolutional neural networks (CNNs)?\n\n2. Would it be possible to evaluate the bound against other bounds in the literature within the authors' proposed learning setting? For instance, could the same models used by the authors be trained, and other bounds calculated for these models to enable comparison?\n\n3. Could the bounds proposed by the authors be applied to more complex architectures, such as convolutional and residual convolutional networks? If so, how would the bounds scale as a function of the number of input/output channels and kernel sizes at each layer? How would this compare with existing studies on bounds for compositional neural networks (e.g., Ledent 2019, Graf et al. 2022)?\n\n4. The authors mention that their bound offers advantages for compositional functions, listing several properties that might contribute to its strength. Is it possible to empirically demonstrate a clear trend where the bound improves as these properties become more pronounced?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper seems to be well-thought and of a high-quality in terms of its writing and presentation. Even though the paper is technically involved, I believe that the story is coherent and the mathematical presentation is well-done. For example, the authors use Sec. 1.1 to explicitly explain the type of result they are achieving without too much technical detail, Sec. 2 to provide the necessary information to lay out the framework in which their contribution operates and Sec. 4.1.1 to explain what are the type of results we want to achieve in order to obtain a bound that deals with the curse of dimensionality.\n2. As far as I understand the use of the F1-norm (Barron norm) and the per-layer Lipschitz norm to establish generalization bounds is a novel approach in analyzing the generalization capabilities of DNNs. While traditional generalization bounds rely on norms related to the weights, for a given network $f_w$ (without biases), the F1-norm captures the minimal norm of $f_v$ such that $f_v\\equiv f_w$. This is a bit original compared to previous work.", "weaknesses": "1. Limited comparison and discussion of related bounds. The literature on generalization bounds for neural networks is extensive, with various techniques and approaches, each offering its own angle, contributions, and limitations. I believe the paper lacks sufficient comparisons, either through direct comparisons of the bounds or discussions of the advantages and limitations of other bounds in the literature. For instance, the result in Theorem 2 closely resembles the bounds of Bartlett et al. (2017) and Golowich et al. (2017). While the paper introduces a nice contribution by replacing the spectral norm with the Lipschitz norm in Bartlett 2017 and the Frobenius norm with the F1 norm, it's not clear to me when the new bound is better than the Bartlett bound. Is it possible to directly compare the current bound with those of Bartlett and Golowich? \nIf so, what are the tradeoffs between these bounds? \n\nAdditionally, other works have extended the bounds of Bartlett et al. (2017) and Golowich et al. (2017) to leverage network compositionality for improved guarantees (e.g., Ledent et al. 2019, Graf et al. 2022, Truong 2022, Galanti et al. 2023). How does your bound compare to these works? \n\nOther potentially relevant studies to discuss include those offering relatively tight generalization guarantees on common datasets (e.g., Dziugaite et al. 2017, Zhou et al. 2019, Lotfi et al. 2022). \n\n2. The presentation of the experiments lacks clarity. Much of the experimental setup is confined to the appendix, with certain details—such as the meaning of dashed lines—insufficiently explained. For example, how is the generalization bound in Figure 1 calculated? Does it include constants? When calculating performance, do you take the square root of the loss as in the generalization bound, or not? What is the training loss? How is the $R(\\theta)$ term computed? How is the F1-norm determined? The conclusions drawn from the experiments are also unclear. For instance, Figure 1 seems to show that the bound is quite loose and not strongly correlated with test performance.\n\n3. The experiments are conducted in relatively simple settings where the model is a basic fully connected neural network (FCNN) trained on MNIST classification or WESAD. I would expect to see experiments comparable in sophistication to those in the existing literature, where some studies demonstrate that their bounds are relatively tight for MNIST or even more complex datasets, and where the models used are more sophisticated than a basic FCNN (see the references below).\n\n4. While it is common in the literature for many bounds to lack tightness, it would be valuable to see how this bound compares with others in the field. This is particularly important since most bounds in the literature may not be directly comparable to the current bound, and each bound could be tighter in specific settings. \n\nReferences:\n\n- Zhou et al. 2019: https://openreview.net/pdf?id=BJgqqsAct7\n\n- Dziugaite et al. 2017: http://auai.org/uai2017/proceedings/papers/173.pdf\n\n- Graf et al. 2022: https://proceedings.neurips.cc/paper_files/paper/2022/file/420492060687ca7448398c4c3fa10366-Supplemental-Conference.pdf\n\n- Lotfi et al. 2022: https://openreview.net/pdf?id=o8nYuR8ekFm\n\n- Ledent 2019: https://arxiv.org/abs/1905.12430\n\n- Truong 2022: https://arxiv.org/abs/2208.04284\n\n- Galanti et al. 2023: https://openreview.net/pdf?id=COPzNA10hZ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "80Sh93WWwp", "reviewer": "Reviewer_4Stc", "summary": "The paper aims to proof non-vacuous generalization bounds for deep neural networks by focusing on learning functions that can be decomposed into smooth components (as quantified by Sobolev complexity bounds) that can each be learned by a shallow neural network, all of which are composed to form a deep \"accordion\" network. They build up to their main result in phases:\n* In Theorem 1, they bound the generalization of shallow neural networks on functions with bounded $F_1$ norm and Lipschitz constant.\n* They adapt these bounds to deeper networks and compositions of such smooth functions in Theorem 2.\n* Proposition 3 replaces the Lipschitzness assumption of the target in Theorem 1 with an bounded-Sobolev norm assumption. They note that this introduces a curse of dimensionality in cases where the Sobolev order is small.\n* Theorem 4 analogously extends Proposition 3 to deeper networks, noting that the curse of dimensionality depends on the highest-dimensional component. This implies that the curse of dimensionality can be avoided if the right hierarchy of symmetries exists in the target function such that each layer is low-dimensional.\n* Theorem 5 shows that the final loss can be bounded for sufficiently large accordion networks regularized by layer-wise $F_1$ norms that are guaranteed to reach a global minima.", "questions": "Is there any particular evidence that can be included about the prevalence of target functions that can be decomposed into low-dimensional components in practical learning settings? It seems to be well-situated within the multi-index model framework for shallow networks, and it's unclear whether compositions of targets like that are thought to be practically relevant.\n\nIs it clear that the $F_1$-norm-based regularization is reasonable for deeper models? If I recall correctly, part of the motivation for the $F_1$ norm in shallow models is that it corresponds with inductive biases for gradient descent, and therefore that bounded $F_1$-norm solutions are likely outcomes even if $F_1$ norm is not explicitly regularized. Are any results like this known for deeper models?\n\nDo these bounds apply when the intermediate function compositions are high-dimensional, but with a low intrinsic dimensionality (e.g. single-index models)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "As far as I can tell, the mathematics of the paper are correct and this particular decomposition is novel.\n\nI am not particularly concerned about the focus on generalization over optimization and the assumption that the trained neural network attains its global minimum. While this is a substantial assumption, this kind of optimization result would be prohibitively difficult for deep networks, and making this assumption makes it possible to prove interesting results about generalization and decomposition.", "weaknesses": "For the sake of clear presentation, I would recommend including examples of the functions that belong to different classes defined herein. For instance, which kinds of functions are Lipschitz but not Sobolev (and vice versa); and what are some examples of targets that can decomposed into a series of Sobolev targets?\n\n## Minor points / nits\n* I would add parantheses to the complexity measure on line 70 to make it clear that the product is just for the Lipschitz terms.\n* In Theorem 4, it appears that $r^*$ and $r_{\\max}$ are confused.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PDXYERqOao", "reviewer": "Reviewer_3rVU", "summary": "The authors derive generalization bounds for deep networks and functions that are compositions of simpler \nfunctions. The bounds primarily depend on the dimension and regularity of the intermediate layers and functions, which can \npotentially have much better properties than the original function. The proof is based on a covering number argument for \na single layer/intermediate function and leverages the fact that covering number behaves well under composition.", "questions": "* Could you clarify the dependence on $L$ of Theorem 4 (see the Weakness part of the review)? \n* I find the remark starting on line 256 unclear. What do you mean by the randomly initialized weights contributing a lot \n  to the parameter norm? In practice and most theoretical works, small initialization is used, and the parameter norm \n  should not decrease too much, if at all, during training when compared to its initial value.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The paper is well-written. The presentation is clear and easy-to-follow.\n* The covering number argument (proving a covering number result for shallow networks and chaining them) is interesting and \n  seems to be very suitable for analyzing deep networks/composition of function. It reduces the problem to a shallow \n  one and leads to clean proofs.\n* The results are solid and improve on previous bounds when the functions are composition of simpler functions, which \n  I believe is a fairly reasonable assumption.", "weaknesses": "* My main concern with this paper is about Theorem 4, and I would raise my score if the authors could clarify it. Theorem 4 seems strange to me as it depends only on the largest ratio\n  $r_{\\max}$ and is independent of the number of layers $L$. \n  Given a function $f$, there are multiple ways to decompose \n  it into a composition of functions, and it seems possible to reduce the ratio $r_{\\max}$ by increasing $L$ and properly\n  rescaling each component. Maybe I am missing something here (e.g., there is an $L$-independent lower bound for $r_{\\max}$),\n  but for now, I do not think the current statement of Theorem 4 is entirely correct. The proof of Theorem 5 (which I \n  assume corresponds to Theorem 12 in the appendix) does not resolve my confusion. Specifically, in line 1343, there is a \n  summation over $L$ terms that vanishes in the next line. \n* Figure 1 (the experiments related to Theorem 2) only shows the scaling laws w.r.t. the size $N$ of the training \n  set, while the theoretical results focus more about the dependence on the regularity of the intermediate layers vs \n  the global regularity. \n\n* Typos and minor issues: \n  * In the statements of most of the results, the failure probability is denoted by $\\delta$, but in some bounds it \n    is denoted by $p$.\n  * The empirical loss is referred to as $\\tilde{L}_N$ in some places and by $\\hat{L}_N$ in others. \n  * Lines 150, 151: the dimensions of $W$ and $V$\n  * Line 196: \"covering number number\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)