Gurbuzbalaban et al. (2024) — ARXIV-2412.01993
Key takeaways
Proposes generalized EXTRA SGLD, a decentralized Bayesian sampling algorithm that eliminates the persistent network-induced bias present in standard DE- SGLD algorithms in the full-batch setting. Provides non-asymptotic convergence bounds in 2-Wasserstein distance that improve on prior DE-SGLD bounds by a factor of at least L^2 (the smoothness coefficient squared).
- Proposition 5 (complexity comparison). Generalized EXTRA SGLD achieves an O(L^2) improvement in iteration complexity over DE-SGLD in 2-Wasserstein distance Holds when: Full-batch or large-batch gradient regime; strongly convex and L-smooth objectives; comparison holds for the same step size eta and same network topology
- Theorem 4 (geometric convergence). W_2(rho_k, pi)^2 <= C * (1 - ceta)^k + O(eta * sigma^2 + eta^2 * L^2) Holds when: Geometric (linear) convergence in 2-Wasserstein distance to a neighborhood of size O(etasigma^2 + eta^2*L^2); neighborhood does not shrink to zero — persistent bias proportional to step size remains
What the evidence does not cover
- Analysis requires strongly convex and smooth component functions; non- convex posteriors are not covered.
- The correction step requires storing an extra momentum-like variable per agent, doubling memory relative to DE-SGLD.
- Convergence neighborhood does not shrink to zero; a persistent bias proportional to the step size and mini-batch noise remains.
- Assumes a connected, fixed network topology with a doubly stochastic weight matrix.
Standing in the anthology
Read — the reading is NOTE-141. Arrived in the imported batch, which brought in the Langevin branch, where the training noise is the sampler.