Markov chain Monte Carlo is one of the most useful tools for obtaining samples from complex distributions, such as posterior distributions in Bayesian inference. Bouncy particle sampler (BPS) is a method that performs sampling using uniform linear motion and elastic collisions. Since BPS does not require time discretization, it is expected to be more advantageous than the widely used Hamiltonian Monte Carlo (HMC) and Langevin Monte Carlo (LMC) for distributions with large curvature changes. To sample more efficiently from multimodal distributions, we propose BPS with parallel tempering (BPS-PT) in the infinite exchange limit, based on LMC-PT with the infinite exchange rate proposed in a previous study. Using a distribution with large curvature changes, BPS-PT showed estimation accuracy comparable to HMC-PT and LMC-PT, and achieved higher ESS per computational time. Therefore, BPS-PT is considered to be effective for distributions with large curvature changes.
Figures & tables
Figure 1: We show a trajectory of a particle generated by the BPS algorithm in a potential of the normal distribution. The particle bounces at t=t1,t2,t4 and randomly changes its velocity at t=t3 .
HMC-PT
LMC-PT
BPS
BPS-PT
Optimization [sec]
6.3×102
1.18×103
-
1.09×103
Sampling [sec]
1.44×102
1.93×102
5×10
1×102
Table 1: Computation times of MGC are shown. The number of samples were 104 for BPS-PT and 105 for the other methods, respectively. To match the optimization time, the episode length for the policy gradient of BPS-PT is 1/10 of that of HMC-PT and LMC-PT. The optimization time and sampling time are the average of 5 and 10 runs, respectively.
HMC-PT
LMC-PT
BPS
BPS-PT
ESS
2×10−4
0.2
1.0
1.0
W1
0.5
0.35
0.8
0.34
KLD
4×10−2
1.3×10−1
∞
2×10−4
estimate of a
2.2×10−2
5.5×10−1
0.7
3.0×10−1
Table 2: Performance metrics of MGC are shown. To match the computation times, BPS-PT used 104 samples and the other method used 105 samples, respectively. Since no transitions between two circumferences occurred by BPS, the KLD is infinity although sample means of a was 0.7 .
Figure 2: 2D histograms of samples obtained by each method. To match the computation times, the number of samples was set to 104 for BPS-PT, and 105 for the others. Compared to the histogram obtained from the target pdf, each method had a following drawback. (a) exhibited anisotropy. (b) concentrated in the inner circumference than the outer one, which was opposite from the target pdf. (c) had no samples from the inner circumference. (d) had 1/10 samples per computation time.
HMC-PT
LMC-PT
BPS
BPS-PT
Optimization [sec]
8×10
4×102
-
2.2×102
Sampling [sec]
6×10
7.6×10
1.00×102
6.4×102
Table 3: Computation times of MNF are shown. The number of samples were 106 for all methods. To match the optimization time, the episode length for the policy gradient of BPS-PT is 1/10 of that of HMC-PT and LMC-PT. The optimization time and sampling time are the average of 5 and 10 runs, respectively.
HMC-PT
LMC-PT
BPS
BPS-PT
ESS
1×10−4
2×10−4
3×10−4
4×10−2
W1
17
5
4
5
KLD
2.7×10−3
2.2×10−5
2.7×10−6
1.5×10−4
estimate of a
3.3×10−1
3.0×10−1
3.0×10−1
2.9×10−1
Table 4: Performance metrics of MNF are shown. BPS-PT used 105 samples and the other methods used 106 samples to match computation times.
Figure 3: 2D histograms of samples obtained by each method. To match the computation times, the number of samples was set to 105 for BPS-PT, and 106 for the others, respectively. Compared to the histogram obtained from the target pdf, the horizontal spread ( x1 ) is narrower for all methods. The peaked part in the vertical direction ( x2 ) is reproduced more closely to the target pdf by BPS and BPS-PT than by HMC and LMC.
HMC-PT
LMC-PT
BPS
BPS-PT
tuning [sec]
1.09×102
1.43×102
-
2.43×102
sampling [sec]
1.36×102
1.21×102
8.1×10
1.21×103
Table 5: Computation time of GMM are shown. The number of samples were 106 for all methods. To match the optimization time, the episode length for the policy gradient of BPS-PT is 1/10 of that of HMC-PT and LMC-PT. The optimization time and sampling time are the average of 5 and 10 runs, respectively.
HMC-PT
LMC-PT
BPS
BPS-PT
ESS
8×10−4
6.4×10−2
5.8×10−1
3×10−4
W1
3.35×10
3.59×10
6.4×10
3.30×10
KLD
4.9×10−4
2.7×10−2
3.9
2.3×10−2
Table 6: Performance metrics of GMM are shown. To match calculation times, BPS-PT used 105 samples and the other method used 106 samples, respectively.
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. · Department of Statistics and Data Science, Yale University. · Department of Mathematics, Duke University. +1
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. · Department of Statistics and Data Science, Yale University. · Department of Mathematics, Duke University. +1