On the hardness of learning under symmetries

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.

This work considers the problem of learning symmetric Neural Networks. The authors provide hardness results for Statistical Query (SQ) and Correlational Statistical Query (CSQ) algorithms (and an NP-Hardness result for properly learning Graph Neural Networks (GNNs)). An example of a symmetric neural network is a 2-layer GNN that maps an input graph $A$ to $g(f(A))$, where $f:\{0, 1\}^{n \times n} \mapsto R^k$ first aggregates $k$ permutation invariant features of the input graph $A$ and $g$ is a one-hidden layer MLP.

The first result is an SQ hardness result for two-layer GNNs showing that for the above class of GNNs $\tau^2 2^{n^{\Omega(1)}}$ queries of tolerance $\tau$ are required. The result follows by designing a 2-layer GNN where the $i$-output of the first layer counts how many nodes have $i-1$ outgoing edges and the second layer selects a subset of those counts and computes its parity. By using properties of GNP graphs, the authors reduce the problem to the well-known hard problem of learning parity functions over the uniform distribution on the $n$-dimensional Boolean hypercube.

The second result considers GNNs that take as input a $n \times d$ feature matrix $X$ and then compute $1_n^T \sigma(A(G) X W) a$, for an adjacency matrix $A(G) \in \{0,1\}^n$,a weight $d \times 2 k$ matrix $W$ and a $2k$-dimensional weight vector $a$. They give a $d^k$ CSQ lower bound for this problem. This result follows from adapting the hard instances of the CSQ lower bound construction of [2].

The third result shows that for CNNs (and more general frame-averaged networks) of the form $f(X) = 1/|G| \sum_{g \in G} a^T \sigma (W^T g^{-1} X) 1_d$ where $X$ is a $n \times d$ input matrix, $G$ is a group acting on $R^n$ (e.g., could be cyclic shifts) either requires $2^{n^{\Omega(1)}}/ |G|^2$ queries or a query with precision $|G| 2^{-n^{\Omega(1)}} + \sqrt{|G|} n^{-\Omega(k)}$. The proof of this results also adapts the construction of [2] For more general frame-averaged networks, the authors use the techniques developed in [1] to show a super-polynomial CSQ lower-bound (for any constant c either $n^{\log n}$ queries are needed or a query with accuracy $n^{-c}$).

[1] Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. ICML 2020.

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

We thank the reviewers for their insightful comments and feedback. As an overall point, we have made two changes to the draft in response to the reviewers’ feedback:

• Under the Our contributions subsection, we have added some further explanation of our technical arguments and a discussion of the differences with and motivation from prior work.
• In response to reviewer kFXh’s feedback about the sensitivity of our experiments with respect to hyperparameters, we have added additional experiments in the supplemental material (Appendix H) with different optimization algorithms and hyperparameters to show that the empirical results are consistent across such choices.

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.

After careful consideration of the reviewers' feedback and the authors' responses, the consensus is that the paper "Statistical Query Lower Bounds for Symmetric Neural Networks" is a valuable contribution to the field of machine learning theory. The paper addresses an important question regarding whether deep learning can benefit from symmetry-inspired algorithmic designs, focusing on the hardness of learning graph neural networks (GNNs) and convolutional neural networks (CNNs) using Statistical Query (SQ) lower bounds.

The strengths of the paper are clear. It presents novel technical contributions by constructing specific function classes to prove the hardness of learning these classes under symmetrized architecture/algorithmic designs. Moreover, the paper thoroughly explores both GNNs and CNNs and discusses the distinction between correlational SQ (CSQ) and SQ lower bounds in certain contexts, adding to the completeness of the work.

While some reviewers pointed out limitations, such as the approach's potential lack of generality and the non-intuitiveness of the hard function classes for those outside the learning theoretic community, these are outweighed by the paper's core contributions. Additionally, the authors have acknowledged these points and expressed their intent to address them in future work, which demonstrates a commitment to furthering the research in this area.

Questions about the applicability of "worst-case" reasoning were raised, and the authors provided a thoughtful response, suggesting future research directions that could bridge the gap between theory and practice. The authors also addressed concerns about empirical validation by including additional experiments in the supplemental material.

In light of the above, the paper is accepted for publication. The combination of theoretical insights, technical novelty, and a thoughtful discussion of the results' implications make this a good paper that will likely stimulate further research.

Accept (spotlight)