Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the communicational complexity of parallel tempering. One example of parallel tempering is when one uses Langevin dynamics with different temperatures to balance exploit and exploration for sampling from a multi-modal distribution. The balance is made by swapping running particles with different temperatures according to a particular schedule. The round trip time (RTT) is a computational complexity metric for measure for the swapping schedule.  It is known that the best-known algorithm suffers from $O(P^2)$ RTT for $P$ parallel particles. By adjusting this algorithm, the authors improve the RTT to $O(P\log(P))$. Then, they demonstrate the application of nonconvex with stochastic gradient descent. 
main_review: **Pros** 
1. The contribution is very concrete
2. $O(P)$ improvement is significant 
3. The proposed algorithm is based on a slight modification of an existing algorithm 
4. The paper is very well written 
5. The proof is quite straight words
6. Literature is well-reviewed in section 2.  
**My concerns**
1.  Is possible to modify the rejection probability in DEO to get the same rounding time (for example use the rejection $O(r^{\log(p)})$? 
2. I could not understand why the paper focuses on the gradient Langevin dynamics. Is it possible to use a different sampling algorithm? 
3. The notion of optimality is rather confusing in the abstract. Is it possible to show that it is not possible to get a communication cost lower than $O(P\log(P))$? I think that the optimality is about the optimal window size for the adjusted DEO. 
4. I wondered whether authors use the real SGD algorithm or they use gradient descent + a Gaussian noise? 
5. The transition from the main result to applications for SGD can be more detailed and more clear. This application can be motivated more and explain why this particular case of parallel tempering is studied in the paper. The difference between SGD and Euler's discretization of Langevin dynamics can be explained in more detail. 
6. I recommend presenting experimental validations for Thm. 1 after this Thm. before talking about SGD. 
summary_of_the_review: I liked the contribution and narrative of this paper, and my opinion about the result is rather positive.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The manuscript considers parallel tempering for sampling from multi-modal distributions. The choice of the swap scheme can great impact the performance of parallel tempering algorithms. The authors propose a modification of the existing deterministic even-odd (DEO) swap scheme. Theoretical results are established which show the proposed scheme improves communication cost from O(P^2) to O(P*logP) for P chains. Simulation studies are performed on a stylised multimodal distribution and on CIFAR100 datasets showing empirical improvements.  
main_review: I thank the authors for their article, which addresses the important topic of choice of swap schemes in parallel tempering. They build upon the current deterministic even-odd (DEO) swap scheme and develop modifications and generalisations which have more favourable theoretical and empirical performance. 

Originality: The authors propose a generalisation of the existing DEO swap scheme. The details of their theoretical analysis and their methodological contributions are original and significant. Their investigation of stochastic approximations for big data, optimal number of chains, analysis of round trip time are detailed and through. 

Clarity: The article is clearly written, even for readers who are less familiar with the swap schemes for parallel tempering. 

I have minor comments about the paper. They are:
1) The approximation analysis theorem (theorem 2) assumes uniform ergodicity, which is stronger than “geometric ergodicity” as currently stated. Secondly, note that the bound given for theorem 2 is vacuous if (1-\rho)<\Delta. Some discussion of this point (that we require small \delta and \rho much less than 1 for the given upper bound \Delta/(1-\rho) to be useful) would be helpful.

2) There should be some discussion about the choice of W (or target swap rate S) in practice, what algorithms/ heuristics are recommended when choosing the parameter W, and what additional computational cost this incurs. For example, at the moment the optimal window size is given as a function of the number of chains and the target swap rate- but how is the target swap rate chosen? I could be misunderstanding something here.

3) If possible, the authors could present a version of Cor 1 which does not assume that the optimal W is chosen, but a generic W. Alternatively, some discussion about the importance of the choice of W should be included. 
summary_of_the_review: This manuscript proposes new swap schemes for parallel tempering. The methodology is supported by theoretical analysis, detailed discussion of methodological details and simulations. It will be of interest to the ICLR community.


