Hogwild!-Gibbs can be panaccurate
© 2018 Curran Associates Inc..All rights reserved. Asynchronous Gibbs sampling has been recently shown to be fast-mixing and an accurate method for estimating probabilities of events on a small number of variables of a graphical model satisfying Dobrushin's condition [DSOR16]. We investigate wh...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143124 |
| _version_ | 1826189176997937152 |
|---|---|
| author | Daskalakis, C Dikkala, N Jayanti, S |
| 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 Daskalakis, C Dikkala, N Jayanti, S |
| author_sort | Daskalakis, C |
| collection | MIT |
| description | © 2018 Curran Associates Inc..All rights reserved. Asynchronous Gibbs sampling has been recently shown to be fast-mixing and an accurate method for estimating probabilities of events on a small number of variables of a graphical model satisfying Dobrushin's condition [DSOR16]. We investigate whether it can be used to accurately estimate expectations of functions of all the variables of the model. Under the same condition, we show that the synchronous (sequential) and asynchronous Gibbs samplers can be coupled so that the expected Hamming distance between their (multivariate) samples remains bounded by O(τ log n), where n is the number of variables in the graphical model, and τ is a measure of the asynchronicity. A similar bound holds for any constant power of the Hamming distance. Hence, the expectation of any function that is Lipschitz with respect to a power of the Hamming distance, can be estimated with a bias that grows logarithmically in n. Going beyond Lipschitz functions, we consider the bias arising from asynchronicity in estimating the expectation of polynomial functions of all variables in the model. Using recent concentration of measure results [DDK17, GLP17, GSS18], we show that the bias introduced by the asynchronicity is of smaller order than the standard deviation of the function value already present in the true model. We perform experiments on a multiprocessor machine to empirically illustrate our theoretical findings. |
| first_indexed | 2024-09-23T08:10:43Z |
| format | Article |
| id | mit-1721.1/143124 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:10:43Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | mit-1721.1/1431242023-01-23T18:59:11Z Hogwild!-Gibbs can be panaccurate Daskalakis, C Dikkala, N Jayanti, S Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2018 Curran Associates Inc..All rights reserved. Asynchronous Gibbs sampling has been recently shown to be fast-mixing and an accurate method for estimating probabilities of events on a small number of variables of a graphical model satisfying Dobrushin's condition [DSOR16]. We investigate whether it can be used to accurately estimate expectations of functions of all the variables of the model. Under the same condition, we show that the synchronous (sequential) and asynchronous Gibbs samplers can be coupled so that the expected Hamming distance between their (multivariate) samples remains bounded by O(τ log n), where n is the number of variables in the graphical model, and τ is a measure of the asynchronicity. A similar bound holds for any constant power of the Hamming distance. Hence, the expectation of any function that is Lipschitz with respect to a power of the Hamming distance, can be estimated with a bias that grows logarithmically in n. Going beyond Lipschitz functions, we consider the bias arising from asynchronicity in estimating the expectation of polynomial functions of all variables in the model. Using recent concentration of measure results [DDK17, GLP17, GSS18], we show that the bias introduced by the asynchronicity is of smaller order than the standard deviation of the function value already present in the true model. We perform experiments on a multiprocessor machine to empirically illustrate our theoretical findings. 2022-06-14T19:04:34Z 2022-06-14T19:04:34Z 2018-01-01 2022-06-14T18:54:38Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/143124 Daskalakis, C, Dikkala, N and Jayanti, S. 2018. "Hogwild!-Gibbs can be panaccurate." Advances in Neural Information Processing Systems, 2018-December. en https://papers.nips.cc/paper/2018/hash/a5bfc9e07964f8dddeb95fc584cd965d-Abstract.html 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 Neural Information Processing Systems (NIPS) |
| spellingShingle | Daskalakis, C Dikkala, N Jayanti, S Hogwild!-Gibbs can be panaccurate |
| title | Hogwild!-Gibbs can be panaccurate |
| title_full | Hogwild!-Gibbs can be panaccurate |
| title_fullStr | Hogwild!-Gibbs can be panaccurate |
| title_full_unstemmed | Hogwild!-Gibbs can be panaccurate |
| title_short | Hogwild!-Gibbs can be panaccurate |
| title_sort | hogwild gibbs can be panaccurate |
| url | https://hdl.handle.net/1721.1/143124 |
| work_keys_str_mv | AT daskalakisc hogwildgibbscanbepanaccurate AT dikkalan hogwildgibbscanbepanaccurate AT jayantis hogwildgibbscanbepanaccurate |