Concentration of tempered posteriors and of their variational approximations

1.1. Motivation

• Theoretical guarantees for variational Bayes remain limited: earlier results do not directly cover high-dimensional or nonparametric models, and one PAC-Bayesian approach requires bounded losses.The paper notes that these limitations obstruct direct application when the log-likelihood is unbounded.Source: §1.1 · p. 2
• The paper extends fractional-posterior concentration analysis to variational approximations and gives a condition under which they concentrate at the same rate as the fractional posterior.Fractional posteriors replace the likelihood L(θ) by L(θ)^α for 0 < α < 1.Source: §1.1 · p. 2

1.2. Definitions and notations

• The variational approximation is defined as the projection of the fractional posterior onto a predefined family F using Kullback-Leibler divergence.The fractional posterior is presented as the ideal estimator for comparison.Source: §1.2 · p. 4
• For the variational family F to concentrate near the true parameter, it must contain distributions concentrated around that parameter; families that are too small are insufficient.The choice of F therefore influences approximation quality.Source: §1.2 · p. 4
• The applications include Gaussian approximations for logistic regression, mean-field approximations for matrix completion, and a nonparametric density-estimation example.For matrix completion, the approximation concentrates at the minimax-optimal rate.Source: §1.2 · pp. 4–5

2.1. A PAC-Bayesian inequality

• The PAC-Bayesian result can also study MAP- or MLE-centered approximations, although some models lack defined MAP or MLE estimators while posterior and VB approximations remain consistent.Source: §2.1 · p. 6

2.2. Concentration of VB approximations

• When F contains all probability distributions, the variational approximation equals the tempered posterior and recovers its risk bound; for α = 1/2, concentration can be stated using Hellinger distance.Source: §2.2 · pp. 6–7
• VB concentration requires the approximation family F to contain distributions near the truth; prior mass alone is insufficient when F is restricted, and εn is a concentration rate when 1/n ≪ εn ≪ 1.The paper extends the usual prior-mass condition with an explicit condition on F.Source: §2.2 · p. 7

2.3. A simpler result in expectation

• The assumptions can be simplified by giving a result in expectation rather than a concentration result.Source: §2.3 · p. 8

2.4. Extension of the result in expectation to the misspecified case

• When the best-fitting model has small KL risk, the misspecified-case oracle inequality remains informative, and the paper gives a nonparametric example attaining the minimax rate.The inequality is not sharp because its left- and right-hand risk measures differ.Source: §2.4 · p. 9

3. Gaussian variational Bayes

• Gaussian VB recasts integration as finite-dimensional optimization, trading approximation accuracy against computational complexity; under a likelihood assumption, integrated α-Rényi divergence converges for most Gaussian approximations.Source: §3 · p. 9

3.1. Stochastic variational Bayes

• For nonconjugate models, the method optimizes a full Gaussian using a covariance factor C and Monte Carlo stochastic gradients over a bounded parameter set; its stated guarantee assumes convexity and Lipschitz gradients.Source: §3.1 · p. 10
• For the stochastic-gradient approximation, T = O(√n) is suggested to mitigate its effect on the convergence rate.Source: §3.1 · p. 11

3.2. Example: logistic regression

• Binary logistic regression is nonconjugate and remains challenging when the dictionary is large.Source: §3.2 · p. 11
• For X1 uniform on the unit sphere, K1 ≤ 2 and K2 ≤ 4, and these terms do not deteriorate the parametric convergence rate d/n.Source: §3.2 · p. 12

4.1. Context

• Matrix-completion theory gives a minimax rate of (m+p)rank(M)/n, possibly up to log terms, but consistency for practical Gaussian priors and their variational approximations was open.Earlier posterior results cited here excluded the Gaussian prior used in practice or concerned a truncated posterior.Source: §4.1 · p. 13

4.2. Definition of the prior and of the VB approximation

• The prior factorizes M into U and V with Gaussian entries and inverse-gamma scale parameters; conjugacy permits conditional posterior calculations and Gibbs sampling.For large datasets, the cited work proposes a mean-field variational approximation.Source: §4.2 · p. 13

4.3. Concentration of the posteriors

• The theorem requires a small prior parameter b, but the paper does not claim its displayed choice is optimal and points to cross-validation for tuning.The authors note that a small b is important for approximating low-rank matrices.Source: §4.3 · pp. 14–15
• Under bounded-entry truth, clipping draws from the Gaussian variational posterior gives an effective procedure with a Frobenius-norm bound; the squared-Frobenius minimax rate is r(m + p)/n, up to possible log terms.The bounded-entry condition is that the true matrix entries have known bound C.Source: §4.3 · p. 15
• For M = ŪV̄ᵀ with factors in M(r, B), Theorem 4.3 gives a concentration result under the stated factor constraints.The factors have bounded entries and zero rows after index r.Source: §4.3 · pp. 14–15

5.3. Nonparametric rates of convergence

• For f0 in a Sobolev ellipsoid, the analysis gives estimation at the minimax rate up to log terms; Theorem 5.1 is stated asymptotically.The cited minimax rate is for squared L2 loss, and the paper notes the additional logarithmic factor.Source: §5 · p. 16, §5.3 · pp. 17–18

