5 papers
Mistake-Bounded Language Generation
Jon Kleinberg, Charlotte Peale, Omer Reingold
We investigate the learning task of language generation in the limit, but shift focus from the traditional time-of-last-mistake metric of a generator's success to a new notion of "…
How Global Calibration Strengthens Multiaccuracy
SÃlvia Casacuberta, Parikshit Gopalan, Varun Kanade +1
Multiaccuracy and multicalibration are multigroup fairness notions for prediction that have found numerous applications in learning and computational complexity. They can be achiev…
On the Impossibility of Separating Intelligence from Judgment: The Computational Intractability of Filtering for AI Alignment
Sarah Ball, Greg Gluch, Shafi Goldwasser +3
With the increased deployment of large language models (LLMs), one concern is their potential misuse for generating harmful content. Our work studies the alignment challenge, with…
Representative Language Generation
Charlotte Peale, Vinod Raman, Omer Reingold
We introduce "representative generation," extending the theoretical framework for generation proposed by Kleinberg et al. (2024) and formalized by Li et al. (2024), to additionally…
Accuracy vs. Accuracy: Computational Tradeoffs Between Classification Rates and Utility
Noga Amit, Omer Reingold, Guy N. Rothblum
We revisit the foundations of fairness and its interplay with utility and efficiency in settings where the training data contain richer labels, such as individual types, rankings,…