Upper and Lower Bounds for Sampling

This thesis studies the problem of drawing samples from a probability distribution. Despite the prevalence of sampling problems in applications, the quantitative behavior of sampling algorithms remains poorly understood. This thesis contributes to the theoretical understanding of sampling by giving upper bounds and more importantly lower bounds for various sampling algorithms and problem classes. On the upper bound side, we propose new sampling algorithms, motivated by the perspective of sampling as optimization [JKO98], and give convergence guarantees for them. We also obtain state-of-the-art convergence results for the popular Metopolis-Adjusted Langevin Algorithm. On the lower bound side, we establish the query complexity for strongly log-concave sampling in all constant dimensions. Our lower bounds rely on simple geometric constructions, which can hopefully be of aid to similar results in high dimensions.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Lu, Chen

Advisor dc:contributor.advisor

• Rigollet, Philippe

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/152686

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/152686