Crafting Global Optimizers to Reasoning Tasks via Algebraic Objects in Neural Nets

We prove rich algebraic structures of the solution space for 2-layer neural networks with quadratic activation and $L_2$ loss, trained on reasoning tasks in Abelian group (e.g., modular addition). Such a rich structure enables us to \emph{analytically} construct the global optimal solutions to the task from partial solutions that only satisfy part of the loss, despite its high nonlinearity. Specifically, we show that the union-ed solution space of different number of hidden nodes of the 2-layer network is endowed with a semi-ring algebraic structure, and the loss function to be optimized consists of \emph{monomial potentials} which are ring homomorphism, allowing composition of partial solutions by ring addition and multiplication. While the constructed global optimizers only require small number of hidden nodes, we show that overparameterization asymptotically decouples the training dynamics and thus is beneficial. We further show that training dynamics move towards simpler solutions under regularization, by proving that global optimizers algebraically connected by ring multiplication are also topologically connected. Experiments verify our theoretical findings.