Exploring Non-Convex Discrete Energy Landscapes: A Langevin-Like Sampler with Replica Exchange

Thank you for your answer. Regarding your response, I may have additional questions:

We gradually increase $\tau_2$ while monitoring the sampler’s ability to escape local minima and explore effectively.

In practice, how do you evaluate this 'ability' of exploration without having access to ground truth samples ? Which metric do you use ?

Swap Intensity is tuned to achieve a swap rate between 5%–20%

Could you explain the origin of this setting for the swap rate ?

About the use of several temperatures in the RE mechanism: the authors seem to claim that using more than two temperatures may need non-trivial adaptation for their algorithm. However, in the case of deterministic even/odd swaps, the swap acceptance (10) would write the same between considered states, and the sampling part would still occur in parallel: where would the difficulty come from ?

While sample-based metrics are commonly used in model evaluation, they often depend on the sample quality. This can introduce biases when the sampling methods fail to converge adequately in high-dimensional spaces or under constrained computational budgets.

I am quite confused about this answer: I don't understand the computational difference between estimating the partition function which requires AIS and directly sampling from the EBM, which seems to require AIS as you suggest below. You seem to suggest that sampling from the EBM may fail; in that case, this would directly question the accuracy of the partition function estimation ?

We run 300,000 iterations of AIS, where each AIS step utilizes DULA to perform 500 sampling iterations.

So you don't use DREAM to sample from the EBM in order to obtain samples after training ? Then, why using DREAM to sample from the EBM when training ?

About the question of using AIS as competing method: sorry if I was not clear in my first question, I'd like to clarify it. I was suggesting the authors to use AIS as a multi-level sampling scheme (ie Sequential Monte Carlo) to compare with RE (since they are often opposed in the continuous setting: sequential vs parallel) : the sampling scheme would proceed exactly the same as done for the EBM evaluation (sequentially, from highest temperature to lowest temperature with DULA steps, while keeping the AIS importance weights to readjust particles). Have you tried to implement it as competitor for RE ? It seems that you have used this method to obtain samples from the EBM at least (see above).

Finally, I'll be happy to increase my score upon the release of a revision that main contain:

• the ablation study on the hyperparameters
• the use of mode collapse / mode weight metrics
• uncertainty errors on numerics (which would be notably meaningful for the EBM experiment)

We appreciate your time and great efforts in reviewing. Please find our responses to the questions below.

The setting of the three main hyperparameters of DREXEL/DREAM (the local Langevin step size, the highest temperature, and the swap intensity) is not discussed anywhere

We outline below the practical guidelines we followed for selecting these key hyperparameters:

• Low-Temperature Sampler:

  • We set $\tau_1 = 1.0$ by default to approximate the unaltered target distribution.
  • For DREAM, $\alpha_1$ was selected to achieve an acceptance rate of approximately 70%–80% in the MH steps to balance stability and sampling efficiency.
  • For DREXEL, $\alpha_1$ was chosen to be smaller than that used in DREAM to ensure stability and guarantee convergence in the absence of MH corrections.

• High-Temperature Sampler:

  • We gradually increase $\tau_2$ while monitoring the sampler’s ability to escape local minima and explore effectively.
  • Larger step sizes $\alpha_2$ are paired with $\tau_2$ to enhance exploratory behavior, with adjustments based on performance in navigating complex energy landscapes.

• Swap Intensity ($\rho$) is tuned to achieve a swap rate between 5%–20%.

No ablation study of the hyperparameters is given anywhere

We acknowledge that our current work includes only a basic ablation study, which is presented in Appendix E.2. We will expand these studies in our future revisions to provide a more detailed analysis of the impact of hyperparameters.

The initialization of the algorithm is not given in each numerical experiment

We summarize the initialization methods employed in our experiments as follows:

• Synthetic 2D Tasks: The starting sample is initialized by uniformly and randomly selecting a position within the 2D grid.
• Ising Models: Initial spin configurations are drawn from a Bernoulli distribution, where the logits are set to $P(\theta_i = +1) \approx 0.6$ and $P(\theta_i = -1) \approx 0.4$.
• RBMs: The sample distribution is initialized using a Bernoulli distribution with equal probabilities for all visible units.
• Deep EBMs: Initial samples are drawn from a Bernoulli distribution parameterized by the empirical mean of the first batch in the dataset.

Why not consider sampling metrics to reflect mode collapse in the 2d synthetic tasks?

We appreciate the reviewer’s insightful suggestion and the reference to relevant work. Integrated probability metrics indeed emphasize a subset of modes, which potentially leads to an underestimation of mode collapse. We will incorporate metrics in our revision that more effectively detect mode collapse and assess the ability of the sampling methods to preserve the true relative weights of the target modes.

The numerical results do not contain error quantifications

We acknowledge that error quantifications were not included for all experiments due to time constraints. We will address this in our revision by reporting error analyses for the results to provide a more robust evaluation.

Have you considered increasing the number of Langevin steps before applying the swap?

