Source-linked AI summary
Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring
Sungjin Ahn, Anoop Korattikara, Max Welling
TL;DR
The paper asks whether Bayesian posteriors can be approximately sampled while accessing only small mini-batches, given SGLD’s slow mixing. It proposes SGFS, which combines stochastic-gradient Langevin updates, estimated Fisher information, and Bayesian asymptotics to move between efficient optimization, Gaussian approximation, and increasingly accurate posterior sampling. The method is useful within the stated trade-off, but its guarantees and Gaussian approximation depend on assumptions and settings that can fail.
Problem
The problem is to approximately sample a Bayesian posterior while touching only a small mini-batch for each generated sample, improving on SGLD’s slow mixing.
Method
SGFS combines stochastic gradients in the Langevin equation with subsampling-noise estimation and an inverse Fisher-information preconditioner.
Results
SGFS uses large stepsizes for Fisher-scoring-like burn-in and Gaussian-approximation sampling, then smaller annealed stepsizes to behave like preconditioned SGLD and approach the true posterior.
Takeaways & Limitations
SGFS provides an anytime trade-off: faster mixing with Gaussian approximation at larger stepsizes and more accurate, slower sampling of non-Gaussian structure after annealing.
Takeaways & Limitations
The method’s Gaussian approximation can fail when Bernstein-von Mises conditions are violated, and convergence claims rely on annealing schedules or fixed preconditioners.
Abstract
from arXiv · showhide
In this paper we address the following question: Can we approximately sample from a Bayesian posterior distribution if we are only allowed to touch a small mini-batch of data-items for every sample we generate?. An algorithm based on the Langevin equation with stochastic gradients (SGLD) was previously proposed to solve this, but its mixing rate was slow. By leveraging the Bayesian Central Limit Theorem, we extend the SGLD algorithm so that at high mixing rates it will sample from a normal approximation of the posterior, while for slow mixing rates it will mimic the behavior of SGLD with a pre-conditioner matrix. As a bonus, the proposed algorithm is reminiscent of Fisher scoring (with stochastic gradients) and as such an efficient optimizer during burn-in.
1. Motivation
Bayesian methods must work with rapidly growing datasets and small data access per update. SGFS addresses SGLD’s slow mixing by combining stochastic-gradient sampling with Fisher-scoring structure.
- Bayesian methods face a computational challenge as datasets grow exponentially, while stochastic gradient descent can make useful predictions sooner than MCMC produces one burn-in sample.The motivation emphasizes efficiency in bits learned per unit of computation.
- SGLD uses mini-batch stochastic gradients to sample from the posterior at O(n) cost with n ≪ N, but its mixing rate is unnecessarily slow.The stated explanation is SGLD’s lack of a proper pre-conditioner.
- SGFS uses stochastic gradients in a Fisher-scoring-style sampler, while subsampling randomness helps produce posterior samples near the mode.This also makes the method an efficient optimizer during burn-in.
2. Preliminaries
The paper formulates Bayesian posterior sampling for an i.i.d. dataset using a parameterized model and prior, then introduces score gradients and Fisher information. Under regularity conditions and large sample sizes, the posterior concentrates near the true parameter and is approximately Gaussian.
- The model uses N i.i.d. data-points, a parameter θ ∈ R^D, and prior p(θ) to define the posterior p(θ|X_N) ∝ p(X_N|θ)p(θ).
- The true data-generating parameter is θ_0, and each data-point contributes a score gradient g_i(θ)=∇_θ log p(θ;x_i).
- For a batch of n data-points, G_n(θ;X_r) sums the individual score gradients.
- The Fisher information is the covariance of score gradients, equivalently the negative expected Hessian of the log likelihood.
- The n-data-point Fisher information is I_n=nI_1, while empirical Fisher information from a batch consistently estimates I_1 at θ_0.
- As N becomes very large, the Bernstein–von Mises theorem gives p(θ|{x_1...x_N}) approximately as N(θ_0,I_N^-1), under suitable regularity conditions.
3. Stochastic Gradient Fisher Scoring
SGFS combines SGLD-like behavior at small step sizes with Gaussian-posterior sampling at large step sizes, using stochastic-gradient Fisher information to support efficient updates and optimization.
- Method: SGFS starts from SGLD but addresses its low mixing rate by combining it with a Markov chain that samples a Gaussian posterior approximation at arbitrary step sizes.The Gaussian approximation is motivated by the Bernstein-von Mises regime for large datasets.
- Fisher estimation: The method estimates Fisher information online from mini-batch score covariances, and the estimate converges to the Fisher information with O(1/N) corrections under posterior sampling.The online update uses κ_t = 1/t.
- Low-step-size regime: At small step sizes, SGFS becomes SGLD with preconditioning matrix B^-1, preserving the connection to stochastic-gradient Langevin sampling.The matrix B is required to be symmetric positive-definite.
- High-step-size regime: At large step sizes, SGFS samples correctly when the posterior is Gaussian, provided the injected-noise covariance is positive-definite and the preconditioner is symmetric.The algorithm avoids Metropolis-Hastings accept/reject steps in this regime.
- Scope and limitation: If Bernstein-von Mises conditions fail and the posterior is non-Gaussian, accurate sampling requires a small step size; slowly annealing the step size offers an anytime strategy.The paper notes that convergence of the fully adaptive chain is not proved, although fixed-preconditioner annealed SGFS inherits SGLD's convergence result.
- Optimization and sampling: SGFS is a stochastic Fisher-scoring optimizer during burn-in and switches to posterior sampling at the appropriate statistical precision scale.Choosing B ∝ I_N makes the updates especially reminiscent of Fisher scoring while requiring only small mini-batches.
4. Computational Efficiency
The method’s computational cost is driven by matrix operations in the parameter dimension, with alternatives that reduce cost through low-rank identities, factorization, or blockwise approximations.
- 4. Computational Efficiency: O(D3) per iteration arises from computing and inverting a D × D matrix, then multiplying its inverse by the mean gradient.When n < D, the Sherman-Morrison-Woodbury equation reduces this to O(nD2).
- 4. Computational Efficiency: Updating Cholesky factors provides a more numerically stable alternative to the Sherman-Morrison-Woodbury implementation.
- 4. Computational Efficiency: O(kd3) complexity is achievable by factoring the Fisher information into k independent blocks of variables of size d.Treating every parameter independently yields a diagonal Fisher-information approximation.
5. Experiments
Experiments evaluate SGFS against SGLD, SGD, and HMC on logistic regression, neural networks, and discriminative RBMs. Across these settings, SGFS combines accurate posterior estimates with favorable mixing and competitive predictive performance.
- 5.1. Logistic Regression: SGFS-f closely matched HMC marginal posterior contours in logistic regression even at the largest stepsize, while SGFS-d underestimated variance there.With smaller stepsizes, SGFS-d becomes similar to SGLD and is guaranteed to sample correctly, though with lower mixing rate.
- 5.1. Logistic Regression: SGFS-f had not reached its error floor within the allowed runtime, while SGLD required lower mixing rates to avoid large approximation bias.SGFS-d reached its covariance error floor but continued to perform well for the mean; the comparison also favored SGFS over HMC and SGLD.
- 5.2. SGFS on Neural Networks: On the HHP dataset, SGFS prevented overfitting like SGLD, and SGFS marginally outperformed both SGD and SGLD with the best regularizer.SGFS-d achieved leaderboard error 0.4635, comparable to the milestone winner's 0.4632.
- 5.3. Discriminative Restricted Boltzmann Machine (DRBM): On KDD99, SGFS-f avoided sharply declining non-Gaussian regions that caused SGLD to be catapulted away, producing contours comparable to variability among HMC runs.At equal mixing rate, SGLD incurred significantly larger approximation bias than SGFS-f for DRBM.
6. Conclusions
SGFS uses stochastic gradients, central-limit-theorem noise estimates, and an inverse Fisher information preconditioner to approximately sample Bayesian posteriors. With annealing, it transitions from Fisher-scoring optimization through Gaussian posterior sampling toward increasingly accurate posterior sampling.
- SGFS combines subsampling noise, artificial noise, and an estimated inverse Fisher information matrix to approximately sample from the posterior.Its stochastic gradients and central-limit-theorem approximation estimate the noise induced by subsampling.
- SGFS uses large stepsizes for efficient Fisher-scoring-like burn-in, then samples from the asymptotic Gaussian posterior approximation after reaching the mode.
- Further stepsize annealing makes SGFS behave like preconditioned SGLD and generate increasingly accurate samples from the true posterior.Smaller stepsizes capture more non-Gaussian structure but reduce mixing speed.