On the hardness of learning under symmetries
Authors: Bobak Kiani
Thien Le
Hannah Lawrence
Stefanie Jegelka
Melanie Weber
Venue: ICLR 2024 spotlight (2024)
Keywords: Equivariance
statistical query
lower bound
computational hardness
invariance
symmetry
neural networks
Primary area: learning theory
TL;DR: We give statistical query lower bounds for learning symmetry-preserving neural networks and other invariant functions.

Abstract: We study the problem of learning equivariant neural networks via gradient descent. The incorporation of known  symmetries ("equivariance") into neural nets has empirically improved the performance of learning pipelines, in domains ranging from biology to computer vision. However, a rich yet separate line of learning theoretic research has demonstrated that actually learning shallow, fully-connected (i.e. non-symmetric) networks has exponential complexity in the correlational statistical query (CSQ) model, a framework encompassing gradient descent. In this work, we ask: are known problem symmetries sufficient to alleviate the fundamental hardness of learning neural nets with gradient descent? We answer this question in the negative. In particular, we give lower bounds for shallow graph neural networks, convolutional networks, invariant polynomials, and frame-averaged networks for permutation subgroups, which all scale either superpolynomially or exponentially in the relevant input dimension. Therefore, in spite of the significant inductive bias imparted via symmetry, actually learning the complete classes of functions represented by equivariant neural networks via gradient descent remains hard.

Published as a conference paper at ICLR 2024
ON THE HARDNESS OF LEARNING UNDER S SYMMETRIES
Bobak T. Kianit Thien Le Hannah Lawrence" Stefanie Steefnii Jegelka 13, Melanie Weber MIT BECS, Harvard SEAS, TU Munich, co-first author
ABSTRACT
We study the problem of learning equivariant neural networks via gradient de- scent. The incorporation of known symmetries ("equivariance") into neural net- works has empirically improved the performance of learning pipelines, in do- mains ranging from biology to computer vision. However, a rich yet separate line of learning theoretic research has demonstrated that actually learning shallow, fully-connected (i.e. non-symmetrie) networks has exponential complexity in the correlational statistical query (CSQ) model, framework encompassing gradient descent. In this work, we ask: are known problem symmetries sufficient to alle- viate the fundamental hardness of learning neural nets with gradient descent? We answer this question in the negative. In particular, we give lower bounds for shal- low graph neural networks, convolutional networks, invariant polynomials, and frame-averaged networks for permutation subgroups, which all scale either super- polynomially or exponentially in the relevant input dimension. Therefore, in spite of the significant inductive bias imparted via symmetry, actually learning the com- plete classes of functions represented by equivariant neural networks via gradient descent remains hard.
INTRODUCTION
In recent years, the purview of machine learning has expanded to non-traditional domains with geometric inputs, from graphs sets to point clouds. Correspondingly, it now common practice to tailor neural architectures to the symmetries of the input - for example, graph neural networks are invariant to permutations of the input nodes, while networks operating on molecules and point clouds are invariant to permutation, translation, and rotation. Empirically, encoding such structure has led to computational benefits in applications (Wang et al., 2021; Batzner et al., 2022; Bronstein et al., 2021). From the perspective of generalization, previous research has quantified the benefits of imposing symmetry during learning (Long & Sedghi, 2019; Bietti et al., 2021; Sannai et al., 2021: Weber et al., 2020; Mei et al., 2021), often achieving rather tight bounds for simple models (Elesedy, 2021; Tahmasebi & Jegelka, 2023). At their core, these results are bounds on sample complexity, i.e. how much data is needed to learn given task. In contrast, the effect of symmetries on the computational complexity of learning algorithms has not been previously studied. Broadly speaking, generalization bounds are necessary but not sufficient to show efficient learnability, as there can be exponentially large gaps between sample complexity and runtime lower bounds.
Indeed, an active line of research in learning theory studies the hardness of learning fully-connected neural networks via "correlational statistical query" (CSQ) algorithms (defined in Sec. 2.1). which notably encompass gradient descent. particular, for Gaussian data distribution, Diakonikolas et al. (2020) proved exponential lower bounds for learning shallow neural networks. Such works provide valuable impossibility results, demonstrating that one cannot hope to efficiently learn any function represented by small neural networks under simple data distributions.
In this work, we ask: does invariance provide a restrictive enough subclass of neural network func- tions to circumvent these impossibility results? Our main finding, shown in various settings, is that an inductive bias towards symmetry is not strong enough to alleviate the fundamental hardness of learning neural nets via gradient descent. We view this result as guide for future theoretical work: additional function structure is generally needed, even in the invariant setting, to achieve guarantees of efficient learnability. Our proof techniques largely rely extending techniques from the general

---

