Back to search

Georgia Institute of Technology

Complexity of log-concave sampling and applications

Abstract

dc:description.abstract

Sampling 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

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Kook, Yunbum. Complexity of log-concave sampling and applications. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/82136