Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The work presents a new Parallel Tempering scheme that adapts a variational reference distribution within a parametric family. They adopt a parameter to minimize the forward KL divergence between the parametric family and the target distribution. They combine a fixed and an adaptive reference that leads to better restart rate performance than the baseline.
strengths_and_weaknesses: Strengths
-Interesting and witty idea combining a fixed and adaptive reference in the scheme.
-Extensive theoretical analysis of the proposed scheme. The authors provide theoretical guarantees for the performance and convergence of the method.
-Good presentation of the work.

Weaknesses
-A lot of toy experiments but not real world datasets. It would be interesting to see the method applied in a bigger model and a bigger dataset (like an image dataset MNIST, CIFAR10). 
-Structure is a bit odd since there are no conclusions and no discussion of limitations, future directions, societal impact. But again this is a theoretical work so societal impact is not applicable in this case. I would like to see the other stuff more in a separate paragraph though.

questions: My main question is regarding the scalability of the algorithm in deeper and bigger models. It would be interesting to see the method in those applications since the choice of Exponential distribution would make the scheme a good candidate for SG-MCMC like SGLD. But if this is not the scope of this work this is totally understandable and my decision is not conditioned on that.

Although I come from the experimental part of Statistical Machine Learning community I like this work and I think it should be accepted in NeurIPS. This work fits the venue and could provide fruitful discussions between Parallel Tempering researchers.


Some comments regarding the presentation:
-I would put the figures closer to the references cause for the reader is very difficult to go back and forth in the text and try to find Figure and the corresponding text.
-You need a conclusions paragraph.
-Write more clear the advantages of the method in the introduction.
-line 21: gold standard methodology for distribution approximation -> I would avoid using phrases as gold standard
-should have legend on the figures and use the description to describe the plots and what the reader should focus on.

limitations: This is a theoretical work so negative societal impact is not discussed and the limitations are briefly but not clearly discussed in the main text (Subsection 3.5).
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors proposed an improved version of the parallel tempering algorithm to solve the non-scalability issue with respect to the data size. In particular, the authors show that in the large-data limit, the restart rate degrades arbitrarily to 0, which strongly affects the communications between the chains associated with the target distribution and the prior distribution. To tackle that issue, the authors proposed to adopt variational inference based on the exponential family. Theories and experiments show much better restart rates.
strengths_and_weaknesses: Pros: 

I like the authors' insight on the weakness of parallel tempering with respect to the data size. Given a fixed schedule of parallel tempering, the communication efficiency does raise a concern in large-data limits. A major reason I am suspecting is that as the number of data points increases, the major mode becomes more dominant, which also inspires the authors to use a tunable prior based on variational inference.

Cons:

1. I think the proposed method is not the right solution to tackle that issue. As is known that parallel tempering not only cares about communication efficiency (or restart rates) but also focuses on the exploration-exploitation trade-off. The current method seems to solve the issue of communication inefficiency, but the impact of exploration is not clear. If we don't know **how much exploration is sacrificed**, why not just adopt a prior that is close enough to the target distribution? In that way, we can maintain a large enough restart rate via the most vanilla method.

2. The combination with a fixed reference further increases my concerns about this method in exploration, which has to resort to a different prior for exploration.

3. Regarding the theories, I feel this paper is more suitable for a journal review.

* I am familiar with Syed's JRSS-B'21 paper but the proof details of this work are not carefully checked.
questions: Before the exploration issue is elegantly solved, I still have concerns about the usefulness of this method to improve parallel tempering in big data.
limitations: NA
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes to learn the prior distribution adaptively for parallel tempering. In particular, the prior distribution is tuned to optimize a proxy objective (forward KL divergence to the posterior) with a simple gradient-free moment matching procedure. In theory, the variational prior reference proves to outperform fixed reference, but in practice it may get stuck in a single mode, which the authors resolve by mixing the adaptive and fixed reference distributions. Empirically, the proposed method achieves a big gain over existing methods on Bayesian inference tasks.
strengths_and_weaknesses: Strengths:
- The paper is very well written and easy to follow.
- The introduced algorithm is intuitive and theoretically sound. In the large data limit, the moment-matched reference could achieve the best possible restart rate of 1/2.
- The authors fixed the collapsed reference by adding fixed reference back in practice, which seems to work well empirically. To be fair, I'm not familiar with the datasets the authors used in the paper, so I don't know how convincing the empirical results are.


Weaknesses:
- Lack of discussions about the assumptions in theoretical analyses. For Propositions 3.1-3.3, the conclusions only hold under some assumptions mentioned in the Appendix. Adding some discussions or giving some intuitive explanations about the settings would be helpful for readers to understand the implications of all these propositions.
- All the experiments are done on traditional inference problems with relatively toy models. In this case, I would expect sampling to be "easy". For models like deep neural networks, the posterior could be very complicated and I don't think the combination of a fixed and an adaptive reference would be enough.
questions: See some of my comments in the weaknesses section.

Other questions:
- The idea of tunning prior is quite natural and similar ideas have been discussed in Bayesian deep learning. So it is quite surprising to me that it has never been used before in parallel tempering. I'm curious about the authors' thoughts on that.
- The authors mentioned that adding the fixed reference could help avoid the local optima and get a better estimate of the variational reference. However, the adaptive reference is still single-mode regardless. I wonder whether this would be an issue for harder problems.
- Parallel tempering seems to be a promising sampling method, but I haven't seen many applications in the context of deep learning. By contrast, many other algorithms (including HMC and AIS) have been used widely in deep learning. I'm curious about the reasons and I wonder if the authors have tried on Bayesian deep learning problems.

limitations: The authors discussed the limitations in the paper and I don't see any negative societal impact of this work.
review_title: null

Meta-review: metareview: The idea of this paper is to tune the reference distribution for parallel tempering to improve efficiency. The key idea is simple: Assume the reference distribution is in the exponential family and use sufficient statistics. Experimental results show that this typically helps in terms of metrics like effective sample size per iteration, though not necessarily in terms of effective samples per second. There are theoretical guarantees which each rely on a long list of assumptions which are deferred to the appendix. While I realize the limitations of space, I echo the reviewers that more discussion of the assumptions should be included in the paper of which should be considered more minor or major. Still this paper proposes a novel approach that is plausibly useful in at least some settings so I recommend acceptance.

A minor point: The font sizes are poorly chosen, to the point of being unreadable if the paper is printed. I had to resort to zooming into individual figures on the computer to reference which was quite tedious.
confidence: Less certain
Decision: Accept