Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose a doubly "adaptive" MCMC algorithm to approximate the partition function in gibbs distributions.
In related work, the partition function of Gibbs distributions are computed using paired product estimators [1].
Such estimators use a cooling schedule $[\beta_{(\cdot)}]$ to estimate two product functions $F$ and $G$ using stationary samples from the Gibbs distribution at each temperature.
The ratio of these two products is then used to compute the partition function.

In the current work, the first "adaptive" refers to the adaptive TPA cooling schedule to decide $[\beta_{(\cdot)}]$.
The second refers to the automatic number of steps used in the MCMC MeanEstimator which is used to estimate the two products mentioned above $F$ and $G$.

[1] - Huber, Mark. "Approximation algorithms for the normalizing constant of Gibbs distributions." The Annals of Applied Probability 25.2 (2015): 974-985.
main_review: ### Strengths

- The method is well motivated and the theoretical analysis is very thorough.

### Weaknesses

- The usage of the word adaptive (as an auto-decision on the number of steps) is highly misleading. An entire line of work [2] exists where the word adaptive refers to changing the transition kernel to improve the efficiency of the MCMC.
- In line 77 describing Huber and Schott's estimator, [1] makes statements on estimating $z=\log(Z)$. Please refer to the discussion 2 paragraphs before algorithm 2.2 in [1] ([29] in reviewed paper). (Maybe I am missing something but in order to apply linearity of expectations to a product and to compute an unbiased estimator of a quotient, the log domain makes more sense. However please correct me if I am missing something.)
- Please consider comparison with Annealed Importance Sampling (AIS) [3] which samples a single transition at each temperature such that stationary samples at each temperature aren't needed.
  - I may have missed a nuance which prohibits the use of AIS, and if that is the case I am willing to change my rating.
  - If AIS can indeed be used in this scenario, the second "adaptation" can only be justified thorough empirical evaluation.
- Please add error bars to all plots not just Fig 1.e.
- Please use larger font in plots.

### Other criteria

- Originality : Existing problem, novel solution which combines [1,4] using original tools.
- Quality : Theory is very rigorous, empirical evaluation lacking.
- Clarity : Motivations are well explained, plots need work and experimental evaluation is lacking.
- Significance : Unclear, refer to comment regarding AIS in Weaknesses.

### Note

I am willing to update my review, especially my overall score, based on a strong rebuttal arguing that either AIS is not applicable in this task or is demonstrably bad when empirically evaluated against the method.

[1] - Huber, Mark. "Approximation algorithms for the normalizing constant of Gibbs distributions." The Annals of Applied Probability 25.2 (2015): 974-985.

[2] - Roberts, Gareth O., and Jeffrey S. Rosenthal. "Examples of adaptive MCMC." Journal of computational and graphical statistics 18.2 (2009): 349-367.

[3] - Neal, Radford M. "Annealed importance sampling." Statistics and computing 11.2 (2001): 125-139.

[4] - Cousins, Cyrus, Shahrzad Haddadan, and Eli Upfal. "Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE." arXiv preprint arXiv:2011.11129 (2020).
limitations_and_societal_impact: Adequately addressed
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a method for estimating the partition function of Gibbs distributions. The method primarily relies on an adaptive mean estimator, and is shown to have theoretical and practical advantages over previous methods.
main_review: The problem of approximating the partition function of discrete probabilistic models is relevant and has a lot of ML applications. This paper mainly focuses on improving previous methods based on paired product estimators [1] by introducing an improved mean estimator that does not require black box (approximately) independent samples. Based on previous work on trace averaging [2], they introduce an adaptive mean estimator, and theoretically show that the resulting method is superior to the state of the art. The final algorithms (Alg. 2 in the paper) and their upper bounds are an interesting contribution, albeit not completely novel, since both adaptive parts (cooling and mean estimation) are largely based on previous work.

