13 citations · 23 across the 26 of their papers we have counts for
11 papers · 1 filter
Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary…
Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks
Xiaoyu Li, Zhizhou Sha, Jiaojiao Jiang +2
An input may activate few hidden units even when different inputs collectively use an entire network. We study the statistical complexity of this input-dependent sparsity in the on…
Matched Excess-Outranker Regularization for Candidate-Set Interference in Continual Knowledge Graph Embedding
Hao Ren, Junbin Gao, Jiaojiao Jiang
Continual knowledge graph embedding updates entity and relation representations as a graph grows. Existing methods primarily address catastrophic forgetting, but entity admission a…
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 a…