arXiv cs.LG
· Papers
Tight Sample Complexity of Transformers
arXiv:2606.09731v2 Announce Type: replace 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 $Omega(L W log (T W