7 citations · 15 across the 10 of their papers we have counts for
10 papers
Local Search with Correlated Randomness
Yunbei Xu
How much does an algorithm's running-time distribution under independent randomness reveal about its behavior when independence is no longer guaranteed? We study sources satisfying…
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}…
Bellman-sufficient Information Complexity
Yunbei Xu
We introduce Bellman-sufficient information complexity for minimax analysis of sequential decision problems. A Bellman-sufficient state retains enough of the history to close the c…
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…
Bayesian Design Principles for Frequentist Sequential Learning
Yunbei Xu, Assaf Zeevi
We develop a general theory to optimize the frequentist regret for sequential learning problems, where efficient bandit and reinforcement learning algorithms can be derived from un…
Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
Yunbei Xu, Assaf Zeevi
We study problem-dependent rates, i.e., generalization errors that scale near-optimally with the variance, the effective loss, or the gradient norms evaluated at the "best hypothes…
Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
Yunbei Xu, Assaf Zeevi
The principle of optimism in the face of uncertainty is one of the most widely used and successful ideas in multi-armed bandits and reinforcement learning. However, existing optimi…
Acceleration of Primal-Dual Methods by Preconditioning and Simple Subproblem Procedures
Yanli Liu, Yunbei Xu, Wotao Yin
Primal-Dual Hybrid Gradient (PDHG) and Alternating Direction Method of Multipliers (ADMM) are two widely-used first-order optimization methods. They reduce a difficult problem to s…