I see two major downsides with this paper:
- The exposition of the main theoretical results in section 2 suffers from lack of clarity. Both sections 2.1 and 2.2 are heavy on notation, and contain very little intuitive explanation.
- The experimental section only discusses very small toy examples, which makes me wonder whether the proposed algorithms would actually be applicable to any practically relevant ML problem.

&nbsp;
### References
[1] Mark Huber and Sarah Schott. Random construction of interpolating sets for high-dimensional integration. Journal of Applied Probability, 2014.\
[2] Cyrus Cousins, Shahrzad Haddadan, and Eli Upfal. Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE. ArXiv, 2020.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The objective of this work is to define a procedure for calculating Gibbs distribution normalization constants. The calculation of normalisation constants is a central problem in many fields and most known methods depend on many hyper-parameters that are difficult to optimise. The most efficient methods (such as "paired product estimator" extending "multiple  sampling" of Valleau and Card) are based on annealing schemes. The normalisation constant is obtained in this case as a product, each term of the product being calculated by means of an MCMC algorithms. Several strategies have been proposed to optimise the annealing schedule. The optimisation of the annealing schedule requires a measure of the complexity of generating samples with the MCMC algorithm, which typically involves using upper bounds on their mixing times. Despite progress in this direction, the estimation of chain mixing times is a difficult subject: the known bounds are, with few exceptions (of very simple models with a lot of symetries), very pessimistic.
The paper presents an imporoved mean estimator for comuting the nomalizing constant of a Gibbs distribution. The proposed algorithm is claimed to improve SOTA results in this field. Compared to other techniques, the proposed algorithm is "less dependent" (the authors words) on the tightness of the bounds use to measure the mixing time. The main improvements bought by the authors is clained to be high-accuracy computaitons. 
main_review: 
Major comments:
Except for the presentation of the basic algorithm (which is fairly classical), the paper is difficult to read. It is difficult to understand the contributions, the results, I was  quite confuse even after reading the full paper. The discussion and the proofs use a lot of external references, which require each time to understand other conventions, notations, concepts. It would be much better to recap the required results in a Section in the supplement paper, to ease the reading. 

I have tried to check the proof of Theorem 2.4 in the supplementary version for example, and I found it quite difficut to follow. I would definitely prefer in the supplement paper to get  complete and detailed arguments, not a sketch of proofs with external references (when you cite an external result in a paper is definitely better to get a precise reference to the theorem or proposition which is used, it is very complicated otherwise). 

I am surprised not to see in the complexity bounds the initial distribution of the Markov chain. The authors use the results  of Jiang, Sun, Fan (2018) [Theorem 1 and 2] which both assumed that the MC is stationary. It would be interesting to know how the authors plan to work with the non-stationary case.  


The assumption of knowing an upper bound of the spectral gap seems difficult to me. The estimators are, except for examples, generally extremely pessimistic, especially for general state chains. 
Minor comments
- I find the discussion at the beginning of Section 2 difficult to follow
- Lemma 1 is dificult to understand because some quantities which are presented are not defined (what is  $\Delta_i$ ? )
- line 177: "estimating means.. union bound)." difficult to understand as it is stated. 
limitations_and_societal_impact: none
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors introduce a new method to estimate the partition functions of Gibbs distributions. They try to improve the classical mean estimate computation by using an adaptive MCMC mean estimator. And they justify the priority of their methods through theoretical analysis and experiments.
main_review: Overall, the reviewer thinks this is a good paper. As claimed by the authors, they introduce a new method that is proven to outperform the state of art algorithms. And the experiments also justify this. 

