Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an MCMC algorithm containing two key ideas: the approximation of the target density with a simpler function (proposed by [Deng, 2020]) and the parallel simulation of many chains that allow for better capturing the global properties of the target density. To be more precise, the main contribution of the paper is the extension of the algorithm by [Deng, 2020] to the case of multiple chains. 

The proposed extension goes as follows. The original algorithm by [Deng, 2020] approximates the target density with piecewise continuous functions using the level sets (slicing the values of the energy function). These functions are parameterized by vector $\theta$, which needs to be defined. In practice, $\theta$ is estimated using the samples from the chain. The current paper then proposes to run many chains in parallel and use all of the available samples for the estimation.

The efficiency of the proposed technique is analyzed both theoretically and empirically. For theoretical analysis, the authors provide convergence speed and asymptotic distribution of the residuals $\theta - \theta^*$. Overall, the analysis favors the proposed method over the original algorithm. The empirical comparison is made on several tasks. Except for the toy task, the authors consider learning policy for contextual bandit problem and sampling from the posterior distribution of a neural network.

[Deng, 2020]: Deng, Wei, Guang Lin, and Faming Liang. "A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions." arXiv preprint arXiv:2010.09800 (2020).
main_review: My main concern is the clarity of the paper. At some points, the paper looks like a riddle where you are looking for some notation and definitions. Some points of the exposition lack intuition. 
- The choice of the piecewise continuous approximation of the target density and the function H is not apparent at all. I would suggest sharing a piece of intuition with the reader to motivate the usage of these functions early on. The clarity is also hardened by the fact that the original paper by [Deng, 2020] also doesn't provide any intuition for the choice.
- The proposed algorithm is presented in the background section together with the algorithm by [Deng, 2020]. It would be much easier for the reader if the authors would highlight the difference between the original algorithm and its modification. For instance, they could say that the main difference between algorithms is in the estimation of parameters $\theta$ and using all of the samples instead of a single chain or even highlight it explicitly in the formulas by using a different color.
- Pictures in Figure 1 are not informative. The pictures depict different aspects of interacting chains algorithms. Fig. 1a represents the jumps in the state space, and Fig. 1b represents the mutual update of parameters. The authors use Fig. 1b as a motivation for better mixing properties, claiming that unlike the replica-exchange method their algorithm shares "messages" between samples at every step. However, one can argue that the replica-exchange method also shares information between samples at every step by running the accept/reject test trying to swap the samples.

Another major issue is that the authors do not compare their algorithm against CSGLD (algorithm by [Deng, 2020]) in one of the main experiments: Bayesian networks on CIFAR-100 and SVHN. Due to the close relations between algorithms, such kind of comparison is essential for the performed empirical study.

summary_of_the_review: This submission is a follow-up to [Deng, 2020] that extends the previous work to the case of multiple parallel chains. Although the extension seems quite straightforward, the authors provide a theoretical analysis of the proposed scheme and perform its empirical study. The main issues are the clarity of the exposition and one inconsistency in the experimental section.

[Deng, 2020]: Deng, Wei, Guang Lin, and Faming Liang. "A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions." arXiv preprint arXiv:2010.09800 (2020).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the problem of sampling from distributions with complex energy landscapes. The authors propose an extension of the contour Stochastic Gradient Langevin dynamics (CSGLD) sampler to efficiently simulate from big-data distributions. The extension is called “interacting” since $P$ different CSGLD are updated simultaneously and the random-field function is obtained as a Monte-Carlo average over the random field functions of these multiple chains run in parallel. This procedure allows to reduce the variance of the self-adapting parameter $\theta$ improving the marginal energy likelihood estimate, and is well-suited for distributed computing. The different chains only share the low-dimensional vector $\theta$ and do not share the model parameters, that are typically high dimensional. The authors prove that the proposed algorithm is asymptotically more efficient than its single-chain counterpart with the same computational budget. This theorem holds for a step size that decreases polynomially in time. Finally, they compare their algorithm to alternative methods on different tasks (e.g., mode exploration on MNIST dataset, uncertainty estimation) achieving competitive performances. 
main_review: I liked reading the paper. Overall, the work addresses a relevant problem and provides a nice introduction to previously existing solutions. 

In my opinion, the contributions are significant and the proposed algorithm is presented in a clear way. The analysis is sound and backed up by numerical evidence in different settings. I believe that the paper is worth publication. 

However, I have some minor questions that require a clarification from the authors.

(i) I do not understand how the parameter $\zeta$ is tuned in practice and I would like to have more details on this procedure in addition to the comments provided in appendix B.1.3. This point seems to play an important role, e.g., in escaping from local regions of the landscape in Figure 2, while Appendix D.1 only says that $\zeta$ is fixed to $3e4$. Since in the other cases (appendix D.2, D.3) $\eta$ is fixed to much smaller values (namely, $0.75$ and $20$) I would like to have more intuition on this.

