On the non-universality of deep learning: quantifying the cost of symmetry
Authors: Emmanuel Abbe
Enric Boix-Adserà
Venue: NeurIPS 2022 Accept (2022)

Abstract: We prove limitations on what neural networks trained by noisy gradient descent (GD) can efficiently learn. Our results apply whenever GD training is equivariant, which holds for many standard architectures and initializations. As applications, (i) we characterize the functions that fully-connected networks can weak-learn on the binary hypercube and unit sphere, demonstrating that depth-2 is as powerful as any other depth for this task; (ii) we extend the merged-staircase necessity result for learning with latent low-dimensional structure [ABM22] to beyond the mean-field regime. Under cryptographic assumptions, we also show hardness results for learning with fully-connected networks trained by stochastic gradient descent (SGD).

On the non-universality of deep learning: quantifying the cost of symmetry
Emmanuel Abbe
Enric Boix-Adserå MIT
EPFL
Abstract
We prove limitations on what neural networks trained by noisy gradient descent (GD) can efficiently learn. Our results apply whenever GD training is equivariant, which holds for many standard architectures and initializations. As applications, (i) we characterize the functions that fully-connected networks can weak-learn on the binary hypercube and unit sphere, demonstrating that depth-2 is as powerful any other depth for this task; (ii) we extend the merged-staircas necessity result for learning with latent ciwddimeniional structure [ABM22] to beyond the mean- field regime. Under cryptographic assumptions, we also show hardness results for learning with fully-connected networks trained by stochastic gradient descent (SGD).
1 Introduction
Over the last decade, deep learning has made advances in areas as diverse as image classifica- tion [KSH12], language translation [BCB14], classical board games [SHS+18] and programming [LCC+22], 22]. Neural networks trained with gradient- bbased optimizers have surpassed classical methods for these tasks, raising the question:
we hope for deep learning methods to eventually replace all other learning algorithms? other words, deep learning a universal learning paradigm? Recently, [AS20, AKM*211 proved that in certain sense the answer is yes: any PAC-learning algorithm [Val84] can be efficiently implemented as neural network trained by stochastic gradient descent; analogously, any Statistical Query algorithm [Kea98] can be efficiently implemented neural network trained by noisy gradient descent.
However, there is catch: the result of [AS20] relies carefully crafted network architecture with memory and computation modules, which capable of emulating an arbitrary learning algorithm. This is far from the architectures which have been shown to be successful in practice. Neural networks practice do incorporate domain knowledge, but they have more "regularity" than the architectures of [AS20], in the sense that they do not rely on heterogeneous and carefully assigned initial weights (e.g., convolutional networks and transformers for image recognition and language processing 9LB++95 LKF10, VSP+ graph neural networks for analyzing graph data [GMS05, BZSL13, VCC-17) and networks specialized for particle physics BBAO+20), We therefore refine question:
Is deep learning with "regular" architectures and initializations universal learning paradigm? If not, can we quantify its limitations when architectures and data are not well aligned?
We would like an answer applicable to a wide range of architectures. In order to formalize the problem and develop general theory, take approach similar to [Ng04, Sha18, LZA21] of understanding deep learning through the equivariance group G (a.k..,, symmetry group) of the learning algorithm.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Definition 1.1 (G-equivariant algorithm), A randomized algorithm A that takes in a data distribution D E P(X y) and outputs a function A(D) X + + is said to be G Gequiivariant for all g E G
A(D) A(g(D)) - g.
(G-equivariance)
Here g is group element that acts on the data space X, and so is viewed as a function g : X' + X, and ((D) is the distribution of (g(x), y), where (ær, u) ~ D.
In the case that the algorithm A is deep learning on the distribution D, the equivariance group depends on the optimizer, the architecture, and the network initialization [Ng04, LZA21J.2
Examples of G-equivariant algorithms in deep learning In many deep learning settings, the equivariance group of the learning algorithm is large. Thus, in this paper, we call an algorithm "regular" if it has a large equivariance group. For example, SGD training of fully-connected networks with Gaussian initialization is orthogonally -equivvl--iiv [Ng04]; and is permuiation-equivarraan if we add skip connections [HZRS16]. SGD training of convolutional networks circular convolutions are used [SNPP19], and SGD training of i.i.d. iidd-inntializzed transformers without positional embeddings is equivariant to permutations of tokens [VSP+17] 17J. Furthermore, [LZA21, Theorem C.1] provides general conditions under which deep learning algorithm is equivariant. See also the preliminaries in Section 2.
Summary of this work Based off of G-equivariance, we prove limitations on what "regular" neural networks trained by noisy gradient descent (GD) or stochastic gradient descent (SGD) can efficiently leam, implying separation with the initializations and architectures considered in [AS20]. For GD, we prove a master theorem that enables two novel applications: (a) characterizing which functions can be efficiently weak-learned by fully-connected (FC) networks on both the hypercube and the unit sphere; and (b) a necessity result for which functions on the hypercube with latent low-dimensional structure can be efficiently learned. See Sections 1.2 and 1.3 for more details.
1.1 Related work
Most prior work on computational lower bounds for deep learning has focused on proving limitations of kernel methods (a.k.a. linear methods). Starting with [Bar93] and more recently with [WLLM19, AL19, KMS20, AL20, Hsu, HSSV21, ABM22] it is known that there are problems on which kernel methods provably fail. These results apply to training neural networks in the Neural Tangent Kernel (NTK) regime [JGH18]. but do not apply to more general nonlinear training. Furthermore, for specific architectures such FC architectures [GMMM21, Mis22] and convolutional architectures [MM21], }, the kernel and random features models at initialization are well understood, yielding stronger lower bounds for training in the NTK regime.
For nonlinear training, which is the setting of this paper, considerably less known. In the context of sample complexity, [Ng04] introduced the study of the equivariance group of SGD, and constructed a distribution on dimensions with a Mdd) versus (11) sample complexity separation for learning with an SGD-traince FC architecture versus arbitrary algorithm. More recently, [LZA21] built on [Ng04] to show a O(1) versus ((d²) complcxtyy separation between SGD-trained convo- lutional and FC architectures. In this paper, we also analyze the equivariance group of the training algorithm, but with the goal of proving superpolynomial computational lower bounds.
In the context of computational lower bounds, it is known that networks trained with noisy² gradient descent (GD) fall under the Statistical Query (SQ) framework [Kea98], which allows showing computational limitations for GD training based on SQ lower bounds. This has been combined in [AS20, SSS17, MS20, ACHM22] with the permutation symmetry of GD-training of i.i.d. FC networks to prove impossibility of efficiently learning high-degree parities and polynomials. In
'The set of probability distributions Q is denoted by P(2)). You should think of D E P(X x y) as distribution of pairs (æ. y) of covariates and labels.
"Note that the equivariance group of a training algorithum should not be confused with the equivariance group of architecture in the context of geometric deep learning [BBCV21]. In that context, G-equivariance refers to the property a neural network architecture fuu(::)) 0) X - y that fun(g(@);; 0) = [(Nu 0)) for all x E X' and all group elements g E G. In that case, G acts on both the input in X and output in )
Here the noise is used control the gradients' precision in [AS20, AKM 21j.

---

our work, we show that these arguments can be viewed in the broader context of more general group symmetries. yielding stronger lower bounds than previously known. For stochastic gradient descent (SGD) training, [ABM22] proves computational limitation for training of two-layer mean- field networks, but their result applies only when SGD converges to the mean-field limit, and does not apply to more general architectures beyond two-layer networks. Finally, most related to our SGD hardness result is [Shal8], which shows limitations of SGD-trained FC networks under a cryptographic assumption. However, the argument of [Shal8] relies on training being equivariant to linear transformations of the data, and therefore requires that data be whitened or preconditioned. Instead, result for SGD does not require any preprocessing steps.
There also recent work showing sample complexity benefits of invarian/lquiivarian neural network architectures [MMM21, EZ21, Ele21, BVB21, Ele22]. In contrast, we study equivariant training algorithms. These are distinct concepts: a deep learning algorithm can be G-equivariant, while the neural network architecture is neither G--ivarrian nor G-equivariant. For example, FC network is not invariant to orthogonal transformations of the input. However, if we initialize it with Gaussian weights and train with SGD, then the learning algorithm is equivariant to orthogonal transformations of the input (see Proposition 2.5 below).
1.2 Contribution 1: Lower bounds for noisy gradient descent (GD)
Consider the supervised learning setup where we train a neural network [NN(:; :00: X + R parametrized by 0 E R2 to minimize the mean-squared error on data distribution D E P(X' R),
(0) = (E (1y - (a; 0))
(I)
The noisy Gradient Descent (GD) training algorithm randomly initializes 0 ei for some initial-
ization distribution μe E P(RP), and then iteratively updates the parameters with step size 17 > 0 direction gD (0*) approximating the population loss gradient, plus Gaussian noise 5 (0 7 T)),
gh+1 0² - 7gg (0*) + 5**
(GD)
Up to a constant factor, gD (0) the population loss gradient, except we have clipped the gradients of the network with the projection operator IT B(),8) to lie in the ball B(0, R) = {= ||2122 S R] c RP,
(0( (<a,)>>D<y - (a ()) Ve (z: 0))].
Clipping the gradients is often used in practice avoid instability from exploding gradients (see, e.g., [ZHSJ19] and references within). In our context, clipping ensures that the injected noise ę* is on the same scale the gradient V fNN of the network and so controls the gradients' precision. Similarly to the works [AS20, AKM 21, ACHM22], we consider noisy gradient descent training to be efficient if the following conditions are met.
Definition 1.2 (Efficiency of GD, informal). GD training is efficient if the clipping radius R, step size T, and inverse noise magnitude 1/7 are all polynomially-boundee in d, since then (GD) can be efficiently implemented using noisy minibatch SGD*.
We prove that some data distributions cannot be efficiently learned by G-equivariant GD training. For this, we introduce the G-alignment:
Definition 1.3 (G-alignment). Let G be a compact group, let μx E P(X)) be distribution over data points, and let f E (xx be a labeling function. The G-alignment of (ux, f) is:
C((px, f); G) = suup Egupa [Bw-px (
h
where Pa is the Haar measure of G and the supremum is over h E T.2 such that [|/]]2 1.
In our applications, we use tools from representation theory (see e.g., [Kna96]) to evaluate the G-alignment. Using the G-alignment, we can prove master theorem for lower bounds:
Theorem 1.4 (GD lower bound, informal statement of Theorem 3.1). Let Dy E P(X x R. be the distribution of (x, (x)) for x ~ px. If pxx is G-invariant and the G-alignment of (μxx f) small, then f cannot be efficiently learned by G-equivariant GD algorithm.
"Note that if fNN is R-Lipschitz model, then (9) will simply be the population gradient of the loss. Spfficient implementability by minibatch SGD assumes bounded residual errors.
Meaning that if pxx. then for any g E G. also have g(x) ~ px.
3

---

Proof ideas We first make an observation of [Ng04]] if a G-equivariant algorithm can learn the function f by training on the distribution D. then, for any group element g G, can learn f g by training on the distribution Djgg- In other words, the algorithm can learn the class of functions F [ o g g E g). which can potentially be much larger than just the singleton set {ʃ}. We conclude by showing that the class of functions F cannot be efficiently learned by GD training. The intuition is that the G-alignment measures the diversity of the funcctinn in F. the G-alignment is small, then there is no function & that correlates with most of the functions in F, which can be used to show F is hard to learn by gradient descent.
This type of argument appears in [AS20, ACHM22] in the specific case of Boolean functions and for permutation equivariance; our proof both applies to more general setting (beyond Boolean functions and permutations) and yields sharper bounds; see Appendix A.3. Our bound can also be interpreted in terms of the Statistical Query framework, as we discuss in Appendix A.4. While Theorem 1.4 intuitively simple, we demonstrate its power and ease-of-use by deriving two new applications.
Application: Characterization of weak-learnabiliit by fully-connected (FC) networks In our first application, we consider weak-learnability: when can function be learned non-negligibly better than just outputting the estimate SNN = 0? Using Theorem 1.4, we characterize which functions over the binary hypercube f {+1, -1 -> IR and over the sphere f gd-1 + R are efficiently weak-learnable by GD-ttrined FC networks with i.i.d. symmetric and i.i.d. Gaussian initialization, respectively. The takeaway is that a function f [+11--11 -13d - IR is weak-learnable if and only if it has a nonnegligible Fourier coefficient of order O(1) or ((1). Similarly, a function f: 5d-1 + R is weak-learnable if and only if it has nonnegligible projection onto the degree- spherical harmonics. Perhaps surprisingly, such functions can be efficiently weak-learned by 2-layer fully-connected networks, which shows that adding more depth does not help. This application is presented in Section 3.1.
Application: Evidence for the staircase property In our second application, we consider learning target function f [+1,-1]4 + R that only depends on the first P coordinates, fx) h(i,,..,, Ip). Our regime of interest here when the function hand {+1,- -1) + IR remains fixed and the dimension d grows, since this models the situation where latent low-dimensional space determines the labels in a high-dimensional dataset. Recently, [ABM22] studied SGD-training of mean-field two-layer networks, and gave near-characterrization of which functions can be learned to arbitrary accuracy in On.e(d) samples, in terms of the merged-staircen property (MSP). Using Theorem 1.4, prove that the MSP is necessary for learnaabilyyy whenever training is permutation-ecnt eqquivvviinneuivaiiininn (which applies beyond the 2-layer mean-field regime) and we also generalize it beyond leaps of size 1. Details are in Section 3.2.
1.3 Contribution 2: Hardness for stochastic gradient descent (SGD)
The second part of this paper concerns Stochastic Gradient Descent (SGD) training, which randomly initializes the weights 6 ~ μe and then iteratively trains the parameters with the following update rule to try to minimize the loss (1):
+++ = 0² 1/ Va JNN( 0))² ( lo-0":
(SGD)
where (1++1, 11)+ D is fresh sample on each iteration, and 17 > 0 is the learning rate.?
Proving computational lower bounds for SGD is a notoriously difficult problem [AKM+21], exacer- bated by the fact that for general architectures SGD can be used to simulate any polynomial time learning algorithm [AS20]. However, we demonstrate that one can prove hardness results for SGD training based off of cryptographic assumptions when the training algorithm has a large equivariance group. We demonstrate the -on-uriversllity of SGD on standard FC architecture.
Theorem 1.5 (Hardness for SGD, informal statement of Theorem 4.4). Under the assumption that the Learning Parities with Noise (LPN) problem² is hard, FC neural networks with Gaussian initialization
For brevity, we focus on one-pass SGD with single fresh sample per iteration. Our results extend to empirical risk minimization (ERM) setting and to mini-batch SGD, see Remark E.
SSee Section 4 and Appendix D.3 for definitions and discussion on LPN.

---

trained by SGD cannot learn fmods {+1, -13" dd + (O,...,?} 7}.
fmnds (a:)
Σ zz (mod 8),
in polynomial time from noisy samples (x, fmoas (a) + {) where a ~ (+1,-1] and NO (), 1).
This result shows a limitation of SGD training based graphic problem. The closest prior result is in [Sha18], which proved hardness results for learning with SGD FC networks, but required preprocessing the data with whitening transformation.
average-case reduction from crypto-
Proof idea The FC architecture and Gaussian initialization are necessary: an architecture that outputted /mods(2) at initialization would trivially achieve zero loss. However, SGD Gaussian- initialized FC networks is sign-flip equivariant, and this symmetry makes fmoas hard to learn. If sign-flip equívariant algorithm can learn the function Smods (a:) from noisy samples, then it can learn the function fmdds ( @ s) from noisy samples, where {+1, -1]4 is an unknown sign-flip vector, and @ denotes elementwise product. However, this latter problem is hard under standard cryptographic assumptions. More details in Section 4.
2 Preliminaries
Notation Let Ha = -1] be the binary hypercube, and g f E Re ||a|| 2 = 1} be the unit sphere. The law of random variable X ((X). If S is finite set, then X S stands for X US. Also let Sd-1 denote drawn from the uniform Haar measure gd-1 For
Ω, let ((2) be the set distributions on Q. Let @ be the elementwise product. For any μ.x E ((2),
d x for x ~ f.x. and any g E G.
and group acting on X, we say μ. is G-invariant if g(x)
2.1 Equivariance of GD and SGD
We define GD and SGD equivariance separately.
Definition 2.1. Let ADD be the algorithm that takes in data distribution E P(X' x R), runs (GD)
on initialization 0 ~ pe for le steps, and outputs the function A = fNN(:;0' 0%)
We say "(fNN, - is G-equivariant" if AGD is G-equivariant in the sense of Definition 1.1. Definition 2.2. Let ASCD be the algorithm that takes in samples (æi, We (eEn) runs (SGD) on initialization 0 po for steps, and outputs ASGD ((xi, V1 sm())) [NN( 0h))
We say "(NNN, (e) --GD is G-equivariant" if ASGD ASGD((2 Bi)ee() _ ASDD ((g(x;) vt)se()) for any E G, and any samples (æi,yi) y1 ())mi
2.2 Regularity conditions on networks imply equivariances of GD and SGD
We take data space X C Rdd and consider the following groups that act on Rd Definition 2.3. Define the following groups and actions:
Let Gperm = Sa denote the group of permutations on (d), An element Gperm acts on x E RRd in the standard way: (xx) (Io()))-.., (d))
Let Gaigo, perm denote the group of signed permutations, an element g = (s, o) E Gaign, perm is given by sign-flip vector E Ha and a permutation a E Gperm- It acts on x E Rd by
g(x) = C (x) =
Let Grot = sO(d) C GL(d, IK) denote the rolation group. An element E Grat is rotation matrix that acts on x E gd by matrix multiplication.
"The group product 9192 (11,0))(52,02) = (sl 001(s)) o02).
5

---

Under mild conditions on the neural network architecture and initialization, GD and SGD training are known to be G perm" Gsign. or =qquivaraat [Ng04, LZA21].
Assumption 2.4 (Fully-connected i..d. first layer and skip connections from the input). We can decompose the parameters as 0 = (W, *b), where W E Rm xm is the matrix of the first-layer weights. and there is function 9NN (: +) I m > R. such that (NN((x; 0) 9NN (W æ;; xb). Furthermore, the @(mxd) for Pow E P(R).
initialization distribution is μi = jw X Hop, where jww = P.
Notice that Assumption 2.4 is satisfied by FC networks with i..d. initialization. Under assumptions on Muv, we obtain equivariances of GD and SGD (see Appendix E for proofs.)
Proposition 2.5 ([Ng04, LZA21J). Under Assumption 2.4, GD and SGD are perm requivariant.
Mwe is sign-flip symmetric, then GD and SGD are Gsign.perm equivariant. If puu NO, o²) for some G, then GD and SGD are Grov equivaraiaa..
Lower bounds for learning with GD
In this section, let P(f.px) P(x x R) denote the distribution of (æ. f(x)) where pxx We give master theorem for computational lower bounds for learning with G-equivariant GD. Theorem 3.1 (GD lower bound using G-alignment). Let G be compact group, and let (: 0): be an architecture and pe E P(R") be an initialization such that GD is G-equivariant.
X +
Fix any G-invariant distribution p.x E P(X)), any label function fo E (2xx) and any baseline function a E 1,2 (1xx satisfying a g = a for all E G. Let @ be the random weights after time-steps of GD training with noise parameter T step size n >> and clipping radius on the distribution D = D(f,, Mx). Then, for any >> 0,
Po=(eD((") S 11f. - -all2((x) - - nRyke 27
C
+
C²
where C = C((ff - -, ax)x; G) is the G-alignment of Definition 1.3.
As discussed in Section 1.2, the theorem states that if the G-alignment C is very small, then GD) training cannot efficiently improve on the trivial loss from outputting a: either the number of steps k, the gradient precision R/T, or the step size 7j have to be very large in order learn. Appendix A shows a generalization of the theorem for learning a class of functions F .f....., f instead of just single function f.. This result goes beyond the lower bound of [AS20] even when G is the trivial group with one element: the main improvement is that Theorem 3.1 proves hardness for learning valued functions beyond just Boolean-vall valued functions. We demonstrate the usefulness of the theorem through two new applications in Sections 3.1 and 3.2.
3.1 Application: Characterizing weak weak-lcarnability by FC networks
In our first application of Theorem 3.1, consider FC architectures with i.i.d. initialization, and show how to use their training equivariances to characterize what functions they can weak-learn: i.e. for what target functions f. they can efficiently achieve non-negligible correlation after training. Definition 3.2 (Weak learnability). Let (palden be a family of distributions pa E P(Xa), and ler (Jayaen be a family of functions fa E T (pa)). Finally, let (Sa)deN be family of estimators, where fa is random function in I.2 (pa)). We say that (fá, pa) daTdeN is "weak-learned" " by the family of estimators (Ja)de if there are constants do, C. <>0 such that for all d >> do.
Pf. Fallia(ue) S [Iffal d 229110. 9/10.
The constant 9/10 in the definition is arbitrary. In words, weak-learning measures whether the family of estimators (fa) has neg-nggli edge simply estimating with the identically functions fa O. We study Definition 3.3. We say that (Ja, day is efficiently weak-learrable by GD-trained FC networks if there are FC networks and initializations (NNN,;; po,a), and hyperparaneters (na, ka, Ra: Tay such that for some constant 0.
by GD-trained FC networks.

---

Hyperparameters are polynomial size: 0 S ka, RR, 1/Ta S O(d));
{fa] weak-learns {fa: Pa) in the sense of Definition 3.2, where fa frun(;; 0a) ) for weights Oa that are GD-Irained on D(Ja, pa) for ka steps with step size Thd clipping radius Ra, and noise Td, starting from initialization pe,a-
If Heaa is i.idd copies of symmetric distribution, say that the FC networks symmetricallly initialized, and Gaussian initialized
Cauusian-initttllzzedd if pa.a is i.i.d. copies of a Gaussian distribution.
3.1.1 Functions on hypereube, FC networks with Li.d. symmetric initialization
Let us first consider functions the Boolean hypercube Ha - R. These can be uniquely written as a multilinear polynomial
f(x)
((S) ((s) SEA
CF &ES
II
where f(S) are the Fourier coefficients of [O'D14]] We characterize weak learnability functions on the hypercube in terms of their Fourier coefficients. The full proof is deferred to Appendix B.1.
Theorem 3.4. Let {faldeN be a family of functions fa Ha + R with (lfallzz(Ha)) S 1. Then (Ja, Ha} is efficiently weak-leernabbee by GD-trained synmetrically-mittatii
FC networks if and only if there constant C 0 such that for each d e N there is Sa S [d] with |Sal S C or |Sa] 2 d C. and (fa(Sa) 2 ()
The algorithmic result can be achieved by two-layer FC networks, and relies random features analysis where each network weight is initialized to with probability 1 1- p. and +1 or -1 with equal probability p/2." Therefore, for weak learning the hypercube, two-layer networks are good as networks of any depth. For the converse impossibility result, we apply Theorem 3.1, recalling that GD is Gsign.perm equivariant by Proposition 2.5, and noting that Gsign.perm porm-aanm--leeent is:
Lemma 3.5. Let f Ha R. Then C((f, Ha); Gsign. maxkeld (+)
Σ Esci f(S) =k
Proof. In the following, let ~ Hu and a ~ Gperm- so that (s. Gsign.perm- Also let x, x H. be independent. For any h Hy + R, by (a) tensorizing, (b) expanding f in the Fourier basis, (c) the orthogonality relation Ex(xs(s)xss
= ds,s', and (d) tensorizing,
E, [[]()(()))))) E.,,,
(a) E. (fte///
Em.a' Σ (19f (dixs))))) (b)
S.S'Cid
(c)
$Cid
( E
Scid]
Σ
i(S)2 B, (S))
SCI4
Σ f(s)
d
Σ
M(S
(S)
SC14
1S
| | (P(H,)) the supremum over h such that [[b]| is achieved by taking h(x)) = (x) ) for some S.
And since Es.is- 1((')²2 <
"SSurrrisingly, this means that the full parity function fx( = I 2s can be efficiently learned with such initializations. See Appendix B.
7

---

So if the Fourier coefficients of f are negligible for all S s.t. min([S]. d |S]) < O(1), then the Geign.porm" aaaii.per--liigmmen of f is negligible. By Theorem 3.1, this means f cannot be learned efficiently. In Appendix 1.1.2 we give a concrete example of a hard function, that was not previously known.
3.1.2 Functions on sphere, FC networks with Lid. Gaussian initialization
We now study learning target function on the unit sphere. f -2 where we take the standard Lebesgue measure on gd-1, A key fact in harmonic analysis is that (2 can be written as the direct sum of subspaces spanned by spherical harmonics of each degree (see, e.g. [Hoc12]).
L2(gd-1)
Val t=0
where Va C (2( is the space of degree-l spherical harmonics, which of dimension dim(Va.) 21 + d 2 (1+
1 ( 1 1--11 (1+--3)
Let Il.,, : (L2(Sa-1) + Va. be the projection operator to the space of degree-l spherical harmonics. In Appendix B.2, prove this characterization of leak-leamabilltyy for functions on the sphere:
Theorem 3.6. Let {Ja)der be a family of functions fa : S - R with II 1) S 1. Then (Ja,S-1) is efficiently weak-learnable by GD Gaussia--niitialzze FC networks if and only there a constant C > 0 such that 2i=o [ d d-c
The algorithmic result can again be achieved by two-layer FC networks, and is consequence of the analysis of the random feature kernel in [GMMM21], which shows that the projection of fa onto the low-degree spherical harmonics can be efficiently learned. For the impossibility result, we apply Theorem 3.1, noting that GD is Grot equiivaaraa by Proposition 2.5, and the Grot- alignmeet is: Lemma 3.7. Let f E I,2 (8d-1). Then C(( (:): Grat)) = maxtez I[T,,,, dim(Va.).
Proof. The -mn--aiigmmet is computed using the representation theory of Grot. specifically the Schur orthogonality theorem (see, e.g., [Ser77, Kna96]). For any I, the subspace Va, is invariant to action by Grot, meaning that we may define the representation tb; of Grot. which for any g E Grot, Va, is given by (g) Ve. Va, and Dr(g)f f fog Furthermore, 4 is unitary, irreducible representation, and @ is not equivalent to Tr, for any + 1' (see e.g., [Sta90, Theorem IJ). Therefore, by the Schur orthogonality relations [Kna96, Corollary 4.10), for any U1, w1 Va,1, and U2 W2 E Va,aa we have
EgwGraa L1rr, (g)u,, w1) w1) 13 1166- (g)02, w2) 12)
61,12 (vi, U2) (206 1y (10) W2) 12 dim((a (3)
Let g Grot, drawn from the Haar probability measure. For any E (22( such that [ by (a) the decomposition of LL(()d-1 into subspaces of spherical harmonics, (b) the -nvv-invree of each subspace Va,1, and (c) the Schur orthogonality relations in (3),
Koff o g, h)
[IIva (f g), HVa, h) 1) 1) (IIvar, (f (fog), II h) L2(3a11))
P Val,, f) g. MVan 1) (aaeee)))(IIIiaala (IIIva,, Iv h) 12(3-19)
4/22
[Iver 11721000-1))) |lll, / (11221080-11
dim (Va.)
1
[Tr,, M (112)
[ [T (122
max dim()a.)
lEZ20
max 162go
11 fll 11
dim Va.1)
8

---

Let (* be the optimal value of in the last line, which is known to exist by the fact that : fll Il and dim(Va.1) - oo as I -> oc. The inequality is achieved by h Ty f/IlilallVv fll-
L
This implies that the Goot alignment of f is negligible if and only if its projection to the low-order spherical harmonics is negligible. By Theorem 3.1, this implies the necessity result of Theorem 3.6.
3.2 Application: Extending the merged-staircase property necessity result
In our second application, we study the setting of learning a sparse function on the binary hypercube (a.k.a. a junta) that depends on only P Σ d coordinates of the input æ; i.e.,
(x) = h, (#1,, ...))...).))...
where h. : Hr R. The regime of interest to is when h, is fixed and d oo, representing hidden signal in a high-dimensional dataset. This setting was studied by [ABM22], who identified the "merged-staircan property" (MSP) as extension of [ABB*21 We generalize the MSP below.
Definition 3.8 (I-MSP). For 1 E 24 and ha Hpp + R. we say that he satisfies the merged staircase property with leap 1 (i.e., I-MSP) if its set of nonzero Fourier coefficients S = {S: h.) & 0} can be ordered S 1S1,,.... Sm3 such that for all i [m]. |S, Uj<i L.
For example, (x) = I1 + 22 + Ij 2223 satisfies 1-MSP; hx(x) = 21 + 21 satisfies 2-MSP, but not I-MSP because of the leap required to learn z22 similarly h,,x)) 2 + I4 satisfies 3-MSP but not 2-MSP. h. satisfies (-MSP for some small I, then the function f. can be learned greedily in an efficient manner, by iteratively discovering the coordinates which it depends. In [ABM22] it was proved that the I-MSP property nearly characterized which sparse functions could be e-leamed in Oz, (d) samples by one-pass SGD training in the mean- mean-field regime.
We prove the MSP necessity result for GD training. On the one hand, our necessity result is for a different training algorithm, GD, which injects noise during training. On the other, our result is much more general since it applies whenever GD is permutation-equu eqqivvarinn,,iiiinnt which includes training of FC networks and ResNets of any depth (whereas the necessity result of [ABM22] applies only to two-layer architectures in the mean-field regime). We also generalize the result to any leap l.
Theorem 3.9 (I-MSP necessity). Lel ON)(;;0) Ha + TR. be an architecture and po <P(RP) be an initialization such that GD is Seperm-equivarte O, step size 1,, and clipping radius R on the distribution D = D(f., Ha). Suppose that f=(x) = (=)z) where ht Hp + R does not satisfy L-MSP for some 1 Z.. Then there are constants C, co depending on h such that
Let 0 be the random weights after k steps
of GD training with noise parameter
CnR 27
k
C
Por ((= S <o]
d
HII
The interpretation is that if hn does not satisfy 1-MSP, then to learn f. to better than co error with constant probability, we need at least (d 11) steps of (GD) on a network with step size n On_.c (1), clipping radius R = .h.,.(1) (1), and noise level c1), The proof is deferred to Appendix C. It proceeds by first isolating the "easily-reachablle coordinates T S [P). and subtracting their contribution from f.. We then bound G-alignment of the resulting function, where G is the permutation group on [d]] T.
Hardness for learning with SGD
In this section, for y > O, we let D (ff,xx))) 7) P(X x R) denote the distribution of f(x) + E) where x ~ μa and { (0, 7²) is independent noise.
We show that the equivariance of SGD on certain architectures implies that the function fmods Ha (O....,7, given by
fmods ( (x)
Σ
Z (mod 8)
(4)
is hard for SGD-trained, i.i.d. symmetrically-initaan on a cryptographic assumption to prove superpolynomial lower bounds for SGD learning. For any S C let xs Ha + {+1,- -1} be the parity function (s())
FC networks. Our hardness result relies
Il It.

---

Definition 4.1. The learning parities with Gaussian noise, (d. n. (.n.n))-LPGa problem is parametrized
by d.n E Σ and ? E Rg.. An instance (S, q, (z,, (e)xe(m)) consists of (i) an unknown subset S S [d] of size | = [d/2], and ((i) a known query vector q Ha. and i..dd samples (2 y4 se)sell ~
D(xs, H), The task is to return Xs (s) E -+1,-
Our cryptographic assumption is that poly (c) (d)- circuits cannot succeed on LPGN.
Definition 4.2. Let > O. We say 7-LPGN is poly(d)-time solvable if there is sequence of sample sizes (ndldeN and circuits (Ad]deN such that na, size(As) S pooyyd) and Aa solves (d, nd, 7)-LPGN with success probability at least 9/10, when inputs are rounded to poly(d) bits.
Assumption 4.3. Fix The Thee-LLL-NNuaie hardness assumption is: 7-LPGN is not poly (d) solvable.
The LPGN problem is the simply standard Learning Parities with Noise problem (LPN) [BKW03], except with Gaussian noise instead of binary classification noise, and we are also promised that |S] [d/2]. In Appendix D.3, we derive Assumption 4.3 from the standard hardness of LPN. We now state our SGD hardness result.
Theorem 4.4. Let {NNN, Ho.d aaen be a family of networks and initializations satisfying Assump- tion 2.4 (fully-connected) with i.idd. symmetric initialization. Let 7i 0 and let {na} be sample sizes such that (JNN,a- ()SDD training on na samples from monds Hd, 7) rounded to poly(d) bits yields parameters Og with
Eo, IllSmods [NN(:: [NN(;;0a)11 02) - 0.0001.
Then, under (x/22)LPGGN hardness, (fNN,d: μe me,a) -SGD on na samples cannot run in (oly time.
In order to prove Theorem 4.4, we use the sign-flip equivariance of gradient descent guaranteed by the symmetry in the initialization. A sign-flip equivariant network that learns f (æ: from y-noisy samples, capable of solving the harder problem of learning smods( (ær @ s) from y-noisy samples, where s E Ha is an unknown sign-flip vector. However, through an average-case reduction we show that this problem is (1/2)-LPGNNhaat
Therefore the theorem follows by contradiction.
Discussion
The general GD lower bound in Theorem 3.1 and the approach for basing hardness of SGD training on cryptographic assumptions in Theorem 4.4 could be further developed to other settings.
There are limitations of the results to address in future work. First, the GD lower bound requires adding noise to the gradients, which can hinder training. Second, real-world data distributions are typically not invariant to group of transformations, so the results obtained by this work may not apply. It is open to develop results for distributions that are approximately invariant.
Finally, it is open whether computational lower bounds for SGD/GD training can be shown beyond those implied by equivariance. For example, consider the function H. + {+1,-1} that computes the "full parity", i.e., the parity of all of the inputs fxx = II 2,. Past work has empirically shown that SGD FC networks with Gaussian initialization [SSS17, AS20, NY21] fails to learn this function. Proving this would represent a significant advance, since there is no obvious equivariance that implies that the full parity is hard learn in fact we have shown weak-learnbiliity with symmetric Rad(1 22) initialization, in which case training is Gsigo, -eqiivrran
Acknowledgements
We thank Jason Altschuler, Guy Bresler, Elisabetta Cornacchia, Sonia Hashim, Jan Hazla, Hannah Lawrence, Theodor Misiakiewicz, Dheeraj Nagaraj, and Philippe Rigollet for stimulating discussions. We thank the Simons Foundation and the NSF for supporting us through the Collaboration on the This work was done in part while
Theoretical Foundations of Deep Learning (deepfoundations..t) E.B. was visiting the Simons Institute for the Theory of Computing and the Bernoulli Center at EPFL, and was generously supported by Apple with an AI/ML fellowship.
Mooe formally, would express this probabilistic promise problem [Ale03].
10

---

References
[AB
E. Abbe, E. Boix-Adsera, M. S. Brennan, G. Bresler, and D. Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Information Processing Systems, 34:26989-
2021.
[ABM22]
E. Abbe, E. Boix-Adsera, and T. Misiakiewicz. The merged-staircant property: a necessary and nearly sufficient condition for sgd learning of sparse functions two- layer neural networks. arXiv preprint arXiv:2202.0865. 2022.
[ACHM22]
E. Abbe, E. Cornacchia, J. Hazla, and C. Marquis. An initial alignment between neural network and target is needed for gradient descent to learn. arXiv preprint arXiv:2202. 12846, 2022.
[AKM*21] E. Abbe, P. Kamath, E. Malach, C. Sandon, and N. Srebro. On the power of differ- entiable learning versus PAC and SQ learning. In Advances in Neural Information Processing Systems, volume 34, 2021.
[AL19]
Z. Allen-Zhu and Y. Li. What can resnet learn efficiently, going beyond kemels?? Advances Neural Information Processing Systems, 32, 2019.
[AL20]
Z. Allen Ahu
Zhu and Y. Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.044/ 2020.
[Ale03]
M. Alekhnovich. More average case approximation complexity. In 44th Annual IFFE Symposium on Foundations of Computer Science, 2003. Proceedings, pages 298-307. IEEE, 2003.
[AS20]
E. Abbe and C. Sandon. Poly-time universality and limitations of deep learning. arXiv preprint arXiv:2001.0299) 2020.
A. Bogatskiy, B. Anderson, J. Offermann, M. Roussi, D. Miller, and R. Kondor. Lorentz group equivariant neural network for particle physics. In International Conference Machine Learning, pages 992-1002. PMLR, 2020.
[Bar93]
A. R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory, 39(3)930-945, 1993.
[BBCV21] M. M. Bronstein, Bruna, T. Cohen, and P. Velicković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104. 2021.
[BBH18]
M. Bremnan, G. Bresler, and W. Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. Conference On Learning Theory, pages 48-166. PMLR, 2018.
[BCB14]
D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint 40%.v.1409.0473. 2014.
[BF02]
N. H. Bshouty and V. Feldman. On using extended statistical queries to avoid member- ship queries. Journal of Machine Learning Research, 2(Feb)::59-395, 2002.
[BIK90]
S. Ben-David, A. Itai, and E. Kushilevitz. Learning by distances. In COLT, pages 232-245, 1990.
[BKW03]
A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-519 2003.
[Boi20]
Boix-Adsera. Average-case statistical query algorithms, 2020. Report for MDS Lab Internship.
[BVB21]
A. Bietti, L. Venturi, and J. Bruna. On the sample complexity of learning under geometric stability. Advances Neural Information Processing Systems, 34, 2021.
[BZSL13]
J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 6203, 2013.
[Ele21]
B. Elesedy. Provably strict generalisation benefit for invariance in kernel methods.
Advances Neural Information Processing Systems, 34, 2021.
[Fle22]
B. Flesedy. Group symmetry pac learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
11

---

[EZ21]
B. Elesedy and S. Zaidi. Provably strict generalisation benefit for equivariant models. International Conference on Machine Learning, pages 2959-2969, PMLR, 2021.
[GMMM21] B. Ghorbani. S. Mei, T. Misiakiewicz. and A. Montanari. Lincarized two-layers neural networks in high dimension. The Annals of Statistics,
2021.
[GMS05] M. Gori, G. Monfardini, and Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, volume 2, pages 729-734, 2005.
[Hoc12]
H. Hochstadt. The functions of mathematical physics. Courier Corporation, 2012.
[HSSV21]
D. Hsu, C. Sanford, R. A. Servedio, and E. Vlatakis VataaissGKaragkouniis On the approxima- tion power of two-layer networks of random relus. arXiv preprint arXiv:2102.0233: 2021.
[Hsu]
D. Hsu. Dimension lower bounds for linear approaches to function approximation.
[HZRS16)
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[JGH18]
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and gener- alization in neural networks. Advances in neural information processing systems, 31, 2018.
[Kea98]
M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1006, 1998.
[KMS20]
Kamath, O. Montasser, and Srebro. Approximate good enough: Probabilistic variants of dimensional and margin complexity. In Conference on Learning Theory, pages 2236-2262. PMLR, 2020.
[Kna96]
A. W. Knapp. Lie groups beyond an introduction, volume 140. Springer, 1996.
[KSH12]
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Advances neural information processing systems, 25, 2012.
[LB+
Y. LeCun, Y. Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10):1995, 1995.
[LCC*22]
Y. Li, D. Choi, J. Chung, N. Kushman, J. Schrittwieser, R. Leblond, T. Eccles. J. Keel- ing. F. Gimeno, A. D. Lago, al. Competition-level code generation with alphacode. arXiv preprint arXXvv2203.0788) 2022.
[LKF10]
Y. LeCun, K. Kavukcuoglu, and C. Farabet. Convolutional networks and applications in vision. In Proceedings of 2010 IEEE international symposium on circuits and systems, pages 253-256 256. IEEE, 2010.
[LZA21]
Z. Li, Y. Zhang, and S. Arora. Why are convolutional more sample-efficient than fully-connected nets? In International Conference on Learning Representations, 2021.
[Mis22]
T. Misiakiewicz. Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint arXiv:2204.1044 10425, 2022.
[MM21]
Misiakiewicz and Mei. Learning with convolution and pooling operations in kernel methods. arXiv preprint 10Xiv:2111008300 2021.
[MMM21]
S. Mei, T. Misiakiewicz, and A. Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory, pages 3351-3418. PMLR, 2021.
[MS20]
E. Malach and S. Shalev-Shwartz. Computational separation between convolutional and fully-connected networks. arXiy preprint arXiv:2010.01369, 2020.
[Ng04]
A. Y. Ng. Feature selection, 1 vs. 12 regularization, and rotational invariance. In Proceedings of the twenty-first international conference on Machine learning, page 78. 2004.
12

---

[NY2]]
I. Nachum and A. Yehudayoff. On symmetry and initialization for neural networks. In Latin American Symposium on Theoretical Informatics, pages 401-412. Springer, 2021.
[O'D14]
R. O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
[Rey20]
L. Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint 200457700. 2020.
[Ser77]
J.-P. Serre. Linear representations of finite groups, volume 42. Springer, 1977.
[Sha18]
O. Shamir. Distribution-specific hardness of learning neural networks. The Journal of Machine Learning Research, 19(1):1355-116; 2018.
[8HS+18] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 362(6419): 140-11444441111 1144, 2018.
[SNPP19] Schubert, P. Neubert, Pöschmann, and P. Protzel. Circular convolutional neural networks for panoramic images and laser data. In 2019 IEEE Intelligent Vehicles Symposium (/V), pages 653-660. IEFF, 2019.
[SSS17]
Shalev-Shwartz, O. Shamir, and Shammah. Failures of gradient- based deep learning, In International Conference on Machine Learning, pages 3067-3075. PMLR, 2017.
[Sta90]
D. Stanton. An introduction to group representations and orthogonal polynomials. In Orthogonal Polynomials, pages 419-433. Springer, 1990.
[Val84]
I.. Valiant. theory of the learnable. Communications of the ACM, 27(11):1134 1 1142, 1984.
[VCC+17] 17]
P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. stat, 1050:20, 2017.
[VSP*17]
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, Jones, A. N. Gomez, t.. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[WLLM19] C. Wei, J. D. Lee, Q. Liu, and T. Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
[ZHSJ19]
J. Zhang, T. He, S. Sra. and A. Jadbabaie. Why gradient clipping accelerates training: theoretical justification for adaptivity. arXiv preprint arXiv: 1881, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "tgBjVAHUXV4", "reviewer": "Reviewer_EG9T", "summary": "This paper studies lower bounds of Gradient Descent (with noise) (GD) and Stochastic Gradient Descent (SGD) training algorithms that are also $G$-equivariant. The paper introduces the concept of $G$-orbit alignment which is used towards proving the first main result which is a computational lower bound on $G$-equivariant GD which appears novel. Two applications of this lower bound are provided in terms of weak learnability of functions on the hypercube, hypersphere, and a necessity result on the merged staircase property. As a separate, but interesting in it's own right contribution, the authors provide a first-of-its-kind hardness result for SGD using fully-connected networks on the Learning Parities with Gaussian Noise problem.", "questions": "One of the central assumptions in much of the technical results is that $\\mu_x$ is $G$-invariant. Often times real-world datasets, due to noise or other randomness in the data collection process exhibit soft equivariance rather than hard ones. Can you provide commentary on how this specifically affects the weak learnability results ---i.e. does depth now matter beyond 2-layer networks?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Disclaimer** \nI did not check the veracity of the proofs beyond Appendix A.\n\nThis paper enjoys several strengths. In my opinion, the paper studies an extremely interesting problem and makes progress by providing several novel insights. I especially appreciated the idea of $G$-orbit alignment and its use in characterizing weak learnability. This is both intuitively clear and a great application. I also equally found the main results of the lower bounds on $G$-equivariant GD insightful and a significant step over previous work. The computational hardness results for SGD seemed interesting but this aspect was a bit beyond my area of expertise. The authors could do a bit more towards making this section more approachable given that the paper does not completely exhaust the 9-page limit. My main criticism of this work is that a lot of the interesting detail in the Appendix could have been brought forward to the main text. For example, the impossibility results for both applications that actually utilize Theorem 3.1 could be better served in the main paper. Overall, I found this paper to be a thoroughly enjoyable read as overall the clarity and high quality of writing made difficult ideas mostly approachable but at the same time did not water down their perceived impact.\n\n**Minor**\n- line 147 compact groups, not any groups\n\n- minor notational issues. In definition 2.4 $\\psi, \\tilde{\\theta}$ are not defined\n\n- Definition 3.2 seems a bit contrived. Can you provide a bit more intuition for the constant 9/10?", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "am1RKRCDMbj", "reviewer": "Reviewer_bjbs", "summary": "This paper studies the learnability of Lipschitz models with GD/SGD optimization. It assumes that the learning algorithm satisfies G-equivariant for some non-trivial symmetry group G (which holds for GD/SGD learning in neural networks), and shows two types of results:\n- With GD learning, the paper characterizes the learnability of Lipschitz models on 1) functions of both the hypercube and the unit sphere; 2) functions with latent low-dimensional structure. \n- For the function given in Eq. (4), with SGD learning, a fully-connected network cannot learn and evaluate the function (4) in polynomial time with respect to the input dimension d.\n", "questions": "Please refer to the [weakness] part.", "limitations": "Please refer to the [weakness] part.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe first result characterizes the learnability of a rather general class of learning models. The second result provides a nice example that neural networks, despite their universal approximation ability, cannot efficiently learn.\n\nWeakness:\n\nMy major concern is that it requires the architecture to have bounded Lipschitz constant over parameters. However, almost all neural networks have unbounded Lipschitz constants. The authors argue (in the supplementary materials) that, in practice, we can clip the gradients to yield bounded derivatives. However, for a purely theoretical paper, this is not a sound justification. Clipping the gradient is equivalent to changing the learning algorithm, but the objective function remains unchanged, still having an unbounded Lipschitz constant. \n\nIn that sense, Section 3 only holds for models with Liptchiz constant, for example, one-hidden-layer networks with fixed output layers and bounded-gradient activations. This deviates from the major claims --- \"regular architectures and initialization\" of neural networks. Meanwhile, the authors criticize that the prior work [AS20] does not \"reflect architectures used in practice\", which is unfair. \n\nTo rigorously prove for neural network training, the authors can either show i) GD operates in a bounded region, within which we have bounded Lipschitz, or ii) the theorem holds for gradient-clipping GD. Please consider addressing this problem. Otherwise, it is not eligible to claim the results hold for general DNN. Note that prior works (such as [Ele22]) that require C-Lipschitz on the learning model did not claim to hold for NN in their theorems.\n\nAnother concern is that the second result does not seem to counter [AS20] directly. [AS20] shows there exists DNN that can emulate any efficient learning algorithm (that is able to learn in poly-time). It assumes that at least one poly-time efficient algorithm exists. However, the non-universality shown in Theorem 4.4 relies on the hardness of γ-LPGN hardness, which is not poly-time solvable by any algorithm. There is a gap between the \"universality\" discussed in [AS20] and this paper. It is still possible that a practical DNN with G-equivariance SGD learning can emulate any efficient algorithm.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NCzQVMDdLLd", "reviewer": "Reviewer_1FaY", "summary": "This paper tries to analyze which functions can and cannot be learned by a standard MLP with gradient descent. This is analyzed by looking at the symmetry of the initialization and GD so the intuition is that functions that do not follow this symmetry are hard to learn. ", "questions": "Can you give an example (that wasn't shown previously) of something that isn't weak learnable?", "limitations": "Not discussed", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I would first want to state that I am not a theoretician so I do not think I am the right person to review this paper, but I did the best I could to evaluate it.\n\nStrength:\n- The paper is clearly written\n- The proofs seem correct to me \n- The question of what functions can be learned is an important one so the work is important and novel.\n\nWeaknesses:\n- I mainly question the significance of some of the results, especially since the definition of weak learnability is very weak (as the \"non-negligible\" edge can be quite negligible with a large value of C). For example in Trm. 3.6 the condition $\\sum_{\\ell=0}^C||P_{V_{d,\n\\ell}}f_d||^2\\geq d^{-C}$, the r.h.s increases (or not decreases) with $C$ and the r.h.s decreases rapidly. It makes the condition very weak (as weak learnability is very weak) so I don't think it adds any value to our understanding.\n- Missing related work Shai Shalev-Shwartz, Ohad Shamir and Shaked Shammah \"Failures of Gradient-Based Deep Learning\".\n- You do not show results for GD/SGD but for GD/SGD with noise. This is equivalent to what is done in SGLD or differentially private learning which significantly hampers performance. It is not clear to me at all that the results with noise are relevant to the standard noiseless training due to the major impact the noise makes on the optimization process.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7fQElNys6sJ", "reviewer": "Reviewer_m7n1", "summary": "This paper mainly focused on the universal property of deep learning. Specifically, the authors showed that when the training algorithm satisfies a certain symmetry/equivairance, deep learning is no longer universal. Then, they characterize two types of functions with gradient descent (GD): 1) the functions that fully-connected networks could weakly learn on the binary hypercube as well as the unit sphere, and 2) the functions that neural networks with latent low-d structure. Lastly the authors extend the results to the stochastic GD.", "questions": "1. In Line 237, the authors mentioned that if the $G-$orbit-alignment is very small, then the GD training cannot efficiently improve on the trivial loss, could the authors elaborate on this part a bit more, since the right-hand side in the equation between 235 and 236 also depends on other factors?\n\n2. As I mentioned in the weakness part, some definitions and assumptions are abstract, could the authors give some examples for readers to follow easily?\n\n3. Could the authors provide some numerical studies to demonstrate the applications mentioned in the paper indeed work in practice.", "limitations": "N/A.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The paper has good novelty and defines a lot of new concepts, e.g., G-orbit-alignment, etc. It pushes the boundary of the research.\n\n2. Use some decent mathematic tools.\n\nWeakness:\n\n1. The paper is very abstract, and some definition is not easy to think about. Could the authors give some examples to help readers better understand the newly defined concepts?\n\n2. The authors always assume that the GD training algorithm is G-equivariant, but in practice, I was wondering if this condition could hold.\n\n3. The paper lacks some empirical study to support the authors' findings.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept