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…
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…
SirenFNO: Efficient and Full Frequency Learning of Fourier Neural Operators
Pengqing Shi, Jie Yin, Stephen Tierney +1
Fourier neural operators (FNOs) are effective and efficient surrogates for approximating solutions of PDEs and generalize across discretizations. However, owing to the reliance on…
Learning Manifold and Itô Dynamics with Branched Neural Rough Differential Equations
Luke Thompson, Dai Shi, Lequan Lin +2
Neural rough differential equations (NRDEs) stay accurate under irregular sampling while taking far fewer integration steps than standard neural differential equations, summarising…