(ii) I would like to have some clarifications on the link between the second footnote on page 7 and the sentence it refers to.
summary_of_the_review: I believe that the paper is worth of publication since it presents an efficient importance sampling method that scales to big data problems and possibly leads to additional future investigations.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper samples from distributions with complex energy landscapes by the powerful contour stochastic gradient Langevin dynamics (CSGLD) methods. In order to reduce the variance of random-field function, this paper proposes a simple but effective method, that combines  random-field functions from multiple chains. Since the parameter $\theta$ typically has small size, the communication overhead is marginal. This paper show that compared to CSGLD which only has one chain, the variance ICSGLD with P chains and same computation budget is asymptotically more efficient. The authors evaluate ICSGLD with multiple experiments.
main_review: The idea of Monte Carlo average of random-field functions from multiple chains in this paper is straightforward and easy to implement. The theoretical analysis seem to be solid too. However, I anticipate more discussion on the connection between empirical results and theoretical implications:
+ The analysis proves that ICSGLD improves estimation accuracy of parameter $\theta$ with non-infinitesimal step size. However, does parameter $\theta$ have any geometric interpretation (e.g. density of states)? Can we visualize the $\theta$ learned from ICSGLD and CSGLD? Can we empirically verify that the estimated variance is reduced?
+ Could the authors compare ICSGLD with different number of chains to further justify the theoretically result?
+ What are the main factors affecting the target $\theta_\ast$? Is it sensitive to model structure / model size / dataset ?
+ Is there any theoretical guide on the choice of hyper parameters e.g. $\zeta$? The first experiment uses $\zeta = 3e4$ and last experiment uses $\zeta = 3\times 10^6$. These values are significantly larger than other two experiments where $\zeta = 0.75$ and $\zeta = 20$.
How these parameters are selected in different experiments?
+ What is the recommended $\Delta u$ for neural network? What are the pros and cons for choosing small $\Delta u$?
+ What is the definition of preconditioned CSGLD and preconditioned ICSGLD? In section 5.3, authors cite [Deng et al., 2020b] for preconditioned CSGLD. However, it seems this paper doesn't contain preconditioned version of CSGLD.

Others:
+ How KL divergence is estimated in Figure 6?
+ It will be appreciated if the code is provided for reproduction.

summary_of_the_review: This paper proposes an interesting extension to CSGLD whose advantages are shown both theoretically and empirically. However, I believe many questions deserve further investigation before applying ICSGLD into practical machine learning. I would like to hear authors' response on how theoretical implications are connected to practical concerns.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposed an interacting contour stochastic gradient Langevin dynamics that extends the contour stochastic gradient Langevin dynamics with efficient interactions in Deng et al. (2020). They obtain asymptotic normality as well as show that this proposed algorithm can be more efficient than  the contour stochastic gradient Langevin dynamics with efficient interactions. The theoretical results are complemented by the numerical experiments.
main_review: The strength of the paper is that it proposes a new algorithm interacting contour stochastic gradient Langevin dynamics that can be shown theoretically more efficient than contour stochastic gradient Langevin dynamics. The paper is well written, and it has both theoretical justification and numerical support. 

The weakness of the paper is that many results seem to be adapted from Deng et al. (2020) for the contour stochastic gradient Langevin dynamics. Even though, a new algorithm is proposed, it should be considered as an extension to the previous work Deng et al. (2020), and some similar theoretical estimates can be found in Deng et al. (2020) and the technical novelty is not clear. 
summary_of_the_review: (1) Page 2. For ICSGLD and CSGLD, I have one naive question. You are sampling (2) with a flattened density compared to the original Gibbs distribution $\pi$. If you are sampling a modified distribution instead, do you need to show that the new target distribution is close to the original distribution?

(2) Page 2. I am a bit confused with the notation here. In equation (2), you have $\Psi^{\zeta}_{\theta}(U(x))$ and then in the bottom of page 2, you have $\tilde{U}_{\Psi_{\theta_{k}}}$. What's the relation between these two different notations?

(3) Page 3. In your Algorithm 1, there is a stochastic approximation step for $\theta_{k}$. In your Assumption A2 in the appendix, you assume that the space $\Theta$ is compact. How do you guarantee your $\theta_{k}$ lives in a compact space since you are doing $k\rightarrow\infty$ analysis.

(4) Your Theorem 1 and Corollary 1 for the asymptotic normality is nice. But do you have a result saying that $x_{k}$ will converge to the Gibbs distribution corresponding to $\theta_{\star}$ or something like that, e.g. ergodic mean etc.?

(5) Lemma 2 (Lemma 7) is very similar to the result for CSGLD (Theorem 1, Deng et al. (2020).) What's the technical novelty here?
review_title: null

Meta-review: This paper proposes a new variant of a stochastic gradient Langevin dynamics sampler that relies on two key ideas: approximation of the target density with a simpler function (as in [Deng, 2020]) and the parallel simulation of many chains. The authors also prove that their approach can be theoretically more efficient than a single-chain algorithm.

The reviewers see the contribution as significant although they did raise some concerns regarding the clarity of the paper. Since these concerns do not appear to be major, I recommend acceptance but I advise the authors to address the comments of the reviewers to maximize the impact of the paper.
Decision: Accept (Poster)