Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling
We study probability measures induced by set functions with constraints. Such measures arise in a variety of real-world settings, where prior knowledge, resource limitations, or other pragmatic considerations impose constraints. We consider the task of rapidly sampling from such constrained measures...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Morgan Kaufmann Publishers
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129329 |
| _version_ | 1826197491255607296 |
|---|---|
| author | Li, Chengtao Jegelka, Stefanie Sabrina Sra, Suvrit |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Li, Chengtao Jegelka, Stefanie Sabrina Sra, Suvrit |
| author_sort | Li, Chengtao |
| collection | MIT |
| description | We study probability measures induced by set functions with constraints. Such measures arise in a variety of real-world settings, where prior knowledge, resource limitations, or other pragmatic considerations impose constraints. We consider the task of rapidly sampling from such constrained measures, and develop fast Markov chain samplers for them. Our first main result is for MCMC sampling from Strongly Rayleigh (SR) measures, for which we present sharp polynomial bounds on the mixing time. As a corollary, this result yields a fast mixing sampler for Determinantal Point Processes (DPPs), yielding (to our knowledge) the first provably fast MCMC sampler for DPPs since their inception over four decades ago. Beyond SR measures, we develop MCMC samplers for probabilistic models with hard constraints and identify sufficient conditions under which their chains mix rapidly. We illustrate our claims by empirically verifying the dependence of mixing times on the key factors governing our theoretical bounds. |
| first_indexed | 2024-09-23T10:48:31Z |
| format | Article |
| id | mit-1721.1/129329 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:48:31Z |
| publishDate | 2021 |
| publisher | Morgan Kaufmann Publishers |
| record_format | dspace |
| spelling | mit-1721.1/1293292022-09-30T23:11:43Z Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling Li, Chengtao Jegelka, Stefanie Sabrina Sra, Suvrit Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We study probability measures induced by set functions with constraints. Such measures arise in a variety of real-world settings, where prior knowledge, resource limitations, or other pragmatic considerations impose constraints. We consider the task of rapidly sampling from such constrained measures, and develop fast Markov chain samplers for them. Our first main result is for MCMC sampling from Strongly Rayleigh (SR) measures, for which we present sharp polynomial bounds on the mixing time. As a corollary, this result yields a fast mixing sampler for Determinantal Point Processes (DPPs), yielding (to our knowledge) the first provably fast MCMC sampler for DPPs since their inception over four decades ago. Beyond SR measures, we develop MCMC samplers for probabilistic models with hard constraints and identify sufficient conditions under which their chains mix rapidly. We illustrate our claims by empirically verifying the dependence of mixing times on the key factors governing our theoretical bounds. National Science Foundation (U.S.). Career Grant (1553284) 2021-01-07T21:20:20Z 2021-01-07T21:20:20Z 2016-12 2020-12-21T18:55:44Z Article http://purl.org/eprint/type/ConferencePaper 1049-5258 https://hdl.handle.net/1721.1/129329 Li, Chengtao, Stefanie Jegelka and Suvrit Sra. “Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling.” Advances in Neural Information Processing Systems, 29 (December 2016) © 2016 The Author(s) en Advances in Neural Information Processing Systems Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Morgan Kaufmann Publishers Neural Information Processing Systems (NIPS) |
| spellingShingle | Li, Chengtao Jegelka, Stefanie Sabrina Sra, Suvrit Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling |
| title | Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling |
| title_full | Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling |
| title_fullStr | Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling |
| title_full_unstemmed | Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling |
| title_short | Fast mixing Markov chains for strongly rayleigh measures, DPPs, and constrained sampling |
| title_sort | fast mixing markov chains for strongly rayleigh measures dpps and constrained sampling |
| url | https://hdl.handle.net/1721.1/129329 |
| work_keys_str_mv | AT lichengtao fastmixingmarkovchainsforstronglyrayleighmeasuresdppsandconstrainedsampling AT jegelkastefaniesabrina fastmixingmarkovchainsforstronglyrayleighmeasuresdppsandconstrainedsampling AT srasuvrit fastmixingmarkovchainsforstronglyrayleighmeasuresdppsandconstrainedsampling |