[논문] Transformer의 정확한 샘플 복잡도

출처: arXiv - 2606.09731v1

개요

우리는 깊이 $L$인 Transformer가 총 $W$개의 파라미터를 가지고 입력 길이 $T$인 시퀀스를 단일 출력으로 매핑하는 경우의 VC 차원을 정확히 규명한다. 상한 $O(L W \log (T W))$와 거의 일치하는 하한 $Ω(L W \log (T W / L))$를 제시한다. 또한 이러한 Transformer를 이용한 체인‑오브‑쓰스(Chain‑of‑Thought) 학습의 샘플 복잡도를 정확히 규명한다. 교사 강제(teacher forcing, 즉 학습 데이터에서 전체 체인‑오브‑쓰스와 일치하는 예측기를 선택하는 방식)가 샘플 복잡도
(O!\left(L W \log \left(\left(T+T^{\prime}\right) W\right)\right)) 로 학습함을 보이며, 체인‑오브‑쓰스 데이터를 사용하는 어떤 학습 규칙도 최소
(Ω!\left(L W \log \left(\left(T+T^{\prime}\right) W / L\right)\right)) 개의 예제가 필요함을 증명한다. 여기서 $T$는 입력 길이, $T^{\prime}$는 자동회귀 단계 수이다.

주요 기여

이 논문은 다음 분야의 연구를 다룬다.

• cs.LG

방법론

자세한 방법론은 전체 논문을 참고하십시오.

실용적 함의

이 연구는 cs.LG 분야의 발전에 기여한다.

저자

• Chenxiao Yang
• Nathan Srebro
• Zhiyuan Li

논문 정보

• arXiv ID: 2606.09731v1
• Categories: cs.LG
• Published: 2026년 6월 8일
• PDF: PDF 다운로드