11 papers
Optimistic Rates for Multiclass PAC Learning
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales w…
On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation
Xiaoyu Li, Andi Han, Dai Shi +2
Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimensi…
The Exact Worst-Case Tail Probability under Bounded Kurtosis
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
We determine exactly what a kurtosis bound buys for one-sided tail control. For the class of real random variables with mean , variance , and fourth moment…
Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2
The John ellipsoid of a symmetric polytope , , is computed by a long line…
Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit
Xiaoyu Li, Andi Han, Dai Shi +3
AI systems coupled to proof assistants now generate formal mathematics at scale, and the gap between what a checker can verify and what a mathematician would value has become the b…
LAUKIN: A Multi-jurisdictional Common Law Contract Dataset
Amrita Singh, Aditya Joshi, Jiaojiao Jiang +2
Multinational companies increasingly require cross-jurisdictional contract review, yet existing legal NLP datasets are largely restricted to a single jurisdiction. We introduce LAU…