On the hardness of learning under symmetries

Bobak T. Kiani, Thien Le, Hannah Lawrence, Stefanie Jegelka, Melanie Weber

Introduction

In Geometric Deep Learning, the prevailing paradigm is that "symmetry is key." By designing architectures that respect the natural symmetries of data—such as translation invariance in Convolutional Neural Networks (CNNs) or permutation invariance in Graph Neural Networks (GNNs)—researchers have achieved significant empirical success. While it is well-established that these inductive biases improve sample complexity (requiring less data to learn), their impact on computational complexity has remained a critical theoretical gap. This paper investigates whether known problem symmetries are sufficient to alleviate the fundamental hardness of the optimization landscape for gradient-based methods.

Theoretical Framework: The CSQ Model

The authors analyze the learning problem through the lens of the Correlational Statistical Query (CSQ) model. This framework encompasses most standard optimization algorithms, including Gradient Descent (GD). In the CSQ model, an algorithm does not access individual data points directly but instead queries the correlation between a chosen function and the target output.

To establish their results, the authors developed a mathematical toolkit using Invariant Hermite Polynomials. They constructed families of "hard" functions that are invariant under specific groups (e.g., cyclic shifts for images or permutations for graphs) but remain "hidden" from gradient-based learners due to their high frequency or complex structure.

Hardness Results and Query Complexity

The core finding is that inductive bias is not a silver bullet for optimization. Even when a model is perfectly restricted to the correct symmetry group, the optimization problem can still resemble a "needle-in-a-haystack" search. The authors prove that for many common symmetries, the number of queries required to learn the target function scales superpolynomially or exponentially with the input size.

Query complexity lower bounds for various symmetric groups under the Correlational Statistical Query (CSQ) model.

As shown in the table above, while the symmetric group on bits has a relatively low query complexity, more complex structures like graphs or cyclic groups exhibit exponential lower bounds. Specifically, for GNNs, the complexity scales exponentially with the number of nodes ($n$), suggesting that even a single message-passing layer can create functions that are intractable for gradient descent.

Key Insights

  • Single-Layer Hardness: Hardness is not exclusive to deep hierarchies; shallow, single-layer GNNs are sufficient to produce exponentially difficult learning tasks.
  • The SQ vs. CSQ Gap: There exists a fascinating separation where certain symmetric functions can be learned efficiently by specialized algorithms (like the "GROWING-BASIS" algorithm) but remain unlearnable by standard backpropagation.
  • NP-Hardness: Beyond statistical queries, the authors demonstrate that the "proper" learning of GNN weights—finding the exact weights to fit a dataset—is NP-hard in the classical sense.

Empirical Validation and Limitations

To verify these theoretical bounds, experiments were conducted on synthetic tasks involving small-scale graphs ($n=15$) and bitstrings. The results confirmed that overparameterized GNNs and CNNs failed to learn the proposed "hard" symmetric functions. While GNNs often failed to even fit the training data, CNNs would fit the training data but fail to generalize entirely.

However, the authors note that these results focus on worst-case complexity. It remains possible that "natural" functions found in real-world datasets possess additional properties that make them easier to learn than the adversarial constructions used in these proofs. Future work may extend these findings to continuous groups, such as 3D rotations ($SO(3)$), and further explore the cryptographic hardness of symmetric functions.

Conclusion

This research provides a sobering counterpoint to the enthusiasm surrounding geometric inductive biases. While encoding symmetries is vital for data efficiency, it does not necessarily simplify the computational task of training. For certain classes of symmetric problems, researchers may need to look beyond standard gradient descent toward more specialized algorithmic approaches.

Summary updated

BibTeX
@inproceedings{kiani2024hardness,
  author = {Bobak T. Kiani and Thien Le and Hannah Lawrence and Stefanie Jegelka and Melanie Weber},
  title = {{On the hardness of learning under symmetries}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=ARPrtuzAnQ},
}
Figure