On the hardness of learning under symmetries

In recent years, the purview of machine learning has expanded to non-traditional domains with geometric input types, from graphs to sets to point clouds. Correspondingly, it is now common practice to tailor neural architectures to the particular symmetries of the input - graph neural networks are invariant to permutations of the input nodes, for example, 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 and Sedghi, 2019, Bietti et al., 2021, Sannai et al., 2021, Mei et al., 2021], often achieving rather tight bounds for simple models [Elesedy, 2021, Tahmasebi and Jegelka, 2023]. At their core, these formal statements are bounds on sample complexity, i.e. how much data is needed to learn a 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 efficiently 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.