From the 1 of 9 linked papers with an AI index.
9 papers
Beyond the -mixing bound for Dikin walks on polytopes
Yunbum Kook
The paper improves the mixing time bound for the Dikin walk used to sample uniformly from polytopes, showing a d^{2.25} iteration bound by leveraging a scaled Lee–Sidford metric an…
A unified complexity bound for logconcave sampling
Yunbum Kook, Santosh S. Vempala
We give a simple, unified, and nearly tight bound for sampling arbitrary logconcave distributions from a warm start using the In-and-Out algorithm along with exponential lifting. T…
Zeroth-order Logconcave Sampling
Yunbum Kook, Santosh S. Vempala
We study the zeroth-order query complexity of sampling from a general logconcave distribution: given access to an evaluation oracle for a convex function $V:\mathbb{R}^{d}\rightarr…
The Localization Method for High-Dimensional Inequalities
Yunbum Kook, Santosh S. Vempala
We survey the localization method for proving inequalities in high dimension, pioneered by Lovász and Simonovits (1993), and its stochastic extension developed by Eldan (2012). Th…
In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
Yunbum Kook, Santosh S. Vempala, Matthew S. Zhang
We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than prev…
Fast Tensor Completion via Approximate Richardson Iteration
Mehrdad Ghadiri, Matthew Fahrbach, Yunbum Kook +1
We study tensor completion (TC) through the lens of low-rank tensor decomposition (TD). Many TD algorithms use fast alternating minimization methods to solve highly structured line…