Quantitative Approximation Rates for Group Equivariant Learning

이 논문은 군 공변적 (Group Equivariant) 및 불변 (Invariant) 학습의 맥락에서 **정량적 근사율 (Quantitative Approximation Rates)**을 제시하는 것을 목표로 합니다. 기존에 신경망이 연속 함수를 근사할 수 있다는 '보편적 근사 정리 (Universal Approximation Theorem)'는 알려져 있었으나, 구체적인 근사 오차와 네트워크 크기 (파라미터 수) 사이의 관계를 군 대칭성을 가진 모델에 대해 분석한 연구는 부족했습니다.

이 논문은 이러한 간극을 메우기 위해, 다양한 군 대칭성 (치환, 강체 운동 등) 을 가진 아키텍처들이 $\alpha$-Hölder 연속 함수를 얼마나 효율적으로 근사할 수 있는지 수학적으로 증명합니다.

주요 내용은 다음과 같습니다.

1. 문제 정의 및 배경 (Problem & Background)

• 배경: 심층 ReLU 신경망은 $[0, 1]^N$ 영역에서 $\alpha$-Hölder 함수를 근사할 때, 오차 $\epsilon$을 달성하기 위해 필요한 파라미터 수가 대략 $O(\epsilon^{-N/2\alpha})$임을 알려져 있습니다.
• 문제: 군 $G$에 대해 불변 (Invariant) 이거나 공변 (Equivariant) 인 함수를 학습할 때, 대칭성으로 인해 유효한 차원이 줄어들어 (Quotient space $V/G$의 차원 $N_G$) 근사율이 $O(\epsilon^{-N_G/2\alpha})$로 개선될 수 있을까요? 또한, 이러한 대칭성을 하드코딩한 현대적인 아키텍처 (Deep Sets, Transformer, Frame Averaging 등) 가 이 이론적 하한을 달성할 수 있을까요?
• 핵심 질문:
  1. 일반적인 ReLU 네트워크가 대칭성을 가진 함수를 근사할 때, 차원 감소에 따른 이점을 얻을 수 있는가?
  2. 대칭성을 명시적으로 인코딩한 아키텍처가 동일한 근사율을 달성하는가?

2. 주요 방법론 (Methodology)

저자들은 세 가지 주요 설정 (Setting) 에서 근사율을 분석했습니다.

2.1 치환 불변/공변 모델 (Permutation Invariant/Equivariant Models)

• Deep Sets: 점 집합 (Point Sets) 에 대한 치환 불변 함수를 근사합니다.
  • 기법: 단위 큐브를 작은 서브-큐브로 분할하고, 각 셀에 속하는 점의 개수를 인코딩하는 특징 매핑을 구성합니다. 이를 위해 Kolmogorov-Arnold 중첩 정리 (Superposition Theorem) 의 증명 기법을 차용하여 불연속적인 특징 함수를 ReLU 네트워크로 근사합니다.
  • 결과: Deep Sets 가 $\alpha$-Hölder 불변 함수를 최적의 근사율 $O(\epsilon^{-nd/2\alpha})$로 근사할 수 있음을 증명했습니다. 여기서 $n$은 점의 개수, $d$는 차원입니다.
• Sumformer 및 Transformer: 치환 공변 함수를 근사합니다.
  • 기법: Deep Sets 의 결과를 활용하여, 각 점 $x_i$와 나머지 점들의 합 $\sum_{j \neq i} x_j$를 입력으로 받는 구조가 Transformer 의 어텐션 메커니즘으로 구현 가능함을 보였습니다.
  • 결과: Sumformer 와 Transformer 도 Deep Sets 와 동일한 최적 근사율을 달성함을 증명했습니다.

2.2 치환 및 강체 운동 (Permutations and Rigid Motions) 불변 모델

• 설정: 점 구름 (Point Clouds) 에 대해 치환과 회전/이동 ($E(d)$) 에 모두 불변인 함수를 다룹니다. 이 경우 유효 차원은 $nd - \dim(E(d))$로 감소합니다.
• ReLU 네트워크의 능력: Gram-Schmidt 직교화 과정을 ReLU 네트워크로 근사하여, 임의의 점 구름을 특정 부분 공간 (Quotient space) 으로 매핑하는 것을 증명했습니다. 이를 통해 일반 ReLU 네트워크도 차원 감소에 따른 최적 근사율을 달성함을 보였습니다.
• Frame Averaging (프레임 평균화): 회전 불변성을 갖는 프레임 (예: 주성분 방향 정렬, SVD 기반 정렬) 을 Deep Sets 백본에 적용하는 모델들의 근사율을 분석했습니다.
  • 결과: 프레임 평균화 연산자가 ReLU 네트워크의 근사 능력을 보존하며, $O(\epsilon^{-(nd-\dim(E(d)))/2\alpha})$의 최적 근사율을 달성함을 증명했습니다.

