Abstract
dc:description.abstractSampling from a high-dimensional distribution is a fundamental primitive underlying integration, statistical estimation, and machine learning. This thesis advances the complexity theory of log-concave sampling, the task of drawing a sample (approximately) from π\propto e-V for a convex function $V$. The first part develops diffusion-based samplers under a zeroth-order oracle, departing from the classical conductance framework. Building on the proximal sampler, we obtain the first improvements in general log-concave sampling complexity in nearly two decades, break the long-standing \widetilde{O}(d3) cold-start barrier for near-isotropic log-concave distributions, and give the first complete treatment of sampling in the Rényi divergence framework for all orders. Finally, we unify the complexity bounds for log-concave sampling across various settings. The second part applies these advances to covariance estimation and integration. Exploiting Markov chain structure in the estimator reduces query complexity by a dimensional factor over i.i.d.-based methods, yielding improved complexities of \widetilde{O}(d3.5) for covariance estimation and \widetilde{O}(d3.5+d3/\varepsilon2) for integration of log-concave functions. The third part develops a sampling analogue of the interior-point method. We make progress toward the conjectured d2-mixing bound for the Dikin walk on polytopes. Moreover, by equipping the Dikin walk with self-concordant metrics adapted to the structure of the constraints and potential, we obtain faster sampling algorithms for structured log-concave distributions over polytopes, second-order cones, and positive semidefinite cones.
Degree
thesis:*- Name thesis:degree_name
- Computer Science, PhD
- Department thesis:degree_department
- Computer Science
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kook, Yunbum
- Advisor dc:contributor.advisor
-
- Vempala, Santosh S.
- Committee members dc:contributor.committeemember
-
- Perkins, Will
- Chen, Zongchen
- Chewi, Sinho
- Wibisono, Andre
Rights
- Language dc:language.iso
- English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/82136