← All setups

Gaussian Variational Inference

Descriptions may be stale. Consult the linked Lean sources.

Gaussian Variational Inference

We minimize the Gaussian variational objective F(m,C)=E[V(m+Cξ)]−∑i=1dlog⁡Cii over m∈Rd and lower triangular C∈Rd×d with positive diagonal, where ξ∼N(0,Id). The differentiable potential V:Rd→R has an L-Lipschitz, μ-strongly monotone gradient, with 0<μ≤L. A given feasible pair (m0,C0) is within Euclidean–Frobenius distance R≥0 of a minimizer (m⋆,C⋆). The oracle returns ∇V(x) at x. For ε>0, the goal is a measurable feasible output (m¯,C¯) with integrable gap satisfying E[F(m¯,C¯)−F(m⋆,C⋆)]≤ε.

Let d≥0 be an integer, equip Rd with its Euclidean inner product and norm, and write ∥⋅∥F for the Frobenius norm. Define Cd={C∈Rd×d:Cij=0 for i<j, Cii>0 for every i}. The coordinates of ξ are independent standard normal random variables. With the objective F defined above, the problem is minm∈Rd, C∈CdF(m,C). The algorithm receives d,L,μ,R,ε,m0,C0, where 0<μ≤L, R≥0, ε>0, and C0∈Cd.

Our assumptions:

Assumption 1 (Smoothness and strong monotonicity). The potential V is differentiable everywhere. For every x,y∈Rd, ∥∇V(x)−∇V(y)∥≤L∥x−y∥,⟨∇V(x)−∇V(y),x−y⟩≥μ∥x−y∥2.

Assumption 2 (Minimizer and initial distance). There exists (m⋆,C⋆)∈Rd×Cd such that F(m⋆,C⋆)≤F(m,C)for all m∈Rd, C∈Cd,∥m0−m⋆∥2+∥C0−C⋆∥F2≤R2.

Queries may be made at any x∈Rd. The oracle returns ∇V(x) at x. The Gaussian expectation defining F is over ξ; output expectations are under P, the law of the algorithm’s randomness. After the allotted oracle calls, the output (m¯,C¯) must be measurable and satisfy C¯∈Cd for every realization. Its objective gap must be integrable under P, and the required accuracy is EP[F(m¯,C¯)−F(m⋆,C⋆)]≤ε.

Results

Differentiable V:Rd→R has L-Lipschitz gradient and μ-strongly monotone gradient, 0<μ≤L. A Cholesky minimizer (m∗,C∗) exists; C0 is lower triangular with positive diagonal and ∥m0−m∗∥2+∥C0−C∗∥F2≤R2. Exact pointwise ∇V access; target E[F(m^,C^)−F∗]≤ε, ε>0. The setup imposes no algorithm restriction.

Gaussian variational inference: GaussianVariationalInference.
Result Oracle complexity Novelty Limitations
(1) ReparameterizedGaussianVI (Ours) (⋆⋆⋆) (review) O(1+(1+d+log⁡κ)(LRμε+dκε)) gradient calls.
(2) Proximal SGD (Kim et al. 2023), Thm. 7 O(1+d[κ2+L2(∥z¯−m∗∥2+trΣ∗)με]ℓ) gradient calls; last-iterate squared distance ≤2ε/μ. (1): Worst-case statistical term d2κ2/ε becomes (d+log⁡κ)dκ/ε; gain when trΣ∗≍d/μ and startup does not dominate. KL implies distance. (1): Weighted average replaces last iterate. Polynomial startup can lose when μR2/ε≫κℓ+d/ε; near trΣ∗≍d/L, no statistical gain is established.
(3) Price estimator (Kim et al. 2026), Thm. 3.3 O(1+dκε+dκ3/2ε(1+log+⁡(κμR2))+κ2ℓ) gradient–Hessian evaluations; μEW22≤ε. (1): Gradient-only access replaces C⊤∇2V, requiring a Hessian or d Hessian-vector products per step; expected KL instead of Wasserstein distance. (1): Leading iteration cost is about d times larger when statistical terms dominate and log⁡κ≲d. Different oracles and accuracy criteria preclude total-cost dominance.
(4) (Park et al. 2026), Thm. 4.1 O((dκ+λH2d3ε)(1+log⁡(Δ0/ε))) gradient calls, including calibration and batches. (1): Scope: no Lipschitz Hessian required. On overlap, smaller statistical term when λH2d≫κ(1+log⁡κ/d), subject to initialization and logarithms. (1): Loses accelerated cost on nearly constant Hessians, especially Gaussian targets. (4) requires Lipschitz Hessian, ∥C0∥F2≤d/μ, and ε≤Δ0.

Abbr: F(m,C)=Eξ∼N(0,Id)V(m+Cξ)−∑ilog⁡Cii; F∗=F(m∗,C∗); κ=L/μ; Σ∗=C∗C∗⊤; z¯=arg⁡minV; ℓ=1+log+⁡(μR2/ε); log+⁡t=max{0,log⁡t} (zero at t=0); W2 is Wasserstein distance; λH=LH/μ3/2 for Hessian Lipschitz constant LH; Δ0=F(m0,C0)−F∗+μ(∥m0−m∗∥2+∥C0−C∗∥F2)/2.

Kim, Kyurae, Qiang Fu, Yi-An Ma, Jacob R. Gardner, and Trevor Campbell. 2026. Stochastic Gradient Variational Inference with Price’s Gradient Estimator from Bures–Wasserstein to Parameter Space. https://doi.org/10.48550/arXiv.2602.18718.
Kim, Kyurae, Jisu Oh, Kaiwen Wu, Yi-An Ma, and Jacob R. Gardner. 2023. On the Convergence of Black-Box Variational Inference. https://doi.org/10.48550/arXiv.2305.15349.
Park, Jaesung R., Uijeong Jang, and Yifan Chen. 2026. Acceleration and Its Limits in Gaussian Variational Inference. https://doi.org/10.48550/arXiv.2610.21020.

Lean setup