Transformer의 타이트한 샘플 복잡도 (Tight Sample Complexity)

우리는 총 $W$개의 파라미터를 가진 깊이 $L$의 Transformer가 길이 $T$의 입력 시퀀스를 단일 출력으로 매핑할 때의 VC 차원 (VC dimension)을 타이트하게 규정하며, $O(L W ext{log}(T W))$의 상한 (upper bound)과 이에 거의 일치하는 $\Omega(L W ext{log}(T W / L))$의 하한 (lower bound)을 확립합니다. 나아가 우리는 이러한 Transformer를 사용하는 사고의 사슬 (chain-of-thought, CoT) 학습의 샘플 복잡도 (sample complexity)를 타이트하게 규정하며, 티처 포싱 (teacher forcing, 즉 훈련 데이터 상의 전체 사고의 사슬과 일치하는 예측기를 선택하는 방식)이 $O\left(L W ext{log} \left(\left(T+T^{\prime}\right) W\right)\right)$의 샘플 복잡도로 학습됨을 보여줍니다. 또한 사고의 사슬 데이터를 사용하는 어떠한 학습 규칙이라도 최소한 $\Omega\left(L W ext{log} \left(\left(T+T^{\prime}\right) W / L\right)\right)$개의 예시를 필요로 함을 증명합니다. 여기서 $T$는 입력 길이이며 $T^{\prime}$은 자기회귀 (autoregressive) 단계의 수입니다.