심층 학습의 알고리즘적 기초: 복잡도 이론적 결과 및 범용 근사 특성 규명

Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation

순방향 신경망(NN)의 표현력은 일반적으로 최적의 기저 확장 방식을 모방하여 연구됩니다. 그러나 이러한 관점은 불완전합니다. 이는 주로 정칙성을 통해 복잡도를 파악하며, 따라서 동일한 정칙성을 갖는 직관적으로 간단하고 복잡한 객체를 구별하지 못합니다. 예를 들어, 제곱근 함수와 일반적인 브라운 운동 경로는 정칙성은 유사하지만 복잡성이 다릅니다. 핵심 메시지는 신경망을 단순히 유연한 기저 함수로만 보는 것이 아니라 계산 모델로 간주해야 한다는 것입니다. 특정 기본 게이트 언어를 사용하는 실수 값 회로에 의해 계산될 수 있는 함수는 명시적인 깊이, 너비 및 0이 아닌 매개변수 제한을 갖는 신경망에 의해 유사한 정확도로 계산될 수 있습니다. 따라서 신경망의 복잡도는 정칙성뿐만 아니라 알고리즘적 복잡성에 의해 결정됩니다. 또한 자연스러운 병렬화 조건을 만족하고 어텐션 또는 레이어 정규화와 같은 다변수 비선형성을 포함할 수 있는 모든 정의 가능한 신경망 모델은, 만약 비선형성이 비-affine 함수인 경우에만 범용 근사자(universal approximator)가 됩니다. 본 연구의 이론적 범위는 연속 함수의 범용 근사 보장, 베소프 클래스에 대한 최소 최대 최적 근사 보장, 올림 함수에 대한 로그 오류 복잡도 등을 통해 설명됩니다. 또한 뉴턴-랩슨 방법과 파워 반복법과 같은 수치 알고리즘을 신경망이 특정 구조를 사용하지 않고도 모방할 수 있음을 보여줍니다. 본 연구의 정확성은 k개의 정점을 갖는 그래프에서의 최단 경로 계산을 통해 예시될 수 있습니다. 트로피컬 동적 프로그래밍 회로를 컴파일하면 O(log(1/ε)) 개의 0이 아닌 매개변수를 갖는 신경망이 생성되며, 이는 일반적인 O(ε^-c k^2) 형태의 리프시츠 근사 스케일보다 지수적으로 개선된 결과를 제공합니다 (단, c > 0).

Feedforward neural network (NN) expressivity is typically studied by emulating optimal basis-expansion schemes. While powerful, this perspective is incomplete: it primarily captures complexity through regularity, and therefore does not distinguish intuitively simple and complicated objects with comparable regularity, such as the square-root function and a typical Brownian path. The guiding message is that neural networks should be viewed not only as flexible basis functions, but also as models of computation. If a function is computable by a real-valued circuit over a prescribed elementary gate language, then it can be computed to comparable accuracy by an NN with explicit depth, width, and non-zero-parameter bounds controlled by the depth, width, gate count, and gate structure. Thus, neural-network complexity is not governed by regularity alone, but also by algorithmic complexity. We then show that any definable NN model satisfying a natural parallelization condition, allowing possibly multivariate non-linearities such as attention or layer normalization, is a universal approximator if and only if it contains a non-affine nonlinearity. The scope of our theory is illustrated by deducing universal approximation guarantees for continuous functions, minimax-optimal approximation guarantees for Besov classes, logarithmic-error complexity for holomorphic functions, and by showing that NNs can emulate numerical algorithms such as Newton-Raphson root finding and power iteration without architecture-specific arguments. Its precision is illustrated by shortest-path computation on $k$-vertex graphs: compiling the tropical dynamic-programming circuit yields NNs with O(log(1/ε)) non-zero parameters, exponentially improving in 1/ε over the generic $O(ε^{-c k^2})$ Lipschitz-approximation scale, for a constant c>0.