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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/152686 |
| _version_ | 1826201207700455424 |
|---|---|
| author | Lu, Chen |
| author2 | Rigollet, Philippe |
| author_facet | Rigollet, Philippe Lu, Chen |
| author_sort | Lu, Chen |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:48:13Z |
| format | Thesis |
| id | mit-1721.1/152686 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:48:13Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1526862023-11-03T03:38:48Z Upper and Lower Bounds for Sampling Lu, Chen Rigollet, Philippe Massachusetts Institute of Technology. Department of Mathematics 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. Ph.D. 2023-11-02T20:08:26Z 2023-11-02T20:08:26Z 2023-09 2023-08-22T19:02:33.251Z Thesis https://hdl.handle.net/1721.1/152686 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Lu, Chen Upper and Lower Bounds for Sampling |
| title | Upper and Lower Bounds for Sampling |
| title_full | Upper and Lower Bounds for Sampling |
| title_fullStr | Upper and Lower Bounds for Sampling |
| title_full_unstemmed | Upper and Lower Bounds for Sampling |
| title_short | Upper and Lower Bounds for Sampling |
| title_sort | upper and lower bounds for sampling |
| url | https://hdl.handle.net/1721.1/152686 |
| work_keys_str_mv | AT luchen upperandlowerboundsforsampling |