The paper investigates the hardness of learning equivariant neural networks using gradient descent, focusing on the computational complexity of this task. Despite the empirical success of incorporating symmetries into neural networks, theoretical studies have shown that learning shallow, fully-connected networks is exponentially complex in the correlational statistical query (CSQ) model, which includes gradient descent. The authors explore whether known problem symmetries are sufficient to alleviate this hardness. They provide negative results, demonstrating that lower bounds for learning shallow graph neural networks, convolutional networks, invariant polynomials, and frame-averaged networks scale superpolynomially or exponentially in the input dimension. This indicates that even with the inductive bias provided by symmetry, learning the complete classes of functions represented by equivariant neural networks via gradient descent remains challenging. The paper contributes to the understanding of the computational hardness of learning and provides insights into the limitations of gradient descent in the presence of symmetries.The paper investigates the hardness of learning equivariant neural networks using gradient descent, focusing on the computational complexity of this task. Despite the empirical success of incorporating symmetries into neural networks, theoretical studies have shown that learning shallow, fully-connected networks is exponentially complex in the correlational statistical query (CSQ) model, which includes gradient descent. The authors explore whether known problem symmetries are sufficient to alleviate this hardness. They provide negative results, demonstrating that lower bounds for learning shallow graph neural networks, convolutional networks, invariant polynomials, and frame-averaged networks scale superpolynomially or exponentially in the input dimension. This indicates that even with the inductive bias provided by symmetry, learning the complete classes of functions represented by equivariant neural networks via gradient descent remains challenging. The paper contributes to the understanding of the computational hardness of learning and provides insights into the limitations of gradient descent in the presence of symmetries.