40 citations · 70 across the 19 of their papers we have counts for
22 papers
A simpler proof of the Matrix Spencer Theorem
Nikhil Bansal, Yunbum Kook
We give a simple exposition of the Matrix Spencer theorem due to Akbas and Sra [AS26].
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…
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). The…
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…
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…
Covariance estimation using Markov chain Monte Carlo
Yunbum Kook, Matthew S. Zhang
We investigate the complexity of covariance matrix estimation for Gibbs distributions based on dependent samples from a Markov chain. We show that when satisfies a Poincaré ine…
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…
Sampling from the Mean-Field Stationary Distribution
Yunbum Kook, Matthew S. Zhang, Sinho Chewi +2
We study the complexity of sampling from the stationary distribution of a mean-field SDE, or equivalently, the complexity of minimizing a functional over the space of probability m…
Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise
Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook +1
Despite the success of the Adam optimizer in practice, the theoretical understanding of its algorithmic components still remains limited. In particular, most existing analyses of A…
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…
Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space
Yunbum Kook, Yin Tat Lee, Ruoqi Shen +1
We demonstrate for the first time that ill-conditioned, non-smooth, constrained distributions in very high dimension, upwards of 100,000, can be sampled efficiently $\textit{in pra…
Evolution of Real-world Hypergraphs: Patterns and Models without Oracles
Yunbum Kook, Jihoon Ko, Kijung Shin
What kind of macroscopic structural and dynamical patterns can we observe in real-world hypergraphs? What can be underlying local dynamics on individuals, which ultimately lead to…
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…
Incremental Lossless Graph Summarization
Jihoon Ko, Yunbum Kook, Kijung Shin
Given a fully dynamic graph, represented as a stream of edge insertions and deletions, how can we obtain and incrementally update a lossless summary of its current snapshot? As lar…