9 papers · 1 filter
Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension
Xiaoyu Li
We study learning an unknown element of a group acting with finite orbits on a countable set, from examples . After a sample on , the consistent hypotheses are the r…
CoRA-NAS: Coarse Ranking and Anchor-Residual Refinement for Neural Architecture Search
Yifan Yang, Zhaoyan Wang, Zheng Gao +2
Zero-cost proxies rank architectures cheaply, but their reliability varies across search spaces. We introduce CoRA-NAS (COarse Ranking + Anchor-residual), a two-stage framework com…
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…
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…
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…
Contrastive Identification and Generation in the Limit
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
In the classical identification in the limit model of Gold [1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hyp…
On the Price of Privacy for Language Identification and Generation
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
As large language models (LLMs) are increasingly trained on sensitive user data, understanding the fundamental cost of privacy in language learning becomes essential. We initiate t…
Breaking Semantic-Aware Watermarks via LLM-Guided Coherence-Preserving Semantic Injection
Zheng Gao, Xiaoyu Li, Zhicheng Bao +2
Generative images have proliferated on Web platforms in social media and online copyright distribution scenarios, and semantic watermarking has increasingly been integrated into di…
Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guarantees
Xiaoyu Li, Guangyu Tang, Jiaojiao Jiang
Many real-world interactions are group-based rather than pairwise such as papers with multiple co-authors and users jointly engaging with items. Hypergraph neural networks have sho…