5. Nonparametric regression estimation

• Fourier projections with model selection yield an adaptive estimator that does not require knowing r or C to compute it.The paper describes model selection here as a variational approximation that places all posterior mass on one model.Source: §5 · p. 16

5.1. Construction of the prior

• The prior is described as assigning enough mass to neighborhoods of f0 to ensure consistency.Source: §5.1 · p. 16

5.2. Construction of the variational approximation

• The variational family restricts candidate functions to finite Fourier expansions with independent Gaussian coefficients and a shared variance, addressing the intractability of the full posterior.The family is the union over finite model sizes K.Source: §5.2 · pp. 16–17

6. Conclusion

• The generic PAC-Bayesian method studies concentration of variational Bayesian approximations, with applications including logistic regression, matrix completion, and density estimation.The conclusion leaves open whether an oracle inequality can compare Kullback-Leibler divergence on both sides rather than using Rényi divergence on the left.Source: §6 · p. 18
• Later extensions cover hidden-variable models and α = 1, but the latter results require stronger assumptions and do not generally extend to misspecified cases [40].Source: §6 · p. 18
• Choosing α remains open: cross-validation is computationally expensive and has no known theoretical guarantees, while online adaptive tuning is not established for this setting.Source: §6 · p. 18
• Removing the extra logarithmic factor in the rates remains an open question; adapting Catoni’s localization technique to this setting is not direct.Source: §6 · p. 19

7.1. Proof of Theorem 2.1

• Theorem 2.1’s proof restricts attention to parameters with finite Rényi divergence by renormalizing the prior; infinite-divergence cases make the bound trivial.Source: §7.1 · pp. 19–21

7.2. Proof of Theorem 2.4

• Theorem 2.4’s proof combines a Chebyshev bound with Corollary 2.3 using a union bound, then invokes assumptions on ρ_n.Source: §7.2 · pp. 21–22

7.3. Proof of Theorem 2.6

• Theorem 2.6’s proof uses Fubini’s theorem and Lemma 2.2, then applies Jensen’s inequality.Source: §7.3 · pp. 22–23

7.4. Proof of Theorem 3.1

• Theorem 3.1’s proof checks likelihood-term KL bounds and computes the KL divergence between the pseudo-posterior approximation and prior to estimate the rate.Source: §7.4 · pp. 23–24

7.5. Proof of Theorem 3.2

• Theorem 3.2’s proof treats Algorithm 1 as online gradient descent and uses a regret bound; its argument also applies Jensen’s inequality.Source: §7.5 · p. 25

7.6. Proof of Corollary 3.3

• Corollary 3.3’s proof verifies that the log-likelihood is 2∥X∥-Lipschitz, satisfying Assumption 3.1.Source: §7.6 · p. 25

7.7. Proof of Corollary 3.4

• For Corollary 3.4, the proof checks convexity and gradient regularity, and the constraint contains the Gaussian distribution used in the proof when ψ ≤ σ² = 1.Source: §7.7 · p. 26

7.8. Consistency of variational approximations in a model where the MAP and the MLE are not defined

• The toy example establishes that a variational approximation can be consistent even when the MLE and MAP are undefined; the tempered posterior is also consistent in this case.Source: §7.8 · p. 30

7.8.1. Description of the model

• The example uses a model with θ = (m, σ²) ∈ R × (0, 1), with m ∼ N(0, 1) and σ² uniformly distributed on (0, 1).Source: §7.8.1 · p. 30

7.8.2. Non-existence of the MLE

• In this model, the likelihood makes the MLE undefined, and the MAP does not exist either.Source: §7.8.2 · p. 30

7.8.3. A variational approximation family

• The variational family consists of uniform distributions over rectangles [a − c, a + c] × [b − d, b], smoothing large likelihood variations around each observation.Source: §7.8.3 · pp. 30–31

7.8.4. Proof of Proposition 7.1

• In the proposition proof, choosing δ = 1/(2n) allows use of (1 − δ) > 1/2 to simplify the bound.Source: §7.8.4 · p. 32

7.9. Proof of Theorem 4.1

• The proof notes that the perturbed matrix factorization belongs to the variational family F.Source: §7.9 · p. 33
• Choosing δ = B/[8(nmp)²] bounds the perturbed factorization’s Frobenius error by the reference error plus B/n.Source: §7.9 · p. 33
• After assembling the bounds, the proof applies Theorem 2.6.Source: §7.9 · p. 35

• For every M, boundedness of M0 gives dα,σ(M, M0) ≥ dα,σ(clipC(M), M0).Source: §7.10 · p. 35
• With N = clipC(M), the squared difference (Ni,j − (M0)i,j)2/(2σ2) is bounded above by 2C2/σ2.Source: §7.10 · p. 36
• Substituting the derived bound into (7.4) gives the result claimed in the proof.Source: §7.10 · p. 36

• The proof sets (m1, . . . , mK) equal to (β1, . . . , βK).Source: §7.11 · p. 37
• The proof invokes the condition f0 ∈ W(r, C2) to obtain a bound by C2.Source: §7.11 · p. 37
• Choosing K = ⌈(n/ log(n))1/(2r+1))⌉ leads to the result of the theorem.Source: §7.11 · p. 37