8 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…
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 efficient…
Entropy Contractions in Markov Chains: Half-Step, Full-Step and Continuous-Time
Pietro Caputo, Zongchen Chen, Yuzhou Gu +1
This paper considers the speed of convergence (mixing) of a finite Markov kernel with respect to the Kullback-Leibler divergence (entropy). Given a Markov kernel one defines ei…
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…
Community detection in the hypergraph stochastic block model and reconstruction on hypertrees
Yuzhou Gu, Aaradhya Pandey
We study the weak recovery problem on the -uniform hypergraph stochastic block model (-HSBM) with two balanced communities. In this model, vertices are randomly divided i…
Generalized Rainbow Differential Privacy
Yuzhou Gu, Ziqi Zhou, Onur Günlü +4
We study a new framework for designing differentially private (DP) mechanisms via randomized graph colorings, called rainbow differential privacy. In this framework, datasets are n…