← All setups

Structured Gaussian VI — Structured Gaussian Variational Inference

Descriptions may be stale. Consult the linked Lean sources.

Structured Gaussian Variational Inference · Lean proof

Structured Gaussian Variational Inference

We optimize Gaussian location m∈Rd and lower-triangular scale C∈Rd×d with positive diagonal and prescribed row supports of size at most w. For a differentiable potential V:Rd→R, define F(m,C)=E[V(m+Cξ)]−∑i=1dlog⁡Cii, where ξ∼N(0,Id) is standard Gaussian. The gradient of V is L-Lipschitz and μ-strongly monotone, with 0<μ≤L. A given feasible pair (m0,C0) lies within Euclidean–Frobenius distance R≥0 of a minimizer. The oracle returns ∇V(x) at x. For ε>0, the goal is a feasible output (m¯,C¯) with EP[F(m¯,C¯)−minF]≤ε, where the minimum is over feasible pairs and P is the law of algorithm randomness.

Let d,w∈{0,1,2,…}, and equip Rd with its Euclidean inner product and norm. For each i∈{1,…,d}, the prescribed support Si satisfies i∈Si⊆{1,…,i},|Si|≤w. Define the structured scale family by CS={C∈Rd×d:Cii>0 for every i,Cij=0 whenever j∉Si}. The optimization problem is minm∈Rd, C∈CSF(m,C). The expectation defining F uses independent standard normal coordinates of ξ. The algorithm receives d,w,(Si)i=1d,L,μ,R,ε,m0,C0, where m0∈Rd and C0∈CS.

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 (Attainment and initial distance). There exists (m⋆,C⋆)∈Rd×CS such that F(m⋆,C⋆)≤F(m,C)for every (m,C)∈Rd×CS,∥m0−m⋆∥2+∥C0−C⋆∥F2≤R2, where ∥C∥F2=∑i=1d∑j=1dCij2 is the squared Frobenius norm.

Queries may be made at any x∈Rd. After the allotted oracle calls, the output (m¯,C¯) must be measurable and satisfy C¯∈CS for every realization. For every minimizing pair (m⋆,C⋆)∈Rd×CS, its objective gap must be integrable under P and satisfy EP[F(m¯,C¯)−F(m⋆,C⋆)]≤ε.

Proved result

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

OracleTemplate.Convergence LongTails.Setups.StructuredGaussianVariationalInference.spec
  OracleTemplate.StructuredGaussianVariational.StructuredGaussianVI.budget

Relevant previous results

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