We follow the traditional reMCMC framework and typically set the swap rate between 5%-20%, which corresponds to approximately 5-20 Langevin steps between successive swaps.

We appreciate your constructive feedback. Please find our responses below.

The return of Alg. 1 is only $\theta_1$, but Theorem 2 analyze the target distribution affected by $\theta_1$ and $\theta_2$.

We agree that when comparing to DULA, our analysis requires an additional step to explicitly show the convergence of the marginal distribution.

The convergence of the marginal distribution of $\theta_1$ can be trivially bounded by the convergence of the joint distribution of $(\theta_1, \theta_2)$ using the triangle inequality, as the total variation distance between the marginals is directly bounded by that of the joint distributions. We will revise our analysis to clarify this point in our revisions.

Theorem 2 cannot be considered as an approximation of $\pi$ considering its marginal distribution due to the additional factor $\tau_1$.

We want to clarify that $\tau_1$ is typically set to 1.0, which ensures that the low-temperature sampler approximates the unaltered target distribution. When $\tau_1 \neq 1.0$, the sampler produces a biased distribution that deviates from the true target distribution. We appreciate the reviewer’s feedback and will clarify this point in the revision.

The authors should claim the advantages of convergence improvement come from the sampling algorithm rather than the TV gap between joint distribution and marginal distribution

Thank you for the feedback. We agree with this observation and will revise our analysis to emphasize that the convergence improvement arises from the sampling algorithm rather than the TV gap between the joint and marginal distributions.

TV gap cannot be bounded by a small constant $\epsilon$ in Theorem 2.

We thank the reviewer for the feedback on our theoretical analysis. We acknowledge that Theorem 2 may be suboptimal. We will improve the theoretical part in future revisions.

The convergence improvement in the analysis is extremely limited.

We acknowledge the reviewer’s concern regarding the improvement in analysis. We want to clarify that investigating the quantitative value of the spectral gap for replica exchange Langevin algorithms remains a fundamental challenge in this field. Recent work [1] demonstrated the potential for improving the spectral gap in continuous settings when employing replica exchange Langevin diffusion compared to vanilla Langevin diffusion. We anticipate that a similar acceleration effect would extend to discrete settings.

Given the methodological focus of this paper, our primary goal is to bridge practical design principles with theoretical insights for discrete samplers. A comprehensive exploration of spectral gap quantification and its improvement in discrete settings is indeed an exciting direction for future research, which we plan to investigate further.

Determining the scaling of different temperatures is difficult. Could authors give some suggestions for tuning the hyperparameters?

For low-temperature sampler:

• We set $\tau_1 = 1.0$ to sample from the unaltered target distribution.
• For DREAM, the step size $\alpha_1$ was chosen to guarantee around 70%-80% accept rate in MH steps.
• For DREXEL, $\alpha_1$ should be smaller than that used for DREAM to maintain stability and ensure convergence.

For high-temperature sampler:

• Larger values of $\tau_2$ and $\alpha_2$ generally enhance the exploration capabilities.
• We gradually increase $\tau_2$ and $\alpha_2$ while monitoring the sampler's ability to effectively explore the energy landscape.

Could authors discuss and compare the method to consider decreasing step sizes in Langevin dynamics?

In continuous distributions, annealing step sizes in Langevin Monte Carlo is a well-established strategy to ensure convergence to equilibrium. However, this approach is less effective when sampling from discrete distributions due to the intrinsic discontinuities of the space. As the step size decreases, the sampler's ability to traverse between discontinuous states diminishes and it is easy to get trapped in local regions.

To address this, the common approach adopts a larger, fixed step size to facilitate broader exploration and avoid local traps. This is particularly important for navigating highly non-convex discrete energy landscapes.

References

[1] Spectral gap of replica exchange langevin diffusion on mixture distributions. Stochastic Processes and their Applications 2022.

We thank you for your constructive review. Please see our responses below.

The theoretical results are not very strong.

Investigating the quantitative value of the spectral gap for replica exchange Langevin algorithms is indeed a fundamental challenge in the field. Recent work [1] has demonstrated a potential enhancement of the spectral gap in continuous settings when employing replica exchange Langevin diffusion compared to vanilla Langevin diffusion. We anticipate a similar acceleration effect in discrete settings.

Note the current work focuses on the design and implementation of samplers specific to discrete spaces to enhance exploration, we propose this work to bridge practical design with theoretical insights. A deeper exploration of spectral gap quantification in discrete settings is an exciting direction for our future work.

Theorem 1 does not provide a non-asymptotic approximation error.

To clarify, the non-asymptotic approximation error analysis is provided in Theorem 2, which demonstrates the required number of iterations for the empirical distribution to converge to the target distribution under specified error bounds.

The asymptotic analysis in Theorem 1 plays a crucial role in designing the swap function in Eq. (10). This swap function ensures detailed balance and promotes efficient exploration, which is foundational to achieving the mixing improvements analyzed in Theorem 2.

Do multiscale chains perform better (empirically) when more levels to this scale are added?

