Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks

arXiv:2607.25200v1 Announce Type: new Abstract: Despite the empirical advantages of deep networks over shallow ones, theoretical depth separations largely concern approximation power, while algorithmic results are mostly limited to comparisons between two- and three-layer networks. In this work, we prove the first algorithmic separation between constant-depth and logarithmic-depth networks. Specifically, we identify a class of Boolean functions with hierarchically structured Fourier spectra that...