arXiv Machine Learning By Chenxiao Yang, Nathan Srebro, Zhiyuan Li

Tight Sample Complexity of Transformers

Read the original on arXiv Machine Learning →

arXiv:2606. 09731v1 Announce Type: new 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 / L))$.

Summary generated by The Flow from the publisher's feed. The full article lives at arXiv Machine Learning.

arXiv Machine Learning
Aug 11

How Many Different Outputs Can a Transformer Generate?

arXiv:2605. 22223v2 Announce Type: replace Abstract: We study how we can leverage only a handful of characteristics of a transformer's architecture to closely predict the number of different sequences it can output, both qualitatively and quantitatively.

By Maxime Meyer, Mario Michelessa, Caroline Chaux, Vincent Y. F. Tan
arXiv Machine Learning
Jun 2

Length Generalization Bounds for Transformers

arXiv:2603. 02238v2 Announce Type: replace Abstract: Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data.

By Andy Yang, Pascal Bergstr\"a{\ss}er, Georg Zetzsche, David Chiang, Anthony W. Lin