Parameter estimation for Gibbs distributions
Harris DG, Kolmogorov V. 2025. Parameter estimation for Gibbs distributions. ACM Transactions on Algorithms. 21(1), 3.
Download (ext.)
DOI
Journal Article
| Published
| English
Scopus indexed
Author
Harris, David G.;
Kolmogorov, VladimirISTA
Corresponding author has ISTA affiliation
Department
Abstract
A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n]. Two important parameters are the partition function, which is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the vector of pre-image counts c_x=|H^-1(x)|.
We develop black-box sampling algorithms to estimate the counts roughly Õ(n²/ε²) samples for integer-valued distributions and Õ(q/ε²) samples for general distributions, where q = (log Z(β_max))/Z(β_min) (ignoring some second-order terms and parameters). We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs, independent sets, and perfect matchings. As a key subroutine, we estimate all values of the partition function using Õ(n²/ε²) samples for integer-valued distributions and Õ(q/ε²) samples for general distributions. This improves over a prior algorithm of Huber (2015) which computes a single point estimate Z(β_max) and which uses a slightly larger amount of samples. We show matching lower bounds, demonstrating this complexity is optimal as a function of n and q up to logarithmic terms.
Publishing Year
Date Published
2025-01-01
Journal Title
ACM Transactions on Algorithms
Publisher
Association for Computing Machinery
Acknowledgement
We thank Heng Guo for helpful explanations of algorithms for sampling connected subgraphs and matchings, and Maksym Serbyn for bringing to our attention the WL algorithm and its use in physics.
This is an extended version, which includes work under the same name from ICALP 2023, as well as the earlier work [22] appearing in COLT 2018.
V. Kolmogorov was supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160
Volume
21
Issue
1
Article Number
3
ISSN
eISSN
IST-REx-ID
Cite this
Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. ACM Transactions on Algorithms. 2025;21(1). doi:10.1145/3685676
Harris, D. G., & Kolmogorov, V. (2025). Parameter estimation for Gibbs distributions. ACM Transactions on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3685676
Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” ACM Transactions on Algorithms. Association for Computing Machinery, 2025. https://doi.org/10.1145/3685676.
D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,” ACM Transactions on Algorithms, vol. 21, no. 1. Association for Computing Machinery, 2025.
Harris DG, Kolmogorov V. 2025. Parameter estimation for Gibbs distributions. ACM Transactions on Algorithms. 21(1), 3.
Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” ACM Transactions on Algorithms, vol. 21, no. 1, 3, Association for Computing Machinery, 2025, doi:10.1145/3685676.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level

Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2007.10824