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

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:36:11

Abstract: We show that deep neural networks (DNNs) can efficiently learn any
composition of functions with bounded $F_{1}$-norm, which allows
DNNs to break the curse of dimensionality in ways that shallow networks
cannot. More specifically, we derive a generalization bound that combines
a covering number argument for compositionality, and the $F_{1}$-norm
(or the related Barron norm) for large width adaptivity. We show that
the global minimizer of the regularized loss of DNNs can fit for example
the composition of two functions $f^{*}=h\circ g$ from a small number
of observations, assuming $g$ is smooth/regular and reduces the dimensionality
(e.g. $g$ could be the modulo map of the symmetries of $f^{*}$),
so that $h$ can be learned in spite of its low regularity. The measures
of reguarity 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.

Main paper: 
 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 [46] . Actually DNNs have been observed to generalize best when the number of neurons is infinite [8, 21, 20] .The now quite generally accepted explanation to this phenomenon is that DNNs have an 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 [11, 36] , in linear networks [24, 30] , or in the NTK regime [28] , but it 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 [12] or explicit in the presence of weight decay [42] ). Thanks to tools such as the F 1 -norm [5] , or the related Barron norm [44] , or more generally the representation cost [14] , it is possible to describe the family of functions that can be represented by shallow networks or linear networks with a finite parameter norm. This was then leveraged to prove uniform generalization bounds (based on Rademacher complexity) over these sets [5] , which depend only on the parameter norm, but not on the number of neurons or parameters.Similar bounds have been proposed for DNNs [7, 6, 39, 33, 25, 40] , relying on different types of norms on the parameters of the network. But it seems pretty clear that we have not yet identified the 'right' complexity measure for deep networks, as there remains many issues: these bounds are typically orders of magnitude too large [29, 23] , and they tend to explode as the depth L grows [40] .Two families of bounds are particularly relevant to our analysis: bounds based on covering numbers which rely on the fact that one can obtain a covering of the composition of two function classes from Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute. covering of the individual classes [7, 25] , and path-norm bounds which extend the techniques behind the F 1 -norm bound from shallow networks to the deep case [32, 6, 23] .Another issue is the lack of approximation results to accompany these generalization bounds: many different complexity measures R(θ) on the parameters θ of DNNs have been proposed along with guarantees that the generalization gap will be small as long as R(θ) is bounded, but there are often little to no result describing families of functions that can be approximated with a bounded R(θ) norm. The situation is much clearer in shallow networks, where we know that certain Sobolev spaces can be approximated with bounded F 1 -norm [5] .We will focus on approximating composition of Sobolev functions, and obtaining close to optimal rates. This is quite similar to the family of tasks considered [39] , though the complexity measure we consider is quite different, and does not require sparsity of the parameters.We consider Accordion Networks (AccNets), which are the composition of multiple shallownetworks f L:1 = f L • • • • • f 1 , we prove a uniform generalization bound L(f L:1 ) -LN (f L:1 ) ≲ R(f 1 , . . . , f L ) log N √ N , for a complexity measure R(f 1 , . . . , f L ) = L ℓ=1 Lip(f ℓ ) L ℓ=1 ∥f ℓ ∥ F1 Lip(f ℓ ) d ℓ + d ℓ-1that depends on the F 1 -norms ∥f ℓ ∥ F1 and Lipschitz constanst Lip(f ℓ ) of the subnetworks, and the intermediate dimensions d 0 , . . . , d L . This use of the F 1 -norms makes this bound independent of the widths w 1 , . . . , w L of the subnetworks, though it does depend on the depth L (it typically grows linearly in L which is 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 W ℓ with SVD U SV T into two matrices U √ S and √ SV T to obtain an AccNet with dimensions d ℓ = RankW ℓ , so that the bound can be applied to traditional DNNs with bounded rank.We then show an approximation result: any composition of Sobolev functionsf * = f * L * • • • • • f * 1can be approximated with a network with either a bounded complexity R(θ) or a slowly growing one.Thus under certain assumptions one can show that DNNs can learn general compositions of Sobolev functions. This ability can be interpreted as DNNs being able to learn symmetries, allowing them to avoid the curse of dimensionality in settings where kernel methods or even shallow networks suffer heavily from it.Empirically, we observe a good match between the scaling laws of learning and our theory, as well as qualitative features such as transitions between regimes depending on whether it is harder to learn the symmetries of a task, or to learn the task given its symmetries. 
accordion neural networks and resnets: 
 Our analysis is most natural for a 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 isf L:1 = f L • • • • • f 1 where f ℓ (z) = W ℓ σ(V ℓ z + b ℓ )for the nonlinearity σ : R → R, the d ℓ × w ℓ matrix W ℓ , w ℓ × d ℓ-1 matrix V ℓ , and w ℓ -dim. vector b ℓ , and for the widths w 1 , . . . , w L and dimensions d 0 , . . . , d L . We will focus on the ReLU σ(x) = max{0, x} for the nonlinearity. The parameters θ are made up of the concatenation of all (W ℓ , V ℓ , b ℓ ). More generally, we denotef ℓ2:ℓ1 = f ℓ2 • • • • • f ℓ1for any 1 ≤ ℓ 1 ≤ ℓ 2 ≤ L.We will typically be interested in settings where the widths w ℓ 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.e. f res 1:L = (f L + id) • • • • • (f 1 + id) for the same shallow nets f 1 , . . . , f L we recover the typical ResNets.FCNN is replaced by a product of two matrices M ℓ = V ℓ W ℓ-1 in the middle of the network (such a structure has already been proposed [34] ). Given an AccNet one can recover an equivalent FCNN bychoosing M ℓ = V ℓ W ℓ-1 , M 0 = V 0 and M L+1 = W L .In the other direction there could be multiple ways to split M ℓ into the product of two matrices, but we will focus on taking V ℓ = U √ S and W ℓ-1 = √ SV T for the SVD decomposition M ℓ = U SV T , along with the choice d ℓ = RankM ℓ .We consider a traditional learning setup, where we want to find a function EQUATION(f ) = 1 N N i=1 ℓ(x i , f (x i ))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 LN (f ) -L(f ) uniformly over certain functions familiesf ∈ F.For regression tasks, we assume the existence of a true function f * and try to minimize the distance ℓ(x, y) = ∥f * (x) -y∥ p for p ≥ 1. If we assume that f * (x) and y are uniformly bounded then one can easily show that ℓ(x, y) is bounded and Lipschitz. We are particularly interested in the cases p ∈ {1, 2}, with p = 2 representing the classical MSE, and p = 1 representing a L 1 distance. The p = 2 case is amenable to 'fast rates' which take advantage of the fact that the loss increases very slowly around the optimal solution f * , We do not prove such fast rates (even though it might be possible) so we focus on the p = 1 case.For classification tasks on k classes, we assume the existence of a 'true class' function f * : Ω → {1, . . . , k} and want to learn a functionf : Ω → R k such that the largest entry of f (x) is the f * (k)-th entry. One can consider the hinge cost ℓ(x, y) = max{0, 1 -(y f * (k) -max i̸ =f * (x) y i )}, which iszero whenever the margin y f * (k) -max i̸ =f * (x) y i is larger than 1 and otherwise equals 1 minus the margin. The hinge loss is Lipschitz and bounded if we assume bounded outputs y = f (x). The cross-entropy loss also fits our setup.In our study, we utilized the Wearable Stress and Affect Detection (WESAD) dataset to train our AccNets for binary classification. The WESAD dataset, which is publicly accessible, provides multimodal physiological and motion data collected from 15 subjects using devices worn on the wrist and chest. For the purpose of our experiment, we specifically employed the Empatica E4 wrist device to distinguish between non-stress (baseline) and stress conditions, simplifying the classification task to these two categories.After preprocessing, the dataset comprised a total of 136,482 instances. We implemented a train-test split ratio of approximately 75:25, resulting in 100,000 instances for the training set and 36,482 instances 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 Ni from Ns, and a learning rate set to 1e-5. 4 The code used for experiments are publicly available here (f ) -LN (f ) ≤ Cρ L:1 r L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 log N √ N (1 + o(1)) + c 0 2 log 2 /δ N .Proof. The strategy is: (1) prove a covering number bound on F (2) use it to obtain a Rademacher complexity bound, (3) use the Rademacher complexity to bound the generalization error.(1) We definef ℓ = V ℓ • σ • W ℓ so that f θ = f L:1 = f L • • • • • f 1 .First notice that we can write each f ℓ as convex combination of its neurons:f ℓ (x) = w ℓ i=1 v ℓ,i σ(w T ℓ,i x) = R ℓ w ℓ i=1 c ℓ,i vℓ,i σ( wT ℓ,i x)for wℓ,i =w ℓ,i ∥w ℓ,i ∥ , vℓ,i = v ℓ,i ∥v ℓ,i ∥ , R ℓ = ℓ i=1 ∥v ℓ,i ∥ ∥w ℓ,i ∥ and c ℓ,i = 1 R ℓ ∥v ℓ,i ∥ ∥w ℓ,i ∥.Let us now consider a sequence ϵ k = 2 -k for k = 0, . . . , K and define ṽ(k) ℓ,i , w(k) ℓ,i to be the ϵ k -covers of vℓ,i , wℓ,i , furthermore we may choose ṽ(0) ℓ,i = w(0) ℓ,i = 0 since every unit vector is within a ϵ 0 = 1 distance of the origin. We will now show that on can approximate f θ by approximating each of the f ℓ by functions of the formfℓ (x) = R ℓ K ℓ k=1 1 M k,ℓ M k,ℓ m=1 ṽ(k) ℓ,i (k) ℓ,m σ( w(k)T ℓ,i (k) ℓ,m x) - ṽ(k-1) ℓ,i (k) ℓ,m σ( w(k-1)T ℓ,i (k) ℓ,mx)for indices i (k)ℓ,m = 1, . . . , w ℓ choosen adequately. Notice that the number of functions of this type equals the number of M k,ℓ quadruples (ṽEQUATION) where these vectors belong to the ϵ k -resp. ϵ k-1 -coverings of the d in -resp. d out -dimensional unit sphere. Thus the number of such functions is bounded byK ℓ k=1 N 2 (S din-1 , ϵ k )N 2 (S dout-1 , ϵ k )N 2 (S din-1 , ϵ k-1 )N 2 (S dout-1 , ϵ k-1 ) M k,ℓ ,and we have this choice for all ℓ = 1, . . . , L. We will show that with sufficiently large M k,ℓ this set of functions ϵ-covers F which then implies thatlog N 2 (F, ϵ) ≤ 2 L ℓ=1 K ℓ k=1 M k,ℓ log N 2 (S din-1 , ϵ k-1 ) + log N 2 (S din-1 , ϵ k-1) .We will use the probabilistic method to find the right indices i(k) ℓ,m to approximate a function f ℓ = R ℓ w ℓ i=1 c ℓ,i vℓ,i σ( wT ℓ,ix) with a function fℓ . We take all i (k) ℓ,m to be i.i.d. equal to the index i = 1, • • • , w ℓ with probability c ℓ,i , so that in expectationE fℓ (x) = R ℓ K ℓ k=1 w ℓ i=1 c ℓ,i ṽ(k) ℓ,i σ( w(k)T ℓ,i x) - ṽ(k-1) ℓ,i σ( w(k-1)T ℓ,i x) = R ℓ w ℓ i=1 c ℓ,i ṽ(K) ℓ,i σ( w(K)T ℓ,ix).We will show that this expectation is O(ϵ K ℓ )-close to f ℓ and that the variance of fℓ goes to zero as the M ℓ,k s grow, allowing us to bound the expected error E f L:1 -fL:1 2 π ≤ ϵ 2 which then implies that there must be at least one choice of indices i(k) ℓ,m such that f L:1 -fL:1 π ≤ ϵ.Let us first bound the distancef ℓ (x) -E fℓ (x) = R ℓ w ℓ i=1 c ℓ,i vℓ,i σ( wT ℓ,i x) - ṽ(K) ℓ,i σ( w(K)T ℓ,i x) ≤ R ℓ w ℓ i=1 c ℓ,i vℓ,i - ṽ(K) ℓ,i σ( wT ℓ,i x) + ṽ(K) ℓ,i σ( wT ℓ,i x) -σ( w(K)T ℓ,i x) ≤ R ℓ w ℓ i=1 c ℓ,i vℓ,i - ṽ(K) ℓ,i wT ℓ,i x + ṽ(K) ℓ,i wT ℓ,i x - w(K)T ℓ,i x ≤ 2R ℓ w ℓ i=1 c ℓ,i ϵ K ℓ ∥x∥ = 2R ℓ ϵ K ℓ ∥x∥ .Then we bound the trace of the covariance of fℓ which equals the expected square distance between fℓ and its expectation:EQUATIONx) -ṽ(k-1)EQUATIONx) -ṽ(k-1)EQUATION+ c i ṽ(k) ℓ,i - ṽ(k-1) ℓ,i 2 w(k-1) ℓ,i 2 ≤ K ℓ k=1 4R 2 ℓ ∥x∥ 2 M k,ℓ (ϵ k + ϵ k-1 ) 2 ≤ K ℓ k=1 36R 2 ℓ ∥x∥ 2 M k,ℓ ϵ 2 k .Putting both together, we obtainEQUATIONWe will now use this bound, together with the Lipschitzness of f ℓ to bound the error . We will do this by induction on the distances E f ℓ:1 (x) -fℓ:1 (x) .E f L:1 (x) -fL:1 (x)We start byE f 1 (x) -f1 (x) 2 ≤ 4R 2 1 ∥x∥ 2 ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,1 .And for the induction step, we condition on the layers f ℓ-1:1E f ℓ:1 (x) -fℓ:1 (x) 2 = E E f ℓ:1 (x) -fℓ:1 (x) 2 | fℓ-1:1 = E f ℓ:1 (x) -E fℓ:1 (x)| fℓ-1:1 2 + EE fℓ:1 (x) -E fℓ:1 (x)| fℓ-1:1 2 | fℓ-1:1 = E f ℓ:1 (x) -f ℓ ( fℓ-1:1 (x)) 2 + EE fℓ:1 (x) -f ℓ ( fℓ-1:1 (x)) 2 | fℓ-1:1 ≤ ρ 2 ℓ E f ℓ-1:1 (x) -fℓ-1:1 (x) 2 + 4R 2 ℓ E fℓ-1:1 (x) 2 ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓ .Now sinceE fℓ-1:1 (x) 2 ≤ ∥f ℓ-1:1 (x)∥ 2 + E f ℓ-1:1 (x) -fℓ-1:1 (x) 2 ≤ ρ 2 ℓ-1 • • • ρ 2 1 ∥x∥ 2 + E f ℓ-1:1 (x) -fℓ-1:1 (x)2 we obtain thatE f ℓ:1 (x) -fℓ:1 (x) 2 ≤ ρ 2 ℓ + 4R 2 ℓ ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓ E f ℓ-1:1 (x) -fℓ-1:1 (x) 2 + 4R 2 ℓ ρ 2 ℓ-1 • • • ρ 2 1 ∥x∥ 2 ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓ . We define ρ2 ℓ = ρ 2 ℓ 1 + 4 R 2 ℓ ρ 2 ℓ ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓand obtainE f L:1 (x) -fL:1 (x) 2 ≤ 4 L ℓ=1 ρ2 L:ℓ+1 R 2 ℓ ρ 2 ℓ-1:1 ∥x∥ 2 ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓ .Thus for any distribution π over the ball B(0, r), there is a choice of indices i(k)ℓ,m such thatf L:1 -fL:1 2 π ≤ 4 L ℓ=1 ρ2 L:ℓ+1 R 2 ℓ ρ 2 ℓ-1:1 r 2 ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓ .We now simply need to choose K ℓ and M k,ℓ adequately. To reach an error of 2ϵ, we chooseK ℓ = -log ϵ + 1 2 log 4ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 R ℓ ρ ℓ d ℓ + d ℓ-1 where ρ L:1 = L ℓ=1 ρ ℓ . Notice that that ϵ 2 K ℓ ≤ 1 4ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ′ ρ ℓ ′ √ d ℓ ′ +d ℓ ′ -1 ρ ℓ √ d ℓ +d ℓ-1 R ℓ ϵ 2 . Given s 0 = ∞ k=1 √ k2 -k ≈ 1.3473 < ∞, we define M k,ℓ = 36ρ 2 L:1 r 2 s 0 L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 R ℓ ρ ℓ d ℓ + d ℓ-1 2 -k √ k 1 ϵ 2 . So that for all ℓ 4 R 2 ℓ ρ 2 ℓ ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓ ≤ R ℓ ρ ℓ d ℓ + d ℓ-1 ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ρ ℓ d ℓ + d ℓ-1 ϵ 2 + R ℓ ρ ℓ d ℓ + d ℓ-1 ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ρ ℓ d ℓ + d ℓ-1 ϵ 2 K ℓ k ′ =1 √ k ′ 2 -k ′ s 0 ≤ 2 R ℓ ρ ℓ d ℓ + d ℓ-1 ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ρ ℓ d ℓ + d ℓ-1 ϵ 2 .Now this also implies thatρℓ ≤ ρ ℓ exp   2 R ℓ ρ ℓ d ℓ + d ℓ-1 ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ρ ℓ d ℓ + d ℓ-1 ϵ 2   and thus ρL:ℓ+1 ≤ ρ L:ℓ+1 exp   2 L ℓ ′ =ℓ+1 R ℓ ρ ℓ d ℓ + d ℓ-1 ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ρ ℓ d ℓ + d ℓ-1 ϵ 2   ≤ ρ L:ℓ+1 exp 2 ρ 2 L:1 r 2 ϵ 2 .Putting it all together, we obtain thatf L:1 -fL:1 2 π ≤ 4 L ℓ=1 ρ2 L:ℓ+1 R 2 ℓ ρ 2 ℓ-1:1 r 2 ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓ ≤ exp 2 ρ 2 L:1 r 2 ϵ 2 ρ 2 L:1 r 2 L ℓ=1 4 R 2 ℓ ρ 2 ℓ ϵ 2 K ℓ + 9 K ℓ k=1 ϵ 2 k M k,ℓ ≤ 2 exp 2 ρ 2 L:1 r 2 ϵ 2 ϵ 2 = 2ϵ 2 + O(ϵ 4 ). Now since log N 2 (S d ℓ -1 , ϵ) = d ℓ log 1 ϵ + 1 and M k,ℓ ≤ 36ρ 2 L:1 r 2 s 0 L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 R ℓ ρ ℓ d ℓ + d ℓ-1 2 -k √ k 1 ϵ 2 + 1, we have log N 2 (F, √ 2 exp ϵ 2 ρ 2 L:1 r 2 ϵ) ≤ 2 L ℓ=1 K ℓ k=1 M k,ℓ log N 2 (S d ℓ -1 , ϵ k-1 ) + log N 2 (S d ℓ-1 -1 , ϵ k-1 ) ≤ 2 L ℓ=1 K ℓ k=1 M k,ℓ (d ℓ + d ℓ-1 ) log( 1 ϵ k-1 + 1) ≤ 72s 0 ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 L ℓ=1 R ℓ ρ ℓ d ℓ + d ℓ-1 K ℓ k=1 2 -k log( 1 ϵ k-1 + 1) √ k 1 ϵ 2 + 2 L ℓ=1 (d ℓ + d ℓ-1 ) K ℓ k=1 log( 1 ϵ k-1 + 1) ≤ 72s 2 0 ρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 2 1 ϵ 2 + o(ϵ -2 ).The diameter of F is smaller than ρ L:1 r, so for all δ ≥ ρ L:1 r, log N 2 (F, δ) = 0. For all δ ≤ ρ L:1 rwe choose ϵ = δ √ 2e so that √ 2 exp ϵ 2 ρ 2 L:1 r 2 ϵ ≤ δ and therefore log N 2 (F, δ) ≤ 144s 2 0 eρ 2 L:1 r 2 L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 2 1 δ 2 + o(δ -2 ).(2) Our goal now is to use chaining / Dudley's theorem to bound the Rademacher complexity R(F(X)) evaluated on a set X of size N (e.g. Lemma 27.4 in [Understanding Machine Learning]) of our set:Lemma 7. Let c = max f ∈F 1 √ N ∥f (X)∥, then for any integer M > 0, R(F(X)) ≤ c2 -M + 6c √ N M k=1 2 -k log N (F, c2 -k ).To apply it to our setting, first note that for all x ∈ B(0, r), ∥f L:1 (x)∥ ≤ ρ L:1 r so that c = max f ∈F 1 √ N ∥f (X)∥ ≤ ρ L:1 r, we then have R(F(X)) ≤ c2 -M + 6c √ N M k=1 2 -k 12s 0 √ eρ L:1 r L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 c -1 2 k (1 + o(1)) = c2 -M + 72 √ N M s 0 √ eρ L:1 r L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 (1 + o(1)).Taking M = -log 2 72 √ N s 0 √ e L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 , we obtain R(F(X)) ≤ 72 √ N M s 0 √ eρ L:1 r L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 (1 + M (1 + o(1))) ≤ 144 √ N M s 0 √ eρ L:1 r L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 -log 2 72 √ N s 0 √ e L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 (1 + o(1)) ≤ Cρ L:1 r L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 log N √ N (1 + o(1)).(3) For any ρ-Lipschitz loss function ℓ(x, f (x)) with |ℓ(x, y)| ≤ c 0 , we know that with probability 1 -δ over the sampling of the training set X from the distribution π, we have for all f ∈ FE x∼π [ℓ(x, f (x))] - 1 N N i=1 ℓ(x i , f (x i )) ≤ 2E X ′ [R(ℓ • F(X ′ ))] + c 0 2 log 2 /δ N ≤ 2Cρ L:1 r L ℓ ′ =1 R ℓ ′ ρ ℓ ′ d ℓ ′ + d ℓ ′ -1 log N √ N (1 + o(1)) + c 0 2 log 2 /δ N . 