2.3 Bi-Lipschitz 불변 모델 (Bi-Lipschitz Invariant Models)

• 설정: 더 일반적인 등거리 군 (Isometry Groups) 에 대해, 몫 공간 $V/G$에 Bi-Lipschitz 매핑 (거리 왜곡이 제한된 불변 임베딩) 을 제공하는 모델들 (예: Max Filtering, Sorting 기반 임베딩) 을 다룹니다.
• 기법: Bi-Lipschitz 임베딩 $E$를 통해 원래 함수 $f$를 몫 공간의 함수 $\tilde{f}$로 변환하고, $\tilde{f}$를 ReLU 네트워크로 근사한 뒤 $E$와 합성하는 방식을 사용합니다.
• 결과: Bi-Lipschitz 불변 모델을 사용하면, 내재적 차원 (Intrinsic dimension, $d_{intrinsic}$) 에 기반한 최적 근사율 $O(\epsilon^{-d_{intrinsic}/2\alpha})$을 달성할 수 있음을 보였습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

1. 최적 근사율의 증명:

   • Deep Sets, Sumformer, Transformer, Frame Averaging 기반 모델, Bi-Lipschitz 모델 등 주요 군 공변/불변 아키텍처가 $\alpha$-Hölder 함수에 대해 이론적으로 기대되는 최적의 근사율을 달성함을 수학적으로 증명했습니다.
   • 근사율은 일반적으로 $O(\epsilon^{-N_G/2\alpha})$ 형태이며, 여기서 $N_G$는 몫 공간 (Quotient Space) 의 차원입니다.

2. 표현력 (Expressivity) 에 대한 통찰:

   • 핵심 결론: 대칭성을 하드코딩한 모델과 일반 ReLU MLP 는 불변 함수를 근사하는 표현력 (Expressivity) 측면에서 동등합니다.
   • 즉, 대칭성을 명시적으로 모델에 포함시킨다고 해서 근사 능력이 떨어지거나 (Expressivity loss), 반대로 파라미터 수 대비 근사 정확도가 획기적으로 향상되지는 않습니다.
   • 기존에 대칭성 모델이 더 좋은 성능을 보이는 이유는 **표본 효율성 (Sample Efficiency)**과 최적화 용이성 (Optimization) 때문이며, 순수한 근사 이론적 한계와는 무관함을 시사합니다.

3. 내재적 차원 (Intrinsic Dimension) 에 대한 개선된 결과:

   • 일반 ReLU 네트워크가 낮은 내재적 차원을 가진 영역에서 함수를 근사할 때, 기존 연구 (Nakada and Imaizumi, 2020) 의 $O(\epsilon^{-d_{intrinsic}/\alpha})$보다 더 빠른 $O(\epsilon^{-d_{intrinsic}/2\alpha})$의 근사율을 달성할 수 있음을 증명했습니다. (지수 부분에서 2 배 개선)

4. 의의 및 시사점 (Significance)

• 이론적 기반 확립: 군 공변 학습 분야에서 오랫동안 간과되었던 '정량적 근사 이론'의 기초를 닦았습니다.
• 모델 설계 가이드: 연구자들이 모델 선택 시 "근사 능력"을 기준으로 대칭성 모델을 선택할 필요는 없으며, 대신 데이터 효율성과 학습 안정성을 기준으로 선택해야 함을 이론적으로 뒷받침합니다.
• 미래 연구 방향:
  • EGNN, Dimenet, Vector Neurons 등 널리 사용되는 구체적인 회전 공변 모델들의 근사율 분석은 여전히 미해결 과제로 남았습니다.
  • 점근적 근사율 (Asymptotic rates) 이 실제 규모 (Realistic scales) 에서의 모델 간 미세한 차이를 포착하기에는 너무 거칠 수 있으므로, 상수항을 고려한 더 정교한 분석이 필요함을 지적했습니다.

요약

이 논문은 "대칭성을 가진 신경망이 일반 신경망보다 더 적은 파라미터로 더 잘 근사할 수 있는가?"라는 질문에 대해, **"근사 이론적 관점에서는 두 모델이 동등한 표현력을 가지며, 대칭성 모델의 실제적 우위는 근사력이 아닌 데이터 효율성과 최적화에서 비롯된다"**는 결론을 내렸습니다. 이는 군 공변 학습의 이론적 이해를 한 단계 높이는 중요한 업적입니다.