Gradient-based Discrete Sampling with Automatic Cyclical Scheduling
Authors: Patrick Pynadath
Riddhiman Bhattacharya
ARUN NARAYANAN HARIHARAN
Ruqi Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: MCMC
Discrete Spaces
Sampling
EBM
Primary area: probabilistic_methods
TL;DR: We improve gradient based discrete sampling by adding cyclical schedules and automated hyperparameter tuning algorithm

Abstract: Discrete distributions, particularly in high-dimensional deep models, are often highly multimodal due to inherent discontinuities. While gradient-based discrete sampling has proven effective, it is susceptible to becoming trapped in local modes due to the gradient information. To tackle this challenge, we propose an automatic cyclical scheduling, designed for efficient and accurate sampling in multimodal discrete distributions. Our method contains three key components: (1) a cyclical step size schedule where large steps discover new modes and small steps exploit each mode; (2) a cyclical balancing schedule, ensuring "balanced" proposals for given step sizes and high efficiency of the Markov chain; and (3) an automatic tuning scheme for adjusting the hyperparameters in the cyclical schedules, allowing adaptability across diverse datasets with minimal tuning.  We prove the non-asymptotic convergence and inference guarantee for our method in general discrete distributions. Extensive experiments demonstrate the superiority of our method in sampling complex multimodal discrete distributions.