EDIT: Having read the review of "mbau" and the corresponding discussion, I agree with the reviewer that the DEO* scheme may not converge to the target distribution of interest. I also agree the current argument in Section C.2 needs to be made more rigorous. Based on this point, I am inclined to revise my initial review score for the paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes generalized DEO scheme (DEO*) that extends DEO with a window where at most one exchange could happen within one window. This paper also extend existing analysis on expected round trip time into DEO* and authors show that O(P logP) expected round trip time could be achieved even for finite number of chains and non-diminishing rejection rate. This paper also proposes multiple approximation to make DEO* practical: The exploration chains substitute gaussian noise with gradient noise, where noise magnitude is controlled with step size. Deterministic swap condition is used to avoid specific temperature. Adaptive learning rates and adaptive correction buffers are adopted to tune acceptance rate. The authors evaluate DEO* on ResNet model over CIFAR100.
main_review: 1. The generalized DEO scheme is interesting and the O(P logP) expected round trip time for finite number of chains and non-diminishing rejection rate is novel. However, DEO* doesn't converge to the target distribution. The following example constitutes a counterexample of soundness of DEO*.

Consider an energy function $f(x) = 8 x^2$ on the domain $[-1,1]$. We construct only two chains with temperatures $T_1=1$, $T_2=\infty$. Two posterior should be $p_1$ as a truncated Gaussian distribution highly concentrated around origin, $p_2$ be a uniform distribution. Let local exploration kernel to be identity (e.g. SGLD with $0$ step size). Let window size to be large enough, such that swap will happens in one window with high probability. Initialize two chains with target distributions $p_1$ and $p_2$, then run DEO* with one even window and one odd window. The output distribution is no longer $p_1$ and $p_2$.

2. This paper is clear until section 4 where DEO*-SGD method is proposed. Although practical, DEO*-SGD contains multiple approximations that require careful investigation:
+ a. While using SGD as approximated local exploration kernel in (6), it seems only gradient noise is considered. However, discretization error is another source of noise. More specifically, for Langevin dynamics $d\beta_t = -\nabla U(\beta_t) + \sqrt{2} dW_t$, the discretization error for Euler discretization is $\int_0^\eta \nabla U(\beta_t) dt-\eta\nabla U(\beta_k)$. How does this discretization error affect the distribution and temperature?
+ b. on second line at page 5, the authors state that "$\beta_k$ converges approximately to an invariant distribution, where the underlying temperature linearly depends on the learning rate $\eta$". What is this invariant distribution? Does different step size induce different invariant distribution?
+ c. With update rule in (12), can we ensure that $\eta^{(p)}$ are always ordered?

3. The experiments also need to be amended.
+ a. Important baseline (E.g. Deep Ensemble) is missing. 
+ b. No uncertainty approximation quality (e.g. expected calibration error) is reported.
+ c. Figure 7.c has incorrect y-axis value.
+ d. experiment code for CIFAR100 experiment is not provided.
summary_of_the_review: The proposed method does reduce expected round trip time but fails to converge. The practical method is not well understood and experiments need to be amended.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers sampling multi-modal distributions by the powerful parallel tempering methodology. An existing exchange scheme, DEO (deterministic even-odd), is improved by generalizing even and odd chain indices to even and odd windows of width W. Some nontrivial theoretical and empirical results are provided.
main_review: The idea considered is very interesting and it demonstrates a lot of promises. The theoretical components seem to be strong too. I’ll be happy to be corrected and increase my rating, but I’d love to see more integration of various theoretical components, as well as how their implications get reflected in the empirical results. For example:
* Is there any theoretical guide on the choice of $a$? By the way, what is the relation between $a$ and $\mathbb{S}$?
* If I understood correctly, Theorem 2 is just for one chain, not all the $P$ chains. When there are $P>1$ chains, don't errors add up? How does that scale with $P$?
* How can Theorem 1 and Theorem 2 be combined to produce a theoretical guarantee of the final algorithm? It will be great if notions built around `round trip’ get translated into final iteration complexity.
* Can wall clock counts be added to the experiments? Since improved efficiency seems to be a key contribution, it is a little odd to only show improved accuracy.
* Can results for various W values be compared in the experiments, so that the theoretically optimal value could be justified?
* Reading `We choose ResNet20, ResNet32, and ResNet56 (He et al., 2016) and train the models on CIFAR100.’ can I assume Bayesian neural network is used based on these architectures? What is the prior?

