Bhar et al. (2023) — ARXIV-2311.03496
Key takeaways
Proposes a gossip-based asynchronous distributed Bayesian learning algorithm where only two agents communicate per cycle (via a Poisson-clock gossip protocol) and each active agent performs T local ULA MCMC steps between communications. Provides theoretical convergence guarantees showing that consensus and KL divergence from the true posterior both vanish asymptotically at the same polynomial rate as canonical synchronous distributed ULA, while yielding faster initial convergence.
- Theorem 1. Consensus error E[||x_i^k - x_j^k||^2] = O(k^{-delta_alpha}) for all agent pairs i,j Holds when: Requires aT < p_m/(nL); same polynomial decay rate as canonical synchronous distributed ULA regardless of T; only the constant factor improves with larger T
- Theorem 2. KL divergence KL(rho_k || pi) = O(k^{-delta_alpha}) where pi is the true posterior Holds when: Proved via log-Sobolev inequality and Fokker-Planck analysis; convergence rate dominated by step-size annealing exponent delta_alpha, independent of T
What the evidence does not cover
- Both active agents in a gossip cycle must agree on and synchronize the same step size alpha_k and number of local steps T; allowing different values for the two agents breaks convergence guarantees.
- Asymptotic convergence rate is the same polynomial O(k^{-delta_alpha}) as canonical ULA regardless of T; only the constant and initial-phase speed improve.
- The constraint aT < p_m/(nL) means that safely increasing T requires a proportionally smaller step size, partially offsetting the gains from more local steps.
- The algorithm is analyzed and evaluated only for logistic regression and shallow Bayesian models; extension to deep neural network posteriors is not addressed.
Standing in the anthology
Read — the reading is NOTE-120. Arrived in the imported batch, which brought in the Langevin branch, where the training noise is the sampler.