Gradient-based Discrete Sampling with Automatic Cyclical Scheduling
Patrick Pynadath
Riddhiman Bhattacharya Department of Management Purdue University
Department of Computer Science
Purdue University
West Lafayette, IN, 47907
West Lafayette, IN, 47907 bhatta76@purduue. edu
ppynadat(purrue. edu. edu
Arun Hariharan
Rugi Zhang
Department of Computer Science
Department of Computer Science
Purdue University
Purdue University
West Lafayette, IN, 47907
West Lafayette, IN, 47907 ruqizêpurdue edu
harihar40purdue edu
Abstract
Discrete distributions, particularly in high-dimensional deep models, are often highly multimodal due to inherent discontinuities. While gradient-based discrete sampling proven effective, it is susceptible to becoming trapped local modes due to the gradient information. To tackle this challenge, we propose an automatic cyclical scheduling, designed for efficient and accurate sampling multimodal discrete distributions. Our method contains three key components: (1) cyclical step size schedule where large steps discover new modes and small steps exploit each mode; (2) cyclical balancing schedule, ensuring "balanced" proposals for given step sizes and high efficiency the Markov chain; and (3) an automatic tuning scheme for adjusting the hyperparameters in the cyclical schedules, al- lowing adaptability across diverse datasets with minimal tuning. We prove the non-asymptotic convergence and inference guarantee for method in general discrete distributions. Extensive experiments demonstrate the superiority of our method in sampling complex multimodal discrete distributions.
Introduction
Discrete variables common in many machine learning problems, highlighting the crucial need for efficient discrete samplers. Recent advances [Grathwohl et al. 2021 Zhang et al., 2022b Sun Xiang al. 2023 have leveraged gradient information in discrete distributions to improve proposal distributions, significantly boosting their efficiency. These advancements have set benchmarks in discrete sampling tasks across graphical models, energy- based models, and combinatorial optimization [Goshvadi et al. 2023].
al. 2021 2023bla
However, one major limitation of gradient- -baed methods is their susceptibility to becoming trapped in local modes [Ruder] 2016 Ziyin et al., 2021], which significantly reduces the accuracy and efficiency of sampling results. In continuous spaces, several strategies such cyclical step sizes [Zhang et al.) 2020), parallel tempering [Swendsen and Wang 1986 Deng et al. 2020aa,, and flat histograms [Berg and Neuhaus 1991 Deng al. 22220], J have been proposed to address this issue. When it comes to discrete distributions, which are inherently more multimodal due to their discontinuous nature, the problem becomes gradient-based discrete samplers to effectively explore multimodal distributions. Current methods
severe. Despite the pressing need, there is a lack of methodology for
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(a) Ground Truth
(b)
(c) DMALA
(d) AB
(e) ACS (Ours)
Figure I: Sampling 2d distribution with multiple modes. (a): ground truth. (b): results from
a random walk sampler. (c): results from DMALA Zhang et al.) 2022b] with a manually tuned method ACS. While the
step size. (d): results from AB (Sun al. 2023a (e): results from random walk sampler can find all modes, its characterization is noisy and lacks details for each mode, Gradient-based samplers (b) and (c) effectively characterize a specific mode but are easily trapped in some local modes. Our method (d) can find all modes efficiently and characterize each mode accurately.
often fall far short in traversing the complex landscapes of multimodal distributions, as illustrated in Figure [
In this paper, we propose automatic cyclical scheduling for gradient-basee based discrete sampling to efficiently and accurately sample from multimodal distributions. To balance between uncovering new modes and characterizing the current mode, we parameterize family of gradient-based proposals that span spectrum from local global proposals. The parameterized proposal dynamically adjusts according to cyclical schedules of both step size and the balancing parameter, smoothly transitioning from global exploratory moves to more localized moves within each cycle. These cyclical schedules are automatically tuned by a specially designed algorithm, which identifies optimal step sizes and balancing parameters for discrete distributions. Our contributions are summarized as follows:
We present the first gradient-based discrete sampling method that targets multimodal dis- tributions. Our method incorporates cyclical schedules for both step size and balancing parameter to facilitate the exploration and exploitation in discrete distributions.
We propose an automatic tuning algorithm configure the cyclical schedule, enabling effort- less and customized adjustments across various datasets without much manual intervention.
We offer non- asymptotic convergence and inference guarantees for our method in general discrete distributions. To our knowledge, this is the first non- non-asymptotic convergence bound of gradient-based discrete sampling to the target distribution with inference guarantees, which could be of independent interest.
We demonstrate the superiority of our method for both sampling and learning tasks including restricted Boltzmann machines, deep mnrgy-bbsed models, and large language models.
2 Related Work
introduced a family of locally informed pro- posals, laying the foundation for recent developments in efficient discrete sampling. Building upon this, Grathwohl et al. [021 further incorporates gradient approximation, significantly reducing computational costs. Following these pioneering efforts, numerous studies have proposed various
Gradient-based Discrete Sampling Zanella 2017
gradient-based discrete sampling techniques [Rhodes and Gutmann] 2022 [Sun et al. 2021 2022
20236 Xiang et al. 2023). Zhang et al. [022b) develops discrete Langevin proposal, translating the powerful Langevin algorithm discrete spaces. [Sansone] [2022] introduces a self-balancing method to optimize the balancing functions in locally balanced proposals. While our work also utilizes an adaptive phase, it differs in that our parameterization extends beyond the local regime, and
our proposal parameterization is considerably simpler.
Perhaps the most closely related study is the any-scale balanced sampler [Sun et al. 2023a This method uses a non-local balancing proposal and adaptively tunes Our work, however, differs in several key aspects: (1) We focus on combining both local and non-local proposals to effectively characterize multimodal discrete distributions, as opposed to focusing on a single optimal proposal. (2) Our automatic tuning algorithm adjusts the step size and balancing parameter by considering

---

the special discrete structures and targets specific Metropolis- Hettopolis-Haatingss acceptance rate, rather than maximizing the average coordinates changed per step. (3) Our method can be applied learning energy-based models (EBM) and sampling large language models, whereas their approach cannot.
Sampling on Multimodal Distributions There exist several sampling methods targeting discrete multimodal distributions, such simulated tempering [Marinari and Parisi. 1992). the Swendsen- Wang algorithm [Swendsen and Wang 1987]. and the Wolff al algorithm [Wolfi, 1989.. However, these methods usually use random walk or Gibbs sampling as their proposals. It is unclear how these methods can be adapted for gradient-basee discrete sampling.
In continuous spaces, various gradient-based methods have been developed specifically for multi- modal distributions [Zhang et al., 2020 Deng et al.) 2020a|b). Our method distinguishes from the additional cyclical balancing parameter schedule and an automatic tuning scheme, which are crucial for efficient exploration in discrete distributions. Furthermore, our theoretical analysis of convergence is different from that in Zhang et al. 2020) which relies on continuous stochastic processes.
eyclical step size in ZZang al. 2020 by incorporating
3 Preliminaries
3.1 Problem Definition
We consider the task of sampling from some target distribution defined over discrete space
π (0) Z (xp() O
Here, is d dimensional discrete variable in domain + U is the energy function, and Z is the normalizing constant. We make the following assumptions the domain and the energy function, following the literature of gradient-basee
discrete sampling [Grathwohl et al. 2021 Sun et al. [202]] Zhang et al. 2022b]: : (1) The domain is coordinatewisely factorized,
G. (2) The energy
function U can be extended to a diffcrentiable function in IRd.
3.2
Locally Balanced Proposals
Zanella 2017
introduces family of informed proposals, which is defined below:
g
=(0") x(0)
Ka (0' 0)
Q9.a ())
Zg.a (0)
Here, K₂ is a kernel that determines the scale of the proposal where a plays a similar role as the step size. g() is balaneing function that determines how to incorporate the information about If g(t) = ( the proposal becomes a locally balanced proposal, which is asymptotically optimal in the local regime, that is, when the step size + 0.
Automatic Cyclical Sampler
We aim to develop sampler capable of escaping local modes in general multimodal discrete distributions, including those that appear in deep energy-based models and large language models. First, we motivate using the cyclical schedule by demonstrating the issue of gradient-based samplers getting stuck in local modes on a toy dataset. We then present our sampler's parameterization of the step size and balancing function. Next, we introduce a cyclical schedule for the proposal distribution that enables effective exploration and characterization of discrete multimodal distributions. Finally. we develop an automatic tuning method that simplifies the process of identifying hyperparameters in cyclical schedules.
4.1 Motivating Example: A Synthetic Multimodal Discrete Distribution
To demonstrate the erucial issue of local modes trapping gradient- basee samplers, we construct a dimensional dataset consisting of integers. We define t {0, 1, ..N22, where N is the maximum
3

---

value for each coordinate. Given a set of modes {HI, M2.... pi
we define the energy as follows:
|00
U()) log Σ
exp
(2)
2x
This distribution enables easy comparison between different methods terms of their ability both explore and exploit the target distribution. We demonstrate the results of various samplers in Figure More experimental details can be found in Appendix D.T
visual comparison reveals that while gradient-based samplers (DMALA /Zhang et al. 2022b] and AB [Sun al. 2023a are very effective at characterizing given mode, they tend to get trapped in some small neighborhood, preventing proper characterization of the distribution as whole.
We can understand this behavior of gradient-based samplers by comparing them to random walk sampler (RW), which is able to explore all the modes but unable to fully characterize the detail each one. While the RW sampler proposes movements uniformly over the sample space, gradient- based samplers propose movement based on the geometry of the distribution as captured by the gradient. Because the proposed movements in the direction of increasing density, these proposals are able to characterize given mode in detail. At the same time, these proposals hinder escape to more distant modes as the gradient points away from their direction. For this reason, observe that local modes are able to "trap" gradient-based samplers.
Parameterized Proposal Distribution
To derive an automatic schedule for the proposal, we need to parameterize the proposal first. We define Ka and g(() in the informed proposal [Zanella 2017 as follows:
-118'-01
Ka (0' - 0) exp
2n
oo);
s( 18, _ (0.5,
(3)
Z
where is called balancing parameter. 0, 0.5 correspond to seaall-bbllanced proposal proposal. Values in between result in
and a - 00, B = correspond to interpolations between reaaly-ballance and dlobally-balance proposals. Note that (0, 1) in Sun et al. [2023a] while our range is narrower.
We substitute these definitions into Equation
①T and apply the first-order Taylor expansion:
110' 011
exp (((VOU(0)( -8) 110
01
Qa,a exp ((U((")-((0)))
2a
2a
(4)
As in Zhang et al. 2022b), use the assumption of coordinate-wise factorization to obtain the following coordinate- proposal funetion:
2 (0.10) = Cat
Softmax (3VU()),0) -
-6)2
(5)
2x
order to make the resulting Markov chain reversible, we apply the Metropolis-Hastinn correction, where we accept the proposed step with the following probability:
A( a, min exex)pUU(()) U()))) Q (..0((10')
(6)
(0,)(
In summary, parameterize our proposal in Equation 5 which includes spectrum of local and global proposals. Our proposal determined by two hyperparameters, the step size a and the balancing parameter (3.
4.3 Cyclical Hyperparameter Schedules
Cyclical Step Size Schedule order to effectively explore the whole target distribution while retaining the ability to exploit local modes, we adopt the cyclical step size schedule from Zhang et al. 2020). The definition of step size a for iteration & as follows:
#mod (k,
Cg = max
A'max COS
+ 1, Cmmin
(7)

---

1.0
accpptacerris
Boaking Peromater
0.8
1.2
Samppeg StrE
Stmpgingg Sina
0.39
Stop Sizs
(a)
(b)
Figure 2: (a) a--chedule along with the corresponding 3 schedule. The initial large steps enable the sampler explore different regions of the distribution, while the smaller steps enable good characterization each region. The balancing parameter / varies with the step size to enable high acceptance rates for all step sizes. (b) Acceptance rate v.s. step size on EBM sampling on MNIST shows a non-monotonic relationship.
Algorithm 1 Cyclical Sampling Algorithm
Require: step size schedule {au)=- balancing parameter schedule {8a]a-1 cycle number
steps per cycle
1: samples <
2: for cycle c in range n do
3: for step & in range do
4: 0 < samplesss-11
5:
for coordinate in range d do
6:
construct Q Qar.e. (-10) as in (5)
7: sample 0 Van.s. (-10)
8: end for
9: samples + H' with probability (
10: end for
11: end for
12:
return samples
where Omax is the initial step size, O'min is the minimum step size, and is the number of sampling steps per cycle. Differing from the cyclical schedule in Zhang et al. 2020), we additionally add Oumin. to make sure that even the smallest step size remains effective in discrete spaces.
can easily result very low acceptance rates, removing any benefit of exploration. To address this issue, we introduce a balancing parameter schedule, which enables reasonable acceptance rates for large step sizes. As discussed in Zanella [2017]. Sun et al. 2202aa] the balancing parameter should vary with different step sizes to achieve "balanced" proposal. balanced proposal ensures that the Markov chain is reversible with respect to certain distribution, which will converge weakly to the target distribution. For example, when the step size a > O, the optimal balancing parameter
Cyclical Balancing Schedule Using large step sizes
0.5, whereas for a + co, the ideal
balancing parameter becomes
Thus for schedule of step sizes, each a requires different Bg [.5, 1), with larger step sizes having 3, closer to and smaller step sizes having 3, closer to 0.5. Using the Metropolis -astiiggss acceptance rate to characterize the quality given a, 3 pair, we define the value of 3 as follows:
B. argmax sE(.5, (Fewa,,"~q... P' [[ 00, a4, ()))
Intuitively, this definition means that the best 3, for given step size a, maximizes the average acceptance rate for the proposal function Qa,3. It also conveys that larger step sizes will have larger balancing parameters.
We include visualization of the resulting schedules in Figure 2h and outline our algorithm using o, schedules in Algorithm [ Note that incurs no extra overhead compared to previous gradient-based discrete sampling methods it only adjusts hyperparameters and 3. By using a combination large and small a and 3, we enable the sampler explore the distribution fully without sacrificing the ability to characterize each mode. This is demonstrated in Figure TT.
5

---

Algorithm 2 Automatic Schedule Tuning Algorithm
Require: Amin = .5, Bmax. target acceptance rate p², initial state finics steps per cycle s, initial largest
step size Oceii 60, initial smallest step size Ortoor .05
1: < InitBurnin(( Fmax Oinis)
2: Ominn f- EstAlpha((Hooor) mmin: 8, p² MAX=False)
3: Omma f EstAlpha(Ocsitt Smax O, p², MAX=True)
4: Construct a-sched of length using
7
5: 8-sched < ESstBalSchedaa-scheee 5max, Bmin, 0)
6: return a-sched, 8-sched
4.4 Automatic Schedule Tuning
we have parameters Omax, Ormax. and {.1, ..... B. to be decided. this section, we will introduce an automatic tuning algorithm to easily find suitable values.
For schedules in Equations 7 and 18)
Main Idea Our automatic tuning algorithm depends the initial balancing parameter Smax. the final balancing parameter Smin. a target acceptance rate p², and the number steps per eycle s. These values relatively easy select, as detailed in Appendix A Below, assume they are already determined. The tuning algorithm first estimates the optimal choices for O'aax and O'min based on p", which can then be used construct the full step-size schedule using (7). We then construct the balancing parameter schedule using (8). The method is summarized in Algorithm [2) with details regarding subroutines in Appendix A Our automatic tuning introduces minimal overhead relative to the more expensive sampling process. For example, in Section 6 we use 500 steps as the budget for Algorithm 2 where the total number of sampling steps is least 5000. We further demonstrate that our algorithm is relatively robust to hyperparameters in Appendix A.I
In short, our tuming algorithm adopts an alternative optimization strategy, leveraging existing knowl- edge about hyperparameter values (e.g. 3mio and 3max should be around 0.5 and respectively). While estimating the best pair 33 is challenging due to their interdependence, it is much casier to fix one and optimize the other [Sun et al. 2023a
Estimating O'max O'min For given 8max Amin. our goal is to find step sizes Omaxx amin that enable an acceptance rate close to p", We can formally state this goal as follows:
Ma, B) = Ea~x [Egr=Q..:((10) Ip- A(0 3)]]
Given Smax, Smin- we construct the following objectives pick the corresponding Omax Ommini
Oryax max(a s.t J (a, Bmax) Rz 0}
O'min min(a s.t [(a, 3min) Rs 0}.
(10)
By defining the initial and final step sizes in this manner, we ensure that our cyclical schedule includes a wide range of hyperparameter pairs with different trade-offs in exploration and exploitation.
To solve (TO), we estimate Omax by starting with large step size and gradually decreasing it find the step size that yields p Unlike existing works that start with small step sizes, we observed that multiple a values can yield the same acceptance rate for given 8, shown in Figure Pp. Therefore, we start with an upper limit aaii and reduce the step size to avoid missing any larger a values that meet our criteria. Detailed implementation is provided in Algorithm 4 in the Appendix. Olmnn can be obtained similarly.
Estimating Balancing Schedule After setting the start and end pairs for the a and schedules. we now define intermediate 3 values. As the entire step size schedule is fixed by (7), the problem is to determine best balancing parameter for each step size. simple strategy is to test different
spaced out evenly throughout the interval [.5, ( and select the best value in terms of acceptance rate. This approach leverages the observation that smaller step sizes tend to have smaller optimal balancing parameters. Detailed implementation is given in Algorithm 5 in Appendix.

---

Theoretical Analysis
In this section, we present convergence rate analysis for Algorithm For general step size and balancing parameter schedules, i.c., at each cycle, the algorithm will through steps in which it will use step sizes Q1, 022, ... a₂ and balancing parameters 31. $2,... S3.. Note that for each pair (as, we have a Markov transition operator which we label P. for = 1, ... s. The Markov operator for single cycle is given by / P1P2 Pe. We have the following two assumptions: Assumption 5.1. The function U() E (RR)) has M-Lipschitz gradient. That is [V) V0 M 1|0 0'1l
Note that it implicitly assumes that the set in domain θ is finite. We define conw(() as the convex hull of the set è.
Assumption 5.2. For each 0 E Rdd there exists an open ball containing @ of some radius re. denoted by (0, re). such that the function (-) me-strongly concave B(f, re) for some my >
Assumptions 5.1 and 5.2 are standard in optimization and sampling literature [Bottou et al. 2018 Dalalyan 2017 Under Assumption 5.2 U(+) m-strongly concave on conw(e), following Lemma
C.3 m Appendix.
We define diam () sup8, |10 0'1 and &n to be
+ 3.M 8.m)
exp
diam - [a)a] diam(@)
20;
The Markov kernel corresponding each P. in each step of the cycle in Algorithm Lis
pr(0'10) = A(8"18 (, a, (,,3,,0au. (8) - (1 60'))
(11)
where
((0) Σ (00)) (010') 8'EO ग (0)Q (0)10 ^ Qun... (0
the total rejection probability from 0. Finally, recall that the total variation distance between two probability measures ys and v, defined on some space O C Rd is
|| p||TV
Im(A) ((A) AEB(O)
sup
where B(O) is the set of all measurable sets in O.
Constant Step Size and Balancing Parameter To analyze [ step size and balancing parameter schedules, we first solve a simpler problem where the step size and balancing parameter fixed and then extend the analysis the setting of Algorithm [
Our main method of proof to establish uniform ergodicity of the Markov chain P. for a single a, B, by establishing uniform minorization for P. We denote the transition kernel for this Markov chain P as p(- (),, which is given in (IT) with ag 3r replaced by fixed a, B.
Lemma 5.3. Let Assumptions 5.1 5.2 with 1 hold. Then for the Markov chain P we have, for any 8, 6' E e,
33d
exp (3U(0')
p(0 0²) 2 63
Ev'e exp (3U(()))
where
3m
63 exp
2x +BM
diam 2
2
(a)( (θ)}
with a mingee [O]]
Proof. The proof is provided in Appendix C.I

---

Theorem 5.4. Let Assumptions 5.1 5.2 hold with < 1/BM. Then for the Markov chain P, the following hold:
i. P is uniformly ergodic with
|P - +||TV S (1 -E,,)"
ti. For any real-valued function f and samples X1, X2, X3, .nn from P, one has
n 11
Vn
((x:)
E 10))(0) $ N(,
for some 8. > 0 as - oc.
Proof. The proof directly follows from our Lemma 5.3 and Jones 2004 |004] [Corollary 5].
Note that as + O, we have 6, - 1 which implies that small step sizes result in low convergence rates. This is intuitive the algorithm could explore much in this case. Furthermore, our results suggest that large 3 restricts a to small values. Given that large 3 generally requires large a, our findings imply an upper bound for the step size.
Adaptive Step Size and Balancing Parameter Now tackle the case of varying step sizes and balancing parameters. Each cycle has s steps with step sizes a1, 02. ... Qg and balancing parameters 81, 182.... _8.. Note that this and the Markov chain no longer homogeneous. However, the marginal chain for each cycle is indeed homogeneous and can be analyzed. We present results in this setting follows:
is more challenging at each step the transition operator changes
Theorem 5.5. Let Assumptions 5.1 and 5.2 hold with 0s; < 1/B.M, i 1,2, .. Then for the
Markov chain P. the following hold i. P uniformly ergodic with
π TV
I (1 - ""
ii For any real-valued function f and samples X2, ... "n, from P, one has
1 Σ ((x)) - (ixx)-E(00))) [(0((1)) $ N(0,00)
Vn
0E0
for some ö. > n - oc, where,
cB2,,, = =xxp {
B.m
+ B.M
diam (0)²
20x,
2
exp { [U(a)]
with a mingee [VU())]
Proof. The proof follows from our Lemma
5.3
Proposition
C.1 and Jones 2004 [Cooollayy 5].
Both Theorems 5.4 and 5.5 hold uniformly over all functions the class of functions with at least a local minima in O The Central Limit Theorem results in Theorems 5.4 and 5.3 imply that may perform inference on the target distribution (--) even though the asymptotic variances are unknown, as we may perform batch-means to estimate these variances Vats et al. 2019.
In summary, we have established geometric convergence rate to the target distribution for our sampler. Previous research has only established asymptotic convergence (Zhang et al., [0226) or relative convergence rate bounds [Grathwohl et al., 2021 for gradient-based discrete samplers. To best of our knowledge, our results present the first non-asymptotic convergence bounds that explicitly quantify the distance between the estimated and target distributions. Further, our convergence bound also shows that discrete spaces play fundamental part in the ergodic nature of these algorithms.

---

Imrii
900
200
30006
32089
$350
12099
10000
1209
orriget
-400
12000
-100
-40
4.0
-2.00
-50
-000
1150
2200 8000 2010
Teruiee
2007 205
200
100
201
2007 2005
8007
2035
2000 2002
2003
Figure 3: Sampling performance of various methods. Top row demonstrates convergence to ground truth on RBMs, bottom row demonstrates convergence speed on deep EBMs. We report the average performance across 11 random seeds within standard error for the top row, and we show the average performance for the bottom ACS demonstrates competitive performance with all baselines.
the error area is not visibly clear. For both distribution types,
6
Experiments
We call our method that combines Algorithm 1 Tand Automatic Cyclical Sampler (ACS). For RBM and EBM sampling tasks, we compare our method to Gibbs-with-Gradient (GWG) Grrthhohl et al. 2021), Any-scale sampler (AB) [Sun et al. 2023a]. and Discrete Metropolis Adjusted Langevin Algorithm (DMALA) Zhang et al. 2022b), which are popular and recent gradient-basee discrete samplers. For learning tasks, omit AB sampler as it is not originally applied to the model learning tasks. More experimental details are in Appendix D We released our code at the following link:
https://github com/ http:///....coaaaaaaaaaaattattta
6.1 Sampling Tasks
We evaluate our sampling method on both Restricted Boltzmann Machines (RBMs) and deep convolutional Energy-Based Models (EBMs). For RBMs, measure accuracy by comparing the Maximum Mean Divergence (MMD) between samples generated by our method and Block Gibbs, which can be considered the ground truth. We sample on EBMs to demonstrate our method's scalability to more complex distributions. Experimental details are provided in Appendices D.2 and D.3 for RBM and EBM sampling, respectively.
In Figure 3 our proposed ACS method performs competitively for both RBMs and EBMs across all datasets. For RBM sampling, ACS is able converge the ground truth quicker than other methods due to the ability to capture the multi-modal nature of the target distribution. We see complex distributions represented by deep EBMs.
Results
that this performance generalizes
6.2 Learning RBMs and EBMs
Table 1: Deep Convolution EBM Log likelihood scores
test data as estimated by AIS. GWG results are taken from Grathwohl et al. [202T] ACS is able to achieve better results than the baselines.
One common application of MCMC techniques is learning energy-based models (EBMs), where a neural net- work parameterized by & represents an energy function Eg. These mod- els are typically trained using Per- sistent Contrastive Divergence (PCD) and evaluated with Annealed Impor- tance Sampling (AIS). Details on ACS for EBM learning are in Appendix B
GWG
DMALA
ACS
Static MNIST
80.031
0.038
79..905
0.057
Dynamic MNIST
80.51
80.120
0.036
79.634
0.024
Omniglot Caltech
94.72
99.243
2.101
91.487 +: 0.128
96.20
-98.001
= 0.371
89.262 +: 0.290
We test algorithm

---

learning deep convolutional EBMs, with experimental details in Appendix D.3 experimentation with learning RBMs Appendix D.4
We include additional
Results Table demonstratess that ACS is capable of learning better quality EBMs given the same com- putational budget DMALA. Furthermore, ACS learns better quality models with less computational budget than GWG.
6.3 Text Infilling
One challenging application of discrete MCMC methods is text-infilling, where the goal is to complete a sentence with some missing words. Given a dataset of sentences, we randomly mask our 50% of the words and fill them in using the distribution given by pretrained RoBERTa model. We include experiment details in Appendix D.6
Results Table demonstrates that ACS is capable of generating more diverse sentences, as ACS has a lower self- BLEU and higher percentage of unique n n-grams. While the perplexity results seem imply that ACS generates lower quality than DMALA, note that the ACS generations are more likely to be predicted as linguistically acceptable as shown by the CoL.A scores. We discuss the results more extensively in Appendix D.6
Unique n-gram (t)
Dataset
Method
Perplexity (L)
CoLA (1)
Self-Bleu (1)
n=2
n=3
DMALA
280.82 = 27.20 26
50.46 + 1.25
41.83 = 6.85
48.55
70.56
Grimm
ACS
369.44 + 30.85
53.42 + 1.26
36.70 6.42
53.91
74.70
DMALA
256.66 10.53
42.62 1.14
37.47 + .79
57.68
75.21
SST2
ACS
307.05 + 14.84
47.12 = 1.20
32.42 + .75
62.54
78.87
Table 2:
Empirical evaluation of the generated sentences. ACS outperforms DMALA for all metrics related to diversity.
7 Conclusion and Limitations
In this work, we propose Automatic Cyclical Sampler (ACS) to more effectively characterize multimodal distributions in discrete spaces. First, we demonstrate that gradient- samplers prone to getting trapped in local modes, preventing a full characterization of target distributions. To address this issue, combine cyclical step size schedule with cyclical balancing parameter schedule along with an automatic tuning algorithm to configure these schedules. We also theoretically establish the non-asymptotic convergence bound of method to the target distribution in addition to providing extensive experimental results.
While our proposed ACS method generates impressive results a wide range of experiments, there are some limitations to our work that should be mentioned. Specifically, though we have proven geometric convergence rate and the relationship between and in our theoretical analysis, require (.) to be twice differentiable as well as locally strongly concave and the proof is not based on the specific tuning algorithm implemented. This is why provide extensive experimentation to demonstrate that our algorithm is capable of picking good a, & schedules.
10

---

References
Bernd Berg and Thomas Neuhaus. Multicanonical algorithms for first order phase transitions. Physies Letters B, 267(2):249-255 223,,53,, 1991.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31,, 2018.
Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society Series B: Statistical Methodology, 79(3):651-676, 2017.
Wei Deng, Qi Feng, Liyao Gao, Faming Liang, and Guang Lin. Non-convex learning via replica exchange stochastic gradient meme. In International Conference on Machine Learning, pages 1474-2483, PMLR, 2020a.
Wei Deng, Guang Lin, and Faming Liang. contour stochastic gradient langevin dynamies algorithm for simulations of multi-modal distributions. Advances in neural information processing systems,
33:15725-15736 2020b.
Yilun Du and Igor Mordatch. Implicit generation and modeling with energy based models. Advances in Neural Information Processing Systems, 32, 2019.
Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Sussman Grathwohl, Dale Schuurmans, and Hanjun Dai. Dises: A benchmark for discrete sampling. In seirth- Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
Will Grathwohl, Kevin Swersky, Milad Hashemi, David Duvenaud, and Chris J. Maddison. Oops I
took A gradient: Scalable sampling for discrete distributions. CoRR, abs/2102.04509, 2021. URL
wrrexiv.org/aaii abs///02...2/2//////////// 04509
Geoffrey E Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1771-18N) 2002.
Galin Jones. On the markov chain central limit theorem. 2004.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1xXiv1997.11699) 2019.
Enzo Marinari and Giorgio Parisi. Simulated tempering: new monte carlo scheme. Europhysics letters, 19(6),451, 1992.
Radford M Neal. Annealed importance sampling. Statistics and computing,
2001.
Benjamin Rhodes and Michael Gutmann. Enhanced gradient-based meme in discrete spaces, 2022.
Sebastian Ruder. An overview of gradient descent optimization algorithms. 1rXiv:1609.04747, 2016.
arXiv preprint
Emanuele Sansone. Lsb: Local self-balancing meme in discrete spaces. In International Conference Machine Learning, pages 19205-19220 PMLR, 2022.
Haoran Sun, Hanjun Dai, Wei Xia, and Arun Ramamurthy. Path auxiliary proposal for meme in discrete space. In International Conference on Learning Representations, 2021.
Haoran Sun, Hanjun Dai, and Dale Schuurmans. Optimal scaling for locally balanced proposals in discrete spaces, 2022.
Haoran Sun, Bo Dai, Charles Sutton, Dale Schuurmans, and Hanjun Dai. Any-scale balanced samplers for discrete space. In The Eleventh International Conference on Learning Representations, 2023a. URL httpp:://penrreviex
Haoran Sun, Hanjun Dai, Bo Dai, Haomin Zhou, and Dale Schuurmans. Discrete langevin samplers via wasserstein gradient flow. In International Conference on Artificial Intelligence and Statistics, pages 6290-6311 13. PMLR, 2023b.

---

Robert H Swendsen and Jian-Sheng Wang. Replica monte carlo simulation of spin-glasses Physical review letters, 57(21):2607, 1986.
Robert H Swendsen and Jian-Sheng Wang. Nonuniversal critical dynamics in monte carlo simulations. Physical review letters, 58(2):86, 1987.
Tijmen Tieleman. Training restricted boltzmann machines using approximations to the likelihood gradient. In Proceedings of the 25th international conference on Machine learning, pages 1064- 1071, 2008.
Dootika Vats, James M Flegal, and Galin Jones. Multivariate output analysis for markov chain monte carlo. Biometrika, 106(2):321-337, 2019.
Ulli Wolff. Collective monte carlo updating for spin systems. Physical Review Letters, 62(4))361, 1989.
Yue Xiang, Dongyao Zhu, Bowen Lei, Dongkuan Xu, and Ruqi Zhang. Efficient informed proposals for discrete distributions via newton's series approximation. In International Conference Artificial Intelligence and Staristics, pages 7288-7310. PMLR, 2023.
Giacomo Zanella. Informed proposals for local meme in discrete spaces, 2017.
Ruqi Zhang, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson. Cyclical stochastic gradient meme for bayesian deep learning. In International Conference on Learning Representations, 2020. URL
Ruqi Zhang, Xingchao Liu, and Qiang Liu. A langevin-like sampler for discrete distributions. In International Conference on Machine Learning, pages 26375-26396. PMLR, 2022a.
Ruqi Zhang, Xingchao Liu, and Qiang Liu. langevin-like sampler for discrete distributions, 2022b.
Liu Ziyin, Botao Li, James B Simon, and Masahito Ueda. Sgd can converge to local maxima. In International Conference Learning Representations, 2021.
12

---

A Details of Automatic Cyclical Sampler Algorithm
Here we include more details regarding the Automatic Cyclical Sampler algorithm. We discuss all the individual sub-routines that compose the algorithm shown in Algorithm2 We also include an ablation study demonstrate the robustness of our algorithm various hyper-parameter configurations.
InitialBurnin We find that in order to produce meaningful estimates for the objective in g it is necessary burn in the MCMC sampling chain. This is due to the dependence of the acceptance rate on current sample 0. If we use & very low in density with respect to the target distribution, the acceptance rates estimated by the tuning algorithm will lose accuracy as the sampler converges the larget distribution. In order to avoid this issue, we run a quick burn-in stage with two distinct stages.
The first stage uses the gradient information to move the sampler away from the initialized point as
quickly as possible. We use the parameterized proposal from Equation (4) with stepsize Oceill Smux without any Mettinolis-Hasttngs correction as this enables very large movements from the initial sample.
For some datasets, this enables very quick burn-in. This can be noticed in Figure 3 for Static/Dynamicc MNIST and Omniglot. We hypothesize that this is due to the distribution hav- ing relatively simple structure that enables the gradient to provide meaningful information for very large sampling steps. It is impossible to determine a priori whether a given distribution will have this property, so we include a following stage that uses a chance of arriving at reasonable sample 8.
correction to increase the
For this stage, we construct naive step size schedule and balancing constant schedule using the values of Oleeil, Offoor Smax, 3min We then run the parameterized sampler from Equation (4) with the Metropolis-
correction. Our goal is to move the sampler to samples 0 that are more likely in the target distribution. This will enable the acceptance rates computed during the tuning algorithm to be closer to the acceptance rates for the steady-state chain.
For all the sampling experiments, these two stages combined use 100 sampling steps.
EstimateAlpha Alpha Here we discuss the algorithm used to calculate both Omax O'min as defined in Equation TT).. When calculating O'max. the goal is pick the largest stepsize Ormax that acheives the acceptance rate p* for a given 3max. When calculating Olmin. the goal is to determine the smallest step-size capable of acheiving the target acceptance rate, We put the full pseudo-code in Algorithm
For calculating ammx and Ommin the algorithm follows the general pattern of automatically shifting the range of potential based on the best values calculated from the previous iteration. When calculating Omax the algorithm starts with an upper-bound initialized to Obound Oceii and iteratively decreases the range of proposed For Ormins the algorithm starts with lower bound Obound Orjoor and iteratively increases the range. For both, the other bound is calculated by the following learning rule:
Agropp Olbound + Clp- p-
Here, < the learning rate that determines how much we can adjust the step size in one tuning step. We found Ç insensitive and set < .5 in all tasks. Additionally, p is the best acceptance rate computed from the previous iteration of the algorithm. For the first step of the algorithm, we set p 0=0) O.
The algorithm uses Orprpp Obound to determine the range of to test. For calculating amax, the algorithm searches in the range of [Approp: (bbound]. For calculating Ommin the range is [Obound approp).
Given the appropriate range of and initial 0, we test l potential and calculate their respective acceptance rates using Equation (6). Once we have computed all the acceptance rates, we set Obound to the value that resulted in the most optimal acceptance rate as determined by Equation (9), 0 to the corresponding 8', and p to the corresponding acceptance rate.
Choice of Smax: Smin: p²: S The automatic tuning algorithm depends on initial choice of Bmaxs Pmin: p", s that enable it to automatically configure an effective papper-rrraeter schedule. Here describe the general approach picking these values.
For some target distributions, it is possible that the best possible acceptance rate with a very high 3max. such as Bmax .95, will not be close to the target acceptance rate p², In this case, the
13

---

EstimateAlphaMax algorithm will keep decreasing the proposed amax. which will result in very small amax- In order avoid this behavior, we recommend starting with Smax .95, and decreasing it by .05 if the resulting Omax is reasonable.
We always set Amin = 0.5 which is the smallest value can take.
We determine the target p² by starting with a value of .5 and increasing it by .05 until desirable performance metrics are obtained. While this process is essentially the same as grid search, we note that we only needed to apply this process the specific case of training a deep EBM on the Caltech Silhouettes dataset. For all other tasks and datasets, the target acceptance rate of p .5 was effective. We discuss the unique difficulty presented within the Caltech Silhouettes dataset in D.5
To determine the steps per cycle we required a similar approach to determine the optimal value. In our experiments, we only look at two different values: either 8 = 8, or = 20. Having longer cycle length tends to enable more exploitation of the target distribution, whereas having a shorter cycle enables more exploration. While we do not have an algorithm for automatically configuring this value, were able to achieve good results across all tasks and datasets by choosing either of these two values. For more details on the resulting hyper- paper-parameters used for each experiment, see Appendix D
A.1 Hyper-parameter Sensitivity
Our method introduces the following hyperparameters: 9max. Smin Ckecil, Offoor learning rate for tuning y, steps per cycle s, target acceptance rate p², and budget B. This may seem like many additional hyperparameters, but the majority of these are introduced due to the automatic tuning mechanism and are not changed across all tasks and datasets in the paper: 7 = .5, Qiooor = .05, Qreiil = 5, 9min .5, B = 200. Thus the only hyperparameters requiring tuning in practice are 3max. p p" and Note that the existing adaptive discrete sampler, any any-scale sampler introduced in [Sun et al., 2023a]. has a similar number of typer-parameett
initial step size a, initial balancing parameter update rate y, decay rate 3, buffer size N, initial Hessian matrix W, and initial diagonal matrix D. Like our method, most of these hyperparameters are fixed across experiments.
We conduct an ablation study to evaluate the sensitivity of our tuning algorithm to these hyperparam- eters choices. We choose one hyperparameter at time to ablate and keep the rest at default values of the hyperparameters at their default setting. We run the RBM sampling experiment over multiple datasets, each for 10 random seeds, and report the average results in Figure 4
We omit the standard error as that would harm the interpretability of the graph as many of the plots are quite close together.
We can summarize the main takeaways as follows:
1. The sensitivity of our algorithm to the hyperparameters depends on the dataset. For example, the sensitivity of our algorithm is low on MNIST, KMNIST, eMNIST, and Omniglot while the sensitivity is relatively high on Caltech.
2. The optimal hyperparameter values depend on the dataset. For example, high values of s generally yield superior results, except for Caltech, where lower values excel. Similarly, low 3mix values are usually less effective, though Caltech an exception, showcasing decent outcomes. In general, the hyperparameter values we selected to generate the final results in the experiment section were the ones that generalized across the datasets.
3. For each ablation, the values tested demonstrate reasonable results when compared with the baselines. While not all hyperparameter values result in equally competitive performance, all of them outperform the Boobs--Wth-GGradeen sampler Grathwohl et al. 2002]. This demonstrates that our method performs well with wide range of hyperparameters and can achieve even better performance with careful hyperparameter tuning.
In conclusion, we believe these results demonstrate that our algorithm relatively robust to choice in hyperparameters.
14

---

Algorithm 3 InitBurnin
Require: Accil Offoors mmax. Smnn, steps per cycle s, steps to take without MH correction to take with MH correction 1wи = 50, initial state
50, steps
1: for step in range(!) do
2: O ~ Q Bu (-16) Run burnin steps without MH correction
3: end for
4: {ai, 01 ... Oig t values from Equation
7 using Oleeil, Ofllor-
5: (Ba, .1....... 3a-1 values from Equation
using Smax. Smin We can use Equation get
interpolations of
6: number of cycles n = floor( ban
7: Obtain f by running Algorithm 1 using the calculated a, B schedule Run burnin steps with MH correction
8: return
Algorithm 4 EstimateAAlpha
Require: Obound: BUDGET, initial state 8, Balancing parameter 3, target acceptance rate p" learning rate Ç. number of proposals per step 5, flag MAX
1: Peur f-
2: while iteration i < BUDGET do
3: if MAX then
4: Opop = a(1 - <pp² Pourl) & adaptively decrease the range of potential or
5: proposed-parant -araams LinSpace((pepp Abound, t) we use Atound Oieeil as the ceiling for proposed a
6: else
7:
Oprop = a(1 + Clp" Powrl) I) > For AlphaMin, adaptively increase the range of potential
8:
proposed -arseems--mmss LinSpace(Ctoound Oppoop t) For AlphaMin, use O'bondd Offoor as the floor for proposed end if
9:
10:
initialize bookkeeping to keep track of proposed states and acceptance rates for a E proposed-paraae paaomsddddpaamssssem do
12:
0' ~ Qay ( (-(10) Use proposed to take sampling step
13:
A(8' (, Ogrop B) &o Compute acceptance rate for proposed +
15:
end for
Set Peur to the acceptance rate closest to the target a*
17:
Set O'hound to the corresponding Update Oboond to shift the range of proposed or for the next step
18:
sct Ocur to the corresponding 0
19:
end while
20:
if MAX then
21:
return Ormax =
Otpound
22:
else
23:
return Oemin Atpound
24:
end if
15

---

onnriglot
cakech
R37-63
Lang WMRD
-42
300
-2
-5.
530
1000
520
1000
550
1050
550
1300
500
1350
lontion
2.0
58
-25
-2.9
4.0
4.0
-35
Log
4.0
4.6
-65
500
1900
-8.0
350
1000
550
1000
510
1000
340
1000
-300
8:23
3.5
2.5
-00
-4.0
9-3300
-22
K.0
3.5
4.0
4.5
5.0
5.0
5.3
1000
1070
1000 1500
Figure 4: Average performance across multiple seeds for various hyper-parameter settings. We note that all configurations to exhibit convergence to the ground truth as indicated by the maximum mean discrepancy (log MMD), albeit with varying convergence speeds. In some cases, specific hyper-parameter configurations are able to achieve better performance than what we report in the RBM sampling experiment. Overall, we can observe that our algorithm is reasonably robust to various arper-parameter configurations it will still demonstrate convergent behavior towards the ground truth.
B
ACS for EBM Learning
B.1 Background
Energy Based Models (EBMs) are a class of generative models that learn some unnormalized distribution over sample space. As discussed in Hinton (2002), these models can be trained via the following Maximum Likelihood objective:
(())= = Exppan [- log (1))
(12)
The gradient updates for this loss function known to be follows:
VoL(Ø) Ez-pan [x)) - [V Ex)))
(13)
While the expectation on the left is straight forward to calculate given a dataset, calculating the right expectation is not clear. Here will mention the two methods that relevant towards experiments with EBMs.
Contrastive Divergence (CD) In order to estimate the second term, we initialize some sampler using the x in the first term and run it for set number sampling steps. For a more detailed description, refer to Hinton 2002
Persistent Contrastive Divergence (PCD) The expectation on the right can be calculated using samples from persistent Markov Chain that approximates the true distribution Tieleman 2008
16

---

Algorithm 5 Estimate EstimateBalSchee BalSched
Require: Step size schedule {Amax, ...... amin h Amax Pmins number of proposals per step t = 10, initial state 0, target acceptance rate p
1: PRoor Pmin: Iceil Amux
2: 8-sched <- {mmaa))
3: for in 2.. 1 do
4: proposed-params + LinSpace(ánon: Smax t) Create t potential balance parameters for
index in the schedule
5: initialize bookkeeping to keep track proposed states and acceptance rates proposed-params
6: for 3 E proposed- params do
7:
~ aa. (. & Use current proposed 3 to take a sampling step A(0 (9, Cc2, B) Evaluate the acceptance rate of proposed for current a; bookkeeping(.) < 0'
8:
9:
10: end for
11: pick (3 as B E bookkeeping largest p
Beell < B, b Shrink the range of potential balancing parameters by using assumption 3 Bi+1
0 == 0' correspending Bi
14: end for @-sche..append(Bmm (Smin)
16: return B-sched
Instead of resetting the chain each training iteration, we maintain a buffer of the generated samples that use calculate the second expectation. This method relies the intuition that the model distribution does not vary too widely within one iteration. Using the intuition provided by (Du and Mordatch 2019], we view this process updating the model parameters é to put more weight true samples and less weight on fake samples. By doing so, the model will in turn generate samples that closer to those from the true distribution.
B.2 Persistent Contrastive Divergence with ACS
Main Idea We can apply the ACS algorithm combining the automatic tuning the cyclical schedule with the original PCD learning algorithm. Our goal in doing is to improve PCD through better characterization the entire model distribution. During training, we can view PCD as adjusting the model parameters "push down" the probability of samples from the model distribution while "pushing up" samples from the true data distribution. Because our sampling method is able to explore adjust more regions of the
the model's distribution more effectively than other samplers, model distribution at a quicker rate than previous sampling methods, which should improve the quality of gradient updates and thus lead to better model parameters. We adapt ACS work within PCD by having the step size depend on the training iteration as opposed to the sampling iteration, with the corresponding or, pair being used for all the sampling steps within the iteration. We include the complete learning algorithm in Algorithm 6
Cyclical Scheduling We find that the learning task requires different approach the cyclical scheduling than the sampling task. Rather than having relative equal amount of exploration and exploitation, we find that more effective to use a cyclical schedule biased towards exploitation. However, exploration is still important as it enables the model to better represent the distribution as whole rather than few local modes. Given this, we construct a cyclical schedule consisting of one iteration that uses m 3 with the rest using aminn 8min.
Tuning One of the advantages of using the simplified cyclical schedule is that it only requires two pairs of Alphaat algorithm to both tune the respective a, 8 pair while also updating the persistent buffer. Not only does this reduce the additional overhead of the tuning component, but it allows the hyper-parameters to adapt to the changing EBM distribution.
to be optimized. Thus we can leverage the EstimateAlphaMaa and
17

---

Algorithm 6 ACS for Persistent Contrastive Divergence
Require: Number Iterations N,, EBM Es, data-loader D, sampler Q, small sampling steps Ssmall
big sampling steps Sbig initial buffer Xy, cycle length s, Ottoors Oceil, adaptive learning rate adaptive budget BUDGET
while iteration $ N do
2: for Xg ~ D do
floor ()) 4: if e mod K = 0 then
3: cycle number
5:
if mod
then
6:
Xj, O'max <- EstAlphaMaxxoeen. budget=BUDDEET, learning-rate =y)
7:
else
8:
end X,, EstAlphaMin(cttorr budget= leamiing-rate=))
9:
10:
Update Sampler Step Schedule Update the buffer by running either the AlphaMax or AlphaMin estimation algorithm
11:
else
12:
if mod then
13:
S Shig
14:
a Ommxx B = 9max Use the ox, 33 pair that best enables exploration
15:
else
16:
S Samall
a amin 3min Use the a, pair that best enables exploitation
18:
end if
Construct Q (. using 44)
20:
for sampling step in range(SSig) do
X
((-(Xy,
22:
if mod = then
X t
24:
continue if is the first step of the cycle, omit the MH correction
end if
26:
X + X with acceptance probability calculated in (6)
27:
end for
28:
end if
29:
Calculate Exppsl V ExE)))
using X,
30:
Calculate Exwpeen Fa
using X,
31:
(L E Exwpo F.F((r)
Ear-pos V Fao(x)) Estimate the gradient of the Maximum-
Likelihood objective as 12
32:
To VL
33:
i+=1
34:
end for
35:
end while
18

---

C
Theoretical Results
We define the problem setting in more detail. We have target that is of the form
((() = Z (x)(
We consider the proposal kernel as
1
e exp (VU(0) (0' -0)
110' 011
2a
and consider the transition kernel
( Q0. 8')
p(0' 0) (00)Q. 10)
A1) Q0 (0) + (1 (()) 60
where 50()') is the Kronecker delta function and L(0) is the total acceptance probability from the point with
T(0')Qu..0010)
L( Σ
11 2a,0(0100)
T00)Qa.,(010
O'EO
We also define
(
Σ exp 3 (U) (a 0)
1 011
2a
which is the normalizing constant for the proposal kernel.
C.1 Proof of Lemma 5.3
Proof. By including the balancing parameter, we start by noting that
exp ( (0' 0) 1/ - 1
(0 Eeso exp (BVU( (0 0) 20 0 2
(14)
Consider the term,
3 VU(O) (0' 3- & _1 - 8/71 (20((11-)) ds) 0¹)
(15)
Substituting
15) in (14).
the numerator of (n,s(0,0)
1
BVU( (0' 0)-
10' 012 =B (-U(0)) + +())
2a
B (0 8') (f," V'U((1 s)0 s0') ds (0 8)
(0 0')² I(0 - 0')
2a
B (-U(0) + +())
(0 87 ( //"" (PU((1-5)0 +0) ds d a
1 (0- 8¹)
From Assumption 5.1
(U M-gradient Lipschitz), we have
PU((1 - s)0 s8') ds) 8)) 12 (1 BM)
8
19

---

Since < 1/3M, the matrix
2a - BM) is positive definite. We note that
a (0)6')
0(
^1
Qa. (0) + (1 L())) 60
(16)
T(0)Q (0110
π a0 (0)0)
A1
Qu,,(0110)
(17)
a0))Qa. (0110)
(0,
^1
(0,))0')0)
(18)
(0))
1
(o, = Σ exp
3 VV) (s ---
-
|| - 0|13
20
xEG
(0 x)²(3 S' (PU((1 8)0 sx) ds) x) - (100-x) m0)
Σ exp
-3 (U()))((s))
This can be seen as
(0)Q (0'10)
Zo exp B + - (0'
1
1
-0)² -0'-
1 v- s)0 + +00 (0' (0--1)-
2a
Since Assumption 5.2 holds true in this setting, we have an 0 such that for any 0 conv (i)
-VU 2 m I.
From this, one notes that exp (U(())
(2= 3 m) diam(())
Σ exp (3U(s)) s (a) S exp (-3U(())) Σ exp (3U(s))
a
xEB
where the right-hand side follows from the fact that < 1/(3M). Therefore,
Za, (0)
exp (3 (-)( + (())))
Zo Za (0))
exp 12 (1 (mm) diam diam(()) (0)²
Also note that
(0'0(0'10) exp { (-U((()+ (0 0²)
T + 2 2 (- ()0 (0 t0 + s01) (0 0n}
Eoeo exp ((--U()++U()) (0 8¹)
1 I+ L V-U((1 5)0+
2a
exp
0'123
Evs exp (3 U-)))))(())))
We also note that
1
-3 (VU(O), - 0)
110 3 -0 0)+ + 10 0¹1 2a
2a
1
<
0) + diam (
2a
(/11- + - + 01 + diam(() (0)²
2a
s 31 - VU( - VU(a)lddiam ()) + 3 VU (a)]laammm)) + diam (0)²
2a
1
< BM + diam(0)2+ ( diam(
2a
Combining, we get
exp (0))
p(0'10) 2 63 E Eer exp (BU(0')
where
{ [-(1 (1 + BB
3m
diam( [[VU(a)) diam( {
C3 = exp
2
20

---

C.2 Proofs of Proposition C.1 and Corollary
C.2
Ps with Proposition C.1. Let P1, P2.... Ps be Markov transition operators with kernels p1, P.....PP respect to reference measure 1, Also, let pi(0' 0) 2 (,v( for some density vi on O and 4; > 0 with respect to reference measure n, Then, for the Markov operator P. defined with respect the kernel as
1=(0010) / J pi+ (1(010_-))d((0))dnp)p ..0.)-00--1111111 dn))
(:00000)).....0--::::::- (200-iit100-1)
have
0) 2
Proof. The proof straightforward by using the minorization of pt. Indeed, one has
p(0' (0) = 1
(. ... ( 6. 100 )dn((()))) ..d(((a))))
2 (0)(00) / Pit (
... dn(0)) dn)(0-1))
2 (6)
which establishes the result.
Note that in Algorithm 1 for each cycle, we go through s steps corresponding to the step size and balancing parameter schedules (fa1, 022' ..2))-a,))) and (1,1, 82, B.)). Let P1. P2. ... P. be the Markov operators corresponding to them.
Corollary C.2. Let Assumptions and 5.2 hold. Then
Pi P,(0,A) (A)
for any measurable subset A O.
Proof. The proof immediate from Proposition C.1
C.3 Additional Lemma
Lemma C.3. Let Assumption 5.2 hold with θ compact. Then, there exists some m >> 0 such that for any 0 conv(O), Amin -U-)(() U() > m.
Proof. Note that since θ is compact cone(O) is also compact. This is easy to see as we only need to establish that conv(() is closed and bounded by the Heine-Borel Theorem. Take any element in 0 E conv(O). By definition, f = a&; + +1 a)0² for some 0, 0g θ and 0 < a < 1. Since is compact, we know that there exists M > such that ||O,]| < M for i 1,2. Therefore ||o|| < M by triangle inequality. Thus the set is bounded. The fact that it is closed is also easy to see. Take any sequence T, con This implies there exists Or,, 01,n: 02,, such that xn, an 01. + (1 0,, Since 2n converges our assumption, it is Cauchy which in turn implies each of an 01,n, 22.n is Cauchy as θ is bounded. Thus the proof immediately follows. Now, consider each 8 con There exits (00, ro) such that 2 U(0') Z my for all 6' B(O, ro). Since comv(O) C Usee (0,, ro), this is an open cover of co) Since conw(() is compact, there exists 01 0g.................. ... ... such that conv(e) C U B(O,, ro.). Thus for each we have V - U(O)) 2 m I when re.). Thus 2 (0) 2 minisiss mø, for all 0 conv(O). Hence we are done.
D Additional Experimental Results and Details
Here, we include the full details for all the experiments we include in this paper, as well as some additional results. All experiments were run single RTX A6000.
21

---

D.1 Multi-modal Experiment Design
Synthetic Distribution In order to construct distribution that easy to visualize, we first must define a few experiment parameters. We must define the space between the modes, the total number of modes, and the variance of each mode a. For convenience, we have the number of modes as 25, which is perfect square. We define the space between modes as 75, and the variance for each mode o² as 11. Given this, we can calculate the maximum value for each coordinate as follows:
Max Val = (v (NNumModes + 1) SpaceBetweenMoods
We can calculate the coordinate value for each mode Pt,j as follows:
Max Val
[s. [0]
NNumoodes + (i 1)
Max
Pig [1]
(j +
VNumModes +
Sampler Configuration Our goal in this experiment is to demonstrate how gradient- samplers typically behave when faced with distribution with modes that are far apart. In order for this experiment to be meaningful, is important that the representation each sample respect the notion of distance between the integer values. For this reason, we cannot categorical distribution or represent each coordinate with one-hot encoding, as every sample in this representation would be within a 2-hamming ball of every other point.
In order to determine the step sizes for the base- lines, we tune each until we reach an acceptance rate around .574. For DMALA, this ends up be- ing around = 53. For the any-scale sampler, we set the initial step size be the same and use their implemented adaptive algorithm.
For the cyclical sampler, we Ommx 1575,
amin = 3, and steps per cycle = 20. Because the goal of the experiment is to demonstrate the need for larger step sizes along with smaller step sizes, we do rithm on this example as restricting the space to be ordinal changes the optimal setting for Oceil- In most practical cases, the samples would be represented by a categorical or binary form, which the proposed tuning algorithm is able to handle as demonstrated by the performance on real data distributions.
use the automatic tuning algo-
Figure 5: Uneven multi-modas target distribution. While the top-left mode does have the most mass, only sampling from this mode will result in an inaccurate representation of the target distribution.
Uneven Multi-modal Distributions Not only does cyclical step-size enable more accurate sampling in highly multi-modal distributions, but is also able to handle distributions where the modes are weighted unevenly. This problem more difficult since this requires not only exploring all the modes of a distribution, but ensuring that the less likely modes are not over represented in the generated samples. We provide visual com- parison between the target distribution, the estimated distribution from DMALA, and the estimated distribution from ACS in Figure 5
Since the modes may be clear due the nature of this specific problem, we also include quantitative comparison between DMALA and ACS in Table by computing the KL divergence between the estimated distribution and the target distribution in addition the average energy of the generated samples. Through both Table 3 and Figure 5] we observe that a cyclical step-size enables accurate sampling from uneven multi-modal distributions.
22

---

Furthermore, it is interesting to ob- serve that generating more high- probability samples does not necessar- ily correspond to accurate sampling, highlighting the difference in goals he- tween generating very likely samples and accurately sampling the target dis- tribution.
Table 3: Quantitative comparison of sampler performance on uneven muulti-modll distribution. ACS retains the ability to accurately capture all the modes within the distribution despite the uneven weighting.
DMALA
ACS
KL Divergence 0.70
0.13
Average Energy
2.66 + 1.68
-3.39 d: 1.63
D.2
RBM Sampling
RBM Overview We will give a brief overview of the Block-Gibbs sampler used to represent the ground truth of the RBM distribution. For more in-depth explanation, see Grathwohl al. [202]] Given the hidden units h and the sample x; we define the RBM distribution as follows:
logp(z: h) h W log Z
(19)
As before, Z is the normalizing constant for the distribution. The sample æ is represented by the visible layer with units corresponding to the sample space dimension and h represents the model capacity. It can be shown that the marginal distributions are as follows:
p(r h)) = Bernuuli(W c)
p(h[z) Bernoulli +
The Block-Gibbs sampler updates x. and h alternatively, allowing for many of the coordinates to get changed at the same time, due to utilizing the specific structure of the RBM model.
Experiment Setup Similar to the experimental setup of Zhang et al. 2022a we use RBM models with 500 hidden units and 784 visible units. We adopt the same training protocol, except we train the RBM with 100 steps of Contrastive Divergence as opposed to 10. We also train the models for 1000 iterations as opposed to single pass through the dataset. We find that this enables the RBMs generate more realistic samples. We include the generated images in Figure 6 demonstrate that these models have learned the dataset reasonably well.
/ tw0
6
4 à
416
|- <ewja 4
7
1.0,,17511 1. <>
87
R
7
T
20 104uwa20 quia
5 4
/A.>>>>>>>>>>>
7 7
6246666770
6
10004 00000
N.49 -00%
h
D22440 0
(a) MNIST
(b) cMNIST
(c) KMNIST
(d) Omniglot
(c) Caltech
Figure 6: Images sampled from RBMs trained by Centrastive-Diverged with Block Gibbs. We Block Gibbs as the sampling algorithm to produce these images as well.
Sampler Configuration For GWG, we use the same settings as Grathwohl et al. [2021], for DMALA, we set step size 22 and for AB we use the default syper-parametery for the first order sampler.
For ACS, use p² = 5, 3mxx .95 Ç .5, cycle length 20 for all the datasets. We also fix the total overhead of the tuning algorithm to 10% of the total sampling steps.
In addition to using the same initialization as Zhang et al. [2022a] Grathwohl et al.] 2222T. we extend the experiment to measure the ability of sampler to escape from local modes. We initialize the sampler within the most likely mode, as measured by unnormalized energy of the RBM. Samplers that are less prone to getting trapped in local modes will be able to converge quicker to the ground truth, as measured by log MMD. We include the performance of the various samplers across random seeds in 7 ACS demonstrates superior robustness to mode-specific initialization due to its capability to escape from local modes.
Escape from Local Modes
23

---

Inreet
Cal
-35
20
10
Tran
10000 5022 10100 5.03
20019
5003
1030
10000
Figure 7: Log MMDs v.s sampling iteration across various datasets. ACS demonstrates more robust sampling behavior across the datasets than other methods, as evidenced by superior convergence on all datasets except KMNIST. We do note that ACS performance is still competitive on KMNIST with the added benefit of smaller standard error.
Generated Images We found that visual inspection of the generated images demonstrates the ability of ACS to escape local modes. We include the generated images in Figure
7 4
4
f
6
i
/
3
0
la
/
8
6
7
4
/
7
2
6
6
6
4
1
4
5
6
6
&
2
7
6
6
2
4
7
2
5
2
/
&
G
(a) GWG
(b) AB
(c) DMALA
(d) ACS
Figure 8: Images sampled from RBM trained on MNIST when the sampler initialized to most likely mode. ACS is able to generate diverse range of digits, demonstrating its ability to escape from modes. It should also noted that while AB is able to generate a diverse range of digits as well, the images are slightly less clear than those generated by ACS.
We can make two primary inferences from the generated images: the first being that ACS is able to escape from local modes and explore the distribution as whole, as demonstrated by the wide range of generated images; and that ACS does not compromise on the ability to characterize each mode as evidenced by the quality of generated samples.
Sampling Speed While the run time vary depending the specific implementation of a given sampling algorithm, we illustrate the efficiency of ACS in Figure ACS is able to outperform DMALA in terms of convergence with respect to time, even including the overhead of the tuning algorithm.
D.3 EBM Sampling
kmnist
DEALA
Base EBM Training In order to train the EBMs, we use Gibbs-with-Gradiem to sample the EBM distribution during PCD, following the same training protocol as Grathwohl et al.) (002I). We train these models for 50,000 itera- tions total with 40 sampling steps per iteration and use the parameters corresponding the best log likelihood scores on the validation dataset.
-4.0
--..5
-5.0
-5.
0.0
2.5
5.0
7.5
10.0 12.3
15.0
17.
20.0
Figure 9: Log MMD for the RBM sampling task across time for both DMALA and ACS for the KMNIST dataset. We observe that while ACS is offset slightly in the beginning due to the initial tuning algorithm, is quickly able demonstrate superior convergence.
Experimental Design For each of the trained models, we evaluate the samplers based on how quickly the average energy of the generated sam- ples rises. This gives an estimate of the speed which a sampler is able to reach a stationary distribution.
24

---

Sampler Configuration For GWG, we use the same settings as Grathwohl et al. [2021], for DMALA, we set step size to 2. and for AB we use the default hyper parameeerssssss for the diagonal variant of the AB sampler. We choose this variant as this is what they evaluate for their experiments when measuring mixing speed of samplers on EBMs.
For ACS, we use p = .5, Smax .8, C = .5, cycle length = 20 for all the datasets. As in RBM Sampling, we fix the total overhead of the tuning algorithm 10% of the total sampling steps.
Sampler Performance It is worth commenting the similarity in performance between ACS and DMALA when sampling from Caltech. We find that when sampling from the EBM trained on the Caltech dataset, ACS finds a Ommx similar to Omins thus making the ACS sampler similar to DMALA for this specific case. We hypothesize that small step sizes are most effective for this dataset. The results in Figure @ demonstrate that ACS can handle such cases automatically: while the step size for DMALA must be hand-tuned, the ACS method can automatically adapt to suitable step size schedule.
Generated Images
We include the images generated by ACS when sampling from deep EBMs in
Figure T0
/
7
8 r
52
0
7
2
7 6
0
g
f
8
# 3
3 5 e
P
v
3
b
7 S
1 z
2 6
4090
3 1 6 5
4
5
6
500450
L 555 9 0
0 3
6
0 18886000
90 5
9 5
1 é
09
b 1
O
0 56
0
2
08
4
7 B
7
O 3 3
(a) Static
(b) Dynamic
(c) Omniglot
(d) Caltech
Figure 10: Generated Images from applying ACS sampling to deep EBMs trained with GWG. These samples capture multiple different modes while retaining good sample quality, demonstrating the benefit of our ACS method.
D.4 RBM Learning
Experiment Design We use the same RBM structure as the sampling task, with 500 hidden units and 784 visible units. However, we apply the samplers of interest to the PCD algorithm introduced by Tieleman (2008). The model parameters are tuned via the Adam optimizer with learning rate of .001.
In order to evaluate the learned RBMs, we run AIS with Block-Gibbs as the sampler to calculate the log likelihood values for the models Neal 2001). We run AIS for 100,000 steps, which is adequate given the efficiency of Block Gibbs for this specific model.
Sampler Configuration For DMALA, we use a step size of .2. For the ACS algorithm, we set Smax -9,p* .5 for all the data-sets. We do modify the number of cycles for each data-set as different distributions require different amounts of exploration and exploitation. We use cycle length of 8 for MNIST, eMNIST, and KMNIST; we use 20 for Omniglot and Caltech silhouettes. This difference reflects the specific needs for each dataset in terms of exploration and exploitation more complex datasets tend to need longer cycles in order to better exploit each region, while simpler datasets tend to need shorter cycles in order to capture all the modes the learned distribution. In Figure II show the samples generated from AIS for 100,000 steps as opposed to the persistent buffer as this forms a longer MCMC chain, thus giving a better visual of what the learned distribution represents.
In order to ensure that the overhead for the tuning algorithm does not add to the overall computational cost, we spread out the computations of the Estimate A algorithm throughout the training process. We keep a running list of Omin and set Okpoor to be one standard deviation below the mean of this list. By doing this, start closer to what the ideal amin For EstimateAlphaMaa, simply call
25

---

the tuning function every 50 cycles containing 50 training iterations, with Goeil = 5. As the initial step does not use the Settropoii-HHastinn correction and has half the sampling steps, the budget for each call of Alphmate can be seen as coming in part by the computation saved.
We include the AIS results for RBMs trained with different sampling methods in Table We see that ACS achieves superior log likelihood results when compared to other sampling methods across all datasets. Furthermore, the AIS results are consistently close to those achieved by Block-Gibbs, which can be considered close ideal for RBMs since it leverages the known structure of the model.
Results
Generated Images We include the generated images from the RBMs trained using different samplers in Figure 11
/ F
15 2
7
1 2
4. 2
B 6 4
mwkavatve
M1 (
%
91
<=
A
0 7
$ 9 1000011 2
2-6 w vav
3 3 (( (2
x
$
00 N 4044
1
[ 11 As
7
O f M 2
3
2 7 4411
0239,8
4 3 4
- 8 a. / 0
8: 8 2 224
4 8 R 7 7774
c 2 22332730000 y
73 $
774777 4 5 9 176655777
9
22
D" Ue 9 (2 P 2K No1s ve 2 " 00 PLL N2447 l at M PAUN
{ 4 10
A
A
5 3 8
A 16
7 06
20
2-
7 0677
2.
2
8 000443444
3 42000
2010
0
77
70
J6 10
Figure 11: Generated images from RBMs trained with different samplers. First row corresponds to GWG, second row corresponds to DMALA, and final row corresponds to ACS. First column represents models trained on MNIST, second on eMNIST, third on KMNIST, fourth on Omniglot, and fifth on Caltech Silhouettes. Images are generated via AIS for 100,000 steps.
In general, the images generated from the ACS-traiied RBM capture more modes than other methods, except for the Caltech Silhouettes dataset. In particular, all the methods struggle to generate reasonable images for this dataset. We hypothesize that this is due to the increased complexity of the distribution relative to the other datasets - Caltech Silhouettes is com- posed of the silhouettes from real ob- jects, whereas the other datasets are hand-written symbols. This hypothesis supported by the generated images in Figure where the images generated when using Block- Gibbs on Caltech Silhouettes also seem less reasonable than the samples obtained from different datasets. Since Block-Gith is the best sampler for this specific model as it leverages the known structure of the RBM, this appears to be unavoidable as a result of limited model capacity. This motivates our experiments with deep convolutional EBMs, where we can understand how our method does when using model architecture with sufficient capacity.
Table Log likelihood scores for RBM learning on test data as estimated by AIS. ACS outperforms all gradient-based baselines across all datasets.
GB
GWG
DMALA
ACS
MNIST
-191.98
-38.334
-278.35
-249.55
eMNIST
-317.78
-590.97
-324.34
-304.96
KMNIST
-357.69
-681.28
-436.3538
-407.39
Omniglot
-161.73
-276.81
-222.61
-220.71
Caltech
-511.65
-827.45
-427.29
-396.04
26

---

D.5 EBM Learning
Experiment Design We use the same EBM model architecture as Zhang al. [2022a] Grathwohl ct al. [202]] and follow the same experimental design, with the only change being to the number of sampling steps alotted for each sampler.
In order determine the number of sampling steps that we could use for ACS-PCD, we tested different sampling steps. For Static/Dynamic MNIST and Omniglot, we found that we only needed to use 10 sampling steps to achieve good models. However, we observed divergence when training models on Caltech. In order to determine what number of sampling steps to use for ACS, we do grid search over the number of sampling steps and p with all other values remaining the same. We test sampling steps of 10, 20, and 30; and we use p 5,, .6, .7, We decide which hyper-paramene to use based on when training diverged the latest; and we use the best model parameters as indicated by validation log likelihood. We use 10 sampling steps for Static, Dynamic MNIST, and Omniglot, while we found 30 was the minimum we could use for Caltech Silhouettes and obtain reasonable results. We apply this number of sampling steps for both DMALA and ACS to demonstrate how the methods compare when facing a similar budget constraint.
In order to evaluate these learned models, we use the same evaluation protocol as Zhang et al. [2022a], Grathwohl et al. [202T]. We run AIS for 300,000 iterations using Gibbs-Wiin Withh-Grrdieet as the evaluation sampler. By following the same experimental design as previous works, we can draw meaningful comparisons from previous results in Grathwohl et al. [202I].
Sampler Configuration For DMALA, we use a step size of .15 as used in Zhang et al. [2022b]. For ACS, we use 200 sampling steps for EstimateAlphaMar and AlphaMtt For Statie MNIST, Dynamic MNIST, and Omniglot, we set the algorithm to tune Omax and Ohmin every 25 cycles, where each cycle has 50 training iterations. The additional overhead of this is 16,000 extra sampling steps, which is a 3.2% of the total budget of 500,000 sampling steps. For Caltech Silhouettes, we have to adapt every 10 cycles with the same number of training iterations. This results in 40,000 additional sampling steps due to the tuning algorithm. For this specific dataset, because we use 30 sampling steps, the additional cost is 2.6% of the total sampling steps 1,500,000.
In terms of the final parameters for cycle length and sampling steps, we find that we can use the same p" across all datasets, with the exception of Caltech Silhouettes. For Static/Dynamic MNIST and Omniglot, we were able to use p = .5 and For this dataset, we found good results by setting pa .7. We hypothesize that the need for higher acceptance rate due to the fundamental difference between Caltech Silhouettes and the other datasets, as previously mentioned. Because Caltech Silhouettes contain samples are derived from real objects, they are more complex than the hand-writter figures.
Experimental Results In addition to the empirical results in Table I we provide some qualitative data in the form of the generated images from the PCD buffer when using ACS. We choose to include the buffer images for this experiment as the chain from the persistent buffer is much longer than the chain from AIS due to the increased training duration: the chain from AIS is obtained using 300,000 sampling steps whereas the persistent buffer is obtained from 500,000 sampling steps on Static/Dynamic MNIST and Omniglot, 1,500,000 sampling steps for Caltech Silhouettes. By visualizing the generated images from the longer chain, we get better understanding of the quality of the trained distribution. We put the images in Figure [2
We also observe that this behavior is not unique to ACS and does occur when Libbs-With- With-nrrddeent and DMALA are used with 40 sampling steps as indicated. Instability is common when training deep EBMs, and this is most likely why the original experimental design included check-pointing throughout the training process as well as comparisons based on the validation set. We also note that despite this behavior, the trained models are able to generate fairly realistic images. We present the images from the PCD buffer for ACS below in figure.
When the images in Figure 12 are taken in context of the improvements in log likelihoods as presented in Table [ the results indicate the benefits of using ACS when learning multi-modal discrete distributions.
27

---

4 3 9
02
201873000 2072
2
5 518131 1133
44004
2 0 1037742
5
6 004455500 44
0 445900
# 128172782
T 698841
6 4 44000/
870
8
2
7 S 4 9 1-1
0 P 7700
V
WE 4 1
120122
0 5 3
2
/ 0 5
1448
2 6
3
3
(e) Static
(f) Dynamic
(g) Omniglot
(h) Caltech
The example images from the representative datasets, along with the samples generated from the persistent buffer when using ACS as the sampler for PCD. The images on the top row are examples from the dataset, while the bottom row are from the trained EBM. The images generated from ACS are remarkably similar those from the dataset, demonstrating that the model is capable of generating high-quality samples.
Figure 12:
D.6 Text Infilling
Experimental Design For both datasets, sample 100 sentences randomly and mask 50% of the tokens. We use a pretrained RoBERTa model available through the Hugging Face API et al. [2019] We 25 separate chains for each example and take the final state of each chain to be sample. We then take the top-5 most likely samples and use these for empirical comparisons.
We define the energy function the same in Zhang et al. [2022a] Let define sentence of length = {01, 02....0.) ...)). where 0, is a one hot vector over vocabulary V. Let M c {1,2,... ........ d} the set of indices wish to sample. We define the function f(0 2)) to be the log probability distribution over V for the i position conditioned on all other positions. Given this, we define the energy function for the sentence to be follows:
U(0)= Σ 5(0m
(20)
MEM
Sampler Configuration For DMALA, we tune the step-size to achieve an acceptance rate of 50%, which ends up being a = 55. For ACS, we use cycle length of 20. We use the same for the tuning algorithms as in previous tasks, demonstrating that our algorithm can be applied across domains and tasks with little modification. We include example generations for both ACS and DMALA in Figure 13
Perplexity v.s Sampling Accuracy In Table 2 we observe that the ACS generations have higher perplexity than the DMALA generations. While perplexity is a popular means of evaluating language generations, it is important to recognize that perplexity based on the likelihood of the generation under the language model. This metric is biased towards frequent patterns and does not account diverse modes. Therefore, it does not completely align with the goal of MCMC, which is to accurately characterize the target distribution.
Minimizing the average perplexity of the sample corresponds maximizing the average likelihood of the generations, which can be at odds with the goal of accurately capturing the target distribution. We illustrate this in Appendix [DI] where we compare the performance of DMALA and ACS when sampling from a uneven multi-modal distribution.
28

---

comedy follows feels huckneyed just plain crude, provoke stares, without opening up deeper
truth.
This comedy could either be hacky, or just plain crude, calculated to provoke shocked curiosity, without opening up to a deeper insight.
A comedy that feels slightly hacky, plain crude, calculated achieve shocked resulls, without coming up with deeper message.
comedy was unnecessarily backy, or just plain crude, calculated create humor, without leading up deeper
plot.
Most comedy is flat or hack-ish or just plain crude, calculated to evoke shocked laughs, without opening up to deeper audience.
(a) ACS
This comedy is either plain hacky, or just plain crade, calculated to provake shocked discussion, without linking deeper
message.
And comedy that backy, just plain crude, calculated provoke shocked discussion, without opening up deeper topic.
Modern comody can be deliberately hacklish, just plain crude, calculated to provoke shocked disbelicf. without opening
deeper meaning.
Simple comedy things backy, just plain crude,
away, without opening up deeper meaning.
A comedy usually ranges from hacky, just plain cnude, calculated provoke shocked surprise, without opening up deeper
reality.
(b) DMALA
Figure 13: Text Generations using ACS and DMALA. As demonstrated empirically in 2 the ACS examples demonstrate higher diversity than the DMALA generations.
29

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: in the introduction, we make four primary claims. We introduce our discrete gradient based sampler in Section 4.2 We introduce the tuning algorithm in Section 4.4
We introduce the theoretical results, along with the necessary assumptions in Section include all the experimental results RBMs, EBMs and LLMs in Section 6
We
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We include the limitations in the conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L_imitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer:
[Yes]
Justification:
We include the assumptions in Section 5 as well as in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We include lengthy appendix that details all the experimental configuration, along with the haper--paraeee parameters used.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
31

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will include link an anonomyzed repository containing all the code run the necessary experiments. All experimental results can be generated by running a bash script.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (httpss//nnis..o cc/
public/guided CodesSumisssionoollo...
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips wwtpccccccppccceeeeeeeeeeeepeeee httlc///guuieee/eeeeuuuttnn wwweeeubbmssiioooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer:
[Yes]
Justification:
We include the experimental details in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For the experimental results on RBMs, which are relatively noisy, we include the performance within standard error across different random seeds. We also include standard error measures for the text infilling experiment, For RBM training, EBM training, and EBM sampling, do not include standard error bars as these experiments not significantly affected by random seeds, at least within our observations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We include the specific GPU at the beginning of Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics battps://me
/ http://awwapp.cccoooooocccccaaaa
Answer: [Yes]
Justification: We have read the Ethics Guidelines, and our submission aligns with all the points listed.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This MCMC sampling technique which does not have direct societal impact. The research presented is either theoretical, or based on common benchmarks such as MNIST. The most relevant impact would be due to text infilling, which can used for LLMs text generation.
Justification:
33

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This foundational research that does not directly have societal impact, it is primarily an MCMC algorithm for discrete spaces.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-us, should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [No]
Justification: We were unable find the license for the datasets used. However, they fairly popular and well known datasets, and we cite the relevant paper where necessary.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
34

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, datasets.paperrstt wwppppsieiaaaae thcode com datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This research does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
There are no study participants.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
35

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "MWZPYcCAjT", "reviewer": "Reviewer_1ido", "summary": "This paper proposes a new discrete sampling method called ACS that addresses a common problem for existing gradient-based  approach where they are susceptible to becoming trapped in local modes. ACS combines local-balancing proposals with a cyclic step size to balance local exploitation and global exploration; it is in essence an extension of cyclic stochastic-gradient MCMC to discrete distributions.  To ensure proposals are still balanced with a varying step size, ACS uses a cyclic balancing\nschedule along with an automatic tuning scheme to easily adapt the schedules.  Non-asymptotic convergence guarantees are provided.  Results demonstrate ACS to outperform prior approaches for sampling from energy based models, training RBMs, and text-infilling.", "questions": "- Why is average energy in Figure 3 negative?  Also, the results for ACS on dynamic_mnist and omniglot are unexpected with better performance on fewer iterations before converging.\n- Why is the scale for average energy in Figure 3 different from that reported in Figure 4 of the [AB paper](https://openreview.net/pdf?id=lEkl0jdSb7B)?", "limitations": "Limitations are adequately discussed.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Using a cyclic step size schedule is a well motivated and effective approach for incorporating global considerations into the original local self-balancing MCMC approach presented in https://arxiv.org/pdf/2109.03867.\n- ACS is accompanied by an automated tuning scheme to make it easy to configure the two cyclic schedules.\n- Strong empirical results on EBM tasks.\n- ACS has non-asymptotic convergence guarantees.", "weaknesses": "- Experimental results for RBM have discrepancies wrt results reported in previous papers.  In particular the ranges differ for average energy from other papers and the curves for log MMD for ACS show unexpected curvature.  Please respond to the questions in the section below to clarify.\n- Inadequate discussion of text-infilling results.  It is not clear why higher perplexity and diversity is good for ACS since the goal is to be able to efficiently sample from a target discrete distribution.\n- Error bars missing for results in Figure 3 and Table 1.\n\nTypos & formatting:\n- Inline citation format should show author name\n- Figure 3 caption: cpnvergence -> convergence", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We answer your questions below.\n# Q1: Missing Error Bars, Figure 3 and Table 1\nThank you for pointing this out. For the log MMD curves for the RBM experiments in Figure 3, it should be noted that the filled in area corresponds to values within one standard error of the mean across 11 different random seeds. However, it is correct that our curves for the mixing time for deep energy based models in Figure 3 and the metrics from Table 1 do not have standard error bars. We have provided the results with error bars in our summary response, which show that our claims still hold.\n# Q2: Negative Average Energy\nThe average energy is negative due to the definition of the distribution we use. We define the target distribution as $\\pi(\\theta) = \\frac{\\exp U(\\theta)}{Z}$, where $Z$ is the partition function. The energy is $U(\\theta) = log (\\pi (\\theta)) - log Z$. Because a log probability is negative and the partition function is the sum of exponentials, which are positive, it should be the case that the energy function is negative. In contrast, [5] use the definition of the distribution from [4] for the experiments with deep energy based models as they train these models using the sampling algorithm proposed in [4]. They define the distribution as $\\pi(\\theta) = \\frac{\\exp (-U(\\theta))}{Z}$. Thus, their energy is positive.\n# Q3: Better performance with fewer iterations before converging\nHere, it should be noted that higher energy of the batch does not correspond to closeness to the target distribution. For a more in depth explanation on the difference between higher average energy and closeness to target distribution, we include a toy example in our response to Q5.\n\nThe energy decrease can be seen as the direct result of ACS being able to escape from modes quicker than other samplers — ACS is able to find very likely samples quickly, but then explores the different modes of the distribution, causing the energy to decrease.\n\nBecause the ground truth distribution in deep EBMs is unknown, we evaluate the sampling performance using average energy following the experiment in [5]. It tells us how quickly different samplers are able to reach likely modes, which gives insight into the **speed** of the various samplers. To evaluate the convergence to the target distribution, we include extensive experiments on RBMs, where it is possible to get an estimate as to how close the sampler is to the ground truth distribution via the maximum mean discrepancy to the block gibbs sampler, which takes advantage of the known architecture of an RBM. This enables us to get insight as to how **accurate** the samplers are. \n# Q4: Average Scale of energy different than AB\nThis is due to the training of the EBMs — because the EBM represents an unnormalized probability distribution, different EBMs tend to have different scales of energy, depending on the sampler used within the contrastive learning routine. [5] uses Path Auxiliary MCMC from [4], whereas we use gibbs with gradient for the models in our EBM experiment. \n# Q5: Higher perplexity and diversity in text infilling task\nWhile we include perplexity as it is a popular means of measuring language quality, this metric faces significant limitations as discussed in the literature (e.g.[6,7]). It fails to capture logical or grammatical coherence, bias towards frequent patterns, does not align with human evaluation, and cannot capture diversity. Because of this, we further include CoLA (measure the grammatical quality) and Self-Bleu (measure diversity) to comprehensively evaluate the generated sentences. The results show that ACS generations achieve better CoLA and Self-Bleu scores.\n\nFurthermore, perplexity is especially limited when trying to measure the accuracy of a sampler in regards to a target distribution. As perplexity is based on the likelihood of the generation under the language model, it does not account for diverse modes. To illustrate this point, we provide the following toy example to show the goals of obtaining the most likely generations and capturing the language model distribution are orthogonal. Similar to Figure 1, we construct a synthetic distribution of 25 modes where 1 mode is weighted heavier than the others. We provide visualizations along with a quantitative comparison of the estimated and target distributions below.\n\nTarget Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_target_dist.pdf \\\nDMALA Estimated Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_dmala_est_dist.pdf \\\nACS Estimated Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_acs_est_dist.pdf\n| Method              | Average Energy |    KL Divergence |\n| :---------------- | :-----------: | :-----------: |\n| DMALA |   $-2.66 \\pm 1.68$   | $0.70$ |\n| ACS  |   $-3.39\\pm 1.63$   | $0.13$ |\n\nDuring the sampling process, DMALA becomes stuck at the high likelihood mode, preventing the sampler from exploring the rest of the sample space. In contrast, ACS is able to visit all the modes in the distribution. This can be seen through a visual inspection of the density maps for DMALA and ACS. While DMALA ends up generating samples with higher energy, ACS estimates a distribution that is far closer to the ground truth as measured by the KL divergence. This demonstrates that generating more likely samples does not correspond to accuracy in terms of convergence to the target distribution. \n\n[1]. Annealed Importance Sampling. Technical Report 1998.\\\n[2]. Oops I Took A Gradient: Scalable Sampling for Discrete Distributions. ICML 2021.\\\n[3]. A Langevin-like Sampler for Discrete Distributions. ICML 2022.\\\n[4]. Path auxiliary proposal for MCMC in discrete space. ICLR 2022.\\\n[5]. Any-scale Balanced Samplers for Discrete Space. ICLR 2023.\\\n[6]. Lower Perplexity is Not Always Human-Like. ACL 2021\\\n[7]. Language model evaluation beyond perplexity. ACL 2021", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gWXmajgF02", "reviewer": "Reviewer_1xVN", "summary": "The paper introduces a novel method for sampling from multimodal discrete distributions, which presents an innovative approach to address the challenge of local modes trapping in gradient-based discrete sampling, together with non-asymptotic convergence guarantee and empirical validation of the proposed method.", "questions": "1. The paper mentions the proof is not consistent with the specific tuning algorithm used in the experiments. Could you elaborate on the reasons?", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method seems novel to address the challenge of sampling from multimodal discrete distributions.\n2. The hyperparameter tuning algorithm seems useful for practical use.", "weaknesses": "1. In the experiments, there seems to be no error bars in Figure 1 and Table 1. \n2. The quality of the samples seems worse than DMALA in Table 2 and Figure 12. Is it possible that the proposed method might sacrifice sample quality to achieve higher diversity?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We answer the questions below.\n\n# Q1: Error Bars Fig 1, Table 1\nFigure 1 corresponds to density estimation, where error bars would not make sense. If you are referring to Figure 3, it should be noted that the shaded area represents the range within 1 standard error of the average performance across 11 seeds for RBM sampling. For the other missing error bars, we include the updated results in the summary response, which show that our claims still hold.\n\n# Q2: Sample quality \nThe proposed ACS does not sacrifice sample quality to achieve higher diversity. It should be noted that Figure 12 does not show that ACS decreases quality — the generated sentences are reasonably fluent and comparable to those generated by DMALA. Furthermore, while our method does result in higher perplexity, which corresponds to lower likelihood under the model generations, it should be noted that we include the CoLA scores to measure the grammatical quality of the generations. As indicated by these scores, our method does not sacrifice grammatical correctness for diversity. \n\nWhile perplexity is a popular means of evaluating language generations, it is important to recognize that perplexity is based on the likelihood of the generation under the language model. This metric is biased towards frequent patterns and does not account for diverse modes. Therefore, it does not completely align with the goal of MCMC, which is to accurately characterize the target distribution. \n\nMinimizing the average perplexity of the sample corresponds to maximizing the average likelihood of the generations, which can be at odds with the goal of accurately capturing the target distribution. We illustrate this in the following experiment, where we construct a synthetic dataset of 25 modes where the top-left mode is weighted far more than all the others. Below are the anonymized links to the images for this experiment: \n\nTarget Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_target_dist.pdf \\\nDMALA Estimated Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_dmala_est_dist.pdf \\\nACS Estimated Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_acs_est_dist.pdf\n\n| Method              | Average Energy |    KL Divergence |\n| :---------------- | :-----------: | :-----------: |\n| DMALA |   $-2.66 \\pm 1.68$   | $0.70$ |\n| ACS  |   $-3.39\\pm 1.63$   | $0.13$ |\n\nThe average energy for the samples from DMALA is higher than that of ACS as DMALA ends up being trapped by the top left mode. This indicates that the samples generated by DMALA are more likely than the samples generated by ACS. However, the visualizations of the estimated distributions show that DMALA ignores the majority of the low-likelihood modes, whereas ACS is able to explore all of them. This is supported by the measured KL divergence between the estimated distribution and the target distribution. This demonstrates the disconnect between maximizing the average likelihood of the generated samples and accurately capturing the target distribution.\n# Q3: Consistency between Theory and Algorithm\n\nIn the Conclusion and Limitations section, we mention that the proof is not based on a specific tuning algorithm. This means that our theoretical analysis does not consider the effect of the tuning algorithm. If we were to take into account the hyperparameters (alpha and beta) provided by the tuning algorithm, it might be possible to make the results more tailored to practical performance. \n\nThe reason for this limitation is that conducting such a theoretical analysis is a challenging problem, as it requires analyzing an inhomogeneous Markov chain. Techniques to analyze such chains in discrete spaces, which may be applied here, are not known to us. In fact, we conjecture that any improvement on the current bound provided by us, in terms of the entire schedule, shall involve developing fundamental theory for inhomogeneous Markov chains in discrete spaces. \n\n[1]. Annealed Importance Sampling. Technical Report 1998.\\\n[2]. Oops I Took A Gradient: Scalable Sampling for Discrete Distributions. ICML 2021.\\\n[3]. A Langevin-like Sampler for Discrete Distributions. ICML 2022.\\\n[4]. Path auxiliary proposal for MCMC in discrete space. ICLR 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eBkUVBVSyz", "reviewer": "Reviewer_iri7", "summary": "The paper proposes a solution to the challenge of sampling from high-dimensional discrete spaces, where conventional discrete samplers often get trapped in local modes. To address this, the authors introduce a discrete Langevin sampler with automatic cyclical scheduling. This method comprises three components: a cyclical step size schedule, a cyclical balancing schedule, and an automatic hyperparameter tuning scheme. The authors provide theoretical guarantees for non-asymptotic convergence and inference, and extensive experiments demonstrate the method's superiority in sampling complex multimodal discrete distributions.", "questions": "- In equations 8 and 9, how do you estimate the acceptance rate A? Is it estimated by averaging across the training batch? If so, that implies the complexity would increase to n*s times compared to the original DMALA samplers at each step, where n is the number of grids for parameters \\beta_i and s is the number of sampling steps per cycle. This would be highly time-consuming.\n- Could you provide a comparison of the running times between the proposed ACS sampler and the DMALA samplers?\n- Could you elaborate on the rationale behind setting the target acceptance rate $\\rho^*$ to 0.5 in your experiments? What are the implications of setting it to 1 or 0.234 instead?", "limitations": "Despite the strong assumptions in the theoretical analysis and the perceived complexity of the algorithm, this paper presents a substantial contribution to the field by offering a well-explained, theoretically sound, and empirically validated approach to enhancing discrete sampling in high-dimensional spaces.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-motivated, and the proposed automatic cyclical scheduling method is presented clearly, making it accessible to readers. The theoretical results, which offer non-asymptotic convergence, support the method's robustness. Additionally, the empirical study is solid, with extensive experiments demonstrating the method's superiority in sampling from high-dimensional spaces.", "weaknesses": "- My primary concern lies in the complexity of the proposed methods. The automatic schedule tuning scheme appears to be quite time-consuming, particularly the grid search required for the balancing parameters \\beta_i, demanding significant computational resources.\n- Another concern pertains to the theoretical assumptions underlying the analysis. The non-asymptotic convergence of the proposed samplers relies on the strong convexity of the negative energy function, an assumption that may not hold in practical deep EBM scenarios. Despite this potentially restrictive condition, the analysis provides valuable insights, and empirically, the proposed method demonstrates effective performance, as supported by extensive studies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your supportive and valuable comments. We will address the issues you raise below. \n# Q1: Complexity of Tuning Algorithm \nIn total, the automatic tuning algorithm takes 500 sampling steps as a budget at maximum, which is much smaller when compared to the 5,000 sampling steps we use for EBM sampling and the 10,000 steps we use for RBM sampling. Furthermore, the cost of a tuning step is almost the same as a standard sampling step — as shown in Algorithm 4 and Algorithm 5, most of the additional steps for the estimation of $\\alpha_\\text{min}, \\alpha_\\text{max}$, and the $\\beta_i$ schedule are arithmetic operations that take constant time or averaging over acceptance rates that are already computed within a normal sampling step. Therefore, the tuning algorithm is neither time-consuming nor costly compared to the main sampling costs.\n# Q2: Estimation of Acceptance rate\n\nThe acceptance rate for a pair of $\\alpha, \\beta$ is calculated by averaging over the current batch for one iteration. As most MCMC algorithms run multiple chains at the same time by sampling in batches, we found that averaging over the batch for a single time step provides useful acceptance rates to use during the tuning process. For a given time step, we take the average acceptance probability as calculated by Equation 6 across the batch. Thus each tested pair of $\\alpha, \\beta$ requires only one step to estimate the acceptance rate. \n\nWhile this does mean that the complexity is $O(n * s)$, where $n$ is the number of potential $\\beta_i$ and $s$ is the number of steps per cycle, we found that the number of potential $\\beta_i$ does not have to be very large. In practice, we found that testing 5 different $\\beta_i$ for each step produces good schedules. The largest cycle length that we use in our experiments is 20 steps — this means that this step takes 100 sampling steps total, which is small compared to the total number of sampling steps of 10,000 in the RBM sampling experiment and 5,000 in the EBM sampling experiment. \n# Q3: Run Time Comparison \nWe found that using a budget of 500 sampling steps enabled the discovery of good hyper-parameter schedules. As discussed in our response to Q2, a tuning step has essentially the same cost as a sampling step. Thus the total overhead amounts to 5% of the total budget of the RBM sampling task and 10% of the total budget of the EBM task. Beyond this overhead, the run times of DMALA and ACS are the same, as both calculate the proposal function and the acceptance rate in the exact same manner. \n\nWe use the RBM sampling experiment to further compare the run times between DMALA and ACS. We we make the results available at the following link: https://anonymous.4open.science/r/neurips_rebuttal-B010/rbm_log_mmds_dmala_acs_comp_time.pdf\n\nAs visible in the results, even if we restrict ACS (including the tuning phase) and DMALA to the same total time budget of 20 seconds, we see that ACS is able to achieve a log-MMDs superior to that of DMALA. Thus even considering the overhead, our proposed sampler outperforms DMALA within a fixed time budget. \n\n# Q4: Rationale behind setting target acceptance rate\nWe base our target acceptance rate of .5 on the study done in [1], where the authors demonstrate that the ideal acceptance rate for locally balanced samplers is close to .5. Besides, .5 is also the commonly used target acceptance rate for gradient-based samplers. Therefore, we use .5 in the paper and find that it works well in practice. If we set the target acceptance rate to be close to 1, we will end up with step-sizes that are too small, resulting in insufficient exploration of the distribution. If we set the target acceptance rate to be around .234, then the sampler will end up rejecting most of the proposed movement, decreasing the efficiency of the sampler. An acceptance rate of .5 avoids either scenario, allowing for efficient and thorough characterization of the target distribution. \n\n[1]. Optimal Scaling for Locally Balanced Proposals in Discrete Spaces. NeurIPS 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PEfFvufJam", "reviewer": "Reviewer_V8nn", "summary": "The paper presents a novel gradient-based algorithm to sample from complex multimodal discrete distributions based on differentiable energy functions. Overall, the method is based on locally balanced proposals, previously introduced, and instantiates it with parametrized functions and a cyclical schedule for the \"learning rate\" that promotes the alternation of modes discovery and modes refinement. \nThe authors also provide an algorithm to automatically tune the introduced parameters based on an input acceptance rate and initial and final balancing parameters.\nThe paper features a theoretical analysis that includes concrete convergence rates under (somewhat restrictive) assumptions and finishes with some experiments in learning and sampling from RBMs and EBMs and finally in text infilling with masked language models.", "questions": "- Can you please discuss in which cases the locally concave hypothesis holds for realistic models such as LLMs? \n- Even if this is probably more of a sanity check, I'd like to see how the method behave on unimodal, or mildly multimodal distributions \n- Can you please describe some other applications of the method to real-world problems (like text infilling)", "limitations": "Partially discussed, see questions", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- to the best of my (limited) knowledge in this area, the algorithm presented in the paper seem novel and potentially quite impactful (provided the author release an \"easy-to-use\" implementation) \n- the illustrative example sets the stage nicely for the need of further development in the field of gradient-based sampling from discrete distribution and provides a very compelling visualization of the efficacy of the method. \n- the non-asymptotic bounds may offer concrete guarantees when assumptions are met.", "weaknesses": "- I think too much of the paper is in the appendix, and the information presented in the paper is not sufficient to fully follow the logical flow (see also points below). In my opinion, some details regarding the development of the method and the theory could be moved to the appendix to make more space for both preliminaries (like how are these methods used in practice) and developing more intuition.  \n- the algorithm is fairly complex and the paper fails in provide enough intuition for some parts of its functioning. Like the authors claim that \"it is fairly easy to choose initial and final balancing factors\", but do not elaborate why (in the main paper)\n- the only \"real-world\" experiment is only sketched in the main paper, not providing enough information to appreciate the task. What is the precise difficulty here? Since roberta is a masked language model I believe it is possible to derive \"pseudo-distributions\" like in [1]  \n- the theoretical analysis seems to require strong assumptions that may be violated in compelling real-world use cases (like LLMs)\n\n\n[1] Hennigen, Lucas Torroba, and Yoon Kim. \"Deriving language models from masked language models.\" arXiv preprint arXiv:2305.15501 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your supportive comments. We include our responses to your points below:\n\n# Q1: Insufficient Content in Main Body regarding Tuning Algorithm\nIn section 4.4, we first provide an intuition for our algorithm under “Main idea” and then present our algorithm by separating it into three separate components: the estimation of $\\alpha_\\text{max}$, the estimation of $\\alpha_\\text{min}$, and constructing the schedule of $\\beta_i$. Section A of the appendix provides the detailed algorithm that shows how each sub-routine works. We will move some content from the Appendix to the main body and try our best to further improve its clarity.\n# Q2: Choosing $\\beta_\\text{max}, \\beta_\\text{min}$\nIn section 4.3 where we introduce the cyclical balancing parameter schedule in lines 139-146, we have discussed that the selection of these values are dependent on the theoretical results from [1], [2], which demonstrate that when the step-size $\\alpha \\to 0$, the optimal $\\beta_\\text{min} = .5$; but when $\\alpha \\to \\infty$, the optimal $\\beta_\\text{max} = 1$. We will move the explanation of this from the Appendix to the main body.\n# Q3: Difficulty of Infilling Task\nThe difficulty of the text infilling task comes from the fact that the probability distribution is over a very large sample space due to the size of the vocabulary and the number of positions to be filled, as discussed in [3]. Furthermore, the paper you mention [4] only considers how to find the distribution of two masked tokens, whereas we mask up to 50% of the sentence. This greatly increases the complexity of the task as it exponentially increases the sample space of potential combinations.\n# Q4: Locally Concave Hypothesis in Practice\nThe locally log-concave assumption is common in both sampling and optimization literature [4], [5]. It holds on several practical discrete sampling tasks, such as Ising Models with negative definite weight matrix $W$ and Poisson distributions. \nThe locally log-concave assumption does not hold with complex models such as LLMs, since theoretical results of sampling on such models are in general difficult to obtain. Our work provides the first non-asymptotic convergence bound for gradient-based discrete samplers. We leave analysis on non log-concave distributions for future work.\nBesides, we provide extensive empirical work demonstrating that our sampler converges on models where this assumption does not hold, such as deep EBMs and LLMs.\n# Q5: Unimodal, mildly multimodal distributions\nWe demonstrate the performance of ACS on a unimodal distribution, similar to the experiment from Figure 1. We put the links for the visual results below.\n\nTarget Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/single_mode_init_dist.pdf \\\nDMALA Estimated Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/single_mode_est_dist_dmala.pdf \\\nACS Estimated Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/single_mode_est_dist_acs.pdf\n\nBelow we provide the results for DMALA and ACS on a mildly multimodal distribution, where the majority of the mass is placed on one mode.\n\nTarget Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_target_dist.pdf \\\nDMALA Estimated Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_dmala_est_dist.pdf \\\nACS Estimated Distribution: https://anonymous.4open.science/r/neurips_rebuttal-B010/slightly_multimodal_acs_est_dist.pdf\n\nWe provide quantitative results below, where we compare the KL Divergence between the estimated and true distribution. \n| Distribution              | DMALA |    ACS |\n| :-| :-: | :-: |\n| Slightly Multimodal |   $0.7011$   | $0.1250$ |\n| Unimodal  |   $0.0089$   | $0.0032$ |\n\nIn both cases, we see ACS achieves a lower KL divergence than DMALA, thus demonstrating that our proposed method is capable of capturing both a unimodal and slightly multimodal distribution.\n# Q6: Other applications of method\nIn addition to sampling from language models, we also demonstrate that our proposed sampler can be used to train deep discrete energy based models more efficiently than previous discrete samplers.\n\nWithin the domain of language modeling, there are many additional applications beyond text infilling. In work such as [7], [8], language models are framed as Energy Based Models and then sampled from in order to perform controlled generation tasks. These tasks include abductive reasoning and counterfactual story rewriting [8]; sentiment guided generation and detoxification as in [7]; and keyword generation as in [7], [8]. Given the success of applying ACS and discrete sampling to the task of text infilling, a natural step would be to investigate the application of ACS to controlled language generation.\n\nFurthermore, controlled generation is remarkably similar to language model alignment as described in [9]. One interesting direction would be to apply the discrete Energy Based Model framework to this task as a decoding time algorithm, similar to [10].\n\n[1] Informed proposals for local MCMC in discrete spaces. 2017.\\\n[2] Any-scale Balanced Samplers for Discrete Space. ICLR 2022.\\\n[3]. A Langevin-like Sampler for Discrete Distributions. ICML 2022.\\\n[4] Deriving language models from masked language models. arXiv Preprint 2023.\\\n[5] Optimization methods for large-scale machine learning. SIAM Review 2018.\\\n[6]  Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society Series B: Statistical Methodology 2017.\\\n[7] Gradient-Based Constrained Sampling from Language Models. EMNLP 2022.\\\n[8] COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamic. NeurIPS 2022.\\\n[9] Reward-augmented decoding: Efficient controlled text generation with a unidirectional reward model. EMNLP 2023.\\\n[10] Args: Alignment as reward-guided search. ICLR 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their constructive reviews. Multiple reviewers have pointed out that our results for sampling from Energy Based Models in Figure 3 and the Annealed Importance Sampling results in Table 1 do not have error bars. Below, we have provided the updated results for Table 1 and Figure 3, both of which confirm that our observations and conclusions remain valid.


Updated Figure 3 EBM Mixing Results: https://anonymous.4open.science/r/neurips_rebuttal-B010/ebm_sample_avg_iter.pdf

Updated Table 1:
| Dataset              | DMALA |    ACS |
| :---------------- | :---------: | :---------: |
| Static MNIST        |   $-80.031 \pm 0.038$   | $-79.905 \pm 0.057$ |
| Dynamic MNIST           |   $-80.120 \pm 0.036$   | $-79.634 \pm 0.024$ |
| Omniglot    |  $-99.243 \pm ​​2.101$   | $-91.487 \pm 0.128$ |
| Caltech |  $-98.001 \pm 0.371$   | $-89.262 \pm 0.290$ |


In the updated Table 1, we ran the AIS evaluation for the models trained with various samplers over 8 random seeds, and we show the mean as well as the standard error for the log likelihood over the test set. The results indicate that our proposed sampler is capable of training the models of better quality given the same computational budget. 

In the updated Figure 3, we show the area within one standard error of the mean across 11 different random seeds for each time step. Our proposed ACS has consistent performance across the datasets in terms of being able to mix in quickly. On Static MNIST, Dynamic MNIST, and Omniglot, we observe that our proposed ACS is able to consistently find high energy modes far quicker than the other methods. ACS is then able to find the less likely modes due to its ability to escape from local modes. On Caltech Silhouettes, ACS converges faster at the beginning and maintains competitive performance against the baselines. 

Finally, we would like to emphasize the key contributions of this work. There has been much work regarding the use of gradient-based discrete samplers, but not enough investigation as to how these gradient-based samplers are affected by the multi-modal nature of high dimensional discrete distributions. We demonstrate that this is a current limitation of discrete gradient-based samplers, and introduce a method that is capable of avoiding this pitfall while retaining the benefits associated with gradient information. Our work introduces cyclical step size and balancing parameter schedules with theoretical guarantees. Furthermore, our method can be automatically configured by a novel tuning algorithm with minimal overhead. We demonstrate on a synthetic highly multimodal distribution and a range of datasets that our sampler can achieve superior performance over existing methods. Given both the theoretical contributions and experimental results for our method, we believe this is a valuable contribution to the field of discrete MCMC sampling.

Meta-review: This paper proposes an automatic cyclical scheduling, designed for efficient and accurate sampling in multimodal discrete distributions. The authors prove a non-asymptotic convergence guarantee in general discrete distributions. The method is also verified by experiments.

All reviewers agree to accept this paper because (1) using a cyclic step size schedule is well motivated, (2) an automated tuning scheme is used, making it easy to configure the two cyclic schedules, (3) strong empirical results, (4) non-asymptotic convergence guarantees, etc. I agree with the opinions and recommend an accept.
Decision: Accept (poster)