Source-linked AI summary
On the properties of variational approximations of Gibbs posteriors
Pierre Alquier, James Ridgway, Nicolas Chopin
TL;DR
The paper tackles the computational difficulty of Gibbs posteriors, whose usual MCMC approximations can be too slow for large datasets. It studies Variational Bayes approximations, develops fast algorithms and empirical bounds, and finds that under suitable KL control they often preserve convergence rates across several learning tasks.
Problem
Gibbs posteriors have strong PAC-Bayesian guarantees but are difficult to implement efficiently, while MCMC can be too slow for large datasets.
Method
The paper studies Variational Bayes approximations of Gibbs posteriors, develops practical algorithms, and derives theoretical and empirical bounds.
Results
Variational approximations often do not deteriorate the Gibbs procedure’s convergence rate across classification, ranking, and matrix-completion settings.
Takeaways & Limitations
The results support using VB as a fast alternative to Monte Carlo methods for approximating Gibbs posteriors.
Takeaways & Limitations
The exposition restricts the margin-assumption analysis to κ = 0 and κ = 1, and regression with unbounded risk is left for future work.
Abstract
from arXiv · showhide
The PAC-Bayesian approach is a powerful set of techniques to derive non- asymptotic risk bounds for random estimators. The corresponding optimal distribution of estimators, usually called the Gibbs posterior, is unfortunately intractable. One may sample from it using Markov chain Monte Carlo, but this is often too slow for big datasets. We consider instead variational approximations of the Gibbs posterior, which are fast to compute. We undertake a general study of the properties of such approximations. Our main finding is that such a variational approximation has often the same rate of convergence as the original PAC-Bayesian procedure it approximates. We specialise our results to several learning tasks (classification, ranking, matrix completion),discuss how to implement a variational approximation in each case, and illustrate the good properties of said approximation on real datasets.
1. Introduction
The paper addresses the practical difficulty of using Gibbs posteriors by studying fast variational approximations and their theoretical and empirical properties.
- Gibbs posteriors provide PAC-Bayesian distributions for random estimators with sharp guarantees without requiring a specific data-generating model.
- MCMC sampling is often difficult to implement efficiently and too slow for large datasets.
- The paper studies Variational Bayes approximations as faster alternatives to sampling from Gibbs posteriors.
- Variational approximation preserves the convergence rate when the posterior–approximation KL divergence is appropriately controlled.
- The paper provides empirical bounds and applies the general results to classification, convex classification, ranking, and matrix completion.
2. PAC-Bayesian framework
The PAC-Bayesian framework combines risks, priors, and pseudo-posteriors to obtain prediction bounds under concentration assumptions.
- The framework compares a risk R(θ) with its empirical counterpart r_n(θ), both typically constructed from a loss function.
- A prior probability measure π is defined on the predictor parameter space Θ.
- The pseudo-posterior minimizes an oracle-inequality upper bound and can yield predictors through averaging or sampling.
- Hoeffding-type assumptions support slow convergence rates, whereas Bernstein-type assumptions may support fast convergence rates.
- Integrated Hoeffding inequalities can accommodate uniformly bounded losses or certain unbounded losses under sufficiently light-tailed priors.
- The exposition focuses on κ = 0 and κ = 1 rather than the more general margin-assumption inequalities.
3. Numerical approximations of the pseudo-posterior
The paper contrasts Monte Carlo sampling with tractable variational families, defining VB approximations through KL minimization and discussing practical optimization methods.
- Monte Carlo: Tempering SMC samples sequentially from Gibbs posteriors at increasing inverse temperatures and serves as the numerical gold standard.
- Monte Carlo: Monte Carlo methods can be too slow when datasets, parameter dimensions, or predictor computations are large, motivating deterministic VB approximations.
- Variational Bayes: The VB approximation minimizes the KL divergence between distributions in F and the pseudo-posterior.
- Variational Bayes: VB restricts optimization to a tractable family F intended to remain close to the Gibbs posterior while keeping computation feasible.
- Variational Bayes: Mean field VB uses product probability measures and can be optimized through successive fixed-point updates.
- Risk guarantees: The paper derives risk bounds when the approximation family satisfies a condition ensuring the variational risk is not worse than the pseudo-posterior risk.
4. General results
The paper develops general risk and oracle inequalities for variational approximations of Gibbs posteriors under Hoeffding and Bernstein assumptions. These results show when variational approximations can match Gibbs-posterior convergence rates, provided an appropriate KL-divergence condition holds.
- The general results establish risk bounds for variational approximations under either Hoeffding or Bernstein assumptions and relate them to Gibbs-posterior bounds.
- 4.1.1. Empirical bounds: The empirical bounds apply to both the pseudo-posterior and its variational approximation, but do not by themselves provide convergence rates.These bounds can be computed from the data and therefore provide a way to evaluate the corresponding procedures.
- 4.1.2. Oracle-type inequalities: The oracle inequalities compare the variational approximation's risk with the best possible risk or aggregation procedure and yield explicit rate expressions in specialized models.
- 4.1.2. Oracle-type inequalities: If the Gibbs posterior achieves rate s_n and some ρ in the variational family satisfies K(ρ, π_λ)/λ ≤ c s_n, then the variational approximation also achieves rate s_n.
- 4.2. Bounds under the Bernstein assumption: Under the Bernstein assumption, replacing R(·) with R(·)−R yields better convergence rates in the corresponding oracle inequality.
5. Application to classification
The classification application develops Gaussian variational approximations to Gibbs posteriors, derives risk bounds under margin-related assumptions, and evaluates mean-field and full-covariance variants empirically. The full-covariance approximation generally matches or exceeds SMC and kernel-SVM performance while computing faster than SMC.
- Theoretical analysis: Under Mammen–Tsybakov’s margin assumption, the Bernstein assumption holds with g(λ, n) = Cλ^2 2n−λ.This margin condition is used to obtain improved classification rates.
- Model and variational families: Linear classification uses Gaussian priors and Gaussian variational families, including mean-field and full-covariance approximations.The optimization problem is non-convex but remains feasible; the approximation families satisfy F1 ⊂ F2 ⊂ F3 ⊂ M1.
- Theoretical analysis: Assumption A1 controls disagreement probabilities between normalized linear classifiers, and it is satisfied when X/∥X∥ has a bounded density on the unit sphere.Without A1, the Gibbs posterior and its variational approximation may have very different shapes.
- Theoretical analysis: Under Assumption A1 and the margin assumption, variational approximations on F1, F2, or F3 achieve a rate in d log(n)/n.The bound uses λ = 2n C+2 and an optimizing prior variance ϑ = d/(d + 2 + 2d/n); d/n is minimax-optimal in this context.
- Implementation and numerical results: The full-covariance optimization may be more severely multimodal because F3 has larger dimension; reparameterization and deterministic annealing are recommended.The reparameterization reduces the optimization dimension to O(n).
- Implementation and numerical results: Full-covariance VB performs as well as or better than SMC and SVM except on Glass, while being much faster to compute than SMC.Mean-field VB performs poorly on some datasets, such as Indian, possibly because its approximation family is too small or optimization is strongly multimodal.
6. Application to classification under convexified loss
The section replaces the nonconvex 0–1 classification loss with the convex hinge loss and studies the resulting variational approximation. Under Gaussian-prior and bounded-design conditions, the approximation retains the preceding oracle rate while enabling iteration-wise error control.
- Convexified classification: The hinge-loss formulation turns variational inference into a convex minimization problem, enabling broader optimization methods and finite-iteration error bounds.The corresponding bound can be evaluated after a prescribed number of solver iterations.
- Theoretical conditions: Under the Gaussian prior and bounded-design conditions, the prior variance must remain suitably constrained relative to λ.The section states that the prior variance cannot be taken too large compared with λ.
- Theoretical conditions: The oracle inequality for the hinge-loss variational approximation has the same convergence rate as the corresponding result in the preceding section.This preserves the rate while using the convexified loss.
- Optimization guarantees: Theorem 6.3 supports computing the number of optimization iterations needed to reach a specified error level at a specified probability.The guarantee applies to the VB measure after the kth iteration of an optimal convex solver.
- Numerical application: On average, hinge-loss variational approximations achieve lower misclassification error than the 0–1-loss approach in the reported comparison.The text attributes the comparison to the fact that the 0–1-loss maximum is not guaranteed to be attained.
7. Application to ranking
The ranking application models pairwise ordering with AUC-related risk and applies variational approximations under Hoeffding- and Bernstein-type conditions. Hinge-loss convexification yields a convex optimization route, while stochastic descent provides practical computation and empirical bound monitoring.
- Ranking formulation: The ranking task assigns larger scores to objects more likely to have label 1, rather than merely classifying individual objects.The section uses linear classifiers and a pairwise ranking criterion.
- Theoretical assumptions: The Hoeffding-type analysis uses f(λ, n) = λ^2 n^-1, while the Bernstein-type analysis uses g(λ, n) = Cλ^2 n^-1−4λ under a margin assumption.These assumptions provide the concentration conditions used for the ranking bounds.
- Variational approximation: The ranking bounds are derived for Gaussian-prior variational families including the mean-field family F1.The empirical-bound analysis considers variational parameters m and σ^2.
- Convexified ranking: AUC ranking can be convexified with the hinge loss, producing a convex minimization problem without requiring assumption (A2).The convexified formulation parallels the classification treatment.
- Algorithms and numerical results: Stochastic descent estimates the gradient from sampled data pairs, making the procedure applicable to the Adult dataset with 193,829,520 pairs.The reported Pima and Adult experiments reached convergence in a few iterations and produced acceptable bounds.
8. Application to matrix completion
The matrix-completion application studies a nonparametric mean-field variational family for a factorized matrix model with a hierarchical prior. Although no theoretical Gibbs-estimator result is available in the considered model, the framework transfers any established PAC-Bayesian rate to the variational approximation.
- Problem and approximation family: Matrix completion is useful here because the approximation family is a product of independent components rather than a parametric family.The paper states that this setting lacks a known theoretical result for the Gibbs estimator in the considered model.
- Problem and approximation family: The model observes noisy matrix entries and uses quadratic risk for predicting the underlying matrix.The matrix is represented through a factorization M = UV^T.
- Prior specification: The hierarchical prior assigns Gaussian distributions to factor columns with inverse-gamma-distributed variance hyperparameters.The hyperparameters γ_j are independently drawn from an inverse gamma distribution.
- Theoretical implication: If a PAC-Bayesian bound gives a convergence rate for the Gibbs estimator, the same rate holds for the variational approximation.Thus a future proof that the Gibbs estimator is minimax-optimal up to logarithmic terms would transfer that property to VB.
- Algorithm: The mean-field VB algorithm iterates the variational-update equation, producing Gaussian factors for the first two components and an inverse-gamma factor for the third.The update structure follows from the specified factorized approximation.
9. Discussion
The paper reports that VB approximations preserve Gibbs-posterior convergence rates in several scenarios and provides practical computation and empirical evaluation. It identifies regression as an important extension requiring more technical analysis because the risk may be unbounded.
- VB approximations do not deteriorate the convergence rate of the corresponding Gibbs-posterior procedure in several important scenarios.
- The paper describes fast algorithms for computing VB approximations and empirical bounds for evaluating their performance.
- The authors recommend VB as the default way to approximate Gibbs posteriors instead of Monte Carlo methods.
- Regression remains future work because its risk function is not bounded, making the approach less direct to apply.
A.2. Proof of the theorems in Subsection 4.1
The proofs in this subsection apply the standard PAC-Bayesian strategy to derive high-probability inequalities uniformly over distributions and then specialize them using variational approximations.
- The proof begins by applying Fubini’s theorem to the first PAC-Bayesian inequality.
- Expectation bounds are converted into probability statements using E[exp(U)] ≥ P(U > 0).
- The arguments establish inequalities holding simultaneously for all ρ ∈ M1 with probability at least 1 − ε.
- The approximation is handled by taking ˜ρλ as the member of F minimizing its KL divergence to the Gibbs posterior ˆρλ.
A.3. Proof of Theorem 4.3 (Subsection 4.2)
The proofs for the fast-rate theorem combine concentration inequalities, variance or margin assumptions, and distributional constructions that control approximation complexity.
- Theorem 4.3: The proof of Theorem 4.3 applies Fubini’s theorem and inequality (10) to derive the first bound, then treats a second inequality separately.
- Theorem 4.3: The two inequalities are combined with a union bound to obtain a statement holding simultaneously for all ρ ∈ M1 with probability at least 1 − ε.
- Ranking: The ranking proof uses Hoeffding decomposition together with Hoeffding’s inequality for iid random variables.
- Ranking: For another ranking bound, the proof uses Bernstein’s inequality after defining the relevant centered pairwise quantity.
- Matrix completion: For matrix completion, the proof constructs distributions around factorized matrices and bounds their KL divergence through a neighborhood set Gδ.
B. Implementation details
The implementation section describes tempering SMC, deterministic annealing, and stochastic gradient methods for approximating or optimizing the relevant objectives. Figure 2 compares deterministic annealing with direct L-BFGS optimization across repeated initializations.
- Tempering SMC: Tempering SMC uses N particles, an ESS threshold τ, a random-walk tuning parameter κ, and an adaptive temperature sequence from λ0 = 0 to λT = λ.
- Tempering SMC: The algorithm outputs a weighted sample approximately distributed as the target posterior and an unbiased estimator of its normalizing constant ZλT.
- Resampling: Systematic resampling samples U uniformly on [0, 1] and returns particle indices based on normalized weights.
- Deterministic annealing: Deterministic annealing solves a sequence of local optimization problems with increasing temperatures, starting from an exactly solvable γ = 0 problem.
- Deterministic annealing: In Figure 2, deterministic annealing’s empirical bound is compared with direct L-BFGS optimization from prior-drawn starting values over 20 repetitions.
- Deterministic annealing: The reported Figure 2 result is that deterministic annealing solutions are on average lower than randomly initialized optimization solutions.