No-Regret Language Generation

Abstract:We introduce no-regret generation, which requires a generator to make a sublinear number of mistakes uniformly over all demonstration sequences and compatible target languages. We also formulate an agnostic variant that allows arbitrary demonstrations that may not be compatible with any languages. For both settings, we introduce tree-based mistake-forcing dimensions that exactly characterize finite-horizon minimax complexity and establish necessary and sufficient conditions for no-regret generation. Our characterizations reveal a rich spectrum of generation rates: up to constant rescaling, every admissible nondecreasing profile is attainable in both the realizable and agnostic settings. Finally, we connect generation complexity to online prediction: for language classes of finite Littlestone dimension \(d\), we obtain realizable mistake bounds of \(O(d\log(1+T/d))\) and agnostic regret bounds of \(O(\sqrt{dT\log(1+T/d)})\). The realizable bound is optimal up to universal constants.

Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2610.23641 [cs.LG]

(or arXiv:2610.23641v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.23641 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.