6 papers
The Dimension of Nonterminating Resampling Computations
Yunbei Xu
A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one…
Bellman-sufficient Information Complexity
Yunbei Xu
We develop Bellman-sufficient information complexity, a representation-level framework for the information-theoretic minimax analysis of sequential decision making. The theory cove…
Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
Yunbei Xu
We prove a variance-aware pointwise majorizing-measure theorem for centered Gaussian processes. Classical generic chaining characterizes the scalar quantity $\mathbb E\sup_{x\in T}…
Pointwise Generalization in Deep Neural Networks
Shaojie Li, Yunbei Xu
We address the fundamental question of why deep neural networks generalize by establishing a pointwise generalization theory for fully connected networks. This framework resolves l…
On the Power of Adaptivity for -Best Arm Identification in Linear Bandits
Arnab Maiti, Yunbei Xu, Kevin Jamieson
We study the minimax sample complexity of -best arm identification in linear bandits. Given a compact action set that spans and an unknown…
On the Blessing of Pre-training in Weak-to-Strong Generalization
Wei Yao, Wang Zhaoyang, Gengze Xu +5
The paradigm of Weak-to-Strong Generalization (W2SG) suggests that a pre-trained strong model can surpass its weak supervisor, yet the decisive role of pre-training remains theoret…