Theoretical and Computational aspects of Polynomial Neural Networks: Training Stability, Algorithmic Complexity and Expressivity

Abstract

This thesis is focused on the study of Polynomial Neural Networks (PNN) and their properties. PNNs are neural networks where the activation functions are themselves polynomials. The main result of the thesis focuses on the maximum learning rate for the stable training of polynomial neural networks in the ultra-rich regime; recent empirical bounds were observed showing a root-like (γ1/d) behavior of the maximum learning rate as a function of the richness factor γ. This thesis provides a fundamental and theoretical explanation of this observed phenomena in the cases of PNNs as well as transformer networks. Two more topics are investigated as part of this thesis: the establishment of a quasi-polynomial time algorithm for the training problem for PNNs, as well as a computational framework for the study of the expressivity of PNNs.