5 papers
Algorithmic Thinking Theory
MohammadHossein Bateni, Vincent Cohen-Addad, Yuzhou Gu +3
Large language models (LLMs) have proven to be highly effective for solving complex reasoning tasks. Surprisingly, their capabilities can often be improved by iterating on previous…
Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits
Yuzhou Gu, Yanjun Han, Jian Qian
We study the evolution of information in interactive decision making through the lens of a stochastic multi-armed bandit problem. Focusing on a fundamental example where a unique o…
Binary Hypothesis Testing for Softmax Models and Leverage Score Models
Yuzhou Gu, Zhao Song, Junze Yin
Softmax distributions are widely used in machine learning, including Large Language Models (LLMs), where the attention unit uses softmax distributions. We abstract the attention un…
Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
Yuzhou Gu, Xin Li, Yinzhan Xu
In the noisy query model, the (binary) return value of every query (possibly repeated) is independently flipped with some fixed probability . In this paper, we obta…
Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
Yuzhou Gu, Nikki Lijing Kuang, Yi-An Ma +2
We consider the problem of sampling from a -dimensional log-concave distribution for -Lipschitz , constrained to a convex body with an effici…