← All setups

Structured Gaussian Variational Inference

Descriptions may be stale. Consult the linked Lean sources.

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

Results

On Rd, V is differentiable, ∇V is L-Lipschitz and μ-strongly monotone, 0<μ≤L. Fix Si⊆{1,…,i} containing i, with |Si|≤w. The family GS has Cii>0 and Cij=0 outside Si. A family minimizer λ⋆=(m⋆,C⋆) exists, λ0∈GS, and ∥m0−m⋆∥2+∥C0−C⋆∥F2≤R2, R≥0. With exact pointwise ∇V access, the target is E[F(λ^)−F(λ⋆)]≤ε, ε>0, where F(m,C)=Eξ∼N(0,Id)V(m+Cξ)−∑ilog⁡Cii. Row (1) constructs single-sample masked proximal SGD with a weighted-average output; the setup imposes no algorithm restriction. Distance comparisons use εd=2ε/μ: row (1) implies this distance target, whereas a distance guarantee alone does not imply the KL target.

Sufficient budgets for structured Gaussian variational inference under the StructuredGaussianVariationalInference setup.
Result Oracle complexity Novelty Limitations
(1) StructuredGaussianVI (Ours) (⋆⋆⋆) (review) O(1+(1+w+log⁡(1+dκ))×(LRμε+dLμε)) gradient calls; sufficient for KL accuracy.
(2) (Kim et al. 2025), Thm. 3.2, Cor. 3.3, Prop. 3.4; mean-field, Gaussian base O(1+κ2(1+log⁡d)×(Qεd+Q(1+log+⁡R2)εd)) gradient calls; last-iterate distance. Requires twice differentiable V. (1): worst-case statistical dependence κ instead of κ2, up to logarithms, when startup is dominated. Scope: arbitrary S, only C1,1. Output: averaged KL guarantee. (1): polynomial R startup instead of logarithmic. If trΣ⋆≍d/L, statistical overhead can reach 1+log⁡(dκ)1+log⁡d.
(3) (Kim et al. 2025), Thm. 3.2, Prop. 3.4; mean-field Gaussian, constant ∇2V O(1+κ2[Q/εd+Q/εd(1+log+⁡R2)]) gradient calls; last-iterate distance. (1): for V(x)=μ2∥x∥2+L−μ2d(1Tx)2, κ≤d+1, κ≫1+log⁡(dκ), R≤dμεd, εd(1+log+⁡R2)2≤d/μ: total O(1+dκ[1+log⁡(dκ)]μεd) versus O(1+dκ2μεd); averaged KL additionally. (1): can lose 1+log⁡(dκ) when κ≲1+log⁡d; worse startup dependence.
(4) (Ko et al. 2025), Thm. 3; coupled target, N=M=1 O(1+dκ2(Q/εd+1)⋅[1+log+⁡(R2/εd)]) gradient calls; last-iterate distance. Here d∗=d for every pattern. (1): worst-case statistical saving about dκw+1+log⁡(dκ), ignoring the additional accuracy logarithm, when statistical terms dominate; averaged KL additionally.

Abbr: κ=L/μ; log+⁡t=max{0,log⁡t} for t>0, with log+⁡0=0; Σ⋆=C⋆C⋆T; z¯=arg⁡minV; Q=∥m⋆−z¯∥2+trΣ⋆. In (5), Ln is the smoothness of Vn, κn=Ln/μ, Qn=∥m⋆,n−z¯n∥2+∥C⋆,n∥F2, z¯n is a stationary point of Vn, and d∗ is the maximum number of base coordinates entering one component. N is the number of components, M the sample batch size, and dz,dy the global and local block dimensions.

StructuredGaussianVariationalInference (continued).
Result Oracle complexity Novelty Limitations
(5) (Ko et al. 2025), Thm. 3; decomposed V=∑n=1NVn, M=1 O(1+[N2(d∗+1)⋅∑n=1Nκn2(Qn/εd+1)+Nκ]⋅[1+log+⁡(R2/εd)]) component-gradient calls; last-iterate distance. Bordered block-diagonal families have d∗=dz+dy. (1): averaged KL guarantee. No established complexity improvement on decomposable targets; different primitive oracles. (1): may lose when d∗ and component κn are small; no component-subsampling guarantee.
(6) Repository full-rank result (ReparameterizedGaussianVI 2026); Si={1,…,i}, w=d O(1+(1+d+log⁡κ)×(LRμε+dLμε)) gradient calls; KL accuracy. (1): scope extends to every sparse Cholesky family, with its own minimizer. Matches known rate at w=d. Earlier unpublished repository result.

Abbr: κ=L/μ; log+⁡t=max{0,log⁡t} for t>0, with log+⁡0=0; Σ⋆=C⋆C⋆T; z¯=arg⁡minV; Q=∥m⋆−z¯∥2+trΣ⋆. In (5), Ln is the smoothness of Vn, κn=Ln/μ, Qn=∥m⋆,n−z¯n∥2+∥C⋆,n∥F2, z¯n is a stationary point of Vn, and d∗ is the maximum number of base coordinates entering one component. N is the number of components, M the sample batch size, and dz,dy the global and local block dimensions.

Kim, Kyurae, Yi-An Ma, Trevor Campbell, and Jacob R. Gardner. 2025. Nearly Dimension-Independent Convergence of Mean-Field Black-Box Variational Inference. https://doi.org/10.48550/arXiv.2505.21721.
Ko, Joohwan, Kyurae Kim, Woo Chang Kim, and Jacob R. Gardner. 2025. Provably Scalable Black-Box Variational Inference with Structured Variational Families. https://doi.org/10.48550/arXiv.2401.10989.
ReparameterizedGaussianVI: Full-Rank Gaussian Variational Inference. 2026. Unpublished Lean theorem in the longtails repository, commit f11d79619482528aec230ba6b3d65088f9c8ae06. https://github.com/k3nfalt/longtails/blob/f11d79619482528aec230ba6b3d65088f9c8ae06/LongTails/Theorems/ReparameterizedGaussianVI.lean.

Lean setup