[Paper] o‑Mininal Structure에서 정의 가능한 모든 Feedforward Neural Network은 Finite Sample Complexity를 갖는다

Source: arXiv - 2605.07097v1

개요

새로운 이론적 돌파구는 고정 크기의 피드포워드 신경망 중 층이 “완만한”(formally, o‑minimal 구조에서 정의 가능한) 수학 연산으로 구성된 경우, 비판적 PAC 프레임워크에서 유한한 양의 데이터만으로 학습이 보장된다는 것을 보여줍니다. 이 결과는 가장 흔히 사용되는 현대 아키텍처—MLP, CNN, GNN, 그리고 고정 시퀀스 길이를 갖는 트랜스포머까지—에 적용되며, 네트워크 가중치에 인위적인 제한을 두지 않습니다.

핵심 기여

• 일반적인 PAC 학습 가능성 정리: 활성화 함수나 파라미터 크기에 관계없이 레이어가 o‑minimal하게 정의된 모든 피드포워드 네트워크에 적용.
• 다양한 아키텍처(MLP, CNN, GNN, 트랜스포머)와 일반적인 구성 요소(선형 맵, 잔차 연결, 어텐션, 풀링, 정규화, 위치 인코딩)를 통합적으로 다룸.
• 유한 샘플 학습 가능성이 완화된 피드포워드 연산의 기본 속성임을 증명: 특정 활성화 함수나 VC 차원 트릭의 특수 경우가 아님.
• 개념적 전환: 연구 초점을 “이 아키텍처가 학습되는가?”에서 “어떤 귀납적 편향, 대칭성, 최적화 특성을 제공하는가?”로 이동.

방법론

1. O‑minimal 구조 – 모델 이론에서 온 프레임워크로, “잘 정의된” 집합과 함수(예: 반대수적, 부분해석적)를 포착한다. 저자들은 실제로 사용되는 대부분의 레이어가 이러한 구조에 속함을 보여준다.
2. 무관심 PAC 분석 – 데이터 생성 분포에 대한 어떠한 가정도 하지 않는 가장 일반적인 학습 설정에서 작업한다.
3. 유한 샘플 복잡도 경계 – o‑minimal 정의 가능한 함수들의 온화한 기하학을 활용하여, 네트워크의 아키텍처(깊이, 폭, 정의 가능한 연산 수)만을 기준으로 하고 파라미터의 크기는 고려하지 않는 샘플 크기 경계를 제공하는 균일 수렴 보장을 도출한다.
4. 층별 구성 – 증명은 o‑minimal 정의 가능한 레이어들의 합성이 여전히 o‑minimal임을 보여줌으로써, 네트워크 전체에 걸쳐 학습 가능성 속성을 유지한다.

Results & Findings

• Finite sample complexity: 고정된 아키텍처에 대해, 오류 (\epsilon)를 신뢰도 (1-\delta)로 달성하기 위해 필요한 학습 예제 수는 (1/\epsilon)와 (\log(1/\delta))에 대한 다항식 상한이 존재한다.
• Parameter‑agnostic: 가중치가 임의로 크게 허용되더라도 이 상한은 성립하므로, 이론적 보장에서 노름 기반 정규화가 필요하지 않다.
• Broad applicability: 이 정리는 특정 활성화 함수(예: ReLU)에 대한 기존 VC 차원 결과를 포함하고, 부드러운 활성화 함수, 유리 함수, 그리고 산업 현장에서 사용되는 다양한 맞춤 레이어를 포함하는 훨씬 더 큰 함수 클래스까지 확장한다.

실용적 함의

• Design freedom: 엔지니어는 o‑minimal 구조 내에 머무르는 한, 이론적 학습 가능성 손실을 두려워하지 않고 이색적인 활성화 함수나 정규화 방식을 실험할 수 있다.
• Benchmarking shift: 학습 가능성이 이제 합리적인 피드포워드 설계라면 당연시되므로, 성능 비교는 “이 아키텍처가 학습조차 하는가?” 대신 inductive bias(예: GNN의 equivariance), scalability, optimization dynamics에 초점을 맞출 수 있다.
• Safety & verification: 온화한 기하학(tame‑geometry) 관점은 이미 반대수적(semi‑algebraic) 추론에 의존하는 형식 검증 도구와 일치하여, 검증 가능한 보장을 생산 파이프라인에 통합하는 것을 용이하게 할 수 있다.
• Curriculum for AutoML: 자동화된 아키텍처 탐색은 별도의 학습 가능성 검사를 삽입할 필요 없이 (any o‑minimal layer) 더 넓은 탐색 공간을 안전하게 탐색할 수 있다.

제한 사항 및 향후 연구

• 고정된 아키텍처 크기: 보장은 사전에 지정된 레이어와 뉴런 수를 가진 네트워크에만 적용되며, 동적으로 레이어를 추가하는 신경 아키텍처 탐색 등은 다루지 않는다.
• 트랜스포머의 시퀀스 길이 제한: 결과는 유한한 입력 길이를 갖는 트랜스포머에 대해서만 성립한다; 무한하거나 가변 길이 시퀀스로 확장하는 문제는 아직 해결되지 않았다.
• 최적화 미포함: 샘플 복잡도는 유한하지만, 정리에서는 확률적 경사 하강법(또는 다른 실용적인 최적화 알고리즘)이 합리적인 시간 내에 좋은 해를 찾을 것을 보장하지 않는다.
• 피드포워드 외: 순환 신경망, 연속시간 모델 및 기타 비피드포워드 구조는 현재 o‑minimal 프레임워크의 범위를 벗어나며, 향후 연구 대상이다.

핵심: 현대 딥러닝 시스템을 구축하는 개발자에게 이 연구는 “다루기 쉬운” 레이어 집합 내에서 네트워크 크기를 고정한다면 견고한 PAC‑학습 기반을 제공한다는 점을 보장한다. 이제 진정한 과제는 네트워크의 귀납적 편향을 어떻게 설계하느냐와 효율적으로 학습시키는 방법에 달려 있다.

저자

• Anastasis Kratsios
• Gregory Cousins
• Haitz Sáez de Ocáriz Borde
• Bum Jun Kim
• Simone Brugiapaglia

논문 정보

• arXiv ID: 2605.07097v1
• 분류: stat.ML, cs.LG, cs.NE, math.LO, math.ST
• 발행일: 2026년 5월 8일
• PDF: Download PDF