본 연구는 선형 어텐션을 사용하는 단일 레이어 Transformer의 학습 가능성에 대한 최초의 다항 시간 학습 가능성 결과(강력하고, 불가지론적 PAC 학습)를 제시합니다. 선형 어텐션을 적절히 정의된 RKHS에서 선형 예측기로 보고, 학습 문제를 확장된 특징 공간에서 선형 예측기 학습 문제로 변환 가능함을 보입니다. 또한, 학습된 모델이 모든 입력에 대해 올바르게 일반화되도록 보장하는 훈련 데이터 세트를 효율적으로 식별하는 방법을 제시합니다. 연관 메모리, 유한 오토마타, 다항 시간 계산 기록을 가진 범용 튜링 머신(UTM)의 클래스를 포함하여 선형 어텐션을 통해 표현 가능하고 다항 시간 학습 가능한 계산의 예시를 제공합니다. 이론적 결과를 세 가지 과제(랜덤 선형 어텐션 네트워크 학습, 키-값 연결, 유한 오토마타 학습)에 대해 경험적으로 검증합니다.