However, the reviewer thinks this paper is not very clear. The reviewer is not familiar with this problem and feels it's a little hard to follow this paper. The reviewer will point out some confusing parts in "Limitations".
limitations_and_societal_impact: Some limitations of this paper are listed as follows: (The reviewer is not an expert in this area and might misunderstand something.)
1. In the contribution section (Sec 1.2), the reviewer thinks the authors can delete lines 121-129 since all four points explain how the paper achieves an improvement in computational complexity. 
It's good that the authors explain how they obtain the improvement. But they are actually not the main contributions, the authors should move them somewhere else.
2. In the conclusion section (Sec 4), Table 1 compares the computation complexity of different methods. But the authors omit the $1/\epsilon$ term. It's true that this term can be omitted when $\epsilon$ is small enough, but the authors should mention the conditions that this holds. The authors also mention $RelR_i$ is a large number, then it seems we should choose $\epsilon$ super small to see the priority of new methods.
3. According to Table 1, the authors don't give any comparison between $\text{Reltrv}^{\tau_i}$ and $V_{rel}$. If they are in the same order, the reviewers think the new method is better because $\ln(l/\epsilon)>l^2$ when $\epsilon$ is small. Then it seems that the main improvement comes from the new bound eliminates the $\ln(1/\epsilon)$ factor. This seems a small improvement. Can the authors give some explanation why this is important?

As a potential reader, the reviewer thinks that there are some confusing places in the paper:
1. In line 59, "the values of random terms in the sum have large variance". According to (1), the reviewer didn't see any randomness. Does the author mean the variance of $\pi_{\beta}$ is large so $Z(\beta)$ is hard to estimate?
2. In line 83, $"O(log(Q)log(H_{\max})"$, this is the first time $H_{\max}$ appears. But the authors define it in Lemma 2.6 line 231. The authors can move the definition forward or at least give an explanation in line 83.
3. In line 84, "TPA(k,d)", this is the first time $d$ appears. Again, there is no definition and explanation. 
4. In lines 100 and 108, what is $\pi_\min$? The reviewer didn't find its definition in the paper. 
5. In the results of Section 2.2, what is $\epsilon$? 
6. In line 303, according to Table 1, the reviewers think "$\ln(l)$" should be "$\ln(l/\epsilon)$".
7. In line 305 Table 1, what is $T_i$? Is it the same as $\tau_i$?
8. As said before, the comparison in Table 1 is very unclear. The authors should spend more space to do the comparison and make it clear.
review_title: null

Meta-review: The goal of this paper is a better algorithm to estimate the partition function / normalization constant in a Gibbs distribution. These are often of interest in many different forms in the NeurIPS community. The best current methods are based on annealing, essentially starting at a normalized distribution and moving through a series of distributions of different temperatures and estimating the ratio of each using MCMC. This paper proposes a new algorithm in this line which is intended to be less sensitive to tightness in the mixing times of MCMC.

This is a highly mathematical paper, where the goal is improved theoretical guarantees (rather than, say, practical performance improvement.) Unfortunately, all reviewers signaled that they were not confidently able to verify the correctness of the core results. In the end, the SAC stepped in and did a careful reading of the paper and recommends acceptance.

The SAC's reasoning is as follows:

The presentation is indeed terse and dense. But that is par for the course for theoretical papers at NeurIPS given the page limit. Everything was well defined (as far as I saw), and all the arguments seemed credible. The authors outlined the strategy of their arguments, hiding the considerable complexity of all the details in the supplementary material. I actually found the writing pretty good compared to the average published Neurips paper.

Regarding the concern by one reviewer about the assumption re spectral gap: I do not see this as a downside. It seems inevitable that one will need some assumptions on the dynamics of these chains in order to say anything theoretical. The goal (in my mind) is not to attempt the impossible task of theoretically explaining what "really" happens in practice, because one never knows. Assuming something about a spectral gap in the transition matrix of a markov chain seems to me to be less fraught epistemologically that (say) assuming one's data is drawn iid from some distribution ... an assumption that I doubt is true of almost all practical applications of machine learning, but upon which almost all ML theory is built... (Thus my view is aligned to that of the authors in their "Note to chair")

So it looks like this is a real advance on a problem of interest. The analysis looks credible (all one can ever really tell without spending a week working through every single step). It is easily at least as clear, correct, and significant as the majority of published Neurips papers so I do not have any qualms recommending acceptance....
Decision: Accept (Poster)