We thank the reviewer for their positive feedback and insightful comments. We respond to specific points below.
> 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.
In our experiments, we found little to no difference in the results based on the choice of hyperparameters. For example, for the varying levels of overparameterization (e.g. more layers) and various learning rates that we tested, the results were essentially the same. Some of this is reported in the appendix, Section H (Figure 3). We have also included an additional plot showing that the performance of the GNN is consistent across three different optimizers (Adam, SGD, RMSprop) and different learning rates for those optimizers.
> 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!
The reviewer raises a good question that we hope forms the basis for future studies. Indeed, as pointed out by the reviewer and in the discussion section of our paper (Section 8), the functions we see in the real world are clearly learnable, and definitely not in the form of the rather adversarial ones studied here. Something has to be changed in the theoretical setting to tie it closer to practice; this is also the case for the existing line of work on SQ/CSQ lower bounds for fully-connected neural networks. To proceed formally, we see two paths for future study. First, worst-case settings such as SQ/CSQ can give too much flexibility to produce hard functions, which are often rather contrived. Some ways to make the setting more practical are to change the data input model (e.g. data that falls on a low dimensional manifold), or to introduce noise to the function class (e.g. weights are randomly chosen or subject to random perturbation). Second, we can reduce the size of the function class to rule out impractically adversarial learning tasks, e.g. by placing restrictions on the weights of the architectures to make them more tied to realistic functions. Such restrictions could also include bounds on the condition number, rank, etc. Promising work in these directions has been done for simple architectures, and we hope these ideas are expanded and studied in the symmetric setting as well [1-4].
**References:**\
[1] Chen, Sitan, et al. "Learning narrow one-hidden-layer relu networks." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.
[2] Diakonikolas, Ilias, and Daniel M. Kane. "Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials." arXiv preprint arXiv:2307.12840 (2023).
[3] Daniely, Amit, Nathan Srebro, and Gal Vardi. "Most Neural Networks Are Almost Learnable." arXiv preprint arXiv:2305.16508 (2023).
[4] Goel, Surbhi, et al. "Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms." Advances in Neural Information Processing Systems 35 (2022): 7328-7341.