Compositional Approximation Can Strictly Outperform Superpositional Approximation

기술 요약: 구성적 근사(Compositional Approximation)가 중첩적 근사(Superpositional Approximation)를 엄격히 능가할 수 있음

문제 제기
본 논문은 근사 이론의 근본적인 질문을 다룬다: 어떤 조건 하에서 구성적 방법(예: 신경망)이 중첩적 방법(예: 딕셔너리 요소들의 선형 결합인 M-term 근사)보다 엄격히 우수한 근사율을 제공하는가? 경험적 증거는 신경망이 강력하다는 것을 시사하지만, 이론적 정당화는 대개 기존 방법을 모방하여 동등하거나 유사한 수준의 비율을 달ing하는 데 그친다. 또한, 많은 고전적 함수 클래스는 최적의 M-term 근사율을 생성하는 딕셔너리를 허용한다. 저자들은 구성적 근사가 중첩적 근사를 엄격히 능가할 수 있는 함수 클래스의 구조적 특성을 식별하고자 하며, 이때 파라미터의 효율적인 비트 문자열 인코딩을 보장하는 제약 조건(무차별한 "브루트 포스" 방식의 딕셔너리 구축을 방지하기 위함)을 준수한다.

방법론 및 프레임워크
저자들은 힐베르트 공간 $H$ 내에서 근사 체계를 비교하기 위해 엄밀한 수학적 프레임워크를 구축한다:

1. 근사율(Approximation Rates): 저자들은 파라미터 예산 $M$에 따른 균일 오차(uniform error)의 다항식 감소 차수인 근사율 $\gamma(C, S)$를 정의한다.
2. 중첩적 체계(Superpositional Schemes): 이는 딕셔너리 요소 $D = (\phi_i)_{i \in \mathbb{N}}$의 $M$-term 선형 결합으로 정의되며, "다항식 깊이 탐색(polynomial depth search)" 제약을 따른다. 이 제약은 사용된 딕셔너리 요소의 인덱스와 계수의 크기를 $M$의 다항식으로 제한하여, 근사치가 $O(M \log^q M)$ 길이의 비트 문자열로 인코딩될 수 있도록 보장한다. **리츠 근사율(Riesz approximation rate, $\gamma_{\text{Riesz}}$)**은 하한 리츠 조건(안정성을 보장함)을 만족하는 임의의 딕셔너리에 의해 달성 가능한 근사율의 상한이다.
3. 구성적 체계(Compositional Schemes): 이는 깊이(depth, $M$에 대한 로그 다항식), 연결성(connectivity, $M$에 대한 선형), 가중치 크기(weight magnitude, $M$에 대한 다항식)에 대한 제약이 있는 신경망을 통해 모델링된다. 이는 유사한 비트 문자열 인코딩 효율성을 보장한다.
4. 기하학적 관점: 핵심적인 이론적 통찰은 함수 클래스의 점근적 기하학에 기반한다. 저자들은 만약 어떤 함수 클래스가 제한된 수의 저차원 선형 부분 공간들의 합집합에 의해 $\epsilon$-근사될 수 있다면(이는 구성에 의해 활용 가능한 구조임), 반면 선형 근사를 위해서는 고차원 선형 부분 공간을 필요로 한다면, 두 방식 간의 비율 격차가 존재할 수 있다고 주장한다. 이는 "커버링 수(covering numbers)" 개념과 연결되는데, 여기서 비선형 근사 집합은 $\epsilon \to 0$일 때 필요한 선형 공간에 비해 매우 작아진다.

주요 기여 및 결과

1. SPOON 구축: 저자들은 SPOON(Superpolynomially growing almost Orthogonal sequeNce, 초다항식적으로 성장하는 거의 직교하는 수열)이라 불리는 전형적인 집합 구조를 도입한다. SPOON은 다음과 같은 성질을 가진 집합 수열 $V_m$으로 구성된다:

   • 카디널리티(cardinality)가 초다항식적으로 성장한다 ($|V_m| \ge 2^{m^\alpha}$).
   • 요소들의 노름(norm)은 $m^{-\mu}$로 감소한다.
   • 요소들은 서로 $\eta$-거의 직교하며, 내적(inner product)의 상한은 $m^{-\nu}$로 감소한다.

