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.

通过梯度下降，我们研究了学习等变神经网络的问题。尽管已知的问题对称（“等变性”）被纳入神经网络中，经验上改善了从生物学到计算机视觉等领域的学习流程的性能，但是一项有关学习理论的研究表明，在相关统计查询模型（CSQ）中，实际学习浅层全连接（即非对称）网络的复杂度呈指数级增长。在这项工作中，我们提出了一个问题：已知的问题对称是否足以减轻通过梯度下降学习等变神经网络的基本困难？我们的答案是否定的。特别地，我们给出了浅层图神经网络、卷积网络、不变多项式和排列子群的框架平均网络的下界，这些下界在相关输入维度中都以超多项式或指数级增长。因此，尽管通过对称性注入了显著的归纳偏差，但通过梯度下降实际学习等变神经网络所代表的完整函数类仍然是困难的。

关于对称性下的学习难度