상수 깊이와 로그 깊이 신경망 간의 알고리즘적 분리

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

심층 신경망이 얕은 신경망보다 경험적으로 우수한 성능을 보이는 반면, 이론적인 깊이 분석은 주로 근사 능력과 관련된 경우가 많으며, 알고리즘적인 연구는 대부분 두 또는 세 개의 레이어를 가진 네트워크 간의 비교에 국한되어 있습니다. 본 논문에서는 상수 깊이와 로그 깊이 신경망 간의 최초의 알고리즘적 분리를 증명합니다. 특히, 계층적으로 구조화된 푸리에 스펙트럼을 갖는 불리언 함수의 클래스를 식별했으며, 이 함수들은 로그 깊이 네트워크가 레이어별 좌표 하강법을 사용하여 효율적으로 학습할 수 있습니다. 이는 스펙트럼을 계층적이고 적응적으로 재구성하는 방식으로 작동합니다. 또한, 특정 서브클래스에 대해, 충분히 규칙적인 활성화 함수와 제어된 스펙트럴 노름을 가진 모든 상수 깊이, 다항식 폭 네트워크는 하이퍼큐브에서의 균일 분포 하에서 일정한 $L^2$ 근사 오차를 갖도록 강제된다는 것을 보여줍니다.

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 logarithmic-depth networks can learn efficiently using layerwise coordinate descent by reconstructing the spectra hierarchically and adaptively. We also exhibit a subclass for which every constant-depth, polynomial-width network with sufficiently regular activations and controlled spectral norms must incur constant $L^2$ approximation error under the uniform distribution over the hypercube.