8 papers
Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms
Yuchen He, Tianhui Jiang, Sihan Wang +1
We develop a discrete optimal transport framework for analyzing simulated annealing algorithms on finite state spaces. Building on the discrete Wasserstein metric introduced by Maa…
The Query Complexity of Uniform Pricing
Houshuang Chen, Yaonan Jin, Pinyan Lu +1
Real-world pricing mechanisms are typically optimized using training data, a setting corresponding to the \textit{pricing query complexity} problem in Mechanism Design. The previou…
Improved sampling algorithms and functional inequalities for non-log-concave distributions
Yuchen He, Zhehan Lei, Jianan Shao +1
We study the problem of sampling from a distribution with density for some potential function with query access to and $\nabla…
On the Problem of Best Arm Retention
Houshuang Chen, Yuchen He, Chihao Zhang
This paper presents a comprehensive study on the problem of Best Arm Retention (BAR), which has recently found applications in streaming algorithms for multi-armed bandits. In the…
Tight Regret Bounds for Fixed-Price Bilateral Trade
Houshuang Chen, Yaonan Jin, Pinyan Lu +1
We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetildeΘ(…
Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
Zichun Ye, Chihao Zhang, Jiahao Zhao
We study the problem of minimizing gap-dependent regret for single-pass streaming stochastic multi-armed bandits (MAB). In this problem, the arms are present in a stream, and a…
On the query complexity of sampling from non-log-concave distributions
Yuchen He, Chihao Zhang
We study the problem of sampling from a -dimensional distribution with density , which does not necessarily satisfy good isoperimetric conditions. Specifi…
Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
Yuchen He, Zichun Ye, Chihao Zhang
We study the stochastic multi-armed bandit problem in the -pass streaming model. In this problem, the arms are present in a stream and at most arms and their statistic…