On the hardness of learning under symmetries
This addresses a fundamental theoretical problem for researchers in machine learning theory, revealing that symmetry incorporation does not alleviate inherent learning hardness, which is incremental as it extends prior hardness results to symmetric cases.
The paper tackles the problem of learning equivariant neural networks via gradient descent, showing that despite the inductive bias from symmetries, learning these networks remains hard with lower bounds scaling superpolynomially or exponentially in input dimensions.
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.