summary_of_the_review: This is a very interesting paper. Since the treatment is rather nontrivial and I feel it deserves appreciation, I’d like to see just a little more about how different theoretical and empirical ingredients of this work mesh together.
review_title: null

Meta-review: This paper proposes the algorithm which they call DEO*-SGD, which is a combination of the ideas of the generalized DEO scheme, denoted by DEO*, to facilitate exploration (Section 3.1), adoption of stochastic gradient descent (SGD) in the exploration chains (i.e., those chains except the one with the lowest temperature) (Section 4), and use of adaptive tuning of learning rates (Section 4.2). The proposal is applied experimentally in Section 5 to demonstrate superiority of the proposal over existing approaches.

The initial review scores of the four reviewers were one positive and three negatives. Most reviewers positively evaluated the proposal, including the proposal of DEO* and its theoretical analysis, as well as its empirical usefulness in deep learning for a computer-vision task. On the other hand, some reviewers showed concern about soundness of the proposal. Upon reading the reviews and the author responses, as well as the paper itself, I think that this paper lacks a clear statement on its objective.

* **What does "uncertainty approximation" mean?:** The paper title would imply that the objective of the proposal in this paper is for "uncertainty approximation," but I could not find any concrete description on what it exactly is.
* **Sampling versus optimization:** The methods of Langevin dynamics, or more generally Markov-chain Monte-Carlo methods, have been used for two distinct purposes: sampling and optimization. In any case fast relaxation towards equilibrium would be of practical importance. For sampling purposes it is also important to assure that the stationary distribution of the Markov chain corresponds to the target distribution (In Langevin dynamics the target distribution would be the canonical ensemble defined by the energy $U(\cdot)$ and the temperature $\tau$). For optimization purposes, however, the assurance of the stationary distribution to be equal to the target distribution would be less of concern. It seems that the authors' interest would be in optimization rather than in sampling, but it is not clearly stated.
* **Soundness issue:** As Reviewer mbau pointed out, DEO* does not have a guarantee of convergence to the target distribution. I thought that if the objective of this paper would be in optimization rather than in sampling, the existence of approximation already in DEO* might be thought of as a minor problem, as the proposal already has other approximations introduced in Section 4. The authors claim that this problem does not affect the main body of the paper, but I feel that it would affect the overall organization of the paper, as the current organization seems to presume that approximation only resides in the adoption of the SGD-based exploration kernels with deterministic swap. In any case, this problem has been acknowledged by the authors themselves, as well as Reviewer ofJx.

In particular, the detailed discussion between the authors and Reviewer mbau has been very fruitful in clarifying technical subtleties in this manuscript, including the soundness issue mentioned above. At the same time, it would imply that this paper still has room for improvement.

An additional point I would like to mention is that this paper is not really self-contained, in the sense that several key notions and quantities are not defined or only defined in the Supplementary Materials ($\tilde{U}$ is not explicitly defined at all, the terms "swap time" and "round trip time" are defined in Appendix A.5, $\sigma_p$ in Corollary 1 and Lemma 2 is defined in Appendix A.1). 

All these weaknesses make me to think that another round of revision would be appropriate to properly judge the quality of this paper, whereas there is no such option within the review procedure of ICLR. I therefore cannot recommend acceptance of this paper at least in its current form.

Minor points (page and line numbers refer to the revised version):
- Abstract, line 5: "given sufficient many $P$ chains" would be better phrased as "given $P$ chains", as the big-O notation usually assumes the large-P asymptotic.
- In several places, there are periods after "Figure" and "Table", which are not needed.
- Page 3, line 32: In Lemma 2 there is apparently no such term found as "the second quadratic term". It should appear only after having assumed the equi-acceptance/rejection rates in equation (4), so that the sum becomes proportional to $P$.
- Theorem 1: "the maximal round trip time" should certainly be "the minimal round trip time". / is the ceiling function(. T -> , t)he round trip time
- Table 1: I did not really understand what "non-asymptotic" / "asymptotic" mean, as the big-O notation used here should by definition be asymptotic.
- Corollary 1: the optimal (number of) chains
- Page 4, line 34: The abbreviation SGLD is not defined in this paper.
- Page 4, line 36: similar(ly) to
- Equation (6): The sign of the last term should be "-".
Decision: Reject