40 citations · 70 across the 19 of their papers we have counts for
13 papers · 1 filter
Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start
Yunbum Kook, Santosh S. Vempala
We show that logconcave probability measures along the Gaussian cooling path have thin-shell stability, generalizing the thin-shell theorem. This result leads to improved complexit…
On two proofs of mixing of weighted Dikin walks
Yuansi Chen, Yunbum Kook
We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result gives a…
Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run
Yunbum Kook, Santosh S. Vempala
For any convex body containing a unit ball, the spectral gap of Hit-and-Run is , where is the Poinc…
Beyond the -mixing bound for Dikin walks on polytopes
Yunbum Kook
Inspired by interior-point methods (IPM) for structured convex optimization, Kannan and Narayanan introduced the Dikin walk for sampling uniformly from polytopes in 2009. As in IPM…
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…
Faster logconcave sampling from a cold start in high dimension
Yunbum Kook, Santosh S. Vempala
We present a faster algorithm to generate a warm start for sampling an arbitrary logconcave density specified by an evaluation oracle, leading to the first sub-cubic sampling algor…
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…
Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
Yunbum Kook, Santosh S. Vempala
We study the complexity of sampling, rounding, and integrating arbitrary logconcave functions. Our new approach provides the first complexity improvements in nearly two decades for…
Rényi-infinity constrained sampling with membership queries
Yunbum Kook, Matthew S. Zhang
Uniform sampling over a convex body is a fundamental algorithmic problem, yet the convergence in KL or Rényi divergence of most samplers remains poorly understood. In this work, we…
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…
Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
Yunbum Kook, Santosh S. Vempala
The connections between (convex) optimization and (logconcave) sampling have been considerably enriched in the past decade with many conceptual and mathematical analogies. For inst…
Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators
Yunbum Kook, Yin Tat Lee, Ruoqi Shen +1
We study the convergence rate of discretized Riemannian Hamiltonian Monte Carlo on sampling from distributions in the form of on a convex body $\mathcal{M}\subset\mathb…
Vertex Sparsification for Edge Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit +5
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether -approximate cut-prese…