Published as a conference paper at ICLR 2024
setting to symmetric function classes. In many of our lower bounds, imposition of symmetry function class reduces the computational complexity of learning by a factor proportional to the size of the group. Some of our lower bounds simple symmetrizations of existing hard families, while others require bona fide new classes of hard invariant networks. For example, intuition from mes- sage passing GNN architectures seems to indicate that complexity would grow exponentially with the number of such message passing steps; however, our results show that even a single message passing layer gathers sufficient features to form exponentially hard functions (Liao et al., 2020).
Our Contributions We consider various interrelated questions on the computational hardness of learning, focusing primarily on how hard it is to learn data generated by invariant architectures.
Question (primary). Given Gaussian i.i.d. inputs in n variables, how hard is it to learn the class of shallow single hidden layer invariant architectures in the correlational statistical query model?
We answer this question in various settings. As a warm-up, for learning invariant Boolean functions in Sec. 3. Next, we show that graph neural networks with a single message passing layer are exponentially hard to learn, either in the number of nodes feature dimension (Theorem 3 and Theorem 4, respectively). Hardness in the feature dimension results from careful symmetrization of the hard functions in Diakonikolas et al. (2020). This technique did not extend to the node dimension hardness result in Theorem 3, for which we instead constructed a customized set of hard functions whose outputs are parities in the degree counts of the graph. Since adjacency matrices of graphs are often Boolean valued, this setting also offers general SQ lower bounds scaling exponentially with the number of nodes n. For subgroups of permutations, we prove CSQ hardness results for "symmetrized" (frame-averaged neural network classes encapsulating CNNs (Theorem of Sec. 5). The proofs here are based on constructions in Goel et al. (2020) and Diakonikolas et al. (2020), ensuring that properly chosen frames retain the underlying structure necessary (c.g., sign invariance) to guarantee orthogonality of hard functions.
give general (SQ) lower bounds
These lower bounds constitute our main results, but we provide two complementary results to pro- vide an even more complete picture. First, we show that classes of sparse invariant polynomials can be learned efficiently, but not by gradient descent, via straightforward extension of the algo- rithm in Andoni et al. (2014) for arbitrary polynomials (Sec. 6). This learning algorithm is SQ, and we give various n (llgg)) CSQ lower bounds for learning over n (log many orthogonal invariant polynomials of degree at most (log(n)). Second, we take a classical computational complexity perspective to establish the NP hardness of learning GNNs. The work of Blum & Rivest (1988) established that even 3-node feedforward networks are NP hard to train, and later expanded to erage case complexity for improper learning by various works (Daniely et al., 2014; Daniely, 2016; Klivans & Kothari, 2014). Although it is perhaps not surprising that these hardness results can be extended to invariant architectures, for the sake of completeness (and since we were unaware of an extension in the literature), Sec. 4.3 we give an NP hardness result for proper learning of the weights of a GNN architecture. Finally, Sec. 7 provides a few experiments verifying that the hard classes of invariant functions we propose are indeed difficult to learn.
1.1 RELATED WORK
A long line of research studies the hardness of learning neural networks. We briefly review the most relevant works here, and refer the reader to App. A for a more holistic review.
Our work is largely motivated extend hardness results for feedforward networks to equivariant and symmetric neural networks. Early results showed that there exist rather artificial distributions of data for which feedforward networks are hard to learn in worst-case settings (Judd, 1987: Blum & Rivest, 1988; Livni et al., 2014). Interest later grew into studying hardness for more natural set- tings via the statistical query framework (Kearns, 1998; Shamir, 2018). Goel et al. (2020) showed superpolynomial CSQ lower bounds for learning single hidden layer ReLU networks, subsequently strengthened to exponential lower bounds in Diakonikolas et al. (2020). We use the hard class of networks in Diakonikolas et al. (2020) as a basis for the frame averaged networks in our work. Hard- ness results for learning feedforward neural networks have also been shown by proving reductions to average case or cryptographically hard problems (Chen et al., 2022a; Daniely & Vardi, 2020).
Though our work is focused on runtime lower bounds, some algorithms exist for learning restricted classes of geometric networks efficiently such CNNs (Brutzkus & Globerson, 2017; Du et al.,
2

---

Published as a conference paper at ICLR 2024
2017: 2018a). Zhang al. (2020); Li al. (2021) give algorithms learning one hidden layer GNNs via gradient based algorithms, which are efficient when certain factors such as the condition number of the weights are bounded. We should also note that for practical separations between SQ and CSQ algorithms, Andoni et al. (2014) show that learning sparse polynomials of degree d in n variables requires ((n")) CSQ queries, but often only (ndd) SQ queries. We extend this to polynomials in the invariant polynomial ring in Sec.
2 BACKGROUND AND NOTATION
We use and A to denote scalars, vectors, and matrices. In denotes the identity matrix of dimension n. We denote groups by G and graphs by G. We denote the normal distribution supported over R" with mean E R" and covariance matrix M E RT*" as (w, MM, often abbreviated as N for (0, I.). We also denote by On the set of graphs on n vertices and, when clear from context, an arbitrary distribution over Gn, To ease notation, we often use [n] to denote the set (1.....n).
Let X' be an input space and D a distribution on X. Given functions f.9: : X - R, their inner product is (f.g)p = Ep[íg] with corresponding norm ||/ - -U.. For functions f,g X {1,,+1} whose outputs are Boolean, the classification error is P. Pa-D
[ (xx + g(æ)).
2.1 SQ LEARNING FRAMEWORK
The well-studied statistical query (SQ) model offers a restricted query complexity based model for proving hardness, which encapsulates most algorithms in practice (Kearns, 1998; Reyzin, 2020). Given a joint distribution D on input/output space x V. any SQ algorithm is composed of a set of queries. Each query takes as input function g X x y + 1, and tolerance parameter 7 0, and returns a value SQ(g, r) in the range:
E(e.v)>D [g( (z, v)] r S SQ( S E(r.y)~ (g( y)] +
A special class of queries correlational statistical queries (CSQ), where the query function X' - [-1,1] is only function of x. and the oracle returns ( (g()) y) the correlation of 9 with y up error T.
Hardness is quantified as the number of queries required to learn a function c* (1x), drawn from a function class C up to desired maximal error. Notably, SQ hardness results imply hardness for any gradient based algorithm, as gradients with respect to a loss can be captured by statistical queries. Furthermore, only CSQ oracles are required for the mean-squared error (MSE) loss.
Example (GD from CSQ). Given a function Ng X' + R with parameters 0, gradients of the MSE loss with respect to 0 can be estimated with correlational statistical query for each parameter:
E(R.y)~< [ (y No(x))²] E
E[vVo.No(z)]
(2)
g independent
CSQ With
Access to the distribution D is typically provided through samples, and the tolerance in part captures the error in statistical sampling of quantities such as the gradient. In fact, by drawing (log(1//))/²)) samples, standard Hoeffding bounds guarantee estimates of a given query are within tolerance with probability 1 5. In the SQ (CSQ) framework, the complexity of learn- ing is determined by the tolerance bound and number queries (loosely corresponding to "steps" in algorithm) needed to lear a function class.
Definition (SQ (CSQ) Learning). Given function class C and distribution D over input space X. an algorithm SQ (CSQ) learns C' up classification error (l2 squared loss) if, given only SQ (CSQ) oracle access to (x. c (x)). x ~ 'D for some unknown c* E C, the algorithm outputs a function f such that P Pa~D (=) F c* (x)
(i.e. |lf c01l c).
SQ lower bounds for Boolean functions are typically shown by finding a set of roughly orthogonal functions that lower bound the so-called statistical dimension. For real-valued function classes, lower bounds on the statistical dimension imply CSQ lower bounds. Applying more general SQ lower bounds is challenging, unless reduces the problem of learning a real-valued function to that of learning a subset therein of (say) Boolean functions within the class (Chen et al., 2022a). We cover this in more detail and also discuss other learning theoretic frameworks in App. B.
3

---

Published as a conference paper at ICLR 2024
3 WARM UP: INVARIANT BOOLEAN FUNCTIONS
Before detailing our main results concerning real-valued functions, we explore the foundational context of Boolean functions where the SQ formalism originated (Kearns, 1998; Blum al., 1994). This illustrative analysis will serve as a warm-up for the more complex scenarios later. It is known that many classes of Boolean functions have exponential query complexity (e.g., the class of parity functions) arising from the orthogonality properties of Boolean functions. Enforcing invariance under given group G. the number of orbits of the 2n bitstrings gives an analogous hardness metric, though care must be taken in dealing with the distribution of these orbits.
More formally, in the Boolean setting, let input distribution D be uniform over (-1,+1)". For group G' with representation p. let O {((g) the orbits of the inputs under the representation. For any given orbit O Op, let æo denote an orbit representative (i.e., some fixed element in the set O). We can represent any symmetric function f:O,= + {-1, +1} as a function of these orbits, where the correlation of two functions f.g is
9 G} E +1])+ denote
(.g) - [ 2 Eo.eo, [0
(3)
The probability po. Op + [0, of a random bitstring falling in orbit Ox E Op is equal to po,(On, (Ox) 10+1/2", With this notation, we have a general lower bound on the SQ hardness of learning invariant Boolean functions.
Theorem (Boolean SQ hardness). For a given symmetry group G with representation p G
+[((-1,+1]"), let IIpo, = (Eoreo, ( [Oxl )/// and let Hp be the class of symmetric Boolean funecionss, defined as
Hp U
+ (-1,+1]: Vg E G, Ve {-1,++1]" H(ls) x)) = f())} (4)
Any SQ learner capable of learning Hop up to sufficiently small classification error probability (E < 1/4 suffices) with queries of tolerance T requires at least 11 queries.
Proof sketch. We show that - ||o,,|12 is the probability that, over independently drawn inputs x, x', the distribution (f(x), fxx') )) is uniformly random over f drawn uniformly from Hp. From a proof technique in Chen et al. (2022a), this connects the task to one of distinguishing distributions, for which the SQ complexity is at least the stated amount. See App. C for complete proof.
For a more direct lower bound, we can use Hölder's inequality such that IIpo, ge
I maxo, |Ox| S |G|2-". This gives query complexity of at least 2-- For com-
monly studied groups, assuming = 0(1, the SQ complexity generally aligns with the number of orbits. Table summarizes these hardness lower bounds for commonly studied groups'.
Group
maxo, 10
Query Complexity
(.722
Symmetric group on bits
@(vn)
O(vT)
Symmetric group X n graphs
n! 2n 2 2- +n O(()
(2(0(n)))
Cyelic group bits
9/22//m
Table 1: Query complexity of learning common invariant Boolean function classes.
4 LOWER BOUNDS FOR GNNS
We now show statistical query lower bounds for graph neural networks, which are invariant to node permutations, in three settings: (1) SQ lower bounds scaling with the number of nodes n for Erdös-Rény Rényi distributed graphs with trivial node features, (2) CSQ lower bounds scaling in the node feature dimension for a fixed graph, and (3) simple extension of NP hardness in a proper learning task (deciding if fitting training set with given GNN is possible).
!Certain sub-classes of Ho may suffice to attain hardness, much like how Parity functions suffice to prove exponential lower bounds in the traditional Boolean setting. We do consider this strengthening here.
4

---

Published as a conference paper at ICLR 2024
4.1 HARDNESS IN NUMBER OF NODES
We consider a class of two hidden layer GNNs that are only a function of the adjacency matrix, and show hardness in the number of nodes n. This covers commonly used procedure where learns node-level equívariant features in the first layer, aggregates these features, and passes them through an MLP (Dwivedi et al., 2020). We consider a Boolean function class of GNNs over the uniform distribution Uni 1)"x"), which can be viewed as the Erdös-Rényi random graph model with p 0.5.² Node features IR" are trivial and always set to x
2 hidden layer GNN family We consider two layer GNNs
-(2) f(). These take the
commonly used form of message passing, f()) [00, 1 ]|nxx - R& which aggregates k permutation
invariant features for the graph, followed by single hidden layer ReLU MLP f(2) (R + {0,
U2 (A)]; 1,,0 (a, + Axr (output of channel E [K1])
(5)
f w (h) Σ k2
u.o(WW h) + v4),
with subscripts for trainable weights. For our hard class of functions, k1 = ((n) and k2 O()) so there are at most Onn²) parameters (proportional to the number of edges).
Family of hard functions We define the hard functions in terms of degree counts CA E [n]*+], where entry [ca]: counts the number of nodes that have - 1 outgoing edges in A:
" Σx k=
[cA]:
[[A1]] =i-1] 1].
(6)
The hard functions in HER. are enumerated over subsets S S [n + 1] and a bit 6 {0,
HER [g5, S [m + 11,6 {0, (s
EsegIcal: mod 2.
(7)
(..((A) is sort of parity function supported over integers in CA in S. We show in Lemma 15 that the GNNs in Eq. (5) can construct these functions. Additionally, the class HERR. is Boolean, so hardness lower bounds apply in the general SQ model.
Theorem (SQ hardness of HERR). Any SQ learner capable of learning HER, up to classifica- tion error probability sufficiently small (e < 1/4 suffices) with queries of tolerance requires at least ex)xp(((()) queries.
Proof sketch. We form networks that in the message passing layer calculate CA, which is passed to the MLP calculating Eq. (7) as a sum of ReLUs via hat-like functions that mimic parities. Based on concentration properties of the Erdös-Rényi model, we show that for some p < 0.5, at least ((n)) entries of CΛ will have values scaling roughly as (vyr) and the probability that any such entry odd converges to 1/2. Also using concentration properties, we condition on a high probability region (where probability of these entries being odd are roughly independent from each other), and use hardness of learning parity functions to get SQ lower bounds.
4.2 HARDNESS IN FEATURE DIMENSION
In this section, we derive correlational statistical query lower bounds (CSQ) for commonly used graph neural network architectures (GNNs), and state the corresponding learning-theoress hardness result. The techniques in this section extend those of Diakonikolas et al. (2020), resulting in an exponential (in feature dimension) lower bound for learning one-hidden layer GNNs.
1-hidden layer GNN For fixed directed, unweighted graph G with E N vertices, let A(G) E and width
Raxn be the adjacency matrix or the Laplacian of G. For input feature dimension parameter A E IN, we consider the following set of functions:
Fds {s: Raxd_ + R, S(X) X)))))() W E Rdx2k a R2k
(8)
for some nonlinearity a. When the graph itself is part of the input, have the function class:
pd,k = {f Raxd x Cn + R, f(X,9f
1, (AG))
W 2d a R2*
(9)
*Our exponential lower bounds arise from the wide range of possible degrees of nodes in the graph. Though we da not generalize this result, this fact means that it is likely extendable to restricted sparse Rédós-Rényi models G(n,pa) Pn) where Pr. w(1/n) (i.e. average degree grows arbitrarily with n))
5

---

Published as a conference paper at ICLR 2024
Family of hard functions fo(X) o (A(G)XW")a' a', (x 1,20 (A(G)xW") a² (10)
First, we define functions fg RR*x - R and fn : R x Gn R Ras
W (cos(TTj/H)) kk) [2() (sin(T]) jE(Ss]]
where
E R2x2
a" ((-1)²) jE(2A] E RR*
(11)
Given set of matrices B < Rdx2, our family of hard functions can now be written as: c= = 99 x f B C = g (X.9)= H I
BX
fx(XB.g)
B
(12)
Below, we show exponential lower bounds for learning Fight and Fdikk:
Theorem (Exponential CSQ lower bound for GNNs). For any number of vertices n independent
of input dimension d and width parameter k, let e > 0 be a sufficiently small error constant and & a distribution over Gn, independent of N. with Pre(((}) < 2211) < 1. Then there exists a set B of size at least 20(d)()) such that any CSQ algorithm that queries from oracles of concept f E C (resp. Chi and oulputs a hypothesis h with |ʃ hlll (resp. || hillxxe S e) requires either
2000 queries or at least one query with precision d Q(k) + 2- 2-000)
Proof sketch. Full details of the proof can be found in App. E. From Lemma 17 of Diakonikolas et al. (2020), there exists a set B C Rdxx of size at least 20((00)) such that
|B B'Il2 = Old-O(())))))) <
(13)
and B B 12 which we use to index C.. We design specialized class of invariant orthogonal Hermite polynomials, such that the correlation in low degree moments vanishes and is bounded as:
(Jg(-B) (B) Sg(- (l S | B'I Σ m>ik |1 l&
B B Soll..
(14)
Finally, Eq. (13) to get the desired almost uncorrelatedness of elements in Cy and use simple total probability argument extend this C
4.3 NP HARDNESS OF PROPER LEARNING OF GNNS
The classic work of Blum & Rivest (1988) showed that there exist datasets for which determining whether or not 3-node neural network can fit that dataset is NP hard. straightforward to prove a similar result for invariant networks. We map the task of training single hidden layer GNN to the NP hard problem of learning halfspaces with noise (Guruswami & Raghavendra, 2009; Feldman et a 2012). Here, one is given set of N labeled examples {ar; ys ) and must determine whether there exists a halfspacce parameterized by vector v and constant / that correctly classifies specified fraction of the labels such that sign ((v, æ.)) 0) = y/. We map GNN learning problem to this task, as informally described below and formally detailed in App. D.
Proposition 5 (NP hardness of GNN training: informal). There exists a sequence of datasets in- dexed by the number of nodes n, each of the form (A;, F., De N.N where y: E +1], such that determining whether a GNN with parameters a, b R c R and = O(n) of the form
fa,bo( A)= => At
relu (æ + ax b; I
(15)
i=1
can correctly classify specific fraction of the data is NP hard.
5 CSQ LOWER BOUND FOR CNNS AND FRAME AVERAGING
Several commonly used invariant architectures take the form of symmetrized neural networks over permutation subgroups G < S,, which can be generalized as frame-averaging architectures (Puny et al., 2023). This includes translation invariant CNNs, group convolutional networks, and networks with preprocessing steps such as sorting. We study the hardness of learning these invariant functions.
"To have meaningful set of functions, of and g. must not vanish, which holds when ar is not low-degree polynomial (ReL.U suffices, see Remark 12 of Diakonikolas al. (2020)) and & 전 (graph with edges).

---

Published as a conference paper at ICLR 2024
Frame averaging and its connection with CNNs. Let G be subgroup of the permutation group Sn that acts on Raxd by permuting the rows. A frame is a function F Raxd + 2% satisfying F)) gF((X) set-wise. As noted in Puny al. (2023), given some frame F, one can transform an arbitrary function (or neural network) )) into an invariant function by averaging its values as [XX]] ) higg For instance, setting VX F(X) G recovers the Reynolds (or group- -verrging) operator. Given fixed frame F, we will first show CSQ lower bounds for the following class of frame-averaged one-hidden-layer fully connected nets:
Hl
Σ f: f:Raxd R, +R ((x)) VIF(X) gET(X)
a ( W E R a E Rk
for some nonlinearity
Example (Frame for CNN). Set d and let G be the cyclic group acting on R" via eyclic shifts of its elements with frame F(X) = G, VX E R". Then, Fü consists of CNNs with one convolutional layer and hidden channels.
Remark 6 (Difficulty of frames). Since the frame F(X) may vary by datapoint X, the distribution Unif(F(XX) (x) X can be significantly different from the original distribution over X, even if X g.X for all g. For example, consider the frame F(X) containing all permutations that sort X lexicographically (where [F(X) > if X contains a repeated row). Even if X N with W invariant to row- now-permutation, the resultant distribution is not row permutation invariant.
We focus on certain cases where such effeets not too pronounced. For instance, it is simple to check that if F(X) is constant over X, then F(X) = G V (Lemma 28). In the following, we assume that G is polynomial-sized (in n) subgroup of S..
Family of hard functions.
Recall the dinddimesioona function from the proof of Theorem 4: Sexp : R2xd + IR with f(X) = =(a") ((W*) X)
(16)
for some special parameter a" E R2h and W E R2x2k in Eq. (11). We now define the family of hard functions, indexed by a set of matrices
RTx2 obtained from Lemma 29:
Cf = {SBB RRad + R with gB (X) = Egec fixp (BT9 X VIGI /IGo-Ilfxxplll IIf
B
(17)
Theorem 7 (Exponential CSQ lower bound for polynomial-sine sized group averaging). For feature dimension d independent of inputs n and width parameter k (n).. let e 0 be sufficiently small error constant. Then there exists set B of size at least 20 /|G/ such that: for any target CF with ||gl|x = 1, any CSQ algorithm outpulting hypothesis h with l|g hil S
requires either 20) /|G|2 queries or at least one query with precision [G|2-=00) G -2())
Proof sketch. Using a union bound argument over the original set B from Diakonikolas al. (2020), and concentration of inner product between permuted unit vectors, we obtain from Lemma 29 a set of orthogonal matrices B' such that both | (B)"II and [(g (g' B'J"II are small VB + B' B', Ng + 9 E G. This construction costs a factor of |G|2 in BB). The rest of the proof proceeds similarly; see App. F.I.
We also obtain superpolynomial lower bounds for more general frames using the technique of Goel et al. (2020). Here, we drop the assumption that G polynomially-sized. The hard functions are based on parity functions, similar to Goel et al. (2020) (but with an extra input dimension for X):
Is x + R with fs(X) = I
Σ
x(w)a((w, Xs) Xs)/Vm))
S Sm [n]] (18)
WE (-1,11
where S.. indicates a size m subset, X is the parity function x(w) = II. we and Xs E Rmxd denotes entries of X in S. Here, (w, Xs) == Σm (Xx)), and a : Rd -> Rd is an activation function. The hard invariant function class consists of frame-averages of the functions above:
H.s.F = fs : x + R with f(X)
{ss
Σ f 'x) S C. [n]] (19)
VIF(X)
9EF(X)
7

---

Published as a conference paper at ICLR 2024
Below, we show a hardness result for this class inspired by that of Goel et al. (2020), whenever the frame F is sign invariant: F(X)= = =[x x) for almost all X and for all x E {-1,
Theorem 8 (Superpolynonial CSQ lower bound for sign-invariant frame averaging). If is sign- invariant frame, then for any c > 0, any CSQ algorithm that queries from an oracle of concept I E Hs.F and output a hypothesis h with || 157-hila hillx S @ needs at least M(n (a)) queries or at least one query with precision O(n where (n) is the size of the largest orbit of size m S log(n) subsets of [ni] under G. If moreover [F(X) 1 for almost all X (a "singleton" frame), then the same result holds with M (n) replaced by 1.
Proof sketch. The proof hinges on the structure of fs. and in particular that applying g to the input of fs yields fas. The sign-invariance of F is necessary to ensure that the proof of Goel et al. (2020), which involves introducing random sign-flips, goes through. See Lemma 33 for the full proof. O
Example 3 (Singleton frames), An example of such a frame is the lexicographical sorting of X E RRnx according to the absolute value of the entries (to make the frame sign-invariant). With probability 1, X does not have any repeated values, and thus there is unique lexicographical sort for X almost surely. In fact, for any group G, singleton frame exists if X has no self-symmetry with probability 1, i.e. X + g. for all g E G.
For the hard class function to be nonvanishing, we show in Corollary 39 that at least a superpolynomial-sizeer subset of Hs.F has norm lower-bounder by (((pol(n))-1 assuming that [F()) is polynomial in n almost surely ((G) does not have to be polynomial in nt).
SEPARATION BETWEEN SQ AND CSQ FOR INVARIANT FUNCTION CLASSES
A natural question is whether there exist real-valued function classes which are hard to learn in the CSQ setting (and hence by gradient descent with mean squared error loss), but efficient learn via a more carefully constructed non-CSQ algorithm. In the general (non nooniinvrriant) setting, one such separation is that of learning k-sparse polynomials, i.e., degree d polynomials in n variables expressible as sums of only k unique monomials over inputs drawn from a product distribution D = X=, 14. Here, an efficient SQ (but not CSQ) algorithm called the GROWING-BAN -BSISS algorithm is known from Andoni et al. (2014). CSQ algorithms require 2(x²) queries corresponding to the number of degree d orthogonal polynomials, but the GROWING-BASIS algorithms learns with (d)) SQ queries, where fdd may be exponential in d but independent of n. We informally illustrate the invariant extension of this here, leaving complete details to App. G.
To perform this extension, we apply GROWING-BASIS to more general spaces (so-called 'rings') of invariant polynomials whose basis consists of independent invariant functions or 'generators' {g: E R[xz] R[ for some E N. Independence here asserts that any 9: cannot be written as polynomial in the others. The space of all polynomials in (x( with degree d and sparsity k (both in g 's expansion) is denoted by R[g1
gr (z))a, We have the following separation result:
Lemma 9 (informal). Let x ~ D such that the induced distribution of (ge(x)) ketr) is a product distribution. Then any CSQ algorithm that learns E Rigi (z)....,
... Gr gr(x)) ( of degree most d Olog n) to a small constant error requires Qy CSQ queries of bounded tolerance. However, the GROWING BASIS algorithm learns f with 2kr logr) r) SQ queries of precision 2211 (ooy)(r)))
A more rigorous exposition and proof is prepared in App. G. Finding independent generators it- self can be a challenging task; however, we provide an example below, and more in App. G, for separations over groups where r = [(()) generators are known (Derksen & Kemper, 2015).
Example 4. The sign group G flips the sign of input elements and is commonly used to study eigenvectors (Lim et al., 2022). G is indexed by vectors v E +-1,++1" with representation p(v)- x O where O represents pointwise multiplication. Consider generators 91.... In where (xx = |.). For inputs x ~ Unif([-1, +1]"), the distribution of (z)........ 9n (x)] is a product distribution (n. 11m) with the "shifted" Legendre polynomials the orthogonal polynomials. For d at most O n.), any CSQ algorithm requires ((n") queries of bounded tolerance to learn these polynomials, whereas the GROWING-BASIS algorithm learns in O(kn² log n) SQ queries.
8

---

Published as a conference paper at ICLR 2024
0.6
Train Set
MSE 0/1 Error
Train Set
MSE
Test Set
10"
Test Set
0.5
Error (log axis)
Error
10 2
0.4
10-4
0
200
400
600
800
1000
100
200
300
400
500
Epoch
Epoch
(a) GNN learning HER.
(b) CNN learning C
Figure 1: Overparameterized GNN (a) and CNN (b) fail to learn functions from the class HER. and C respectively by either failing to fit the training set or overfitting the data. Plots are aggregated and averaged over five random realizations.
EXPERIMENTS
We train overparamettrrzze GNNs and CNNs on the hard functions from Sec. and Sec. 5, respec- tively. Specifically, we attempt to learn relatively small instances drawn from the function classes HER.. for graphs (Theorem 3) and C for translationally invariant data (Theorem 7). For the func- tion class H.n., we consider n = 15 node inputs and the target function Is.6 where S C [r]] is random subset of size 7 and b is either 0 or 1 at random. For the function class C we choose a random orthogonal matrix B and then symmetrize the function class as per Eq. (17).
Fig. Ia and lb plot the performance of the GNN and CNN respectively. The GNN is unable to fit even the training data consisting of 225 n 15 node graphs drawn uniformly from the Erdös-Rényi model (i.e., p 0.5). The CNN trained on n 50 dimension inputs fits the training set of size 500 appropriately, but fails to generalize in the mean squared error loss. The GNNICNN were overparameterized with 3 layers of graph/cyclic convolution followed by a two layer ReLU MLP on the aggregated invariant features. We refer the reader to App. H for further details.
8 DISCUSSION
Our study asked how hard it is to learn relatively simple function classes constrained by symme- try. Setting aside mathematical formality, one may conjecture that such function classes are good representations or approximations of the data observed in nature. Our results indicate that such an least in worst-case settings, where we show such assumption is unlikely to be realistic one Provable guarantees of learning will have to incor- functions would be exponentially hard to learn. porate further assumptions in the model class or biases in training to better account for the practical success of learning algorithms (Lawrence et al., 2021; Gunasekar et al., 2018; Le & Jegelka, 2022).
We now state potential directions for future work and conjectures. It would be interesting extend our hardness results beyond the SQ setting or to apply to continuous groups. For example, a natural question is whether symmetric functions are cryptographically hard to learn, as shown Chen al. (2022a) for two hidden layer ReLU networks. A line of work in probability and statistics has identi- fied barriers to many algorithms solving average-case settings of classic optimization problems, such as max cut or largest independent set. These include the overlap gap property (Gamarnik, 2021) and bounds on low degree algorithms (Hopkins & Steurer, 2017; Brennan et al., 2020). Whether these barriers extend to the types of problems studied in geometric deep learning is an open question. We should note that there are restricted settings where learning neural networks is possible (see App. A). Recent work (Chen et al., 2022b; Chen & Narayanan, 2023) has shown that ReLU networks with (11) hidden nodes are learnable in polynomial time. Extending this result to invariant network classes with (11) channels would similarly expand the set of learnable invariant networks.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
The authors thank Sitan Chen for insightful discussions and feedback. BTK and MW were supported by the Harvard Data Science Initiative Competitive Research Fund and NSF award 21 12085. TL and SJ were supported by NSF awards 2134108 and CCF-2112665 (TILOS AI Institute), and Office of Naval Research grant 100114200-1220 (MURI ML-SCOPE), HL supported by the Fannie and John Hertz Foundation and the NSF Graduate Fellowship under Grant No. 1745302.
REFERENCES
Emmanuel Abbe and Colin Sandon. Polynomial-time universality and limitations of deep learning. Communications on Pure and Applied Mathematics, 76(1 (((11)33493-5444 2023.
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and L.i Zhang. Learning sparse polynomial func- tions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete al algorithms, pp. 500-510. SIAM, 2014.
Eric R Anschuetz and Bobak T Kiani. Quantum variational algorithms are swamped with traps. Nature Communications, 13(1):7760, 2022.
Eric R Anschuetz, Andreas Bauer, Bobak T Kiani, and Seth Lloyd. Efficient classical algorithms for simulating symmetric quantum systems. arXiv preprint arXiv:2211.1699 16998, 2022.
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two lectriiid neural networks in polynomial time. Conference on Learning Theory, pp. 195-268. PMLR, 2019.
A Barvinok. Measure concentration lecture notes. edu/harvinok//toal/100, pdf, 2005.
See http://www. math. Isa. umich.
Simon Batzner, Albert Musaelian, Lixin Sun, Mario Geiger, Jonathan P Mailoa, Mordechai Ko- mbluth, Nicola Molinari, Tess Smidt, and Boris Kozinsky. E (3)-equivariant graph neural networks for data-efficient and accurate interatomic potentials. Nature communications, 13(1): 2453, 2022.
Arash Behboodi, Gabriele Cesa, and Taco S Cohen. pac-bayesian generalization bound for equiv- ariant networks. Advances in Neural Information Processing Systems, 35:5654-5668, 2022.
Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity learning under geometric stability. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: wwwp///eeeeeeeeeeoooeeeeeeeooeee net forum?
[d=vif02TKa550
Avrim Blum and Ronald Rivest. Training 3-node neural network is np-complete. Advances in neural information processing systems, 1, 1988.
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 253-262, 1994.
Matthew Brennan, Guy Bresler, Samuel B Hopkins, Jerry Li, and Tselil Schramm. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint arXiv:2009.06107 2020.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint 1144::2200.13478 2021.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian inputs. In International conference machine learning, pp. 605-614. PMIR, 2017.
Yuan Cao and Quanquan Gu. Tight sample complexity of learning one- eee-hidden-layyee convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2024
Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky. The Vex geometry of linear inverse problems. Foundations of Computational Mathematics, 12(6): 805-849, 2012. doi: 10.10077/100088-122-913333 s. 01002-00222 02228-012-9115-17
URL
Sourav Chatterjee. Supercomccetration and Related Topics. Springer Cham, 2014. http://
example. htt///ootor/e.oce../.ecc of htt.ttiee.ppii.... pdf((iiited 2016-01-01).
Sitan Chen and Shyam Narayanan. A faster and simpler algorithm for learning shallow networks.
arXiv preprint arXiv: 2023.
Sitan Chen, Aravind Gollakota, Adam Klivans, and Raghu Meka. Hardness of noise-free free learning for two-hidden-laye neural networks. Advances in Neural Information Processing Systems, 35: 10709-10724, 2022a.
Sitan Chen, Adam R Klivans, and Raghu Meka. Learning deep relu networks is fixed- parammer tractable. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pp. 696-7077 IEFE, 2022h.
Sitan Chen, Zehao Dou, Surbhi Goel, Adam Klivans, and Raghu Meka. Learning narrow one- hidden-layer relu networks. In The Thirty Sixth Annual Conference Learning Theory, pp. 5580-5614. PMLR, 2023.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10395, 2020.
Ziyu Chen and Wei Zhu. On the implicit bias of linear equivariant steerable networks: Margin, generalization, and their equivalence to data augmentation. arXiv preprint arXiv:2303.04198 2023.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pp. 1305-1338. PMLR, 2020.
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physies, 15(12):1233-1278 2019.
Amit Daniely. Complexity theoretic limitations learning halfspaces. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 105-117, 2016.
Amit Daniely and Gal Vardi. Hardness of learning neural networks with natural weights. Advances in Neural Information Processing Systems, 33:930-940, 000900000--00 2020.
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average complexity to improper learning complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 441 441-44 2014.
Amit Daniely, Nathan Srebro, and Gal Vardi. Most neural networks almost learnable. arXiv preprint 2rXiv:2305.16500 2023.
Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, and Rina Panigrahy. On the learnability of deep random networks. arXiv preprint 1904 03866, 2019.
Giacomo De Palma, Bobak Kiani, and Seth Lloyd. Random deep neural networks are biased towards simple functions. Advances Neural Information Processing Systems, 32, 2019.
Harm Derksen and Gregor Kemper. Computational invariant theory. Springer, 2015.
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73-84, 2017. doi: 10.1109/FOCS.
2017.16.
Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one- heddhd----llerr relu networks. In Conference on Learning Theory, pp. 1514-1539. PMLR, 2020.
11

---

Published as a conference paper at ICLR 2024
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learss ane-hidden-layer cnn: Don't 't be afraid of spurious local minima. In International Conference on Machine Learning, pp. 1339-1348, PMLR, 2018a.
Simon Du and Surbhi Goel. Improved learning of one-hidden-layer convolutional neural networks with overlaps. arXiv preprint arXiv: 11008887599999 2018.
Simon Du, Jason D Lee, and Yuandong Tian. When a convolutional filter easy to learn? arXiv 1 709.06129, 29,1299922 2017.
preprint Xiv:
Simon S Du, Yining Wang. Xiyu Zhai, Sivaraman Balakrishnan, Russ R Salakhutdinov, and Aarti Singh. How many samples are needed to estimate a convolutional neural network? Advances in Neural Information Processing Systems, 31, 2018b.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
Bryn Elesedy. Provably strict generalisation benefit for invariance in kernel methods. Advances in Neural Information Processing Systems, 34:17273-17283, 2021.
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. Agnostic learning of monomials by halfspaces is hard. SIAM Journal Computing. 4156):15 2012.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint 1rXiv:1903.02423 2019.
David Gamarnik. The overlap gap property: A topological barrier to optimizing over random struc- tures. Proceedings of the National Academy of Sciences, 118(41):e2108442211 2021.
Floris Geerts and Juan L Reutter. Expressiveness and approximation properties of graph neural networks. arXiv preprint arXiv:2204.046611 2022.
Surbhi Goel, Adam Klivans, and Raghu Meka. Learning one convolutional layer with overlapping patches. In International Conference on Machine Learning, pp. 1783-1791. PMLR, 2018.
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolyno- mial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, pp. 3587-3596. PMLR, 2020.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances neural information processing systems, 31, 2018.
Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noise. SIAM Journal Computing, 39(2):742-765, 2009.
Samuel B Hopkins and David Steurer. Bayesian estimation from few samples: community detection and related problems. arXiv preprint arXiv:1710.00264 2017.
Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint MwXiv:2204.07697, 2022.
Ziwei Ji and Matus Telgarsky. Directional convergence and aligmment in deep learning. Advances in Neural Information Processing Systems, 33:17176-11 17186, 2020.
J Stephen Judd. Learning in networks is hard. In Proc. of 1st International Conference on Neural Networks, San Diego, California, June 1987, IEEE, 1987.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang. Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in neural information processing systems, 32, 2019.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. (JACM), 45(6)9983-1066 1998.
Journal of the ACM
12

---

Published as a conference paper at ICLR 2024
WF Kibble. An extension of a theorem of mehler's hermite polynomials. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 41, pp. 12-15. Cambridge Univer- sity Press, 1945.
Adam Klivans and Pravesh Kothari. Embedding hard learning problems into gaussian space. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROXIRANDOM 2014). Schloss Dagstubl-LLcibnizzZZnttu fuer Informatik, 2014.
Mihail N Kolountzakis, Evangelos Markakis, and Aranyak Mehta. Learning symmetric k-juntas in time n' (k). arXiv preprint math/0504246, 2005.
Hamnah Lawrence, Kristian Georgiev, Andrew Dienes, and Bobak Kiani. Implicit bias of linear equivariant networks. arXiv preprint arXiv:21 10.06084, 2021.
Thien Le and Stefanie Jegelka. Training invariances and the low-rank phenomenon: beyond linear networks. In International Conference on Learning Representations, 2022. URL https:// openreview net ttt:://ormmmddd//// f
Qunwei Li, Shaofeng Zou, and Wenliang Zhong. Learning graph neural networks with approximate gradient descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8438-8446, 2021.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach generalization bounds for graph neural networks. arXiv preprint arXiv:2012.07690, 2020.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv
preprint arXiv:2202.1301. 2022.
Richard Lipton, Evangelos Markakis, Aranyak Mehta, and Nisheeth K Vishnoi. On the fourier
spectrum of symmetric boolean functions with applications to learning symmetric juntas. In 20th Annual IEEE Conference on Computational Complexity (CCC pp. 112-119. IEEE, 2005.
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. Advances in neural information processing systems, 27, 2014.
Philip M Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks.
arXiv preprint 1905. 12600, 2019.
Andreas Loukas What graph neural networks cannot learn: depth vs width. arXiv preprint 1rXivv1907.0311 2019.
Shaogao Lv. Generalization bounds for graph convolutional neural networks via rademacher com- plexity. arXiv preprint 2xii:2102.100244 2021.
I GG Macdonald. Symmetric functions and Hall polynomials / by I. Oxford University Press, Oxford New York, 1979.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. Conference on Learning Theory, pp. 3351-3418, PMLR, 2021.
Johannes Jakob Meyer, Marian Mularski, Blies Gil-Fuster, Antonio Anna Mele, Francesco Arzani, Alissa Wilms, and Jens Eisert. Exploiting symmetry in variational quantum machine learning. PRX Quantum, 4(1 4(1):010328, 2023.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 2019.
Elchanan Mossel, Ryan O'Donnell, and Rocco P Servedio. Learning juntas. In Proceedings of the thirty-fifth annual ACM symposium Theory of computing, pp. 206-212, 2003.
13

---

Published as a conference paper at ICLR 2024
Quynh T Nguyen, Louis Schatzki, Paolo Braccia, Michael Ragone, Patrick J Coles, Frederic Sauvage, Martin Larocca, and M Cerezo. Theory for equivariant quantum neural networks. ar preprint urXiv:2210.085666 2022.
Samet Oymak and Mahdi Soltanolkotabi. End-to-end learning of a convolutional neural network via deep tensor decomposition. arXiv preprint arXiv: 10:::180) (85.00555.... 2018.
Ian Parberry. Circuit complexity and neural networks. MIT press, 1994.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Arthur Pesah, Marco Cerezo, Samson Wang. Tyler Volkoff, Andrew T Sornborger, and Patrick Coles. Absence of barren plateaus in quantum convolutional neural networks. Physical Review X. 11(4):04001, 2021.
Mircea Petrache and Shubhendu Trivedi. Approximationn-eeealliaaooooo trade-offs under (approxi- mate) group equivariance. arXiv preprint 1xXXx 2023.
Gilles Pisier. Probabilistic methods in the geometry of banach spaces. In Giorgio Letta and Maurizio Pratelli (eds.). Probability and Analysis, pp. 167-241, Berlin, Heidelberg, 1986. Springer Berlin Heidelberg. ISBN 978 978-3-540-40955-7.
Omri Puny, Derek Lim, Bobak T Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks. arXiv preprint arXiv:2302. 1556, 2023.
Michael Ragone, Paolo Braccia, Quynh T Nguyen, Louis Schatzki, Patrick J Coles, Frederic Sauvage, Martin Larocca, and Cerezo. Representation theory for geometric quantum machine learning. arXiv preprint arXiv:2210.079800 2022.
Lev Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00557 2020.
Akiyoshi Sannai, Masaaki Imaizumi, and Makoto Kawano. Improved generalization bounds of group invariant/equivariant deep networks via quotient feature spaces. In Uncertainty in Artificial Intelligence, pp. 771-780. PMLR, 2021.
Louis Schatzki, Martin Larocca, Frederic Sauvage, and Marco Cerezo. Theoretical guarantees for permutation--qquiiarian quantum neural networks. arXiv preprint arXiv:2210.09974 2022.
Hanie Sedghi, Majid Janzamin, and Anima Anandkumar. Provable tensor methods for learning mixtures of generalized linear models. In Artificial Intelligence and Statistics, pp. 1223-1231.
PMLR, 2016.
Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Praneeth Netrapalli, The pit- falls of simplicity bias neural networks. Advances in Neural Information Processing Systems, 33:9573 9985,,9555518 2020.
Ohad Shamir. Distribation-specific hardness of learning neural networks. The Journal of Machine Learning Research,
2018.
Andrea Skolik, Michele Cattelan, Sheir Yarkoni, Thomas Bäck, and Vedran Dunjko. Equivariant quantum circuits for learning on weighted graphs. npi Quantum Information, 91))47, 2023.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization error of invari- ant classifiers. Artificial Intelligence and Statistics, pp. 1094-1103. PMLR, 2017.
Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural net- works. Advances in neural information processing systems, 30, 2017.
14

---

Published as a conference paper at ICLR 2024
Min Jae Song, Ilias Zadik, and Joan Bruna. On the cryptographic hardness of learning single periodic neurons. Advances neural information processing systems, 34:29602-29615, 2021.
Joel Spencer. Asymptopia. volume 71. American Mathematical Soc., 2014.
Balázs Szörényi. Characterizing statistical query learning: simplified notions and proofs. In International Conference on Algorithmic Learning Theory, pp. 186-200. Springer, 2009.
Behrooz Tahmasebi and Stefanie Jegelka. The exact sample complexity gain from invariances for kernel regression on manifolds. arXiv preprint arXiv:2303.14265 2023.
Michel Talagrand. On Russo's Approximate Oero-One Law. The Annals of Probabilityy. 22(3):1576 1587, 1994. doi: 10. 11 14.2244/00/117766862222 URL /ttpss///6ll..rr/111.111
1176988612.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, (7(11): (::1:):11114111 1142244-1,,,, 1984.
Guillermo Valle-Perez, Chico Camargo, and Ard A Louis. Deep learning generalizes because the parameter-function map is biased towards simple functions. arXiv preprint arXiv: www::880,.k0 005.08522, 2018.
Gal Vardi. On the implicit bias in deep-learning algorithms. Communications the ACM, 66(6): 86-93, 2023.
Santosh Vempala and John Wilmes. Gradient descent for one-hidden-laye layer neural networks: Poly- nomial convergence and sq lower bounds. In Conference on Learning Theory, pp. 3115-3117. PMLR, 2019.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Dian Wang, Robin Walters, and Robert Platt. So(2)-equivariant reinforcement learning. In International Conference on Learning Representations, 2021.
Melanie Weber, Manzil Zaheer, Ankit Singh Rawat, Aditya Menon, and Sanjiv Kumar. Robust large-margin learning in hyperbolic space. Advances in Neural Information Processing Systems, 33:17863-17873, 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A com- prehensive survey graph neural networks. IEEE transactions neural networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. unifying view on implicit bias in training linear neural networks. arXiv preprint arXiv:2010.02500 2020.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arx preprint 1XXi:22001.0950: 2023.
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Fast learning of graph neural networks with guaranteed generalizability: one-hidden-layer case. In International Conference on Machine Learning, pp. 1 11268-111 11277. PMLR, 2020.
Yuchen Zhang, Jason Lee, Martin Wainwright, and Michael I Jordan. On the learnability of fully- connected neural networks. Artificial Intelligence and Statistics, pp. 83-91. PMLR, 2017.
Kai Zhong, Zhao Song, and Inderjāt S Dhillon. Learning non-overlapping convolutional neural networks with multiple kernels. arXiv preprint arXiv:1711.03440 2017.
Pan Zhou and Jiashi Feng. Understanding generalization and optimization performance of deep cnns. In International Conference on Machine Learning, pp. 5960-5969, PMLR, 2018.
15

---

Published as a conference paper at ICLR 2024
TABLE OF CONTENTS
Extended related works
16
B Extended background into learning frameworks
18
C Boolean statistical query setting
19
D Complexity theoretic hardness extension
20
GNN hardness proofs
22
E.1 Lower bound for Erdös-Rény' distributed graphs
22
E,2 Invariant Hermite polynomial
E.3 Proof of Theorem 4
29
F
Frame-Averaging hardness proofs
32
F.1
Exponential lower bound for constant frame and Reynolds operator
32
F2 Superpolynomial lower bounds
36
F3 Proof of extra tools
Learning invariant polynomials
44
H Experimental Details
47
A EXTENDED RELATED WORKS
Restricted learning algorithms for CNNs and GNNs Various works show that convolutional and graph neural networks can be efficiently learned under various assumptions on the form of the network. For given input distributions, Brutzkus & Globerson (2017); Du et al. (2017) give an efficient learning algorithm for learning single convolution filter and Zhong al. (2017) give a of polynomial number of convolution kernels applied to an input. These can be viewed as a single hidden layer network where the last layer weights are all equal to one. Du & Goel (2018) (improving Goel et al. (2018)) give polynomial time algorithm for learning single layer convolutional networks (not necessarily invariant) with filters that have stride at least half the filter width. These CNNs have single channel but not invariant to the cyclic group due to the presence of weights in the second layer that vary by each patch of the filter. Similarly, Du al. 8a) show that gradient descent also learn networks of similar form with non-overlapping patches in the random setting (weights are random) with high probability. Oymak & Soltanolkotabi (2018) learn convolutional networks of depth 1) layers with single kernel per layer and make similar assumption that stride is at least as large width. Zhang et al. (2020); Li al. (2021) provide learning algorithms for a class of one hidden layer GNNs via gradient descent based algorithms whose sample complexity and runtime depend on factors like the condition number or norm of the weights of the target function. These algorithms are only guaranteed to polynomial in runtime for the restricted instances when such factors are appropriately bounded.
polynomial time algorithm for learning
Learning feedforward neural networks The study of the hardness of learning feedforward nueral networks has rich history dating back many decades. Judd (1987); Blum & Rivest (1988) show that in the proper learning setting. it is NP complete find set of weights of a given network that fits given training set. These results were later expanded in (Zhang et al., 2017) to more realistic settings. Many works study the hardness of improperly learning the class of ReLU feedforward networks. In
16

---

Published as a conference paper at ICLR 2024
the SQ setting, Goel et al. (2018); Diakonikolas et al. (2020); Song et al. (2017) show that at least a superpolynomial number of queries are needed to learn even single hidden layer networks in the correlational statistical query model. Chen et al. (2022a) show that networks with two hidden layers are even hard in the general SQ setting by using the networks to round inputs to boolean inputs and applying hardness results from Boolean learning theory and cryptography. We should remark that there are also other papers that reduce the task of learning feedforward neural networks to average case or cryptographically hard problems (Song et al., 2021; Daniely & Vardi, 2020). To sidestep these hardness results and provide proofs of learaailiity in the PAC setting, a number of works make assumptions on the networks or inputs/outputs to give efficient PAC learning algorithms for single hidden layer neural networks (Bakshi et al., 2019; Goel et al., 2018; 8: Shamir, 2018; Sedghi et al., 2016; Vempala & Wilmes, 2019). Such assumptions include bounds on the condition number (Bakshi et al., 2019), approximation guarantees of the network by polynomials (Vempala & Wilmes, 2019), positivity of the second layer weights Diakonikolas et al. (2020), and others. In perhaps the most general setting, Chen & Narayanan (2023); Chen et al. (2023) give polynomial time learning algorithm for learning single hidden layer ReLU networks with (11) hidden nodes (i.e. runtime is exponential in the number of nodes but polynomial in other parameters such as the input size and error).
Random neural network learnability Though the class of neural networks may be challenging to learn, various works study the average case setting where one is interested in learning random neural networks or random features from neural networks. In fact, prior work has shown that the complexity of such random neural networks, measured via statistical measures, continuity, or robustness, is rather low though this is by no means a guarantee of learnability (Kalimeris et al., 2019; De Palma et al., 2019; Shah al., 2020; Valle-Perez et al., 2018). Various hardness results exist for this setting of learning random neural networks. Das et al. (2019) gives SQ hardness results for learning neural networks with sign activation that shows query complexity increasing exponentially with the depth of the network. Daniely & Vardi (2020) show that neural networks with random weights are hard to Iearn if the input distribution is allowed to depend on the weights based on reductions to random K-SAT. Nevertheless, recent work by Daniely et al. (2023) shows that random constant depth neural networks with ReLU activation can be learned in error c in time scaling as (Polylon(1ee) where d is the size of the network.
Sample complexity and generalization bounds Separate from the question of computational complexity of learning is the question of how many samples are needed to learn a function class. Specific to (exactly or approximately) invariant neural network architectures, there exist papers studying the sample complexity of learning convolutional neural networks (Du et al., 2018b; Zhou & Feng, 2018; Cao & Gu, 2019) and graph neural networks (Zhang et al., 2020).
Various papers consider how generalization bounds improve when enforcing equivariance. These include generalization bounds based on covering numbers or the complexity of the invariant function space Sokolic et al. (2017); Petrache & Trivedi (2023), based on invariant kernel method algorithms Bietti et al. (2021); Tahmasebi & Jegelka (2023); Flesedy (2021), and based on equivariant ver- sions of norm-based PAC-Bayesian generalization bounds (Behboodi et al., 2022). For the group of translations, there also exist papers studying generalization bounds for architectures with convo- lutional layers though these architectures are not strictly invariant (Long & Sedghi, 2019; Zhou & Feng, 2018). Similarly, there are various generalization bounds as well for the class of graph neural networks (Lv, 2021; Verma & Zhang, 2019).
Other related topics Though not directly a statement of computational hardness, various papers give no-go theorems for learning function classes by studying expressivity limitations of graph neu- ral networks (Jegelka, 2022; Wu et al., 2020; Loukas, 2019). These expressivity results provide a set of functions that graph neural network cannot express and thus by definition also cannot learn to arbitrary accuracy. The most well known set of results are related to limitations of graph neural networks in distinguishing non-isomorphic graphs via the Weisfeiler-Lehman hierarchy (Xu et al., 2018; Morris et al., 2019: Geerts& & Reutter, 2022). Other work show expressivity limitations of GNNs by studying their power in expressing invariant polynomials (Puny et al., 2023), identifying graph biconnectivity (Zhang et al., 2023), counting substructures (Chen et al., 2020), and through various other means.
17

---

Published as a conference paper at ICLR 2024
Various works study the implicit bias of neural networks primarily to help address why neural net- works can even learn in overparameterized settings (Vardi, 2023; Chizat & Bach, 2020; Ji & Telgar- sky, 2020). Here, the aim of these works is to show that gradient descent will converge to specific regularized functions that fit a given training set. Implicit bias results have heen proven for linear but multi-layer classes of convolutional neural networks (Gunasekar al., 2018; Yun et al., 2020; Le & Jegelka, 2022) and equivariant neural networks (Lawrence et al., 2021; Chen & Zhu, 2023). Generally, these results show that gradient descent on the parameter space of such neural networks is implicitly regularized under some norm or semi-norm depending on properties of the group. Ex- tending these results to more realistic settings is likely challenging.
In Boolean learning theory, there are various results on the problem of learning symmetric k-junta (Mossel et al., 2003; Lipton et al., 2005; Kolountzakis et al., 2005). Here, we are promised that the Boolean function only depends on l variables, and within that k variable subset, the function is symmetric and thus only depends on the number of 1s in that subset. For this problem, Kolountzakis al. (2005) achieve a runtime n O(k log&) that is polynomial in for fixed k. Note, that the functions we study in the Boolean setting are assumed to be symmetric over the whole input space and not just on a size subset of the inputs bits which drastically simplifies the problem. fact, the hardness of the symmetric k-junta learning problem largely arises from challenges in finding which & bits are in the support of the Boolean function.
Finally, in quantum machine learning, there has been a recent interest in studying quantum varia- tional algorithms or quantum neural networks that are constrained under symmetries (Meyer et al., 2023; Ragone et al., 2022: Skolik et al., 2023; Cong et al., 2019). Some recent theoretical work has quantified the hardness and sample complexity associated with these models that are generally linear though acting on high dimensional Hilbert spaces (Pesah et al., 2021: Schatzki et al., 2022; Anschuetz & Kiani, 2022; Nguyen et al., 2022; Anschuetz et al., 2022). Since these quantum models typically operate in different regime than classical models and are typically focused quantum tasks, they are out of the scope of our current work.
B EXTENDED BACKGROUND INTO LEARNING FRAMEWORKS
There are various models used to rigorously quantify the hardness of learning. We recommend the review in Reyzin (2020) for an overview of the SQ formalism and its connections to other learning models. Here, we briefly mention the PAC model and overview further the background into the SQ framework from the main text.
Perhaps the most widely used framework for quantifying hardness of learning is the provably ap- proximately correct (PAC) model (Valiant, 1984).
Definition 10 (PAC Learning (Mohri et al., 2018)). A concept class C is PAC-learnable if there exists algorithm such that for any 0 and 5 0, for all distributions DD on X, and for any larget concept c* E C, the algorithm takes at most m = poly(1/e, 1/5, n) samples drawn i.i.d. from (x, c(x)) with æ D, and returns a function f satisfying || c* 1l < e with probability at most 1 - 8. If the algorithm runs in time at most poly(1/e, n). then C is efficiently PAC learnable. The algorithm a proper learner if it returns f E C, and otherwise denoted an improper learner.
Proving computational hardness in the PAC model typically requires reducing learning tasks to cryptographically or complexity theoretically hard problems. Unconditional hardness results for leamingg with neural networks would imply + NP: Abbe & Sandon (2023) show that the task of training neural networks via gradient descent is P-Complete, i.e. any poly-time algorithm in P can be reduced to the task of training a given poly-sized neural network with stochastic gradient descent.
Given the above, the statistical query formalism sidesteps these challenges by constraining algo- rithms to be composed of set of noisy queries. Perhaps the most important restriction in the SQ framework is that algorithms do not have access to individual data points but only noisy queries averaged across the input/output distribution. The classic example of an efficient non-SQ algorithm is Gaussian elimination for learning parities (Blum al., 1994). Nevertheless, the SQ formalism naturally captures most algorithms used in practice including gradient descent as shown for example in Example 1 of the main text for gradients over the mean squared error loss.
18

---

Published as a conference paper at ICLR 2024
For boolean functions, correlational statistical queries can capture any general statistical query since any query can be split into its +1 or -1 output cases (Reyzin, 2020). For example, assume one performs SQ query with query function q X' x 1-1,+11 [-1, +1], then
- y y E (g(2, v) E g(x, +1) 2
+ g(æ. -1) -1)
(20)
which decomposes into two correlational statistical queries and two functions independent of the target.
We remarked the main text that generalizing real-valued hardness results proven in the CSQ framework to the SQ framework is in general challenging. In fact, Vempala & Wilmes (2019) more rigorously underscored this challenge (see their Proposition 4.1) 1) by providing a rather unnatural, yet efficient, SQ algorithm that learns any finite real-valued function class satisfying non-degeneracy assumption that the set of points f(x) = ((x) measure zero for any pair of functions f. g in the class. Namely, they show the following no-go theorem.
Theorem 11 (Limitations on SQ hardness for real-valued functions (Vempala & Wilmes, 2019)).
Given a concept class C of functions f X - R of size [C] where for all f.g E C the set of inputs where (x) g(x) is measure zero, the family C can be learned with Oloo CI) queries to SQ with a constant error tolerance r.
Proof. We aim to choose a query g - [-1,1] which maps the target function f C to unique value in the range [], For our target function f E C, let us call this value v. To specify its corresponding unique value in
the form of this query, it suffices to send each pair ( [-1, +1] i.e. output v for every input (I, f(x)). Since outputs of disjoint functions in C are equal only on a support of measure zero, this mapping can be performed with probability one. Thus, we can query the value and receive an output, say o' up to error T. Repeating this procedure iteratively only include functions the tolerance range [E T, vt + T]. we can select the target function after (log (C)) queries.
Loosely, the above theorem shows that real-valued classes of functions are only hard SQ settings when there exist sufficiently many hard functions with fimitely many outputs. Chen et al. (2022a) achieved such a result for two-hidden layer networks by constructing networks that round inputs to the nearest boolean bitstring.
C BOOLEAN STATISTICAL QUERY SETTING
As discussed in Sec. 3, the Boolean function setting provides nice illustration of the types of results obtainable via SQ lower bounds. For further background into the boolean SQ setting, we recommend the review in Reyzin (2020). Here, we will prove Theorem restated below for convenience.
Theorem (Boolean SQ hardness). For given symmetry group G with representation p G GI((-1,+13%) let IIpo, = (Eo,eo, Boolean functionn, defined as
[Oxl] ) and let Ho be the class of symmetric
= (-
E Vo (-1,+1]" f(pg)) = =) (4)
Any SQ learner capable of learning Ho up to sufficiently small classification error probability e < 1/4 suffices) with queries of tolerance requires at least -3|1po,,11 2 queries.
For simple proof of the above statement, we will follow the proof technique in Appendix B of Chen et al. (2022a). The above statement will follow as a consequence of the pairwise independence of functions in H. defined below.
Definition 12 (Boolean Case of Definition C. of Chen et al. (2022a)). Let C be a hypothesis class mapping {-1,+1}" - to [-1,+1) and let D distribution on X. C is a (1 -aiiaiis indepen- dent function family if with probability - n over the choice of x drawn independently from D, the distribution of (f(x), f(x')) for drawn uniformly at random from C the product distribution
Unif([-1,+1)*
19

---

Published as a conference paper at ICLR 2024
Pairwise independent function families offer convenient means to bound the number of queries needed to distinguish the outputs of a given unknown function f versus uniformly random outputs from the function class.
Theorem 13 (Theorem C.4 of Chen et al. (2022a)). Let function class C mapping { (-1,+1}" to {-1,41} be a (1 -piirwiie independent function family w.r.l. a distribution 'D on {-1,+1}² For any f C. let Dy denote the distribution of (x, f(x)) where the distribution of (z. where a ~ DD and y f(x) for f Unif(C). Any SQ learner able to distinguish the labeled distribution Dj- for an unknown f E from the randomly labeled distribution Duifte) using bounded queries of tolerance requires at least Σ such queries.
D. Let Dunif(c) denote
Finally, we ready prove Theorem 2.
Proof of Theorem 2. Since the symmetric function is constant orbits, we can represent any sym- metric function as f On 7 (-1,+1) and the correlation between two functions f. can be written
(g = E [ʃg] 2- Σ (0) (0(().))
(21)
O2EO,
The probability po, : O + [0, 1] a uniformly random bitstring falling in orbit OK E O2 is equal to po, (0x) |0x]2"0 Note that the distribution of (f(x)), f fxoo)) is equal to the uniform distribution whenever 20 * zO since we have a uniform distribution over all possible symmetric functions. This occurs with probability
Ox 2 2
Σ
= -IPO,,11
(22)
OLEO,
Therefore, Hp is (1 - (11-1)-paiivee pairrise independent function family with parameter v) as above.
To apply Theorem 13, note that for given function f Hpp distinguish Dy. from Dunif(H.)> it suffices to return function f that has classification error at most 1/4 with respect to f*. Since distinguishing the two distributions requires 2nj queries, we arrive at the final result.
D COMPLEXITY THEORETIC HARDNESS EXTENSION
In this section, we would like to show a reduction from the task of training an invariant neural network on given dataset previously NP hard problem. This extends the classic result of Blum & Rivest (1988) showing that there exists a sequence of datasets such that determining whether or not 3-node neural network can fit that dataset is hard. Though consider extending this to simple graph neural network here for simplicity, we remark that we chose this only for convenience and similar extensions be found for other classes of networks.
The particular NP hard problem we consider is the decision version of the learning halfspaces with noise problem (Guruswami & Raghavendra, 2009; Feldman al., 2012).
Problem 1 (Learning halfspaces with noise (Guruswami & Raghavendra, 2009)). Given set of N labeled examples (æ,, y4 J where æ; E {0, 1) and yı E [1] and constants e where 0 < 8 < e 1, we distinguish between the following cases:
* Case 1: There exists vector v E R" constant 0 E R, and set S S [N] of size at least
| > (1 - N)N such that yi ((v, 2.) 0) 2 for all S.
Case 2: For v E R", 0 R, and sets S C [N] such that |S] 2 (1 e)N, there exists
some E S such that yı ((v, x.) 0) 0.
Consider the following class of message passing GNNs with single hidden layer and k channels which acts on an adjacency matrix A {0, 1] j and node features æ e R":
k
(x, c Σ
rolu (x + a,Ax),,
(23)
20

---

Published as a conference paper at ICLR 2024
We will map the below problem of fitting the weights b, of the GNNs above to given dataset consisting of a set of graphs and their corresponding outputs.
Problem 2. Given labeled set of graphs, node features, and outputs {A,, T. 34 h where A, E {0, 1)m1,,m x; R" and Yt E {-1,+1) and constants ó,e where between the following two cases:
S 1. distinguish
Case 1: There exists weights ai..... ags b,,, ....... bR, E R and set S S [N] of size least
|S] 2 (1 - N) such that yifa, (T, A,) 2 0 for all E S.
Case 2: For all weights 01,.... ak b1 ....... c
R, and sets 5 C [N] such that |S| 2
(1 - c)N, there exists some E 5 such that b, A.) < O.
Proposition 14 (NP hardness of GNN training). Training the GNN in Eq. (23) to solve Problem 2 NP hard.
Proof. We show that solving Problem 2 is equivalent to solving Problem which previously shown to be NP hard (Guruswami & Raghavendra, 2009; Feldman et al., 2012). Given dataset {ær, yi J for Problem over n-bit Boolean strings, we map this to a dataset over graphs [A,, zi,, V of Ek=1 k = nnn + 1)/2 nodes where x = -1 for all inputs and yi = y are the same for both datasets. Adjacency matrix A, is constructed by including disconnected k- clique (including self loops) in the graph whenever [æs]aa = 1. Since there are n(n + 1)/2 nodes, there are sufficient nodes to construct any such graph. E.g.. for (1, 1) corresponding adjacency matrix is
0
0
0
0
0
0
0
0
0
(24)
0
0
0
1
0
0
0
0
0
We also assume that the GNNs have h n channels. In this setting, we have that for any E [N]
fa,b = c Σ
relu (at + aaA,)))))) by
j=1
(25)
c
e A.] velu(-1 - Eaz),
t=1
clique E A, the indicator function for whether or not É-clique is in the graph A,- The above is clearly linear function in the vector E 10, where [rile = 1/3 E - clique E A,). Furthermore, the graph chosen so that r; = a:. Thus, any choice of weights a, e corresponds to halfspace for
where 1 f
only remains to be shown that any such halfspace can be written in the form of Eq. (25). Note that
fa, A,) c' [b by
b Mr::
(26)
where d' is an updated constant and
relu( -1 a1) relu( -1 02)
2 relu -1 2aa
nreuu -1 naj n relu -1 na2)
reluu -1 2ag)
M
(27)
relu -1 a.)
2 2relu(-1 2a,)
n relu( nl,
Setting a+ (1/2 -1 makes the above matrix have non-zero entries the diagonal and every entry above the diagonal. Such a matrix is invertible by Gaussian elimination so every possible halfspace be constructed by proper choice of the weights bı,..., b.,...,,,,c. C'.
21

---

Published as a conference paper at ICLR 2024
E GNN HARDNESS PROOFS
E. LOWER BOUND FOR ERDÖS-RÉNYI DISTRIBUTED GRAPHS
Here, we will consider model over graphs of n nodes where adjacency matrices A (n, 1 })=x)) are drawn uniformly from all possible directed graphs. This distribution can be viewed as an Erdös-Rényi G(n, p) over directed graphs including self edges with p = 0.5. Node 1 in all instances (i.e., node features are trivial.. Note, that we consider Boolean functions here w.l.ogg as {0, 1] valued as opposed to (11,+1} valued as in previous sections since using {0, 1} valued functions in this section makes the story easier to follow.
features fixed in this model to æ R" where
Our aim is to prove Theorem copied below.
Theorem 3 (SQ hardness of H.R.,)) Any SQ learner capable of learning HER. up to classifica- tion error probability e sufficiently small (e < 1/4 suffices) with queries of tolerance requires at least (+² exp(nn())) queries.
The function class HER. that achieves the desired lower bound are Boolean valued functions that depend on the counts of the degrees or number of neighbors of the nodes. To describe this class, we first introduce some notation. For a given graph A E {0, 1)axn, let dA E [n] R be vector with entry [d equal to the number of outgoing edges (or degree) for node i. From here, let CA E [m] n+1 denote the count of the degrees where entry [ca]: counts the number of nodes that have i 1 outgoing edges in A more formally
[CA] = Σ I[dAk = -i-1i 1].
(28)
Note that CA is a length + 1 vector since the number of outgoing edges can be anything from {0, 1,..., n). Also note that this vector is an invariant vector as permuting the nodes leaves the counts invariant. Given a subset S _ [n + 1] and bit E {0, 1], the functions we aim to learn take the form
gs.b (A) b Eicale mod 2,
(29)
which are sort of parity function supported over the elements of the degree counts CA in S. There- fore, our hypothesis class H. consists of 2 functions:
HER = {gs S S In + 1],be 13,
(30)
First, we will show below that the class HER, is exponentially hard to learn in the SQ setting. Later in Lemma 15, we show that the functions in H. can be constructed by the GNN architecture thus completing our proof.
Proof of Theorem 3. To simplify the function gs.s even further, let êΛ E {0, 10 be boolean valued version of ca where entry [CA]: [cA]: mod 2. Then the function gs.b is equivalently parity function in CA:
(A) b Eical: mod 2 = (-1)6 (-1) (--I)E
(31)
EES
YES
We will prove an SQ lower bound using Theorem 13 based the (1 pairwise independence property of the function class HER, in Definition 12. Namely, note that for two graphs A, A' E {0, 1)am if ČA * CA', then the distribution of (g5,o(A) gs,( for gs, drawn uniformly from HERR equal to the product distribution (n0 1) This follows from the fact that 9s.((A) "
is parity function of the entries in čΛ. Since HERR spans uniformly over all possible parity functions in (0, 1 g=+1 the pairwise independence properties follows from this whenever ČΛ # CA'
Thus, the parameter 1 - ry in the pairwise independence is equal to the probability that č + ČA- We will establish that this probability is least 1 ((exp((nx)))) the end of this proof thus
22

---

Published as a conference paper at ICLR 2024
guaranteeing 7 22 (exp(n Once this is established, that for a given function f E HER.N. to distinguish Dj- from Dumi((H,)) as in Theorem 13, suffices to return a function f that has classification error at most 1/4 with respect to f". Since distinguishing the two distributions requires žे queries, we arrive at the final result by noting that 7 = Ω (exp(n(()))
apply Theorem 13 and note
To finish this proof, must establish that
"A--ttii(((.1))>>>)CAA ēA 2 O()
(32)
We will show this result by proving that for some constant C'> 0 and p < 1/2, for large enough n, there are at least Cn² entries of čλ such that the probability of those entry being even or odd is at most 1/2 + (1). To continue, let us denote this region
A (0, ,........ m) n |n/2 Cn², n/2 CnP], p < 1/2,
(33)
as the set of integers within the range [n/2 Cne, n + Cnej. This range is chosen to coincide with the largest entries of CA-
The degree of any node is independently distributed as binomial with distribution (nn.n..5), To asymptotically expand around the peak of the binomial coefficient, let index nn/ + r for given r such that E Ap. Therefore, for any such n/2 + E Ap, we have that any given node j E [r]] has degree dg with probability
p[d: = 1| = n
n1
2
(1 + O(1nn))
(34)
n/2 +
Vin n
In the above, we the asymptotic approximation (Spencer, 2014) for the binomial coefficient around its peak (,"/2 of
12 2 2" exp (-2m +0(%%/2)) = (1 +1+ 01+0(1))))
(35)
mn
Thus, the marginal distribution of any entry E A, [cAls ~ bin (n. (1+ is also binomial distributed with probability converging to 2_ E[cA]: = OVvn). From the Chernoff concentration bound for the binomial distribution, we also have that for any E A, and for any 8 > 0:
र For entry E Ap. this implies that
1/2-26 (Elcal)" 22/2A2(()()))))))
P [ccal: E(cAli nn 14466]
2eep
exp (-2(n2))) (36)
2
By union bound over all i E Ap. we therefore have that with exponentially high probability, [[ca]: F(cA]i S 1/4++ for all E Ap.
Summarizing the previous results, we have that there are 2Cn" entries of [ca] where for any entry i Ap. it holds that for some arbitrarily small 8
(((n))())))) - -n 1/4+8 S [CAl: S ( + +n 1/445
(37)
VT
Since the probability that [cA]e is equal to any number is at most O(n-1/4,, the probability that [cA]; is odd is most 1/n2+Onn=11) (1/4). We now aim to show that conditioned other entries of ca. the probability that given entry of cA is odd or even is roughly independent of this conditioning.
Given set of known values Sknown Ap equal (CALı my for k Sknowns the marginal distribution of any entry of [cal; for j & Sknowm conditioned on [CA]k for & E Sknown is also binomial. We now estimate the parameters of this binomial distribution. Given the convergence guarantee in Eq. (37), EkeSt [CA]s = O([Smnown |n 1/2) (n1//pp)) which is o(n) since p 1/2. Therefore for any set Sknown C Ap, there are at least o(n) remaining nodes whose degree or number of outgoing edges are left to distribute. These remaining nodes cannot have degrees whose values fall in Sknown, but note that since [Sknow!!
O(nP) and 1/2, there
23

---

Published as a conference paper at ICLR 2024
still ( buckets (values of the possible degrees) remaining each with probability proportional to (1/ n)) by Eq. (35). Therefore, from the convergence guarantee of Eq. (37), we have
([cala [cAlı = my: k Sknown) ~ bin (n - o(n), @(1/v))
(38)
Thus, the conditional probability that [cali is equal to any number implies that the probability that [caly is odd most 1/2 O0 even when conditioned on entries in Skownn
most Onn 1/141 and this
Finally, let calculate the desired probability that čΛ CAs. For ease of notation, let us index the elements of A ri,.... TN- We have for large enough n that
P = f - P |[cAl = [CAilr...... fEAleN = =[A
= P |(aln = =(erin P[[Cr)> = 1 [Eale = 1r
x... P[CAAl [ealee [Calr: (cAil....... [CAlx--: [CAl
< (1 144
AAp
(39)
= Olexp(- -2( (((1)))))))))))))))))))))))))(
(oxxp((S((n)))
Since P AA~Unif((0:1))x)) (CA * Cxr 1 P An- C..). this completes the proof.
L
Finally, we need to show that the functions JS.s can be constructed as ReLU networks. Before proceeding to give this construction, should note that it is known that any Boolean function that can be computed in time (n)) can also be expressed by neural network of size (n?(n²) (Parberry, 1994; Shamir, 2018). Our construction will be specific to the GNN class we consider and show that the boolean functions in Is.6 are similarly efficiently constructible.
Lemma 15 (gs,s as GNN). For GNN f(-) of the form of Eq. (5) with hidden layer widths equal to k = (n) and 22 = On)). there exist weights a, b Rk: u, v E R²² W E Rhaxk1 such that for any S In + 11. b {0, 1}, 95,6 (A) f (A; b, u. W) for all inputs A E {0,1)
Proof. Let us fix given S S [ + 1), b (0, (i1.).TT. The function we want to represent is
(A) = b+ Eicale mod 2,
(40)
iES
where a reminder, [ca]; counts the number of nodes that have i - outgoing edges (see Eq. (28)).
For the construction, we will set the form:
12 n
As a reminder, the two layers of the GNN take
1, (a, + b.Ax)
(output of channel E [[x]]
l2 Σ
(41)
(h) fe
uo (W.,,, h) + v:).
i=1
Throughout this construction, the node features x are constant.
For the first layer, we will choose a; = 2 and b, 1 for all i. This first layer can only be function of d d take values in (0. 1, ....., n). we can equivalently write this first layer output as a function of the counts CA. In fact, this first layer is linear as a function CA and equal to
A1 where entry is a count of the number of outgoing edges. Since entries in
I
2
n
n 17
0
1
n
= McA
CA
(42)
0 0
2
0
0
0
1
24

---

Published as a conference paper at ICLR 2024
h(x) for n =
h(x))
0
2
4
8
Figure 2: Sample form of function h(z) used in constructing (s,)(A) as a GNN. For the construc- tion, we will have r = Eves|cAli
where the matrix M is clearly full rank and invertible since it strictly positive along the diagonal and in entries above the diagonal.
Our aim in the second layer is to take the sum b ++ EiesIcat and take its parity (i.e. mod 2). To achieve this via sums of ReLUs a we can consider the function h(-) of the form below:
h(x) = (x + b) 2x + b - 1) + 20 + 2) ....... + (-1)" + n).
(43)
A sample version of this plot is in Fig. 2. Setting æ = b+ Eies (cA]: achieves the end goal with (nn) hidden nodes.
To provide actual values for the second layer parameters, let 1s E 0, 1 denote the vector where entry is equal to i E S and equal to otherwise. Then, in the second layer, we have
W (M 1 for all columns i [12 1]
.1 and 0 2(-1) for all i .2...., 1}
v; i + 1 for all [n++1] 1]
Using the values above, we have
(ll) (h) = 1s + +
1s,
(- (002220 1s. McA) +b-i+)
im2
=a (0+ +icalal/
b+
+ (-1) -icali+b-ing
iES
2=2
iES
h ((cAli).
(44)
As Eiel(cal only takes values in {0, 1, 1.....n.,, n), the above is supported on all of its inputs and this completes the proof.
E.2 INVARIANT HERMITE POLYNOMIAL
Multivariate Hermite polynomials To handle the graph setting with scaling feature dimension.
first extend the technical machinery related to Hermite polynomials to the invariant settings
consider.
Recall from Diakonikolas al. (2020) that the d-variate normalized Hermite polynomial is defined for every multi-index J = (J1,..., Ja) E Nd as:
H (x)
Hy Rd +R RR (I1, F2, ma) + II H1,, (xz),
H: R RRIH
N, (45)
Vi!
25

---

Published as a conference paper at ICLR 2024
where He, is the usual probabilist Hermite polynomial.
Graph-invariant Hermite polynomial Fix a graph 9 on n vertices and let :
== A(g) E R be a graph shift operator (say the Laplacian). Define, for any multi-index J E Nd:
1 Raxd R: X
Σ H)((AX))). P=1
(46)
We have the following orthogonality property:
Lemma 16 (Orthogonality of invariant Hermite polynomial). For a fixed A E Ruxx such that Σn A 1 for all v E [n], (H HANNNN رر=J² cJ for all J, J (o for some
CJ (1) that depends only on A.
1 p
f for some p E (-1,1). We will also Mehler's formula (Kibble,
Proof. Let E E(p)= =
1945) which states:
(m
(47)
(N)
m=0
where P.((,E) is the pdf of the bivariate normal distribution with mean 0 and covariance E and pm the pdf of the univariate standard normal distribution.
We first show orthogonality of Hermite polynomials evaluated on dependent random variables. For all i N:
((..)))N (())) / H y)drdy
(48)
[ (
PA v)
drdy
(49)
PN(())p(())
[ H((2)H Epn (
(50)
Σ TT (HHAA)Hma(a)aP ( ((I())))))))PPi
m=0
(51)
Σ p" 8,=m
(52)
m=0 p dims.
(53)
We are now ready to present the proof of Lemma 16. Pick J' E (O). We have:
(TSHH))
1
Σ ([
(54)
(2.
(55)
[())
where zu is the v-th row of Z e gaxd and P is multivariate normal distribution over RRodd with mean 0 and covariance:
0, EE A Av =: Poe's otherwise.
i H
Cov( Zeyr) =
(56)
Furthermore, for any v and any j / j'. Zuz is independent of Zuzz. This is because columns of X
are independent from one another. Note that when U = and j = j' the variance is Σi= A by assumption A.
26

---

Published as a conference paper at ICLR 2024
By the dependence structure of P, one can write:
d II L (n))tt (Z,'))
(57)
5=1
I (2. 5=1
5z (Z
(58)
II j=1
Pee ō أ==ي
(59)
Pee ò==J'.
(60)
Therefore,
1 Σ 0,t'E(n]
(HJ. HAN 85=n
Prol = ōz=J' CJ
(61)
where Cj = 1 Ev Pou.
Remark 17. The quantity Pee deserves an explanation. Essentially, Powr measures how similar two nodes u and o' are, in term of composition of its incoming edges. Algebraically, it is the (vv")- th entry of the gram matrix AAT. We can get the correct normalization of A in the premise of Lemma 16 by starting with a graph G, adding a self-loop to each node of G and set A = =Dt) where M is the adjacency matrix of (with self-loops) and D is the in-degree matrix, we can ensure that Pve E [0, 1] for each v $ * v':
N.. n N... V deg(v) deg(u") < 1,
Pey! Σ A Avu u=l
(62)
where N. is the of vertices with incoming edge to [n].
This immediately gives a bound max, CJ I n?. Finally, it is also worth noting that cj does not vanish under the above normalization, since adding self-loops before the normalization to & ensures that Pee = 1 for all E [x] even e was an isolated vertex in the original graph. Therefore, without loss of generality, we can assume that cJ E (()).
It is possible to use a different normalization, such as the Laplacian, as long as one can ensure that Poor, CJ = (1). The requirement that rows of A sums is also not strictly necessary but does greatly simplify our exposition.
Note that we are not claiming complete orthonormal basis for the space L L2((Rex,,AA ,Voxd). How- ever, all of the functions we care about will lie in H(d) = span ( (H)) JeNe- For a fixed n and a function f E H(d), we define fy = (f, (f and the degree m part of f: fimi (X) = Ej (x).
Facts about gradients of Hermite polynomial also earry over to invariant Hermite polynomials: Lemma 18. For fixed graph on vertices and corresponding A, have:
1. JX., (x)
8
- +. /M,H ((AX)v) A for all E [n], [d] M
Nd, where Es is the vector with 1 at the j' -th position and 0 everywhere else.
2. E Ex~Anad ( (X), V (X)) 8M=L |M
3. Ex~Aaxd (
(X)) 8MLL [MI([M) 1) ..M / + 1)cM.
In the above, CM n -n E. Peigh-
M
27

---

Published as a conference paper at ICLR 2024
Proof.
1. We have:
0 0x
1 n
(X)
Σ
(VHM((AX)))))
(63)
Vn
o'=1
Σ
VMJHM-E ((A))
(64)
where Ey is the vector with 1 at the j'thh position and everywhere else. The second equality is a known fact for the multivariate Hermite polynomials (See Appendix C of Diakonikolas et al. (2020)).
2. Sum the above over all pairs v, vf and take expectation to get:
Ex~Naxa
H
(65)
m
Naxd
(HH(((A)))), A (VHL((AX))')) A
71
(66)
By the orthogonality property of Hermite multivariate polynomial under dependent multi- variate Gaussian (equation 60), we can compute:
Ex~Aaxa (HM- ((AX) or HL-B,
= 1MI-1 8M==L
(67)
and,
n
(XH,) VHA
E
A ÓM=L Σ Mj
|
n v,u,,===1
(68)
8M==L
M
Σ
n
Peteer Σ
|M
7
A Apr (69)
n
v'v"==1
8=1
M
JM Potere
5M==L
(70)
0',0"=
3. Recursively apply the first part to get:
gl
H
(71)
0X 0x XXiiisn. X
Apep
M
Ej,r
H HM cip ((AX)))
(72)
Summing indices and passing through the expectation to get:
Ex~Aaxa|[V
X), v' H (X))
(73)
Σ A Awn Ap )
8M=L
P M
Σ
Σ
Ezg
Σ
(74)
n
p²=1
=δM=1 M ([
1) (IM) 1)
1
JM] Paryer
(75)
28

---

Published as a conference paper at ICLR 2024
Corollary 19. Fix k, k, E N. Let p.q q be linear combinations of H R + R with M E N varying among all cellfi-idiies of size k |M Then.
(X),, V q (x))
k! EE X--Nux (pll
(p( (X)x)))(]
(76)
Proof. Let p(X)= E MiJM =b by H (X) and g(X) = EKIKK= (
Then:
E Ex~amxe (X))( = E
fasDuCes
(77)
M:|M|=k
where as before, CM -n - ,0'"""=111 Pur From the previous lemma,
MI
K
E ANNZUAAI
pl (XX,, V (x)) ExxNuxa
Σ bm HM))H
(78)
K:|K|=K
E
balakklbasKKM
(79)
M.K: [K|=
k! E bas Smscs
(80)
M:
k! Ex=Nuxd Exxx)xxll((Xg(( (p(X)((X))
(81)
E.3 PROOF THEERRMM
The proof of Theorem 4 is derived from the construction in Diakonikolas et al. (2020). Hence, much of the setup will taken from their construction. However, care must be taken to use the proper invariant Hermite polynomial basis we derived in the previous subsection. For completeness, we extend their formalism here as needed and note where proofs are directly derived from their work.
We first verify that the orthogonal system of invariant Hermite polynomial subsumes 1-hidden-layer GNNs. We formally show this below to continue the proof later on in the basis of the invariant Hermite polynomials. As reminder, we defined H(() := span ( (H ( JeNu-
Lemma 20 (Inner product decomposition). For every E and g E Cn. Fdlkk c H(d).
Proof. Pick J Fe with corresponding W and a. Let : Rd - R: + Σ a.0 (ar, wx)) where w. is the e-th column of W. Then we have f(X) = En ((AX).) where the subscript represents the row of the corresponding matrix. Since L²(N), is in (22 and we can write uniquely:
g(x) Σ (z).
(82)
JEN"
Therefore,
f(X) Σ ((A)))))
Σ
Σ (AX))
(X) H(.
(83)
w=1 JEN
JEN"
Now we verify that the special function fg in our construction of the family of hard functions has vanishing low degree moments:
Lemma 21 (Low degree moment vanishes). For any k E N, for any g and appropriate A, fg 22)), Furthermore, (fe), for every [] k.
29

---

Published as a conference paper at ICLR 2024
Proof. The first part follows from specializing Lemma 20 for d 2. The second part follows from the fact that the corresponding function in the proof of Lemma 20 for f is the function fę.o in Diakonikolas al. (2020), whose low degree moments vanish.
It is also easy to verify that C. C Fg
Lemma 22. For any d, N. for some activation a that is not low-degree polynomial, C C F
Proof. Pick B E B arbitrarily and let (xx) f)( We have:
h(X) (x (A( a" 1, (AX(BW'))
(84)
Since BW is Rdx2* and a² is in R22 we have h E Fd.k Functions in F also do not vanish, as long A does not have vanishing rank and the activation function is not low-degree polynomial, by the same argument as in Diakonikolas et al. (2020).
From Diakonikolas al. (2020), we know the following facts about matrices Rxxx Lemma 23 (Lemma 4.7 in Diakonikolas et al. (2020)). Fix c E (0, 4). Then there is a set S C Rdx2
of size at least 20(4)) such that for each A, B S, A B 2 S 1).
The following Lemma generalizes Lemma 4.6 in Diakonikolas et al. (2020):
Lemma 24. Fix a function H(2) p : R2x2 + R and U, V Rdx2 such that U VTV =
12. Then:
(ol-
(2V7 U VIl2)" -1p"""
(85)
122 ===
where pl is the degree m part p.
Proof. Let s.g: : paxd + be defined as s(X) = p(UU) and g = v(VV.. Let fIml, gmml
and pmml be the degree m part of the corresponding function.
From Corollary 19,
20
m [mm) X): T ml (X))
Σ x SanNax (X)
(86)
[[ [x=Nxxa (X)g(X))
(87)
- (p( (XU ((U)((X)
(88)
8
Σ ExmNnxa(p! XU) (XV)
(89)
lm)
XU), 1ml [ml (XV)..
(90)
m=
Fix m R, for each indices 01 .1...., Um [n)) s1,.....
8m [d]. in Einstein notation,
(Dm ... Som sm plm)) (X)
...
... Dom mm (X)
(91)
=mmii Pom Im mm (XU)Om.. Opm s'a XV) Unmin VoUsi V Am
(92)
(93)
Taking the sum over all .i...., Um E [m], si.... Sm E [d], while still in Einstein notation, to get:
IVTT mm)
(UU),
Vi Iml (XV))
(94)
:00s ...
(XU)O ... O Dem.y [m] (U V) Duu ... ...(UT
(UTV)) V) Im
(95)
<2nh
ml
(UU)
Vnm - VIE
(96)
=m! - E (xx ())) (2 [ 112"
(97)
30

---

Published as a conference paper at ICLR 2024
where we used 3-variable Cauchy-Secie Schwarz inequality JannsbyaCinl & be Go obtain the inequality and Corollary 19 obtain the last line.
gor to
Notice that the previous derivation, inequality only occurs the Cauchy-Schver inequality step. We can do more careful analysis get:
Corollary 25. In the same setting as Lemma 24, we have:
((UU)(-V))Lau
(98)
Σ
Σ
Dords Dum Dmm (XU)d, ... Dem.i plm)
X (UV)
V) V)sut ... (UV))
V)
m=0
(99)
As the last ingredient, we need the following lemma that connects the family of hard functions to lower bounds on CSQ algorithms:
Lemma 26 (Lemma 15 of Diakonikolas et al. (2020)). Let X' be the imput space and DD some
distribution over X. For a finite set of functions C = [ - RJ. define:
pC) = 1/|C|² Σ (f.9)
(100)
1.EEC
The correlational statistical query dimension is defined as:
SDA(C, D, max p(C)) S TT, VC C C,IC'//I 1/m}.
(101)
Suppose that SDA D,+) 2 m for some C,D.T and then there is small enough such that any CSQ algorithm that queries from an oracle of f E C' and learn a hypothesis h E with (f - h) LP) S e either requires (mm) queries or at least query with precision more than vT.
We can now proceed to the proof of the main theorem:
Theorem 27. Any correlational SQ algorithm that, for every concept E C. learns a hypothesis
such that llg - h(]( & é foor some small e > requires either 2d00 queries or queries of tolerance most d i0() + (20)
Proof. This proof mirrors that in Diakonikolas et al. (2020). Fix c E 10,1/2). To upper bound pairwise correlation between different functions in Cg. consider for any B, # B, B:
< Σ (2 Byll2) m
(102)
m=0
(2 n B, 11
(103)
s (2vnl
B B)ll2)*
Σ m>*
1155 C (PEPeN
(104)
S 11
(105)
In the above derivation, the first line uses Lemma 24; the second line uses Lemma 21; and the last two lines use Lemma 23 and the fact that we can choose an appropriate parameter to make B Byll2 < 1. Dividing both sides by l gives
Lo
96
B 1 s (112)-112))
(106)
Now, since B. B, 12, have [l/a( 1 [15s ( and therefore 11og [P())) 1.
31

---

Published as a conference paper at ICLR 2024
B We are in position to apply Lemma 26. Let m ( ,9 1P(N)- Computing average pairwise correlation of Og yields:
p(C 1/|B] + (13) - 1)7 1 +
(107)
Finally, setting r' == 1/|B| + r gives (D)( 20(d)) and an application of Lemma 26
completes the proof for g
To get the proof for F.ikk, by law of total expectation:
(108)
(109)
E Wr
(110)
GEGm
Σ Pre(g).
max (2vrl (, B)(la))) -Ifellizus (111)
EBB
GEG
(112)
where in the third line, we use the fact that fz(Z) (Z, and triangle inequality; in the fourth line, we use Eq. (105) and in the last line, we use another instance of total expectation to get
Eg-E fl Il. (e(()))) El=lellfelll is worth pointing out that the only instance of for which we cannot apply Eq. (105) in the fourth line (assuming we use the normalized Laplacian
A(g)) is L/slllee (e()) = 0 since fc = 0 and the inequality when G is the empty graph. However, in that case, f
the fourth line still holds.
Lastly, proceed identically to the proof for Fg to use Lemma 26 and get the final bound.
F FRAME-AVERAGING HARDNESS PROOFS
Frame averaging. Let be a subgroup of the permutation group Sn that acts on Ren by per- muting the rows and its identity element. Let p: G GL(n) with p(g) the representation of g as a matrix in Re*x,, For any group element E G and X E Raxd, we will write g.X as a shorthand for p(g) X where the product is matrix multiplication. A frame is a function F Raxd {0) satisfying F(gX) = gF(() set-wise. For given frames F, we will show a hardness result for the following class of functions:
HlF = {
f: p:Raad - with f(X)
Σ VIF(X] gEF(X)
1
a ( X))1a
W E Run a R* M (113)
for given nonlinearity a that is not a polynomial of low degree.
F.1 EXPONENTIAL LOWER BOUND FOR CONSTANT FRAME AND REYNOLDS OPERATOR
Lemma 28 (Constant frame must be whole group). If F(X) is constant function, i.e. F(X) is independent of X, then F(X) G
Proof. When F(X) is constant function, say F C G for all X, then the frame property mandates that # B and there is some is a group), f-1 F = F and thus e E F. Pick any element g E G and observe that since F and
F. The frame property also tells that since f G (and G
F F, g must also be in F. As this is true for all elements g E G, F must be the whole group G itself.
L
In the following, we will therefore assume that G is a polynomial-sizee (in n) subgroup of S,,. We will slightly modify Lemma 17 of (Diakonikolas et al., 2020) show:
32

---

Published as a conference paper at ICLR 2024
Lemma 29. For any 0 1/2, and small E (0, 1), for any potynomial sizedd sized subset F S. there exists set B' of at least 20("") matrices in R such that for each pair B, B' E B and for each g.9' E F, it holds that:
1. ()
2. (l(g)) (g' BB) B')[22 - 1/2 when B +
B';
and
[a b1 b2
3. when # g. BB T ( B));j =:
where b; S O(n8-1/2) and,
02
Fng
01
S 5(n
(114)
nV
F g.9
a
20
(115)
for E [2]. Here F g.9" is the number of fixed points of g gr (number of cycles of length one).
The proof is delayed to App. F.3 for more streamlined read.
Family of hard functions. Recall the low-dimensional function from the proof of Theorem 4:
Sepp R2xd IR with f(x) "aa""a((""""
((WW)) X)
(116)
for some special parameter a" 122 and W g2x2k in Eq. (11). We now define the family of hard functions, indexed by set of matrices B C RTx2 obtained from Lemma 29:
- Ruxd + R with 9n(X) Eyec fexp (B 9 'X) BEB' C (RXx3]. (117)
VIGI -1.fppppll
Theorem 30. For any feature dimension d ((1) and width parameter k = O(n). Let G be a subgroup of Sn with |G| = (ppoly(n)). Pick set B C RRxx of size at least 20() /|G/ according to Lemma 29 and normalize each function in the hard function fantion C to have || Il norm 1. Let é' >> 0 be sufficiently small error constant. Then for any C any CSQ algorithm that queries from oracles of concept E C and outputs hypothesis h with || -lllx é requires either 21)) /|G|2 queries or at least one query with precision (G 20) + VIG -(())
Proof. First we review properties of the constructed objects. By Lemma 29, g and g' B' are almost orthogonal for any B + B' E B' and g,g' G.
Then by Theorem 27 with matrix
Ia, for any + B' e B' and any g. E G, noting that B (g (X) (g X since permutation matrix is orthonormal, we have
|Ex~Nlfozp () X) ((g (('''') X)I| S ((-1(111/2)) 1/2
(118)
for the same that chosen in the statement of Lemma 29.
Now we verify that lgglll = 22(1) for each gB E C CF Let B Jx y) and B, = gB, By = Bg
19 l
(119)
( (B) x))
fexp (BB X)s (BJ.)
ExaN
(120)
[ lly
G
G
gEG
g7g'EG
=1+
E
Ex-N [foe (B) x) X) ( [J)
(121)
Ge
EG
"The different notation highlights the fact that we are using slightly different set of matrices from Lemma 23 and (Diakonikolas al., 2020).
33

---

Published as a conference paper at ICLR 2024
Now split the sum into two parts. In the first part, examine 9 g' such that max y' I: Kev. < e for some constant 0 < 1/v3, and leave the remaining cases for the other part. Collect the pairs 9, g' in the first part into a set G₁. Then
Ex-N [Sexp (B,
(xxx X) B x)
(122)
G Glllfxpplly
g#g'EG.
[E [ (B. (B) X) (B x)]
(123)
Glll
l
gfg'EG1
1
Σ
|B
By
(124)
G
9#''EG
where is the number of neurons in the hidden layer fexp- The second line comes from the triangle inequality and the last line comes from Theorem 27.
We have,
BB B < [B B
(125)
= =22² + (ga, (g' ) + (gy. (2))
(126)
< 3 ((22)* + Nga, (s)) + Key. (z))))"
(127)
The last line uses power mean inequality. By our assumptions,
32/2-1 Σ Mgx, (o')=)\* |G 1) (Av3)**
< 1)(c)))))))
(128)
3
9E''EG
and similarly 3*/2-1 - Eg Koy, (g') [GI[ (c)33
Plugging back.
Σ
Ex^N [Sexp( BB (Bx S 1) v3)*.
(129)
fexp 1
ggg''EG,
Since |G| = poly(n) and A = (n)), the final expression is o(1) in n.
We now consider the remaining part which reproduced here:
Ex-N [Fox (9B) X) ()f= ((''B) [x]
(130)
flllf &v GG
Zooming in, we have:
Σ
Ex2N [fop BB X) Xf [)
(131)
Σ 14
Σ
Σ
Σ
3tg'EG=
"l....... jn I P...--mm
Ooyii ... Ommiii (Sesp [ml] (.)0
)(ml
D ) Br) ... ...(B.. Dinhh
(132)
d Σ Σ
Σ
Σ
E G1 m=
Vi tn
Oer ... Domiim (Sopp) Ilml
(-))0..)) ... Drm Sin (m By )i ... (B, B jmm
(133)
34

---

Published as a conference paper at ICLR 2024
where the second line comes from Corollary 25 and the last line is because all low-degree moment of fexp vanishes.
Further zooming in, for each + g' E G each m 2 k and each uy,..., Um E [2] denote P. as d. Demad (Sexp) (mll() for each E [2]m, and the corresponding vector E IR²" We
have, using Einstein notation to sum over ji.... Jm: Ji......... Im
Der.i ... Demum (Fep)) (-)0 ... Demit (Fexp) ylml (mxp))m((())))))))))) ()B BB ... (B. Bg) Imm (B, Byy))mmp @
(134)
By Corollary 43, it suffices to show that C' := B Bg satisfies =1 Cz 2 for all x E R?. However, note that by concentration results of Lemma 29, for any small E (0, 1),
Fg.s' + 8m
(ga, g/a)) E
F F
8z
(135)
-1-c
Fass + by
g'y. E
F. bg:
(136)
VI-E
(gx, y) = 61
(137)
(gy. g x) = E2
(138)
for 0y 2 max(02, sy le11, (22l) 0(n-1122) and Fa.0/ Fog /n with Fgg denotes the number of fixed points of " as in Lemma 29. Note that 2 F Fggg ci is bounded away from 0 (by definition of G1 and concentration result in Lemma 29). Choose small enough that VI -e =fgggg C2 C2 oz C2 by all bounded away from O when is large enough. Thus, for any R2
Cz 2 2/2
8z) +
22 - 5g)
+ #1222(c1 + 62)
(139)
E2
(E1 + E2)
(c2
dz)
21
#2
+ x2
C2
8y
(140)
02
8z
C2 8n
which is clearly nonnegative for large enough n C2 is bounded away from O. We conclude that pd p (B, Bg)) @mm p is nonnegative and thus removing these terms leads lower bound on || |
For pairwise correlation, we have:
KgB. ((B.9B))lL 5 Gl |1fésp li
Ex Σ
x)5= ((g X))
x)
(141)
g.g'EG
Σ
((B X X) frmp ((g B')
(142)
Gl |I
1l
9.9'EG
< ((n2((11/)))00)
(143)
Now we replace each 9ø by its normalization to make |1 1 Note that this only decreases (or increases by at most constant factor) the correlation between different hard functions since [|ge I = (1).. We are in position to apply Lemma 26. Let == maxB, (gB,, (9B,,9B,) La(N))- Computing average pairwise correlation of Og yields:
M(C5) 1/ + - 1/(B')) S 2/11B' +
(144)
Finally, setting T' B + gives SDA(CE (AAAC, -2(19) and application of Lemma 26 completes the proof.
35

---

Published as a conference paper at ICLR 2024
F.2 SUPERPOLYNOMIAL LOWER BOUNDS
Throughout, we will use the notation Cs to denote a subset of size k. The technique from this part comes mainly from (Goel al., 2020). Define:
fs : Raxd + R, where fs(X)= 1r
Σ WE (-1.1}
X(w)o((w, (ss)Vi
S S [n]]
(145)
where x is the parity function x(w) = II. Wi, and Xs E X or alternatively Xs E R denotes Σ w; (X));:
Xs and Rd + Rd an activation function. Throughout, we will set k S log, n so that the above network has at most ((n) hidden nodes. For any E (-", let X o be the matrix in Rand whose v-th row is x, v.:- We will use the following lemma, which is a basic consequence of properties proven in Goel et al. (2020), but include the proofs here to be self-contained.
the rows of X indexed by S. Here, (w) X))
Lemma 31. For all S # T C+ [n]. g G. and # E {-1, we have:
1. fs(g- (X o x))) = Xg- Xgg X) Xg xg 1.8 (X).
2. ||ss| 2
and (ss (T) = O.
Proof. Fix S / Ck [n].
1. By definition:
fs(X)
Σ x(w))((ww, (X.))s\/V
(146)
j=1 WE(-11111
where X.j is the j-th column of X. G acts on the rows of X, i.e. (gX):: = X Therefore, letting the order of S be fixed, we have (gX)s X g-1.--
We have, for any E G and any z E {-1,11²"
d
fs(g (X o o))) = Σ
x(w)o((w, ((g (X oz)))sss\//( (-1,1)))
Σ
(147)
/=l wE
Σ
x(w)o((w,((C 2))
(148)
1=l WE (-1.1)"
Σ
Σ
x(w))o(w,(X (X Zg ())
(149)
1=1 wE(-1114
Xg-1.5(2)
Σ
Σ
x(w 2g-1.s) 20-1. (X (x.))-11s)//
Jll (E(1,11
(150)
= -xg-1.((2) Σ
Σ
(xx))(t(((
(151)
j=l (-1,1
= -X
(152)
=X)-is(2)fs(g X).
(153)
In the above derivation, we use the definition of fs to get the first line. The second line comes from the fact that permuting by g. then taking the subset equivalent to taking the subset g S. The third line comes from the fact that each element of is scalar. The fourth line comes from the fact that x(w) = ss)) w 1g Finally, the last line comes from the
s a s.)).) The
fifth line is change of variable definition fs. and noting that the dependence of fs on S only comes from which row of X is selected by S; thus, (g)) fs(g X).
36

---

Published as a conference paper at ICLR 2024
2. We have, for any S $ T:
(TW
F [x-c4m)](s(X)]xx(
(154)
(155)
(156)
(157)
0
(158)
by sign-invariance of N and orthogonality of parity functions under 1ni
When S T, the same argument as Goel et al. (2020) Theorem 3.8 shows that Ss does not vanish.
Now, define the family of hard functions as:
Hs.F
fs 1
1 VIF(X)
fs(g [n] Ses gEF((X)
Σ
(159)
for some set depending on and The subsets in S such that these hard functions are orthogonal will determine the size of the family of hard functions, and therefore the CSQ dimension lower bound.
Definition 32 (Sign-invariant frame). A frame F is sign-invariant if F(X) = F(X oz) for almost all X (under the given data distribution) and for all = E (-1,13"
Lemma 33, F is any ingarintt frame, then there exists S with S 2 () (m) such that the functioons in H..FF are pairwise orthogonal, where (n) the size of the largest orbit of (Inl) where m = 2(log n) under G. If moreover [F(X) = for almost all x, then
|S] = ((1
Proof. We have for any S + T:
fus.f) Ex-N F(X)
Σ fslg X)fr(g'-x -X)
(160)
9.9'EF(X)
Σ
sslg (X o2))sT(('' (X o 22)
F(X
0.9 (.0'EF(Xoz)
(161)
-Es-Uni(-111p11Ex o(X
Σ
X xons (162)
9.9 (:00))(X0))
Un..Unit(-1,) F(X)
Σ
X X
(163)
9.x)FF(X)
Ex-N F(X)
fx
(.x'
(164)
Here, we have used that the frame sign-invariant to replace F(X o x) with simply F(X), and rearrange the expectations accordingly. Now, if we have no further assumptions F. then
37

---

Published as a conference paper at ICLR 2024
require S and T to be m 22oog -izzed subsets in different orbits (in other words, S + gf for all g E G). Then, by Lemma 31, 9 -' S + (g')) for any and g', and the inner expectation over x (and therefore the entire expression) is O. This yields a lower bound on |S] of ((((((l (n), from choosing one log n-sized subset from each orbit.
we moreover have that F has size one almost everywhere, then 5 * T suffices to ensure orthog- onality, and
set [S] n where of [n]- Note that if subsets are size ((logn), the hidden width of the network is polynomial and furthermore, if m S log, then the width ((n).
@ n) by letting S be all (log n)-sized subsets
Remark 34. Note that the definition of frame always allows one to choose a singleton frame F(X) for any X whose stabilizer trivial under the action of G on Raxd For any other X with nontrivial stabilizer, since G' is a subgroup of the permutation group, X must have at least 2 equal entries and thus lies manifold of dimensions strictly smaller than n d. Density of A thus ensures that PIx-N[[F(X)] = 1] = 1 as long as we choose the singleton frame at every X without self- symmetry. A practical choice of frame in this case, which is also sign-invariant, is the frame F(X) which is the set of all permutations that lexicographically sort X by absolute value. It is not hard to see that with probability under N, there is only permutation that sorts X.
Remark 35. The case of sign-invariant frames includes F(X) = G, the Reynolds operator.
Corollary 36. Let FF be sign-invariant frame. For any c > 0, any CSQ algorithm that queries from an oracle of concept f E HHs and outputs a hypothesis h with ||f hill S ( needs at least (nn / queries or at least one query with precision onn_)/2).
Corollary 37. Let F be a sign-invariant singleton frame. For any 0, any CSQ algorithm that queries from an oracle of concept f E Hss and outputs hypothesis h with || - h|la S O(1)
needs at least ((n2(log n)) queries or at least one query with precision o(n-e/2)
Proof. These corollaries are immediate applications of Theorem 4.1 and Lemma 2.6 from Goel al. (2020) to Lemma 33.
It remains show that the norms of the hard functions in HssF do not vanish. We show this below for aogn-invrriance, almost surely polynomial frames.
Lemma 38. Let Hs. be the hard functions derived in Lemma 33 from the class of hard func- tions H.s in Eq. (145) (which comes from Goel et al. (2020), but with an extra input dimension). Let (E(SE)) Unir(Hs) denote the average squared norm of functions uniformly drawn from H.s and let Mns.r max, jaEX,sEHs>> E[fs(X) ) denote the maximum squared norm of the hard functions in H..F. If /us.// (E(f31) Unif(Ha) (ppoyy(n)), then there exists constant e and subset C C H.SF of size |C] 2(HHs,ll/ poly(n)) many functions whose norms are at least c unlf()))m
Proof. We use a second moment method argument to prove the above statement. Let the ran- dom variable Z denote the squared norm E((fs(X)) of function drawn from the distribution Unif(Hs.rr) which is uniform over all functions in Hs.r. The Paley-Zygmund inequality states that for any given 0 E [0.
P(Z > 0E[Z]) 2 (1 0)2 E|Z
(165)
L|Za]*
The probability above calculates the portion of functions in Unif(Hs,F) which have non-vanishing norm.
Now, we calculate the first two moments of Z over the [Hs (*) functions in the class where k Olog n)) as in the construction in Goel et al. (2020). For the first moment,
38

---

Published as a conference paper at ICLR 2024
Ex~N12
1
Σ
(x,r(fs(X)))
(166)
|HssF
ieENs,
Ex~N
Σ
fs(g x))s()fsl x)
(167)
[(())
9.g'EF(X)
11
Ex-N
Σ
fs(X)
E
fslg X)fs(d
x)
k
[F(X)
SCt(n]
((EF((X)
at9'EF(X)
(168)
-1
2
Ex-N
E
Σ
fslg- x)²
k
[((x)
(EF(X) SEL(m)
11
Σ ExaN
Σ
((0s(())(00
k
F(()
|CN(m)
3.9 (.(')
9 S''
(169)
Ex-N
Σ
Σ
[slg x)²
[F(X)
(EF(X) (C
11
-1
Σ
Σ
ExWN (gg'FF(X) F(x)]
(g-1s(X)(())1s155
k
SC
EG (
(170)
where in the third line, we had the inequality 2 since we ignore g # g' such that g - (g')-1S
(the summands in this case is f fg-1s(X) > 0 so ignoring them gives lower bound) and then use reverse triangle inequality Ja + bl aa
[b].
The first term is
11 (m) 4:
11 k
Ex-N
[F(X)
Σ
Σ
fs(g x)²
=
ExaN
Σ fs(x)²
(EI(3)) Unil(Hs))
gEF(X) SCain]
SCa/nl
(171)
Now we show that the second term is O. For a fix S Ck [m]. E G such that g g # (g') we have:
Ex~N
[F(X) fo (x1s(()((on11s(
[
( fg 1s( =z) oz)
Ex-N
[F(X o 2)]
=Ex-N
[F(X) fg is(X)f(g) is(X)E= [x, is())x() ss(2)]
-0,
where we have used the fact that the frame is sign-invariant and the decomposition result from Equation (1) of (Goel et al., 2020). Thus the second term is 0.
39

---

Published as a conference paper at ICLR 2024
For the second moment, we have
F[Z9]
Σ
E[Js(X)))2
[
fsEHs.F
Σ
Elfs(X)??
(172)
max fsE
[Hs.Fl
JsE
M
Thus, applying Jaley-Zygmund, we have
P P(Z> 0 (Elfš)) Unit(P)s)) (1 0)- E E|Za| 2 (1 0)2 (EIfEl) (ni M M
Hs.5"
(173)
Setting c = (1 - 0) completes the proof.
Corollary 39. Assuming that the activation ReLU or sigmoid, the subset of non-vanishing func-
tions in Hs.F is superpolynomial in n.
Proof. It suffices show that / (EIS)) is O(poly(n)).
Theorem 3.8 of Goel et al. (2020) guarantees that (EI(E)) 2 ((-0())) Ω (poly(n) (since k = @(logm))
To upper bound MHS.F, we uniformly bound, for each fs E H....
(ue, (g X..)s))
Ex (
Σ Σ
x(w)o
Vic
gEF(#) 1=1
WE (-
(174)
(x(w)a (wu, (g (wW, X x.))ss)
< EEx-N VIF(X)j2*
Σ Σ
Σ
Vk
8EF(X) j=1 (-d,e
(175)
((w, (g. xs))s))²
< EEx>N
VIF(X) Σ
Σ
(176)
k
gEf(X) j=l WE(-1.1)
$ Ex
VIF(X))2*
Σ Σ
Eg.
(177)
(EF(X) we 11,1)&
Ex-N ( dkamj (oly(n) (xx))
(178)
where æn is the largest entry in absolute value of X. In the above, we use Canchy-Schwarz in- equality for the second and fourth line, while the third line uses the fact that ReLU(x)² < x² for all IR. Since with probability 1, FFX) is at most polynomial in by our assumption, it suffices to show that the order (either largest or smallest) statistic Z[j) has small moment when X is a iid Gaussian random vector of length n d.
Bounding this moment is classical study in concentration inequalities. By inequality of Ta- lagrand (Chatterjee, 2014; Talagrand, 1994), we know that E. (=(1) (F=(2 s C/log(nd) for some constant C. The first moment is also bounded by O ((vloo((d)) and thus F=((=f]) S (llg((n)).
Thus MHs (ppol((n)) and our conclusions follow.
40

---

Published as a conference paper at ICLR 2024
F.3 PROOF OF EXTRA TOOLS
Lemma 40 (Sub-Gaussian concentration for inner-product with permuted vector). Let G S Sn with least elements and fix arbitrary 9 + g' G. Then for any e 10,1/2):
[ga. g'a))
Pr
Pgggg
2 22(n9) I exp( exp(-S2(n2*),
(179)
|-|||
for some pg.g Fa.o' Fa.g vn-T: vn
9. (1 and where Fg.g is the number of fixed points g g' (i.e. the number of cycles of length in its cycle representation).
.ie i.e Hg.
Proof. Let
f(x)= = (gar, g' g'xr) a:) ||0|||
(180)
where x NOO, In).
Note that
(gx) g'x)
V (()
| ch + xh-1)
(181)
||a0] (ar, ar)
where Hy consists of æ with entries reordered by = =9- gogggoo g', i.c. [an]e = (2))--(()) Via triangle inequality,
S | | S
(182)
Thus, by Gaussian Lipschitz concentration (Lemma 2.2 of (Pisier, 1986)), we have that:
Pr
(gx.g'zt x)
Ef(x))
2 S((())
S exp(-1222 ()n(-))(n?)))..
(183)
|x|
Finally, we compute = Exf()). To do this, note that for every i * j E [m].
(-0;,) O,
F
F
(184)
x
| l|
by a change of variable formula x ++ (I1....,
I. Izs 2++1. ................................ Fr.)
At the same time, for every i * E [ns].
x
x
1
E
Ex
Ex
Exe
|
(185)
x
2
n
by a change of variable that swaps m, and æ. using permutation Jacobian matrix with determinant +1.
Thus Fess' E, |a//222 where Fo.g is the number of fixed points of g' We appeal to elemen-
tary analysis of Gaussian vectors (for instance, Chandrasekaran et (2012)) to obtain:
Ea = 22 T((n + 1)/2) E In//vn+1,v,,
(186)
T(n/2)
where I' is Euler's Gamma function. Thus, we have
1 E Fa.
Fgg
(187)
Vn
Lemma 41. Let E RD be unit vector iid uniformly distributed the n-dimensional unit sphere. Let G < Sn and # g' E G. Let Fg be the number of fixed points of h := g g action on [n]. Then for all 1/2) and small (0, 1):
Fg.00
Pr (gar, 9' g'x))
2 10n 1/2)
< <exp(_S((17)
(188)
n/1
(go, g'a:) -VT Fg.g' < - 12(n
Pr
$ (exp(-S((m1))
(189)
41

---

Published as a conference paper at ICLR 2024
Proof. Recall that an alternative way to sample unit vectors i..dd uniformly from the hypersphere is to first sample = ~ NN(,, In) and then set a == T=llaa Thus, we study (9z.g'z) =)
To do this, note that concentration of ||=||2 is well studied (Proposition 2.2 and Corollary 2.3 of Barvinok (2005)), for any 0 < c
< 1:
max
Pr
|| la
n2 V 11-e)
Pr
[|2||2 S v(I S <cxp(-en/4)
(190)
Concentration of the random variable (gz, g' 2) || was studied in Lemma 40 as:
[ gf x)/1|=|12 - Ma.grl 2 1/22 - exp( exp(-I((2*)),
Pr Nm
(191)
for some Ha.9' E (Fa.g// Vn= + 1, 1. Fa.a/ /n]. Since J.. - O(n 3/2) and Fa.0¹ S n, we can also write:
(gx, g'z)
Fo.g/ 2 2(15))
Pr
S exx((-2(nn
(192)
||a|||
Vn
and
Pr
(gxr, g'x))
Fg.g Vn
< -Q(n())
S Sexp(-SS(11
(193)
||0||
We have by union bound:
(gz, g'z)
Fg.g
ggz.
Fgg
Pr
< Pr > 1/3)
+ a(n9))
+ Pr|[|l2|2 < /(1 - e)ml
1 2
nvl-c
||
vn
(194)
< <exp(- (S((12)))) + exp(-e?n/4)
(195)
S Exp((1((n>
(196)
On the other side,
Pr
[gz, g' z)
2
Fa.g
n
< 212))11/2)
Pr
(gz,g'z)
||
<
Fas
vn
2(n9)
+ +Pr
|| 2l >
V
1
n
(197)
I (xxp(-S(n22)) + expl-c2n//
(198)
S exp((-S((220)
(199)
Lemma 42 (Kronecker product of PSD matrices PSD). For some m. n N. Fix A E Rm and B E Ruen not necessarily symmetric. for all x E RT x² Ax 2 O and for all E IR" RR, By 2 0 then for all z E Rmmn z (A B)z 2 0, where & is the Kronecker product.
Proof. Write x (z01) , 2m..), where 211 E RD for each i [m], then we have:
z =T 2 B)z
Σ
(A ) [0)
(200)
j.j
Σ
A
Σ
2/
i B B
(201)
w
j,'=1
m
Σ
A...
(202)
++=11
11) B Bi 2/y
(1)
where C.,y time, for any w RT
2,
Now it is not hard to see that C' is symmetric. At the same
n Σ
12
w Cw=
w. W
2
B
3
Σ
(wiz)
B),r (w)z))))
(203)
1,==1
=-'=1
i,
=
42

---

Published as a conference paper at ICLR 2024
By property of B, the inner sum is nonnegative and thus w" Cw is nonnegative. Therefore conclude that C' is symmetric positive semi definiefnite and thus admits a spectral decomposition:
C
(204)
for of vectors nl8l and nonnegative A 0, k E [r] for some Thus,
A Cis
Σ
A
(205)
k=1
6, k=
By property of A and the fact that 2 are nonnegative, the inner sum is nonnegative and we get our conclusion.
Corollary 43 (PSD of tensor power). For any m, n E IN if A E R such that x. T Ax > Ofror all Rm, then A &n satisfies: z A for all Rm
Proof. Apply Lemma 42 times.
Proof of Lemma 29, We use Corollary D.3 from (Diakonikolas et al., 2017) copied below:
Lemma 44 (Corollary D.3 from (Diakonikolas et al., 2017)). Let æ, y E R" be two unit vectors iid uniformly distributed over the n-dimensional unit sphere. Then:
Prik b)1 2 U(n (22n-112) s exp(-s((n2
(206)
for any c E (0,1/2)
Let g.g E F be two arbitrary permutations that act on Rn by permuting the vector. Since the uniform distribution over the n-dimenional unit sphere is invariant to permutation of the indices, its pushforward via g and g' still uniform. Therefore, we have, for any g. E F:
Pr Pril g y)) 2 ((n=-1/2) (xx(-S((n29))
(207)
a.y
Draw 22(nn)/ F| such iid vectors to form set C R". We have, by union bound:
Pr
Pi + j 3g. F. (gxz gf (x;) 1(n=-112
(208)
Pr [1 x, 2(n 1 Di
(209)
(JE((T 9:0 <20(1))
exp(-S((n22)
(210)
(211)
On the other hand, let o' be the number of fixed points of g "''' for some g # g' E F. also want to union bound using Lemma 41, for any small constant e (0, 1):
Fg.g'
Pr
Bi [T], 3g + g' E F, (g
2 2(no-1/2))
(212)
noT
Σ
Pr
(gI1.
n/1 2 1125-113) 2 1(22-1133)
Fg.g'
(213)
1E|2" g'
<3 20(1))
exp( exp((S((122))
(214)
<xpl
(on--(((2))) Exx((-((n1)
(215)
43

---

Published as a conference paper at ICLR 2024
Similarly,
[ # g E F, (' -1 Fa.g S 112
Pr
s <exp(-S((n"))
(216)
Therefore, for every small E (0, 1), there exists a set S C R of size T = /00nn) //1// such that for every x + y E S. for every g # g' E we have:
| 12 =1
(217)
max(Kga (y)), (gre, gf ")1)) S O(2-1112),
(218)
Fggo S (((n1112)
(gwi, x;)
(219)
nv 1
(g<;, g'm)) - v1 Fg.g -0(n-1/22)
(220)
Pair elements of S (as column vectors) together arbitrarily to obtain set B' of matrices in RT*2 of size T/2. Each element of B' has two columns, each one of these columns is a distinct vector in S.
We have, for any B 11,,,, 21,2), B' =: (22,1, #2,2) E B², and for any g.g' F.
[(gB) (g'
(g'BB))))))) BD) = () B)) I
Σ (J
1/2-11/3).
(221)
The remaining conditions in Lemma 29 are also straightforward to check.
G LEARNING INVARIANT POLYNOMIALS
Here, we aim to extend the algorithm of Andoni et al. (2014) to the setting of invariant polynomials. This algorithm is an SQ algorithm, but not CSQ algorithm.
First, let us review the GROWING-BASIS algorithm. Assume inputs æ E IR" are distributed ac- cording some product distribution D Un X X Mn. The goal of the algorithm is to learn the coefficients of some polynomial f(xx) = Σ s ag Hs(x) (x) where S = Sg........ ..). is tuple of positive integers which indicate the degree of the polynomial in the i-th variable. The monomials in the polynomial take the form
('))) = Σ as (ggH(()) where Hs(x)
II Hs, (z:).
(222)
where Hs, is the S,-th degree polynomial in class of polynomials orthogonal under the distribu- tion D: (H, H3) = Hz (x)),(r)dr= = 0 for all i + j. An example of such an orthogonal set of polynomials are the Legendre polynomials which are orthogonal under the uniform distribution over [-1,
Next, rigorously obtain separation invariant function classes, we need define few objects. We will often simplify notation or definitions for ease of readability; the presentation this material its full mathematical rigor can be found in various textbooks, e.g. Derksen Kemper (2015).
Independent generators Let .I..... Ir be invariant functions and K a field, either R or C. The ring of polynomial K(g,,..., gr] is the set of all sums Σ.er- G, where g = IT 9,a Assume that {gi)-= are independent in the sense that for all i [r]. there is no polynomial function K" - K. It is not hard to
P E [[g1,.... 1, 9i -it1.........................1.. Or| that agrees with see that if member of K(g...... : 9rl can be evaluated as a function K" + K then they are also invariant functions. The converse is not true, in general, as some invariant functions may not be written as polynomials over certain generators. However, some special groups have nice, finitely many generators whose polynomial ring spans almost the whole space of invariant functions. De- note by Jdd := K(g......,ge [r] Sd the set of all polynomials in g, 's with degree at most d, i.c., Enenn Σ. a.
44

---

Published as a conference paper at ICLR 2024
Vector space of bounded degree polynomials generated by finite set A different way of thinking about Fulr is as a vector space. Let (gi........ . be the (r + 1)d dimensiooa vector space over the field k. whose canonical basis is the set (e))))()))))))) It is not hard to show that
(g1,...... :........................... 9r) is isomorphic to Klgi..... 9- _ by identifying e, to the monomial IT==1 91, where 9o = 1. This perspective as a vector space allows for a nice calculus tool: let be a product distribu- tion over K" (tuples of length r, with each entry an element in K) and (f, g)F := f s'dP. Here, we once again think of gi is functions KM + K and so are elements in Fddr. Applying Gram-Schmidt generates another set of orthogonal (in (-s-))) elements H1.... H( 1)a. Note that there are still (r + 1)dh such orthogonal functions since Gram- Schmidt preserves dimensionality of the input and ouput vector spaces. This process in analogous to that constructing the Hermite and Legendre polynomials for Gaussian in uniform distributions respectively. When P is a product distribution, we can reindex this basis as (E(O)U(()))))
orthogonalization to basis elements of V ('
9 ...0.....99.).
Sparse polynomial Before giving any formal results, we must state some technical preliminary restrictions that must be set for learning to be possible. Our learning setting restricts frdr only contain polynomials in 91.-..,9r 9r with at most k terms in the expansion using ( HH, ((0))(()) In other words, when viewed vectors in (gi...... 9r) under the basis {(H))ε((())()))) only k elements are non-zero. Call this new set Fdd.r.k.
We should also note that for technical reasons, we restrict the outputs of the polynomials to be nor- malized within some bounded range to properly normalize the function with respect the error metric and allow for the SQ query bounds to also properly query such functions. In the GROWING- BASIS algorithm, one must make queries to estimate (H,. f*) and (He, (f) Given any sta- tistical query function has output bounded in the range [-1, to measure the correlations, we must choose a query function that divides by the maximum value of ( in some high prob- ability region D) S K" with measure P(D) 2 o1((1) and outputs zero elsewhere. This way, statistical query functions whose outputs are bounded in the range --1++1] can effectively cal- culate the proper correlations needed in the algorithm. Thus, we introduce a normalization term
Ma. max D. (eE((() { and introduce this quantity into the query tolerance to allow for proper estimation of relevant variables. This normalization plays a similar role to the quantity Ma. in Andoni al. (2014) for their guarantees of sampling complexity. When the target function f is properly bounded, it is not too hard to see that this quantity is also easily bounded.
For example, when | = (1) in the range [-1,+1]" +1]", Ma, is at most a constant for inputs drawn from the uniform distribution over the interval [-1, since the Legendre polynomials are also ap- propriately bounded. In general, functions can always be normalized by dividing by an appropriate constant.
Finally, the GROWING-BASHI algorithm depends on a parameter Ta that controls how much higher order terms show up in the square of polynomial. More formally, let H, : K - denote the i-th orthogonal polynomial for some given distribution on K. For any such orthogonal polynomial, we have the decomposition (see equation 2.1 of Andoni et al. (2014))
2
H₂(x) = 1+
Σ Ce. (z). j=1
(223)
Let et c222, then Fa = minega Ct. This quantity is generally bounded for common distributions, e.g., when H, are the Hermite or Legendre polynomials then Tą (2(1) (Andoni et al., 2014).
With this set up, we are ready to state and prove our main result for this section:
Theorem 45 (Adapted from theorems 2.1 and 2.2 of Andoni et al. (2014)). Let K be a field, I1....,9r 9r be independent functions K" + K that are invariant to group G acting alge-
'We also note that it is technically more efficient to apply this procedure to each of the generators indi- vidually. That is, apply Gram-Schmin to the space gi, ....... 9.".. Since there is a product distribution, this procedure constructs orthogonal polynomials in each basis which can then be combined to construct orthogonal polynomials in K K[g ([g1....994 D-]
"We note that there are likely more effective means of handling this normalization requirement, by e.g., composing multiple queries together to calculate the relevant quantities. However, we do not consider this strengthening here for sake of simplicity.
45

---

Published as a conference paper at ICLR 2024
braically on Klgı.....,hh defined above. Let P be product distribution and define the in- ner product (p. q)p := (g==( ((()) Let ((0o)ee( be the output of Gram- Schmidi on Jrd.r with respect to this inner product. Further assume that the polynomial quotient H2m.o.....// (Hm.H.......)
(ignoring remainders) is Ta for every E [ld/2]]. Let Fd.r k be the space of polynomials in Fdl that is k sparse in H2 basis. Then any CSQ algorithm with oracle access to (' for some f E Fdirk that outputs a hypothesis h E F.drr while achieving mean square error ||h (lh-Fi Ip < O1) must make either least (r + 1) calls to the oracle or require precision less than O(r for any c > O. However, GROWING-BA MIOOINNG-BSSS can learn h with error ||h --- [[ < x0(1) using only O(krd(1/Ta)) calls oracles (: and (;(()))) with precision (2(T3) / (krddax)))
Proof. The CSQ lower bound can be obtained by invoking standard correlational statistical queries dimension bound form orthogonal polynomials (Diakonikolas al., 2020; Goel et al., 2020; Reyzin, 2020; Szörényi, 2009). Specifically, by correctness of Gram-Schmidt orthonormalization, the set of basis elements { ( ) (e(()))(r)) also form a pairwise orthogonal set, which each themselves have norm 1 under (p. q) thus CSQ dimension of I* E Jrd,,k is immediately lower bounded by M(1a)) and the conclusion for CSQ algorithms follow.
The SQ upper bound via BROWING-BASIS can be obtained by observing that Andoni et al. (2014)'s proof still works verbatim when the main ingredients are there: a product distribution, an inner product with an orthornormal basis, and access to oracle {-, )²) Note that although the GROWING-BASE BASIS algorithm presented error free, we allow small errors, by making a thresh- olding in Step 2 and 8 of Andoni et al. (2014) equal to the error tolerance guaranteed to miss only terms with low correlation and thus bounded effect on the final mean square error. To be more precise, every time we made error on the cutoff of step 8, we lose as most fraction of the precision that amounts to T where as stated before Ta is the coefficient of H2n.0.....0 in oH.. Intuitively, when losing a monomial in the final product, the norm of the monomial can multiplicatively compound over each variable. Ta is the lowest possible amount each variable can contribute to this loss (See (Andoni et al., 2014), Lemma 2.3). Finally, we also must divide the query tolerance by a factor Ma.e to account for the normalization of the target function as discussed earlier.
This way. we are
In the same setting as Theorem 45, if instead, we are interested in polynomials that are k-sparse in the canonical basis ([T 96 E, a; = =} (recall that F.dr..k was sparse in the orthogonal basis (()))((()))()))))) Then the query complexity of GROWING-BASIS becomes at most Okrrd2)) with precision R(1/(krd2d) whenever 2(1) and targets are normalized so that Ma,k = O1).
Corollary 46.
Proof. By the same argument as Lemma 2. of (Andoni et al., 2014), any change of basis in the vector space of polynomials of bounded degree incur at worst multiplicative factor 2d in the spar- sity parameter. Since the new function class is k-sparse in the canonical basis, it is -sparee in the orthogonal basis. Apply Theorem 45 to this new sparsity level get the desired result.
This separation is weaker than when there is sparsity in the orthogonal basis. However, there is still polynomial (in r) separation between CSQ and SQ if d and &s are set to be constant independent of r and a superpolynomial separation when d = (llo(())).
Finally, for the above theorem to give meaningful separation, we list some example groups for which there is a simple distribution D over inputs such that the push-forward distribution P = Φ D
via the map o: x (a1,...., 2n,) +> (g1()), (x)) is product distribution.
Example Consider inputs X E Rax3 which correspond to n points in RR3, Ordered point clouds are symmetric under the action X U for matrix U (33) in the orthogonal group. Let inputs X have entries drawn i.i.d Gaussian. Consider generators 91..... In where g (z) = |X | is the sum of the squares of the i-th row of X and clearly invariant orthogonal transformations.
which
The pushforward distribution after the mapping X + [gi (X)..... ............ 9.. (X)) is product distribution over Chi-squared random variables x²())".
46

---

Published as a conference paper at ICLR 2024
Train Set
MSE 0/1 Error
100
Test Set
0.5
Error (log axis)
10-3
Error
0.4
10
0.3
10-9
Train
MSE
Test Set
500
1000
1500
2000
250
500 Epoch
750
1000
Epoch
(a) GNN learning HER.
(b) CNN learning C
Figure 3: Replication of experiments as in Fig. 1, except here, consider minimal architecture consisting of a single layer of graph or cyclic convolution followed by a single hidden layer MIP. This is the minimal number of layers needed learn the desired function classes for the architectures considered. For the CNN plot, the jumps in the train set MSE are due to perturbations in the loss at very low values near computer precision.
optimizer Adam
optimizer SGD
optimizer RMSprop
Train Set
Test Set
0.7
metric
MSE
Error Value
0.6
0/1 Emor
0.5
0.4
0.3
0
100
200
100
200
0
100
200
epoch
epoch
epoch
Figure 4: Replication of experiments in Fig. 1a with different optimizers show that the performance of the GNN is virtually the same across the various optimizers. Performance is averaged over 10 runs. For each run, the learning rate chosen by perturbing the default learning rate by random multiplicative factor in the range [0.1, 10).
Example 6. Consider inputs E C drawn from U|C {|2] | = 1}}" uniformly from unit norm complex numbers in each entry. The power sum symmetric polynomials consist generating ba- sis E, Fi ... E, ad] Another way to parameterize each æ; is as æ; e where 0 is distributed U10, 2T), for all E [na. Thus Z also be parameterized by e0 with the exact same distribution of U(0 2m), for all j E [m], E [d]. The distribution of [Σ, T...... E, x therefore a product distribution (Law(X) (n Zd))d where Z; ~ UCC n {|æ] These generators and input distribu- tions come from the classical text of Macdonald (1979). Here, as long S. only depends and not n. Plugging this r into Theorem 45 gives straightforward bounds that are independent of n-the original number of variables, but does not give meaningful separation in Corollary 46.
As reminder, also have example in the main text for the sign group (Lim et al., 2022).
H EXPERIMENTAL DETAILS
GNN experiments were performed using the Pytorch Geometric library for implementing geometric architectures (Fey & Lenssen, 2019). The hard functions drawn from HER, (see Eq. (7))
47

---

Published as a conference paper at ICLR 2024
where subset S S [n]] was drawn uniformly from all the possible subsets of size |n/2] and b was either 0 or 1 with equal probability. For our experiments, we set n = 15 and trained on n² 225 datapoints. The overparameterized GNN used during training consisted of 3 layers of graph convolution followed by a node aggregation average pooling layer and a two layer ReLU ML.P with width 64. The graph convolution layers used 32 channels.
For the CNN experiments, we constructed the hard functions in Eq. (17) setting n = 50 and k: = 10. Here, matrices B B were drawn randomly from all possible 71 x orthogonal matrices by taking QR decomposition of random ni x 2 matrix with Gaussian i.i.d. elements. For sake of convenience, we did not divide by the norm of the function. The CNN architecture implemented consisted of three layers of fully parameterized cyclic convolution each with 100 output channels. This was followed by global average pooling layer and and two layer ReLU MLP of width 100. The network was given 10n 500 training samples and was trained with the Adam optimizer with batch size 32.
Experiments in the main text considered architectures which were overparameterized in terms of the number of layers with respect to the target function. For sake of completeness, Fig. 3 results for merely sufficiently parameterized networks which consist of a single convolution layer, pooling and single hidden layer MLP. The results in Fig. 3 are consistent with those observed in Fig. Additionally, to further confirm that these results are robust to hyperparameter choices for the optimizer, repeated the GNN learning experiments with the choice of optimizer varying between Adam, SGD, and RMSprop (Paszke et al., 2019). Fig. 4 shows the results for these different optimizers. For each optimizer, 10 simulations were performed where for each simulation, the learning rate was chosen by multiplying the default learning rate by a random number in the range (0.1,10]
include in
All experiments were run using Pytorch on a single GPU (Paszke et al., 2019). Default initialization schemes were used for the initial network weights. In our experiments, we used the Adam optimizer and tuned the learning rate in the range [0.0001, 0.003]. For CNN experiments, to increase stability of training in later stages, we added scheduler that divided the learning rate by two every 200 epochs. Plots are created by combining and averaging five random realizations of each experiment.
48


Reviews:
[{"review_id": "xvgzdc1Rz7", "reviewer": "Reviewer_aiE7", "summary": "This paper studies the hardness of learning certain two-layer or one-hidden-layer neural networks under symmetrized architecture/algorithmic designs on Gaussian inputs, via the Statistical Query (SQ) lower bound techniques. It provides several results characterizing the hardness of learning GNNs and CNNs via leveraging correlational SQ (CSQ) lower bounds for learning boolean functions and by connecting them with learning parity functions. It also discussed when CSQ lower bounds can be different than SQ lower bounds.", "questions": "None", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The question studied in this paper is closely related to a core question in understanding deep learning, that is: can deep learning benefit from symmetry-inspired algorithmic designs? In this sense I deem the question studied in the paper valuable and this paper's attempt to deal with it respectful.\n2. The technical contribution of this paper, although still depended on some prior works, is novel enough to my understanding to be nontrivial. This paper constructed function classes that were not studied before to specifically deal with their problems, and proved hardness of learning these classes, which is a notable effort. \n3. This paper covers both GNN and CNNs, and discussed the difference between CSQ and SQ in certain scenarios, which is good for completeness.", "weaknesses": "The weaknesses listed below are, in my opinion, secondary to the contributions of this paper.\nThe approach of this paper in studying the hardness of learning symmetry-enhanced neural networks has certain limitations. It cannot account for all neural architectures at once and requires specific construction whenever the problem formulation changes by a little bit. And the hard function classes, although are well designed for the proof, are not very intuitive in terms of broader impact to people who are outside of the learning theoretic community. Perhaps there could be more illustrative explanation for the intuition behinds the constructions and also its possible impacts outside pure theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6zP8ThkuVD", "reviewer": "Reviewer_Fgas", "summary": "This work considers the problem of learning symmetric Neural Networks.  The\nauthors provide hardness results for Statistical Query (SQ) and Correlational\nStatistical Query (CSQ) algorithms (and an NP-Hardness result for properly\nlearning Graph Neural Networks (GNNs)).  An example of a symmetric neural\nnetwork is a 2-layer GNN that maps an input graph $A$ to $g(f(A))$, where\n$f:\\{0, 1\\}^{n \\times n} \\mapsto R^k$ first aggregates $k$ permutation\ninvariant features of the input graph $A$ and $g$ is a one-hidden layer MLP.\n\nThe first result is an SQ hardness result for two-layer GNNs showing that for\nthe above class of GNNs $\\tau^2 2^{n^{\\Omega(1)}}$ queries of tolerance $\\tau$\nare required.  The result follows by designing a 2-layer GNN where the\n$i$-output of the first layer counts how many nodes have $i-1$ outgoing edges\nand the second layer selects a subset of those counts and computes its parity.\nBy using properties of GNP graphs, the authors reduce the problem to the\nwell-known hard problem of learning parity functions over the uniform\ndistribution on the $n$-dimensional Boolean hypercube.\n\nThe second result considers GNNs that take as input a $n \\times d$ feature\nmatrix $X$ and then compute $1_n^T \\sigma(A(G) X W) a$, for an adjacency matrix\n$A(G) \\in \\{0,1\\}^n$,a weight $d \\times 2 k$ matrix $W$ and a $2k$-dimensional\nweight vector $a$.  They give a $d^k$ CSQ lower bound for this problem.  This\nresult follows from adapting the hard instances of the CSQ lower bound\nconstruction of [2].\n\nThe third result shows that for CNNs (and more general frame-averaged networks)\nof the form $f(X) = 1/|G| \\sum_{g \\in G} a^T \\sigma (W^T g^{-1} X) 1_d$ where\n$X$ is a $n \\times d$ input matrix, $G$ is a group acting on $R^n$ (e.g., could\nbe cyclic shifts) either requires $2^{n^{\\Omega(1)}}/ |G|^2$ queries or a query\nwith precision $|G| 2^{-n^{\\Omega(1)}} + \\sqrt{|G|} n^{-\\Omega(k)}$.  The proof\nof this results also adapts the construction of [2] For more general\nframe-averaged networks, the authors use the techniques developed in [1] to\nshow a super-polynomial CSQ lower-bound (for any constant c either $n^{\\log n}$\nqueries are needed or a query with accuracy $n^{-c}$).\n\n\n[1] Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent.\nICML 2020.\n\n[2] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks. COLT 2020.", "questions": "1. See weaknesses. \n\n2. While the authors clearly state which lemmas and proofs of the prior works they are using, I think a more detailed high-level explanation of the arguments and the differences from prior work should appear in the main body of the paper.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The problem considered in this work is interesting and well-motivated. Most theoretical prior works on learning neural networks focused on fully connected shallow networks; investigating the learnability of popular and practically relevant classes of neural networks such as GNNs and CNNs (that have more restricted symmetric structure) is a natural\nnext step.\n\n2. The paper provides hardness results for various classes of ``symmetric'' neural networks in the SQ and CSQ models that are general models of computation capturing, for example, stochastic gradient descent algorithms.\n\n3. I found the paper to be well-organized and written. The authors clearly state what results of prior works they rely on to get their results.", "weaknesses": "1. The novelty of the technics and arguments used in the lower bounds provided in this work may be limited in the sense that most of the claimed results rely heavily on machinery developed in the prior works [1,2].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CcXKfWf3zW", "reviewer": "Reviewer_kFXh", "summary": "The authors study the computational hardness of learning equivariant networks using gradient descent.  They show that enforcing symmetries like permutation invariance does not make learning any substantially easier, and that their hardness results hold even for shallow 1-layer GNNs and CNNs.  They provide statistical query (SQ) lower bounds that scale exponentially with feature dimensions for various architectures.  Additionally, the authors provide an efficient non-gradient based algorithm for learning sparse invariant polynomials, separating SQ and correlational SQ complexity.  Lastly, they perform numerous experiments to verify their results.", "questions": "Could the authors comment more on the applicability of \"worst-case\" reasoning re: the likelihood of these function classes to well-describe nature?  It seems plausible that the worst case could be significantly harder than the typical case for problems that we care about.  In practice, these sorts of hardness results don't seem to impact practitioner's usage of these model classes much at all!", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Originality:\n\nThe authors prove numerous new results on the sample complexity of learning in neural networks, and provide ample empirical support for their work.\n\nQuality/clarity:\n\nThe authors sketch their proofs using careful, clear technical arguments.  Additionally, their experiments are simple, but clear demonstrations of the practical difficulty of learning networks within the families they authors study.\n\nSignificance:\n\nThe author's work significantly advances progress on the hardness of learning symmetric networks, opening the door to clear avenues of future, follow-up work.", "weaknesses": "I would've liked a _slightly_ more thorough empirical treatment, if only to make sure that the failure to learn was not due to poor hyperparameter choices / poor initialization etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)