← All setups

Reparameterized Gaussian VI — Gaussian Variational Inference

Descriptions may be stale. Consult the linked Lean sources.

Gaussian Variational Inference · Lean proof

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⋆)]≤ε.

Proved result

max{1,⌈(2+3⋅d+8⋅log⁡(48⋅Lμ))⋅(26⋅L⋅Rμ⋅ε+32⋅d⋅Lμ⋅ε)⌉+}

OracleTemplate.Convergence LongTails.Setups.GaussianVariationalInference.spec
  OracleTemplate.GaussianVariational.ReparameterizedGaussianVI.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.