2. 중첩적 근사율의 상한 (정리 3.4): 중심이 되는 이론적 결과는 함수 클래스 $C$가 $(\mu, \nu)$-SPOON을 포함할 경우, 달성 가능한 최선의 리츠 근사율이 다음과 같이 제한됨을 증명한다:
   $$\gamma_{\text{Riesz}}(C) \le \frac{1}{2} + \frac{\mu}{\nu}$$
   이 증명은 거의 직교하는 집합의 기하학적 특성과 리츠 딕셔너리의 성질을 이용한 모순 증명을 사용한다. 이는 리츠 조건을 만족하는 어떤 딕셔너라도 SPOON 내의 지수적으로 거대한 거의 직교하는 집합을 오직 다항식 개수의 항만을 사용하여 효율적으로 덮을 수 없음을 보여준다.

3. 명시적 구축 (섹션 4): 저자들은 "hat" 함수 $f$의 구성을 사용하여 명시적인 함수 클래스 $V(k, \alpha, \beta, \mu)$를 구축한다. 이 클래스들은 이진 벡터들에 의해 정의된 함수들의 반복적 구성으로 형성된다.

   • 이들은 이러한 클래스들이 큰 거의 직교하는 함수 집합을 포함함을 증명한다.
   • 또한 ReLU 신경망이 이 클래스들을 $\gamma_{\rho}^N \ge \frac{\mu}{\alpha}$의 비율로 근사할 수 있음을 보여준다.
   • 이를 리츠 상한과 결합하면, 특정 파라미터 선택(예: $\mu = \sqrt{k}$)에 대해 구성적 근사와 리츠 근사율 사이의 격차가 구성의 깊이 $k$가 증가함에 따라 임의로 커질 수 있음을 보여준다. 구체적으로, $\lim_{k \to \infty} \gamma_{\rho}^N = \infty$인 반면 $\lim_{k \to \infty} \gamma_{\text{Riesz}} \le \frac{1}{2}$이다.

4. 병리적 직교성 예시 (부록 A): 논문은 계수가 로그 단위로 감소하는 정규 직교 체계를 포함한 더 단순하지만 병리적인 예시를 제시한다. 이 경우 중첩적 근사는 $-\infty$의 비율(다항식 감소 없음)을 나타내는 반면, 신경망은 양(+)의 비율을 달성하여 중첩적 방법이 매우 직교하는 구조에서 겪는 어려움을 부각시킨다.

의의 및 주장
본 논문은 중첩적 방법이 안정성(Riesz) 및 인코딩 제약 조건 하에서 최적의 딕셔너리를 선택할 수 있음에도 불구하고, 구성적 근사가 중첩적 근사를 엄격히 능가하는 첫 번째 명시적 사례를 제공한다고 주장한다.

그 의의는 특정 구조적 특성—유한 차원 부분 공간 내에 존재하는 거대하고 거의 직교하는 집합의 존재—을 식별했다는 점에 있다. 이는 선형 결합으로는 효율적으로 포착하기 어렵지만, 단순한 빌딩 블록들의 계층적 구성을 통해서는 자연스럽게 처리될 수 있는 구조이다. 저자들은 이러한 구조적 불일치가 신경망이 특정 클래스에 대해 더 나은 비율을 달성할 수 있는 이유를 설명한다고 주장한다. 이 연구는 신경망의 이점이 단순히 보편적 근사(universal approximation) 능력에 있는 것이 아니라, 이러한 "거의 직교하는" 구조를 가진 함수 클래스에 대한 특정한 기하학적 적응성에 있음을 시사한다.

저자들은 자신의 결과가 이러한 특정 SPOON 구조를 포함하는 함수 클래스에 적용된다는 점을 명시하며 신중한 태도를 유지한다. 또한 현재의 중첩적 근사율 상한은 리츠 딕셔너리로 제한되어 있으나, 이는 근본적인 한계라기보다는 기술적인 제한이라고 믿는다. 저자들은 이 결과가 모든 함수 클래스에 적용되거나 신경망이 보편적으로 우월하다는 것을 주장하는 것이 아니라, 이러한 특정한 점근적 기하 구조를 가진 클래스들에 대해 우월하다는 것을 주장하는 것이다.