Yunbum Kook

ICML Conference 2025 Conference Paper

Fast Tensor Completion via Approximate Richardson Iteration

• Mehrdad Ghadiri
• Matthew Fahrbach
• Yunbum Kook
• Ali Jadbabaie

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 linear regression problems at each step (e. g. , for CP, Tucker, and tensor-train decompositions). However, such algebraic structure is often lost in TC regression problems, making direct extensions unclear. This work proposes a novel lifting method for approximately solving TC regression problems using structured TD regression algorithms as blackbox subroutines, enabling sublinear-time methods. We analyze the convergence rate of our approximate Richardson iteration-based algorithm, and our empirical study shows that it can be 100x faster than direct methods for CP completion on real-world tensors.

FOCS Conference 2025 Conference Paper

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 algorithms for inputs in (near-)isotropic position. A long line of prior work incurred a warm-start penalty of at least linear in the dimension, hitting a cubic barrier, even for the special case of uniform sampling from convex bodies. Our improvement relies on two key ingredients of independent interest. (1) We show how to sample given a warm start in weaker notions of distance, in particular q-Rényi divergence for $q=\widetilde{O}$ (1), whereas previous analyses required stringent $\infty$-Rényi divergence (with the exception of Hit-and-Run, whose known mixing time is higher). This marks the first improvement in the required warmness since Lovász and Simonovits (1991). (2) We refine and generalize the $\log$-Sobolev inequality of Lee and Vempala (2018), originally established for isotropic logconcave distributions in terms of the diameter of the support, to logconcave distributions in terms of a geometric average of the support diameter and the largest eigenvalue of the covariance matrix.

SODA Conference 2025 Conference Paper

Rényi-infinity constrained sampling with d 3 membership queries

• Yunbum Kook
• Matthew S. Zhang

STOC Conference 2025 Conference Paper

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 given an evaluation oracle. Our new approach provides the first complexity improvements in nearly two decades for general logconcave functions for all three problems, and matches the best-known complexities for the special case of uniform distributions on convex bodies. For the sampling problem, our output guarantees are significantly stronger than previously known, and lead to a streamlined analysis of statistical estimation based on dependent random samples.

NeurIPS Conference 2024 Conference Paper

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 previously known, namely in Rényi divergence (which implies TV, $\mathcal{W}_2$, KL, $\chi^2$). The proof departs from known approaches for polytime algorithms for the problem - we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density.

ICML Conference 2024 Conference Paper

Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise

• Kwangjun Ahn
• Zhiyu Zhang
• Yunbum Kook
• Yan Dai 0002

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 Adam show the convergence rate that can be simply achieved by non-adative algorithms like SGD. In this work, we provide a different perspective based on online learning that underscores the importance of Adam’s algorithmic components. Inspired by Cutkosky et al. (2023), we consider the framework called online learning of updates/increments, where we choose the updates/increments of an optimizer based on an online learner. With this framework, the design of a good optimizer is reduced to the design of a good online learner. Our main observation is that Adam corresponds to a principled online learning framework called Follow-the-Regularized-Leader (FTRL). Building on this observation, we study the benefits of its algorithmic components from the online learning perspective.

NeurIPS Conference 2022 Conference Paper

Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space

• Yunbum Kook
• Yin-Tat Lee
• Ruoqi Shen
• Santosh Vempala

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 \emph{in practice}. Our algorithm incorporates constraints into the Riemannian version of Hamiltonian Monte Carlo and maintains sparsity. This allows us to achieve a mixing rate independent of smoothness and condition numbers. On benchmark data sets in systems biology and linear programming, our algorithm outperforms existing packages by orders of magnitude. In particular, we achieve a 1, 000-fold speed-up for sampling from the largest published human metabolic network (RECON3D). Our package has been incorporated into a popular Bioinformatics library.

SODA Conference 2021 Conference Paper

Vertex Sparsification for Edge Connectivity

• Parinya Chalermsook
• Syamantak Das
• Yunbum Kook
• Bundit Laekhanukit
• Yang P. Liu
• Richard Peng
• Mark Sellke
• Daniel Vaz 0001

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1 + ∊ )-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity- c mimicking networks with O ( kc 4 ) edges exist and can be found in time m ( c log n ) O ( c ). We also give a separate algorithm that constructs such graphs with k · O ( c ) 2 c edges in time mc O ( c ) log O (1) n. These results lead to the first data structures for answering fully dynamic offline c -edge-connectivity queries for c ≥ 4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.