Empirical evidence from prior works in continuous settings [2, 3] suggests that applying multiple temperature levels in replica exchange Langevin methods can significantly enhance performance, particularly when sampling from multi-modal distributions. This approach is also promising in discrete settings, where multi-scale exploration could address the challenges posed by highly non-convex landscapes.

However, such an effective technique may not directly translate to discrete scenarios. For instance, window-wise corrections in the swap function [2] may require adjustment for discrete sampling, and the efficacy of previously employed swap schemes (stochastic or deterministic even-odd strategies) remains unclear in discrete domains and warrants further investigation.

We recognize that extending multiscale methods to discrete settings involves non-trivial challenges. Exploring the potential benefits and adaptations of these techniques will be a promising direction in our future work.

How many times are the proposals typically rejected in practice? Does this affect the optimal step-size scaling compared to the other algorithms?

The rejection rates are problem-dependent and vary significantly based on the complexity of the energy landscape. For simple tasks, we observed that rejection rates of 30–50% resulted in good performance. This aligns with findings in prior work [4] but does not fully showcase the potential advantages of DREAM.

For non-convex energy landscapes, such as those encountered in training Deep EBMs, the rejection rates differed markedly between the two chains. Specifically, a 20%-30% rejection rate for the low-temperature chain and 70–90% for the high-temperature chain yielded great performance. These settings reflect the need for more exploratory behavior in the high-temperature chain to overcome local traps, while the low-temperature chain focuses on detailed exploitation.

We appreciate your thoughtful review. Please find our responses to the questions below.

The new approach simply combines existing ideas (DLS and reMCMC)

While the approach builds upon DLS and reMCMC, this work addresses unique challenges in discrete settings.

Existing reMCMC methods rely on decaying step sizes to ensure asymptotic convergence. However, this strategy is practically unsuitable for discrete spaces, particularly in high-dimensional, non-convex discrete landscapes, as discussed in Section 4.2. To address these limitations, we propose a novel swap function (Eq. (10)) specifically designed for discrete sampling. This swap function not only maintains detailed balance but also enables robust exploration across challenging discrete energy landscapes.

Our contributions go beyond a simple integration of existing ideas. By addressing the fundamental incompatibilities of reMCMC with discrete sampling, we advance both the theoretical and practical capabilities of sampling methods, as supported by our theoretical analysis (Section 5) and experimental results (Section 6).

What is the dependence of log RMSE on temperature $\tau$ in Ising model results (Fig. 3)? Are the conclusions of Fig. 3 the same for a lower target distribution temperature (e.g., $\tau=0.1$)?

In our Ising model experiments, the temperatures are typically set to $\tau_1 = 1.0$ and $\tau_2 = 5.0$ for DREXEL and DREAM. At $\tau_1 = 1.0$, the low-temperature sampler draws from an unaltered target distribution in Eq. (1). If $\tau_1 \neq 1.0$, the sampler will produce a biased distribution that deviates from the target distribution, which leads to incorrect sampling results unless a proper rescaling or correction is applied.

When the target temperature is reduced to $\tau = 0.1$, the distribution in Eq. (1) becomes much sharper and more concentrated around the mode. This increased sharpness significantly reduces the sampler's ability to explore the broader energy landscape, making it more prone to getting trapped in local minima. Consequently, it will impair the conclusions drawn in Fig. 3, as the sampler's efficiency in navigating the energy landscape would be diminished.

Compared to the Ising model, what if we consider other spin connectivity exhibiting more frustration (e.g. fully connected Sherrington-Kirkpatrick problems)?

The Sherrington-Kirkpatrick (SK) model is an ideal benchmark to demonstrate the strengths of DREXEL and DREAM due to its fully connected structure and highly frustrated energy landscape. Its rugged landscape with exponentially many local minima requires efficient exploration and avoidance of local traps. DREXEL and DREAM are specifically designed to tackle such complexity, which makes them well-suited for problems like the SK model and aligns with their goal of enhancing exploration in discrete spaces. We appreciate the reviewer’s suggestion and will consider it as a benchmark in our revision.

How are temperatures and step sizes chosen in each approach?

For temperatures, we set $\tau_1 = 1.0$ to sample from the unaltered target distribution. The choice of $\tau_2$ depends on the complexity of the problem. Specifically:

• For simpler landscapes with fewer local minima, $\tau_2$ can be set slightly larger than $\tau_1$ (e.g., $\tau_2 = 2.0$).
• For more complex landscapes with multiple local minima, $\tau_2$ should be significantly larger than $\tau_1$ (e.g., $\tau_2 = 5.0$ or $10.0$) to enhance exploration and avoid local traps.

For step sizes, the low-temperature step size ($\alpha_1$) in DREXEL and DREAM is set similar to those used in DULA and DMALA to focus on exploring local modes. The high-temperature step size ($\alpha_2$) is larger than $\alpha_1$ to facilitate a broader exploration of the energy landscape. Both step sizes are tuned based on the problem's energy landscape to achieve an effective balance between local exploitation and global exploration.