Generation through the lens of learning theory

Vinod Raman, Jiaxun Li, Ambuj Tewari
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:4740-4776, 2025.

Abstract

We study generation through the lens of learning theory. First, we formalize generation as a sequential two-player game between an adversary and a generator, which generalizes the notion of “language generation in the limit” from Kleinberg and Mullainathan (2024). Then, we extend the notion of “generation in the limit" to two new settings, which we call “uniform" and “non-uniform" generation. We provide a characterization of hypothesis classes that are uniformly and non-uniformly generatable. As is standard in learning theory, our characterizations are in terms of the finiteness of a new combinatorial dimension termed the Closure dimension. By doing so, we are able to compare generatability with predictability (captured via PAC and online learnability) and show that these two properties of hypothesis classes are incomparable – there are classes that are generatable but not predictable and vice versa. Finally, we extend our results to capture prompted generation and give a complete characterization of which classes are prompt generatable, generalizing some of the work by Kleinberg and Mullainathan (2024).

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-raman25a, title = {Generation through the lens of learning theory}, author = {Raman, Vinod and Li, Jiaxun and Tewari, Ambuj}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {4740--4776}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/raman25a/raman25a.pdf}, url = {https://proceedings.mlr.press/v291/raman25a.html}, abstract = {We study generation through the lens of learning theory. First, we formalize generation as a sequential two-player game between an adversary and a generator, which generalizes the notion of “language generation in the limit” from Kleinberg and Mullainathan (2024). Then, we extend the notion of “generation in the limit" to two new settings, which we call “uniform" and “non-uniform" generation. We provide a characterization of hypothesis classes that are uniformly and non-uniformly generatable. As is standard in learning theory, our characterizations are in terms of the finiteness of a new combinatorial dimension termed the Closure dimension. By doing so, we are able to compare generatability with predictability (captured via PAC and online learnability) and show that these two properties of hypothesis classes are incomparable – there are classes that are generatable but not predictable and vice versa. Finally, we extend our results to capture prompted generation and give a complete characterization of which classes are prompt generatable, generalizing some of the work by Kleinberg and Mullainathan (2024). } }
Endnote
%0 Conference Paper %T Generation through the lens of learning theory %A Vinod Raman %A Jiaxun Li %A Ambuj Tewari %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-raman25a %I PMLR %P 4740--4776 %U https://proceedings.mlr.press/v291/raman25a.html %V 291 %X We study generation through the lens of learning theory. First, we formalize generation as a sequential two-player game between an adversary and a generator, which generalizes the notion of “language generation in the limit” from Kleinberg and Mullainathan (2024). Then, we extend the notion of “generation in the limit" to two new settings, which we call “uniform" and “non-uniform" generation. We provide a characterization of hypothesis classes that are uniformly and non-uniformly generatable. As is standard in learning theory, our characterizations are in terms of the finiteness of a new combinatorial dimension termed the Closure dimension. By doing so, we are able to compare generatability with predictability (captured via PAC and online learnability) and show that these two properties of hypothesis classes are incomparable – there are classes that are generatable but not predictable and vice versa. Finally, we extend our results to capture prompted generation and give a complete characterization of which classes are prompt generatable, generalizing some of the work by Kleinberg and Mullainathan (2024).
APA
Raman, V., Li, J. & Tewari, A.. (2025). Generation through the lens of learning theory. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:4740-4776 Available from https://proceedings.mlr.press/v291/raman25a.html.

Related Material