generalization bound for dnns: 
 The reason we focus on accordion networks is that there exists generalization bounds for shallow networks [5, 44] , 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 to extend the results for shallow nets to the composition of multiple shallow nets, i.e. AccNets.Roughly speaking, we will show that the complexity of an AccNet f θ is bounded by the sum of the complexities of the shallow nets f 1 , . . . , f L 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 F 1 -norm [5] , and then prove a generalization bound for deep AccNets.The complexity of a shallow net f (x) = W σ(V x + b), with weights W ∈ R w×dout andV ∈ R din×w , can be bounded in terms of the quantity C = w i=1 ∥W •i ∥ ∥V i• ∥ 2 + b 2 i .First note that the rescaled function 1 C f can be written as a convex combination1 C f (x) = w i=1 ∥W•i∥ √ ∥Vi•∥ 2 +b 2 i C W•i σ( Vi• x + bi ) for W•i = W•i ∥W•i∥ , Vi• = Vi• √ ∥Vi•∥ 2 +b 2 i , and bi = bi √ ∥Vi•∥ 2 +b 2 i , since the coefficients ∥W•i∥ √ ∥Vi•∥ 2 +b 2 i Care positive and sum up to 1. Thus f belongs to C times the convex hullB F1 = Conv x → wσ(v T x + b) : ∥w∥ 2 = ∥v∥ 2 + b 2 = 1 .We call this the F 1 -ball since it can be thought of as the unit ball w.r.t. the F 1 -norm ∥f ∥ F1 which we define as the smallest positive scalar s such that1 1 s f ∈ B F1 . For more details in the single output case, see [5] .The generalization gap over any F 1 -ball can be uniformly bounded with high probability:Theorem 1. For any input distribution π supported on the L 2 ball B(0, b) with radius b, we have with probability 1 -δ, over the training samples x 1 , . . . , x N , that for allf ∈ B F1 (0, R) = R • B F1 L(f ) -LN (f ) ≤ ρbR d in + d out log N √ N + c 0 2 log 2 /δ NThis theorem is a slight variation of the one found in [5] : we simply generalize it to multiple outputs, and also prove it using a covering number argument instead of a direct computation of the Rademacher complexity, which will be key to obtaining a generalization bound for the deep case. But due to this change of strategy we pay a log N cost here and in our later results. We know that the log N term can be removed in Theorem 1 by switching to a Rademacher argument, but we do not know whether it can be removed in deep nets.Notice how this bound does not depend on the width w, because the F 1 -norm (and the F 1 -ball) themselves do not depend on the width. This matches with empirical evidence that shows that increasing the width does not hurt generalization [8, 21, 20] .To use Theorem 1 effectively we need to be able to guarantee that the learned function will have a small enough F 1 -norm. The F 1 -norm is hard to compute exactly, but it is bounded by the parameternorm: if f (x) = W σ(V x + b), then ∥f ∥ F1 ≤ 1 2 ∥W ∥ 2 F + ∥V ∥ 2 F + ∥b∥ 2, and this bound is tight if the width w is large enough and the parameters are chosen optimally. Adding weight decay/L 2regularization to the cost then leads to bias towards learning with small F 1 norm.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 F 1 balls. More precisely, if∥W ℓ ∥ 2 + ∥V ℓ ∥ 2 + ∥b ℓ ∥ 2 ≤ 2R ℓ then f L:1 belongs to the set {g L • • • • • g 1 : g ℓ ∈ B F1 (0, R ℓ )} for some R ℓ , which is width agnostic.As already noticed in [7] , the covering number number is well-behaved under composition, this allows us to bound the complexity of AccNets in terms of the individual shallow nets it is made up of:Theorem 2. Consider an accordion net of depth L and widths d L , . . . , d 0 , with corresponding set offunctions F = {f L:1 : ∥f ℓ ∥ F1 ≤ R ℓ , Lip(f ℓ ) ≤ ρ ℓ }.With probability 1 -δ over the sampling of the training set X from the distribution π supported in B(0, b), we have for allf ∈ F L(f ) -LN (f ) ≤ Cρbρ L:1 L ℓ=1 R ℓ ρ ℓ d ℓ + d ℓ-1 log N √ N (1 + o(1)) + c 0 2 log 2 /δ N .Theorem 2 can be extended to ResNets (f L + id) • • • • • (f 1 + id)∥ 2 F = ∥V ℓ ∥ 2 F = ∥M ℓ ∥ * . Some boundsFigure 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 saling laws (even though they are orders of magnitude too large overall). We consider a compositional true function f * = h • g where g maps from dimension 15 to 3 while h maps from 3 to 20, and we denote ν g , ν h for the number of times g, h are differentiable. In the first plot ν g = 8, ν h = 1 so that g is easy to learn while h is hard, whereas in the second plot ν g = 9, ν h = 9, so both g and h are relatively easier. The third plot presents the decay in test error and generalization bounds for networks evaluated using the real-world dataset, WESAD [37] .assuming rank sparsity of the weight matrices also appear in [41] . And several recent results have shown that weight-decay leads to a low-rank bias on the weight matrices of the network [27, 26, 19] and replacing the Frobenius norm regularization with a nuclear norm regularization (according to the above mentioned equivalence) will only increase this low-rank bias.We compute in Figure 1 the upper bound of Theorem 2 for both AccNets and DNNs, and even though we observe a very large gap (roughly of order 10 3 ), 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 L 2 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 a lot to the parameter norm, and thus lead to a larger generalization bound. During training with weight decay, these random initial weights slowly vanish, thus leading to a 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 to future work. 
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 on this family of tasks because they are well adapted to 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 it (e.g. Figure 1 ).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 measureR(f 1 , . . . , f L ) = L ℓ=1 Lip(f ℓ ) L ℓ=1 ∥f ℓ ∥ F1 Lip(f ℓ ) d ℓ + d ℓ-1 .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 a few times differentiable). The final plot on the right displays the difference between the two. The lower left region represents the area where g is easier to learn than h, the upper right where h is easier to learn than g, and the lower right region where both f and g are easy..The family of Sobolev norms capture some notion of regularity of a function, as it measures the size of its derivatives. The Sobolev norm of a function f : R din → R is defined in terms of its derivatives ∂ α x f for some d in -multi-index α, namely the W ν,p (π)-Sobolev norm with integer ν and p ≥ 1 is defined as∥f ∥ p W ν,p (π) = |α|≤ν ∥∂ α x f ∥ p Lp(π) .Note that the derivative ∂ α x f 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 B W ν,p (π) (0, R) = {f : ∥f ∥ W ν,p (π) ≤ R} are a family of function spaces with a range of regularity (the larger ν, 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 a distribution π with support the L 2 ball with radius b, we have that withprobability 1 -δ for all functions f ∈ F = {f : ∥f ∥ W ν,2 ≤ R, ∥f ∥ ∞ ≤ R} L(f ) -LN (f ) ≤ 2ρC 1 REν /d (N ) + c 0 2 log 2 /δ N .whereE r (N ) = N -1 2 if r > 1 2 , E r (N ) = N -1 2 log N if r = 1 2 , and E r (N ) = N -r if r < 1 2 .But this result also illustrates the curse of dimensionality: the differentiability ν needs to scale with the input dimension d in to obtain a reasonable rate. If instead ν is constant and d in grows, then the number of datapoints N needed to guarantee a generalization gap of at most ϵ scales exponentially ind in , i.e. N ∼ ϵ -d in ν .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 x i to a test point x is typically very far away.To break the curse of dimensionality, we need to assume some additional structure on the data or task which introduces an 'intrinsic dimension' that can be much lower than the input dimension d in :Manifold hypothesis: If the input distribution lies on a d surf -dimensional manifold, the error rates typically depends on d surf instead of d in [38, 10] . that respect the same symmetries) [31] .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 to learn translation symmetries, since they can learn so-called low-index functions which satisfy f * (x) = f * (P x) for some projection P (with a statistical complexity that depends on the dimension of the space one projects into, not the full dimension [5, 2] ). 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 modulo map g * simultaneously, hence the importance of feature learning.For g * to be learnable efficiently, it needs to be regular enough to not suffer from the curse of dimensionality, but many traditional symmetries actually have smooth modulo maps, for example the modulo map g * (x) = ∥x∥ 2 for rotation invariance. This can be understood as a special case of composition of Sobolev functions, whose generalization gap can be bounded:Theorem 4. Consider the function set F = F L • • • • • F 1 where F ℓ = f ℓ : R d ℓ-1 → R d ℓ s.t. ∥f ℓ ∥ W ν ℓ ,2 ≤ R ℓ , ∥f ℓ ∥ ∞ ≤ b ℓ , Lip(f ℓ ) ≤ ρ ℓ , and let r min = min ℓ r ℓ for r ℓ = ν ℓ d ℓ-1 , then with probability 1 -δ we have for all f ∈ F L(f ) -LN (f ) ≤ ρC 0 L ℓ=1 (C ℓ ρ L:ℓ+1 R ℓ ) 1 r min +1 rmin+1 E rmin (N ) + c 0 2 log 2 /δ N ,where C ℓ depends only ond ℓ-1 , d ℓ , ν ℓ , b ℓ-1 .We see that only the smallest ratio r min matters when it comes to the rate of learning. And actually the above result could be slightly improved to show that the sum over all layers could be replaced by a sum over only the layers where the ratio r ℓ leads to the worst rate E r ℓ (N ) = E rmin (N ) (and the other layers contribute an asymptotically subdominant amount).Coming back to the symmetry learning example, we see that the hardness of learning a function of the type f * = h • g with inner dimension d mid and regularities ν g and ν h , the error rate will be (upto log terms) N -min{ 1 2 , νg d in , ν h d mid} . This suggests the existence of three regimes depending on which term attains the minimum: a regime where both g and h are easy to learn and we have N -12 learning, a regime g is hard, and a regime where h is hard. The last two regimes differentiate between tasks where learning the symmetry is hard and those where learning the function knowing its symmetries is hard.In contrast, without taking advantage of the compositional structure, we expect f * to be only min{ν g , ν h } times differentiable, so trying to learn it as a single Sobolev function would lead to an error rate ofN -min{ 1 2 , min{νg ,ν h } d in } = N -min{ 1 2 , νg d in , ν h d in} which is no better than the compositional rate, and is strictly worse whenever ν h < ν g and ν h din < 1 2 (we can always assume d mid ≤ d in since one could always choose d = id).Furthermore, since multiple compositions are possible, one can imagine a hierarchy of symmetries that slowly reduce the dimensionality with less and less regular modulo maps. For example one couldimagine a composition f L • • • • • f 1 with dimensions d ℓ = d 0 2 -ℓ and regularities ν ℓ = d 0 2 -ℓ so that the ratios remain constant r ℓ = d02 -ℓ d02 -ℓ+1 = 1 2 , leading to an almost parametric rate of N -1 2 log Neven though the function may only be d 0 2 -L times differentiable. Without compositionality, the rate would only be N -2 -L .Remark. In the case of a single Sobolev function, one can show that the rate Eν /d (N ) is in some sense optimal, by giving an information theoretic lower bound with matching rate. A naive argument suggests that the rate of E min{r1,...,r L } (N ) should similarly be optimal: assume that the minimum r ℓ is attained at a layer ℓ, then one can consider the subset of functions such that the imagef ℓ-1:1 (B(0, r)) contains a ball B(z, r ′ ) ⊂ R d ℓ-1 and that the function f L:ℓ+1 is β-non-contracting ∥f L:ℓ+1 (x) -f L:ℓ+1 (y)∥ ≥ β ∥x -y∥, then learning f L:1 should be as hard as learning f ℓ over the ball B(z, r ′ ) (more rigorously this could be argued from the fact that any ϵ-covering of f L:1 can be mapped to an ϵ /β-covering of f ℓ ), thus forcing a rate of at least E r ℓ (N ) = E min{r1,...,r L } (N ).An analysis of minimax rates in a similar setting has been done in [22] .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 a model that can achieve those rates. Though many models are possible 2 , we focus on DNNs, in particular AccNets.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: • At a global minimizer fL:1 of the regularized lossTheorem 5. Given a true function f * L * :1 = f * L * • • • • • f * 1 goingf 1 , . . . , f L → LN (f L:1 ) + λ L ℓ=1 Lip(f ℓ ) L ℓ=1 ∥f ℓ ∥ F 1 Lip(f ℓ ) d ℓ-1 + d ℓ , we have L( fL:1 ) = Õ(N -min{ 1 2 ,r1,...,r L * } ).• At a global minimizer fL:1 of the regularized loss f 1 , . . . , f L → LN (f L:1 )+λ L ℓ=1 ∥f ℓ ∥ F1 , we have L( fL:1 ) = Õ(N -1 2 + L * ℓ=1 max{0,r ℓ -1 2 } ).There are a number of limitations to this result. First we assume that one is able to recover the global minimizer of the regularized loss, which should be hard in general 3 (we already know from [5] that this is NP-hard for shallow networks and a simple F 1 -regularization). Note that it is sufficient to recover a network f L:1 whose regularized loss is within a constant of the 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 [2, 1, 35] ).We propose two regularizations because they offer a tradeoff:First regularization: The first regularization term leads to almost optimal rates, up to the changefrom r ℓ = ν ℓ d * ℓ to r ℓ = ν ℓ d * ℓ +3which is negligible for large dimensions d ℓ and differentiabilities ν ℓ . The first problem is that it requires an infinite width at the moment, because we were not able to prove that a function with bounded F 1 -norm and Lipschitz constant can be approximated by a sufficiently wide shallow networks with the same (or close) F 1 -norm and Lipschitz constant (we know from [5] that it is possible without preserving the Lipschitzness). We are quite hopeful that this condition might be removed in future work.The second and more significant problem is that the Lipschitz constants Lip(f ℓ ) 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 unreasonable. It might be more reasonable to leverage an implicit bias instead, such as a large learning rate, because a large Lipschitz constant implies that the nework is sensible to small changes in its parameters, so GD with a large learning rate should only converge to minima with a small Lipschitz constant (such a bias is described in [26] ). It might also be possible to replace the Lipschitz constant in our generalization bounds, possibly along the lines of [43] .Second regularization: The second regularization term actually does not require an infinite width, only a sufficiently large one. Also its regularization term is equivalent to(∥W ℓ ∥ 2 + ∥V ℓ ∥ 2 + ∥b ℓ ∥ 2 )which is much closer to the traditional L 2 -regularization (and actually one could prove the same or very similar rates for L 2 -regularization). The issue is that it lead to rates that could be far from optimal depending on the ratios rℓ : it recovers the same rate as the first regularization term if no more than one ratio rℓ is smaller than 1 2 , but if many of these ratios are above 1 2 , it can be arbitrarily smaller.In Figure 2 , we compare the empirical rates (by doing a linear fit on a log-log plot of test error as a function of N ) and the predicted optimal rates min{ 1 2 , νg din , ν h d mid } and observe a pretty good match.Though surprisingly, it appears the the empirical rates tend to be slightly better than the theoretical ones.Remark. As can be seen in the proof of Theorem5, when the depth L is strictly larger than the true depth L * , one needs to add identity layers, leading to a so-called Bottleneck structure, which was proven to be optimal and observed empirically in [27, 26, 45] . These identity layers add a term that scales linearly in the additional depth(L-L * )d * min √ Nto the first regularization, and an exponential prefactor (2d * min ) L-L * to the second. It might be possible to remove these factors by leveraging the bottleneck structure, or simply by switching to ResNets. 
conclusion: 
 We have given a generalization bound for Accordion Networks and as an extension Fully-Connected networks. It depends on F 1 -norms and Lipschitz constants of its shallow subnetworks. This allows us to prove under certain assumptions that AccNets can learn general compositions of Sobolev functions efficiently, making them able to break the curse of dimensionality in certain settings, such as in the presence of unknown symmetries.The Appendix is structured as follows:1. In Section A, we describe the experimental setup and provide a few additional experiments.2. In Section B, we prove Theorems 1 and 2 from the main.3. In Section C, we prove Proposition 3 and Theorem 4. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: In the experimental setup section in the Appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: The numerical experiments are mostly there as a visualization of the theoretical results, our main goal is therefore clarity, which would be hurt by putting error bars everywhere.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? 
 
 Appendix: In Section D, we prove Theorem 5 and other approximation results concerning Sobolev functions.In Section E, we prove a few technical results on the covering number.A Experimental Setup 4In this section, we review our numerical experiments and their setup both on synthetic and real-world datasets in order to address theoretical results more clearly and intuitively.A This outlines the general procedure of our sampling method for synthetic data:1. Sample the training dataset X ∈ R D×din 2. From X, compute the D × D kernel K g with given ν g 3. From K g , sample Z ∈ R D×d mid with columns sampled from the Gaussian N (0, K g ).4. From Z, compute K g with given ν hFrom K h , sample the test dataset Y ∈ R D×dout with columns sampled from the Gaussian N (0, K h ).We utilized four AMD Opteron 6136 processors (2.4 GHz, 32 cores) and 128 GB of RAM to generate our synthetic dataset. The maximum possible dataset size for 128 GB of RAM is approximately 52,500; however, we opted for a synthetic dataset size of 22,000 due to the computational expense associated with sampling the Matérn kernel. This decision was made considering the time complexity of O(n 3 )and the space complexity of O(n 2 ) involved. Out of the 22,000 dataset points, 20,000 were allocated for training data, and 2,000 were used for the test datasetA.1.Proposition 8 (Proposition 3 from the main.). Given a distribution π with support in B(0, r), we have that with probability 1 -δ for all functionsf ∈ F = {f : ∥f ∥ W ν,2 ≤ R, ∥f ∥ ∞ ≤ R} L(f ) -LN (f ) ≤ 2C 1 REν /d (N ) + c 0 2 log 2 /δ N .whereE r (N ) = N -1 2 if r > 1 2 , E r (N ) = N -1 2 log N if r = 1 2 , and E r (N ) = N -r if r < 1 2 .Proof.(1) We know from Theorem 5.2 of [9] that the Sobolev ball B W ν,2 (0, R) over any d-dimensional hypercube Ω satisfies log N 2 (B W ν,2 (0, R), π, ϵ) ≤ C 0 R ϵ d νfor a constant c and any measure π supported in the hypercube.(2) By Dudley's theorem we can bound the Rademacher complexity of our function class B(X) evaluated on any training set X:R(B(X)) ≤ R2 -M + 6R √ N M k=1 2 -k C 0 R R2 -k d ν = R2 -M + 6R √ N C 0 M k=1 2 k( d 2ν -1).If 2ν = d, we take M = 1 2 log N and obtain the boundR √ N + 6R √ N C 0 1 2 log N ≤ C 1 R log N √ N .If 2ν > d, we take M = ∞ and obtain the bound6R √ N C 0 2 d 2ν -1 1 -2 d 2ν -1 ≤ C 1 R 1 √ N .If 2ν < d, we take M = ν d log N and obtain the boundR2 -M + 6R √ N C 0 2 d 2ν -1 2 M ( d 2ν -1) -1 2 d 2ν -1 -1 ≤ C 1 RN -ν d .Putting it all together, we obtain that R(B(X)) ≤ C 1 Eν /d (N ).(3) For any ρ-Lipschitz loss function ℓ(x, f (x)) with |ℓ(x, y)| ≤ c 0 , we know that with probability 1 -δ over the sampling of the training set X from the distribution π, we have for all f ∈ FE x∼π [ℓ(x, f (x))] - 1 N N i=1 ℓ(x i , f (x i )) ≤ 2E X ′ [R(ℓ • F(X ′ ))] + c 0 2 log 2 /δ N ≤ 2C 1 Eν /d (N ) + c 0 2 log 2 /δ N .Proposition 9. Let F 1 , . . . , F L be set of functions mapping through the sets Ω 0 , . . . , Ω L , then if all functions in F ℓ are ρ ℓ -Lipschitz, we havelog N 2 (F L • • • • • F 1 , L ℓ=1 ρ L:ℓ+1 ϵ ℓ ) ≤ L ℓ=1 log N 2 (F ℓ , ϵ ℓ ).Proof. For any distribution π 0 on Ω there is a ϵ 1 -covering F1 of F 1 with F1 ≤ N 2 (F 1 , ϵ 1 ) then for any f1 ∈ F1 we choose a ϵ 2 -covering F2 w.r.t. the measure π 1 which is the measure of f 1 (x) ifx ∼ π 0 of F 2 with F2 ≤ N 2 (F 2 , ϵ), and so on until we obtain coverings for all ℓ. Then the setF = fL • • • • • f1 : f1 ∈ F1 , . . . , fL ∈ FL is a L ℓ=1 ρ L:ℓ+1 ϵ ℓ -covering of F = F L • • • • • F 1 ,indeed for any f = f L:1 we choose f1 ∈ F1 , . . . , fL ∈ FL that cover f 1 , . . . , f L , then fL:1 covers f L:1 :f L:1 -fL:1 π ≤ L ℓ=1 f L:ℓ • fℓ-1:1 -f L:ℓ+1 • fℓ:1 π ≤ L ℓ=1 f L:ℓ -f L:ℓ+1 • fℓ π ℓ-1 ≤ L ℓ=1 ρ L:ℓ+1 ϵ ℓ ,and log cardinality of the set F is boundedL ℓ=1 log N 2 (F ℓ , ϵ ℓ ). Theorem 10. Let F = F L • • • • • F 1 where F ℓ = f ℓ : R d ℓ-1 → R d ℓ s.t. ∥f ℓ ∥ W ν ℓ ,2 ≤ R ℓ , ∥f ℓ ∥ ∞ ≤ b ℓ , Lip(f ℓ ) ≤ ρ ℓ , and let r * = min ℓ r ℓ for r ℓ = ν ℓ d ℓ-1 , then with probability 1 -δ we have for all f ∈ F L(f ) -LN (f ) ≤ ρC 0 L ℓ=1 (C ℓ ρ L:ℓ+1 R ℓ ) 1 r * +1 r * +1 E r * (N ) + c 0 2 log 2 /δ N ,where C ℓ depends only ond ℓ-1 , d ℓ , ν ℓ , b ℓ-1 .Proof.(1) We know from Theorem 5.2 of [9] that the Sobolev ballB W ν ℓ ,2 (0, R ℓ ) over any d ℓ - dimensional hypercube Ω satisfies log N 2 (B W ν,2 (0, R ℓ ), π ℓ-1 , ϵ ℓ ) ≤ C ℓ R ℓ ϵ ℓ 1 r ℓfor a constant C ℓ that depends on the size of hypercube and the dimension d ℓ and the regularity ν ℓ and any measure π ℓ-1 supported in the hypercube.Thus Proposition 9 tells us that the composition of the Sobolev balls satisfieslog N 2 (F L • • • • • F 1 , L ℓ=1 ρ L:ℓ+1 ϵ ℓ ) ≤ L ℓ=1 C ℓ R ℓ ϵ ℓ 1 r ℓ.Given r * = min ℓ r ℓ , we can bound it byL ℓ=1 C ℓ R ℓ ϵ ℓ 1 r *and by then choosingϵ ℓ = ρ -1 L:ℓ+1 (ρ L:ℓ+1 C ℓ R ℓ ) 1 r * +1 ℓ (ρ L:ℓ+1 C ℓ R ℓ ) 1 r * +1 ϵ, we obtain that log N 2 (F L • • • • • F 1 , ϵ) ≤ L ℓ=1 (ρ L:ℓ+1 C ℓ R ℓ ) 1 r * +1 r * +1 ϵ -1 r * .(2,3) It the follows by a similar argument as in points (2, 3) of the proof of Proposition 8 that there isa constant C 0 such that with probability 1 -δ for all f ∈ F L(f ) -LN (f ) ≤ C 0 L ℓ=1 (ρ L:ℓ+1 C ℓ R ℓ ) 1 r * +1 r * +1 E r * (N ) + c 0 2 log 2 /δ NIn this section, we first give the proof of Theorem 5 and then present detailed proofs of lemmas used in the proof. The lemmas are largely inspired by [5] and may be of independent interest. • At a global minimizer fL:1 of the regularized loss f 1 , . . . , f L → LN (f L:1 )+λR(f 1 , . . . , f L ),we have L( fL:1 ) = Õ(N -min{ 1 2 ,r1,...,r L * } ).• At a global minimizer fL:1 of the regularized lossf 1 , . . . , f L → LN (f L:1 )+λ L ℓ=1 ∥f ℓ ∥ F1 , we have L( fL:1 ) = Õ(N -1 2 + L * ℓ=1 max{0,r ℓ -1 2 } ). Proof. If f * = f * L * • • • • • f * 1 with L * ≤ L, intermediate dimensions d * 0 , . . . , d * L * , along with a continuous input distribution π 0 supported in B(0, b 0 ), such that the distributions π ℓ of f * ℓ (x) (for x ∼ π 0 ) are continuous too and supported inside B(0, b ℓ ) ⊂ R d * ℓ .Further assume that there aredifferentiabilities ν * ℓ and radii R ℓ such that ∥f * ℓ ∥ W ν * ℓ ,2 (B(0,b ℓ )) ≤ R ℓ .We first focus on the L = L * case and then extend to the L > L * case.Each f * ℓ can be approximated by another function fℓ with bounded F 1 -norm and Lipschitz constant. Lemma 14, and byActually if 2ν * ℓ ≥ d * ℓ-1 + 3 one can choose fℓ = f * ℓ since ∥f * ℓ ∥ F1 ≤ C ℓ R ℓ byassumption Lip( fℓ ) ≤ ρ ℓ . If 2ν * ℓ < d * ℓ-1 + 3, then by Lemma 13 we know that there is a fℓ withfℓ F1 ≤ C ℓ R ℓ ϵ -1 2r ℓ +1 ℓ and Lip( fℓ ) ≤ C ℓ Lip(f * ℓ ) ≤ C ℓ ρ ℓ and error f * ℓ -fℓ L2(π ℓ-1 ) ≤ c ℓ f * -fℓ L2(B(0,b ℓ )) ≤ c ℓ ϵ ℓ .Therefore the composition fL:1 satisfiesf * L:1 -fL:1 L2(π ℓ-1 ) ≤ L ℓ=1 fL:ℓ+1 • f * ℓ:1 -fL:ℓ • f * ℓ-1:1 L2(π) ≤ L ℓ=1 Lip( fL:ℓ+1 )c ℓ ϵ ℓ ≤ L ℓ=1 ρ L:ℓ+1 C L:ℓ+1 c ℓ ϵ ℓ .For any L ≥ L * , dimensions d ℓ ≥ d * ℓ and widths w ℓ ≥ N , we can build an AccNet that fits eactly ρ L ℓ=1 ρ L:ℓ+1 C L:ℓ+1 c ℓ ϵ ℓ + B 2 log 2 /δ N + λ √ 2d L * ℓ=1 C ℓ ρ ℓ L * ℓ=1 1 C ℓ ρ ℓ C ℓ R ℓ 2ν * ℓ ≥ d * ℓ-1 + 3 C ℓ R ℓ ϵ -1 2r ℓ +1 ℓ 2ν * ℓ < d * ℓ-1 + 3 + 2(L -L * ) min{d * 0 , . . . , d * L * } .Taking ϵ ℓ = E rmin (N ) and λ = N -1 2 log N , this is upper bounded byρ L ℓ=1 ρ L:ℓ+1 C L:ℓ+1 c ℓ + C √ 2dr L * ℓ=1 C ℓ ρ ℓ L * ℓ=1 R ℓ ρ ℓ + 2(L -L * ) min{d * 0 , . . . , d * L * } E rmin (N )+B 2 log 2 /δ N .which implies that at the globla minimizer of the regularized loss, the (unregularized) train loss is of order E rmin (N ) and the complexity measure R( f1 , . . . , fL ) is of order 1 N E rmin (N ) which implies that the test error will be of order EQUATIONL * ℓ=1 C ℓ R ℓ 2ν * ℓ ≥ d * ℓ-1 + 3 C ℓ R ℓ ϵ -1 2r ℓ +1 ℓ 2ν * ℓ < d * ℓ-1 + 3 (2 min{d * 0 , . . . , d * L * }) (L-L * ) .Which for ϵ ℓ = E rmin (N ) and λ = N -1 N is upper bounded byρ L ℓ=1 ρ L:ℓ+1 C L:ℓ+1 c ℓ E rmin (N )+B 2 log 2 /δ N +N -1 2 L * ℓ=1 C ℓ R ℓ √ N E rmin (N ) (2 min{d * 0 , . . . , d * L * }) (L-L * ) .Which implies that both the train error is of orderN -1 2 L * ℓ=1√ N E rmin (N ) and the product of the F 1 -norms is of orderL * ℓ=1 √ N E rmin (N ).Now note that the product of the F 1 -norms bounds the complexity measure up to a constant sinceLip(f ) ≤ ∥f ∥ F1 R(f 1 , . . . , f L ) = r L ℓ=1 Lip(f ℓ ) L ℓ=1 ∥f ℓ ∥ F1 Lip(f ℓ ) d ℓ-1 + d ℓ ≤ L √ 2d L ℓ=1 ∥f ∥ F1 .And since at the global minimum the product of the F 1 -norms is of orderL * ℓ=1√ N E rmin (N ) the test error will of orderL * ℓ=1 √ N E rℓ (N ) log N √ N .Note that if there is at a most one ℓ where rℓ > 1 2 then the rate is up to log term the same as E rmin (N ).Now we present the lemmas used in this proof above that concern the approximation errors and Lipschitz constants of Sobolev functions and compositions of them. We will bound the F 2 -norm and note that the F 2 -norm is larger than the F 1 -norm, cf. [ ∥ĝ∥ F2 ≤ C ′′ (d, ν, R)ϵ -d+3-2ν 2ν .Proof. Given our assumptions on the target function g, we may decompose g(x) = ∞ k=0 g k (x)along the basis of spherical harmonics with g 0 (x) = S d g(y)dτ d (y) being the mean of g(x) over the uniform distribution τ d over S d . The k-th component can be written asg k (x) = N (d, k) S d g(y)P k (x T y)dτ d (y) with N (d, k) = 2k+d-1 k k+d-2 d-1and a Gegenbauer polynomial of degree k and dimension d + 1:P k (t) = (-1/2) k Γ(d/2) Γ(k + d/2) (1 -t 2 ) (2-d)/2 d k dt k (1 -t 2 ) k+(d-2)/2 ,known as Rodrigues' formula. Given the assumption that the Sobolev norm ∥g∥ 2 W ν,2 is upper bounded, we have ∥f ∥ 2 L2(S d ) ≤ C 0 (d, ν)R for f = ∆ ν/2 g where ∆ is the Laplacian on S d [18, 5] .Note that g k are eigenfunctions of the Laplacian with eigenvalues k(k + d -1) [4] , thusEQUATIONwhere the last inequality holds because ∥f ∥ 2 L2(S d ) = k≥0 ∥f k ∥ 2 L2(S d ) converges. Note using the Hecke-Funk formula, we can also write g k as scaled p k for the underlying density p of the F 1 and F 2 -norms:g k (x) = λ k p k (x)where λ k = ω d-1 ω d 1 -1 σ(t)P k (t)(1 -t 2 ) (d-2)/2 dt = Ω(k -(d+3)/2 ) [5, Appendix D.∥g∥ 2 F2 = S d |p| 2 dτ (v) = ∥p∥ 2 L2(S d ) = 0≤k ∥p k ∥ 2 L2(S d ) = 0≤k λ -2 k ∥g k ∥ 2 L2(S d ) .Now to approximate g, consider function ĝ defined by truncating the "high frequencies" of g, i.e.setting ĝk = 1[k ≤ m]g k for some m > 0 we specify later. Then we can bound the norm with∥ĝ∥ 2 F2 = 0≤k:λ k ̸ =0 λ -2 k ∥ĝ k ∥ 2 L2(S d ) = 0≤k≤m λ k ̸ =0 λ -2 k ∥g k ∥ 2 L2(S d ) (a) ≤ C 2 (d, ν, R) 0≤k≤m k d+2-2ν (b) ≤ C 3 (d, ν, R)m d+3-2νwhere (a) uses Eq 1 and λ k = Ω(k -(d+3)/2 ); (b) approximates by integral.To bound the approximation error,∥g -ĝ∥ 2 L2(S d ) = k>m g k 2 L2(S d ) ≤ k>m ∥g k ∥ 2 L2(S d ) ≤ C 4 (d, ν, R) k>m k -2ν-1 ≤ C 5 (d, ν, R)m -2ν by integral approximation.Finally, choosing m = ϵ -1 ν , we obtain ∥g -ĝ∥ L2(S d ) ≤ C(d, ν, R)ϵ and∥ĝ∥ F2 ≤ C ′ (d, ν, R)ϵ -d+3-2ν 2ν .Then it remains to bound Lip(ĝ) for our constructed approximation. By construction and by [13, Theorem 2.1.3], we have ĝ = g * h with nowh(t) = m k=0 h k P k (t), t ∈ [-1, 1]by orthogonality of the Gegenbauer polynomial P k 's and the convolution is defined as(g * h)(x) := 1 ω d S d g(y)h(⟨x, y⟩)dy.The coefficients for 0 ≤ k ≤ m given by [13, Theorem 2.1.3] areh k (a) = ω d+1 ω d Γ(d -1) Γ(d -1 + k) P k (1) k!(k + (d -1)/2)Γ((d -1)/2) 2 π2 2-d Γ(d -1 + k) (b) = O k Γ(d -1 + k)where (a) follows from the (inverse of) weighted L 2 norm of P k ; (b) plugs in the unit constantP k (1) = Γ(k+d-1)Γ(d-1)k! and suppresses the dependence on d. Note that the constant factor Γ(d-1)Γ(d-1+k)comes from the difference in the definitions of the Gegenbauer polynomials here and in [13] . by Cauchy-SchwartzEQUATION-1 h k h j P k (t)P j (t)(1 -t 2 ) d-2 2 dt   1/2by [13, Eq A. 5 .1]= √ ω d Lip(g) m k=0 h 2 k 1 -1 P k (t) 2 (1 -t 2 ) d-2 2 dt 1/2by orthogonality of P k 's w.r.t. this measure= √ ω d Lip(g) m k=0 h 2 k π2 2-d Γ(d -1 + k) k!(k + (d -1)/2)Γ((d -1)/2) 2 1/2 = √ ω d Lip(g) O(1) + m k=1 O k Γ(d -1 + k)k! 1/2 = √ ω d Lip(g)C(d)for some constant C(d) that only depends on d. Hence Lip(ĝ) = C ′ (d)Lip(g).The next lemma adapts Lemma 12 to inputs on balls instead of spheres following the construction in In particular, W ν,2 ⊆ F 2 for ν ≥ (d + 3)/2 even.EQUATIONEQUATIONProof. This lemma reproduces [5, Proposition 5] to functions with bounded Sobolev L 2 norm instead of L ∞ norm. The proof follows that of Lemma 12 and Lemma 13 and noticing that by Eq 1,∥g∥ 2 F2 = 0≤k:λ k ̸ =0 λ -2 k ∥g k ∥ 2 L2(S d ) ≤ 0≤k k d+3-2ν ∥(∆ ν/2 g) k ∥ 2 L2(S d ) ≤ ∥∆ ν/2 g∥ 2 L2(S d ) ≤ C 1 (d, ν)∥g∥ 2 W ν,2 ≤ C 1 (d, ν)R.Finally, we remark that the above lemmas extend straightforward to functions f :B(0, b) → R d ′with multi-dimensional outputs, where the constants then depend on the output dimension d ′ too.With the lemmas given above and the fact that the F 2 -norm upper bounds the F 1 -norm, we can find infinite-width DNN approximations for compositions of Sobolev functions, which is also pointed out in the proof of Theorem 5.Lemma 15. Assume the target function f : Ω → R dout , with Ω ⊆ B(0, b) ⊆ R din , satisfies:• f = g k • • • • • g 1 a composition of k Sobolev functions g i : R di → R di+1 with bounded norms ∥g i ∥ 2 W ν i ,2 ≤ R for i = 1, . . . , k, with d 1 = d in ; • f is Lipschitz, i.e. Lip(g i ) < ∞ for i = 1, . . . , k.If ν i ≤ (d i + 2)/2 for any i, i.e. less smooth than needed, for depth L ≥ k and any ϵ > 0, there is an infinite-width DNN f such that Proof. Note that by Lipschitzness,• Lip( f ) ≤ C 1 k i=1 Lip(g i ); • ∥ f -f ∥ L2 ≤ C 2 ϵ;(g i • • • • • g 1 )(Ω) ⊆ B   0, b i j=1 Lip(g j )   ,i.e. the pre-image of each component lies in a ball. By Lemma 12, for each g i , ifν i ≤ (d i + 2)/2,we have an approximation ĝi on a slightly larger ball b′ i = b i-1 j=1 C ′′ (d j , d j+1 )Lip(g j ) such that • ∥g i -ĝi ∥ L2 ≤ C(d i , d i+1 , ν i , b ′ i , R)ϵ; • ∥ĝ i ∥ F2 ≤ C ′ (d i , d i+1 , ν i , b ′ i , R)ϵ d i +3-2ν i 2ν i ; • Lip(ĝ i ) ≤ C ′′ (d i , d i+1 )Lip(g i );where d i is the input dimension of g i . Write the constants as C i , C ′ i , and C ′′ i for notation simplicity.Note that the Lipschitzness of the approximations ĝi 's guarantees that, when they are composed,(ĝ i-1 • • • • • ĝ1 )(Ω) lies in a ball of radius b ′ i = b i-1j=1 C ′′ j Lip(g j ), hence the approximation error remains bounded while propagating. While each ĝi is a (infinite-width) layer, for the other L -k layers, we may have identity layers 5 .Let f be the composed DNN of these layers. Then we haveLip( f ) ≤ k i=1 C ′′ i Lip(g i ) = C ′′ (d 1 , . . . , d k , d out ) k i=1Lip(g i )and approximation error∥ f -f ∥ L2 ≤ k i=1 C i ϵ j>i C ′′ j Lip(g j ) = O(ϵ)where the last equality suppresses the dependence on d i , d out , ν i , b, R, k, and Lip(g i ) for i = 1, . . . , k.In particular, by Lemma 14, if ν i ≥ (d i + 3)/2 for any i = 1, . . . , k, we can take ĝi = g i . If this holds for all i, then we can have f = f while each layer has a F 2 -norm bounded by O(R).Here we show a 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 2 of [17] :Theorem 16. The d-dimensional ellipsoid E = {x : x T K -1 x ≤ 1} with radii √ λ i for λ i the i-th eigenvalue of K satisfies log N 2 (E, ϵ) = M ϵ (1 + o(1)) for M ϵ = i: √ λi≥ϵ log √ λ i ϵ if one has log √ λ1 ϵ = o M 2 ϵ kϵ log d for k ϵ = i : √ λ i ≥ ϵFor our purpose, we will want to cover a unit ball B = {w : ∥w∥ ≤ 1} w.r.t. to a non-isotropic norm Furthermore, log N (B, ∥•∥ K , ϵ) ≤ TrK 2ϵ 2 (1 + o(1)) as long as log d = o √ TrK ϵ log √ TrK ϵ -1 . Proof. If Ẽ is an ϵ-covering of E w.r.t. to the L 2 -norm, then B = K -1 2 Ẽ is an ϵ-covering of B w.r.t. the norm ∥•∥ K , because if w ∈ B, then √ Kw ∈ E and so there is an x ∈ Ẽ such that x - √ Kw ≤ ϵ, but then w = √ K -1 x covers w since ∥ w -w∥ K = x - √ Kw K ≤ ϵ.Since λ i ≤ TrK i , we have K ≤ K for K the matrix obtained by replacing the i-th eigenvalue λ i of K by TrK i , and therefore N (B, ∥•∥ K , ϵ) ≤ N (B, ∥•∥ K , ϵ) since ∥•∥ K ≤ ∥•∥ K . We now have the a[proximation log N (B, ∥•∥ K , ϵ) = Mϵ (1 + o(1)) for Mϵ = kϵ i=1 log √ TrK √ iϵ kϵ = TrK ϵ 2 .We now have the simplificationMϵ = kϵ i=1 log √ TrK √ iϵ = 1 2 kϵ i=1 log kϵ i = kϵ 2 ( 1 0 log 1 x dx + o(1)) = kϵ 2 (1 + o(1))where the o(1) term vanishes as ϵ ↘ 0. Furthermore, this allows us to check that as long aslog d = o √ TrK 4ϵ log √ TrK ϵ , the condition is satisfied log √ TrK ϵ = o kϵ 4 log d = o M 2 ϵ kϵ log d .Second we prove how to obtain the covering number of the convex hull of a function set F:Theorem 18. Let F be a set of B-uniformly bounded functions, then for allϵ K = B2 -K log N 2 (ConvF, 2ϵ K ) ≤ √ 18 K k=1 2 K-k log N 2 (F, B2 -k ).Proof. Define ϵ k = B2 -k and the corresponding ϵ k -coverings Fk (w.r.t. some measure π). For any f , we write fk [f ] for the function fk [f ] ∈ Fk that covers f . Then for any functions f in ConvF, we havef = m i=1 β i f i = m i=1 β i f i -fK [f i ] + K k=1 m i=1 β i fk [f i ] -fk-1 [f i ] + f0 [f i ].We may assume that f0 [f i ] = 0 since the zero function ϵ 0 -covers the whole F since ϵ 0 = B.We will now use the probabilistic method to show that the sums Thus if we take m k = 1 a k ( 3ϵ k ϵ K ) 2 with a k = 1 we know that there must exist a choice of g(k) j s such β i f i -fK [f i ] Lp(π) + K k=1 1 m k m k j=1 g(k) j - m i=1 β i fk [f i ] -fk-1 [f i ] Lp(π) ≤ 2ϵ K . Since C = K k=1 Fk m k Fk-1 m k , we have log N p (C, 2ϵ K ) ≤ K k=1 1 a k ( 3ϵ k ϵ K ) 2 (log N p (F, ϵ k ) + log N p (F, ϵ k-1 )) ≤ 18 K k=1 1 a k 2 2(K-k) log N 2 (F, ϵ k ).This is minimized for the choice Justification: The contribution section accurately describes our contributions, and all theorems are proven in the appendix.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.This construction can be used for any convex set B that is symmetric around zero (B = -B) to define a norm whose unit ball is B. This correspondence between symmetric convex sets and norms is well known.One 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 a very similar model: this would be equivalent to a AccNet where only the W ℓ weights are learned, while the V ℓ , b ℓ weights remain constant. Another family of models that should have similar properties is Deep Gaussian Processes[15].Note that the unregularized loss can be optimized polynomially, e.g. in the NTK regime[28,3,16], but this is an easier task than findinig the global minimum of the regularized loss where one needs to both fit the data, and do it with an minimal regularization term.Since the domain is always bounded here, one can let the bias translate the domain to the first quadrant and let the weight be the identity matrix, cf. the construction in[45, Proposition B.1.3]. 


Decision: This paper includes a non-anonymous link to their code on Github in footnote 4 on page 13 (in the appendix). This violates the double-blind reviewing policy. Hence this paper is rejected.

Reviews: review: paper_summary: paper_summary: The authors introduce accordion networks (AccNets), which are compositions of multiple shallow networks. By leveraging prior workthat computes norm-based generalization bounds for shallow two-layer networks, the authors bound the complexity of a deep AccNet (as measured by its F1 norm) but the sum of the complexities of the individual shallow networks. They empirically observe that the rates predicted on real-world data are roughly representative of the trained networks, and are indeed much better than those for kernels trained on the same tasks. They put forth a nontrivial scaling law for the excess risk: $N^{-\mathrm{min}(1/2, \nu_g/d_{in}, \nu_h/d_{mid})}$ for an Acc Net compared to $\mathcal L \sim N^{-\mathrm{min}(1/2, \nu_g/d_{in}, \nu_h/d_{in})}$ for a kernel in terms of the dimensionalities $d$ and Sobolev constants $\nu$ of the respective spaces and functions. From this, the authors obtain predictions of several phases, that they put forth experiments to verify.
strength_weakness: strength_weakness: I am not sure how compelling the phase plots in Figure 2 are. The bounds in general are extremely loose, however the comparison of the rates in Figure 2c and Figure 3 is very promising. In general, however, it is the experience of the reviewer that measuring a rate is an extremely finicky business. It is therefore important to add a section in the appendix explicitly stating how the rates were obtained and measured. I also strongly encourage the authors to make the code for all figures public. 

Because they are used very early on throughout the paper, it is the opinion of the reviewer that the notions of F1 distance and Sobolev norm should be defined earlier on in the paper. Without this, it seems like the audience will be constrained to the set of learning theorists familiar with these terms. However, if these terms are defined early on, the paper becomes remarkably accessible to a much broader audience.
questions: questions: The plot labels in Figures 2 and 3 are very difficult to read. 

A small comment: I have not seen the term "modulo space" used before. Often the term is "quotient space" 

The sentence defining the $F_1$ ball (above theorem 1) is confusing, circular, and difficult to read. Please rewrite it.

The excess rate formula $\mathcal L \sim N^{-\mathrm{min}(1/2, \nu_g/d_{in}, \nu_h/d_{mid})}$ is a very important result and I recommend that it be formatted for display, not inline.

How are you measuring "dimension" in 4.1.1? A high-dimensional gaussian with spectral decay of its covariance going as $k^{-\alpha}$ for capacity exponent $\alpha$ is nominally "full dimensional" since it is not strictly speaking constrained to a sub-manifold, and yet basic results in kernel theory and high-dimensional linear regression can show that the generalization error achieves a much better rate at larger values of $\alpha$. Specifically, a model with capacity exponent $\alpha$ and source exponent $r$ achieves a rate of $N^{-2\alpha min(r, 1)}$. See, e.g. https://arxiv.org/abs/2105.15004 .  Such power law anisotropy is in abundant in natural data. In particular shallow two layer networks in the lazy limit can achieve this scaling for such 'easy tasks' with quick spectral decay. On the other hand, the bounds that you state cannot decay faster than $N^{-1/2}$. 
* In this sense, it seems that the bounds (shallow or deep) presented are certainly not tight for some datasets. Am I incorrect in concluding this? Do you have an intuition for what causes the breakdown in correctly predicting the error rates in this case?
* Given that they breakdown in that setting, what about the datasets that you study makes it so that the scaling law predictions seem to hold?
limitations: limitations: Given the theoretical nature of this work, it is unlikely to have major social implications.
paper_summary: paper_summary: The authors present a generalization bound for deep neural networks that describes how depth enables models to learn functions that are compositions of Sobolev functions. To do this, they both prove a generalization bound for compositions of accordion networks (densely connected networks with a low-rank weight structure) and for compositions of Sobolev functions. They then present a sample efficiency result for different kinds of regularization on accordion networks.
strength_weakness: strength_weakness: 1. I would like to see a more thorough comparison with shallow networks and generalization bounds, as this comparison is a central argument for the usefulness of the presented theory. While it is clear how the findings for the shallow network are a special case of the findings on the deep networks (as presented in Thm. 1), it remains a bit unclear to me how the theory can explain improved generalization in deep compared to shallow networks. The authors certainly present different several pieces of evidence on this: both Fig. 1 and Fig. 3 demonstrate that shallow networks exhibit worse scaling. I also appreciated the theoretical explanation of a particular contrast in l. 256-261. However, I think it would be really useful to provide a general theoretical explanation for this difference and test it empirically: would it be possible to extend the theoretical comparison in l. 256-261 to the general experimental setup studied in the figures --- and if so, would this theoretical comparison predict the conditions under which deep networks have the strongest advantages over shallow networks (or perhaps the conditions under which they don't perform that much better)? Not only would this serve as a useful validation of the theory, I think it would also provide a more extensive intuition for the authors' findings.

2. I appreciated the fact that the authors compare their findings with related work wherever this becomes relevant. However, I think a (potentially brief) section comparing the results here to other theoretical investigations of depth in deep networks (perhaps using different approaches) would be useful. 

3. The linked codebase does not contain the notebooks indicated in the README as far as I can tell and therefore currently can't be used to directly reproduce the findings.

4. I believe the figures would still benefit from error bars or some other indication of the overall statistical error in the findings. I agree that the main contribution of this paper is theoretical, but since the experiments test the empirical validity of the theory, I believe it is nevertheless important to get a sense for the overall deviation in these findings (e.g. across model seeds). If the authors are concerned about a lack of clarity, they could leave the bars out of the main figures but add supplementary figures with error bars. Moreover, some of the lines in Fig. 1 do contain error bars and it would be good to clarify what these error bars represent.
questions: questions: 1. Do you think my suggestion in point 1 of the weaknesses make sense or do you have a reason why you see it as unnecessary?

2. As far as I understand, the reason for the asymmetry between $\nu_g$ and $\nu_h$ in Fig. 2 is the different dimensionality, correct? It would be good to mention these dimensionalities, as I was only able to find them in the appendix.

3. Could you clarify why in Fig. 2, you're using the scalings from Prop 3 rather than from Thm. 5?
limitations: limitations: The authors adequately discuss the limitations of this work.
paper_summary: paper_summary: This paper introduces Accordion Networks (AccNets), a novel neural network structure composed of multiple shallow networks. The authors propose a generalization bound for AccNets that leverages the F1-norms and Lipschitz constants of the subnetworks, demonstrating that these networks can break the curse of dimensionality by efficiently learning compositions of Sobolev functions. The paper also provides theoretical insights and empirical validation, showcasing the superior performance of AccNets in learning complex compositional tasks compared to shallow networks and kernel methods.
strength_weakness: strength_weakness: 1. The practical implementation of the proposed regularization methods might be challenging, particularly the first one requiring infinite width. 

2. The paper mentions the difficulty in optimizing Lipschitz constants, which could be a limitation in practical applications.

3.  Additional experiments on more diverse real-world datasets could further demonstrate the robustness and generalizability of AccNets.

4. Although the author has discussed the differences between DNN and AccNet, there is still not enough information for me to be sure in which settings to use AccNet and in which settings to use DNN. More clear differences and applicable conditions, especially the shortcomings of each need to be pointed out.
questions: questions: Can the authors provide more details on the computational complexity of training Accordion Networks compared to traditional DNNs?

How sensitive are the generalization bounds to the choice of hyperparameters, particularly the Lipschitz constants and F1-norms?

Are there any specific types of tasks or datasets where Accordion Networks might not perform as well as traditional methods?
limitations: limitations: See weaknesses.

Comments: title: To Authors and Reviewers
comment: We apologize for this mistake. But the reviews are not wasted, they are very useful to us to improve our future submission.
Dear Authors and Reviewers,

Thanks for submitting or reviewing this paper.

Unfortunately, this paper includes a non-anonymous link to their code on Github in footnote 4 on page 13 (in the appendix). This violates the double-blind reviewing policy. Hence this paper will be rejected.

On 13 Jul, reviewers were told that: "It's up to you to decide whether to keep your comments and participate in the rebuttal phase (this does not affect the fact that this paper will be rejected). I suggest keeping the comments as they are still contributing to the authors and the community at large."

I appreciate the reviewers for keeping their comments and I suggest the authors can respond to the questions raised by the reviewers. 

Hope all of us can learn something from the discussion.