Tight Sample Complexity of Transformers

Abstract

We tightly characterize the VC dimension of depth-L Transformers with a total of W parameters, mapping an input sequence of length T to a single output, establishing an upper bound of O(L W log (T W)) and a nearly matching lower bound of Ω(L W log (T W / L)). We further tightly characterize the sample complexity of chain-of-thought learning using such a Transformer, showing teacher forcing (i.e. selecting a predictor consistent with the entire chain-of-thought on training data) learns with sample complexity O(L W log((T+T^') W)) and that any learning rule that uses chain-of-thought data requires at least Ω(L W log((T+T^') W / L)) examples, where T is the input length and T^' is the number of autoregressive steps.