Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?

Kyurae Kim, Yi-An Ma, Jacob R. Gardner

Abstract

We prove that black-box variational inference (BBVI) with control variates, particularly the sticking-the-landing (STL) estimator, converges at a geometric (traditionally called “linear”) rate under perfect variational family specification. In particular, we prove a quadratic bound on the gradient variance of the STL estimator, one which encompasses misspecified variational families. Combined with previous works on the quadratic variance condition, this directly implies convergence of BBVI with the use of projected stochastic gradient descent. For the projection operator, we consider a domain with triangular scale matrices, which the projection onto is computable in $\theta(d)$ time, where $d$ is the dimensionality of the target posterior. We also improve existing analysis on the regular closed-form entropy gradient estimators, which enables comparison against the STL estimator, providing explicit non-asymptotic complexity guarantees for both.

Introduction

Variational Inference (VI) is a cornerstone of modern Bayesian machine learning, used to approximate complex posterior distributions by optimizing the Evidence Lower Bound (ELBO). "Black-Box" VI (BBVI) simplifies this process by using stochastic gradient descent (SGD) to optimize the ELBO, requiring only the ability to evaluate the gradient of the log-posterior.

However, BBVI has historically been limited by the convergence speeds of stochastic optimization. Because it relies on stochastic gradients, it typically inherits the sub-linear convergence rates of SGD—often $O(1/T)$ for strongly convex problems. In the broader optimization literature, the "gold standard" is linear convergence ($O(\log 1/\epsilon)$), which is significantly faster. To achieve this in a stochastic setting, the gradient variance must vanish as the algorithm approaches the optimum—a property known as the "interpolation condition." This paper investigates whether the "Sticking-the-Landing" (STL) estimator, a popular control variate technique, can unlock this linear convergence rate.

The Sticking-the-Landing (STL) Estimator

The STL estimator is a variance reduction technique that modifies the standard reparameterization gradient. It functions by "stopping" the gradient from propagating through the entropy term of the ELBO. While empirically successful, its theoretical properties regarding convergence rates remained largely unproven until now.

STL as an Interpolator

The core contribution of this work is the proof that when the variational family is perfectly specified—meaning it contains the true posterior—the STL estimator satisfies the interpolation condition. In this scenario, the noise in the stochastic gradient disappears at the optimum, allowing the algorithm to achieve deterministic-like speeds. This effectively moves BBVI from a complexity of $O(1/\epsilon)$ to $O(\log(1/\epsilon))$, representing a massive theoretical speedup for high-precision applications.

Theoretical Framework and Misspecification

The authors utilize a Quadratic Variance (QV) framework to bound the expected squared norm of the gradients. This framework allows for a rigorous analysis of both well-specified and misspecified models.

In the case of misspecification—where the true posterior lies outside the chosen variational family—the linear convergence rate is lost, and the speed reverts to the standard sub-linear $O(1/T)$. The authors demonstrate that the residual variance in these cases is directly proportional to the Fisher-Hyvärinen divergence between the variational family and the true posterior. This provides a clear geometric interpretation of the "cost" of using an inadequate variational family.

Computational Efficiency: Triangular Parameterization

Beyond the convergence rates, the paper introduces a practical improvement for high-dimensional VI. Standard BBVI often requires expensive projection steps during optimization, particularly when dealing with scale matrices. Previous methods using matrix square-root parameterizations required $O(d^3)$ time for projections.

This work proposes a new parameterization using triangular scale matrices (Cholesky factors). They derive a projection operator for this domain that runs in $\Theta(d)$ time. This reduction from cubic to linear complexity relative to the dimensionality ($d$) makes high-dimensional BBVI significantly more computationally feasible.

Key Results and Complexity

The paper establishes several non-asymptotic complexity guarantees:

  • Linear Convergence: For a $d$-dimensional strongly log-concave posterior, BBVI with STL finds parameters $\epsilon$-close to the optimum in $O(d \kappa^2 \log(1/\epsilon))$ iterations, where $\kappa$ is the condition number.
  • Tightness: The authors established matching lower bounds for the STL variance, proving that their analysis is essentially tight.
  • CFE Comparison: The authors also sharpened the constants for the Closed-Form Entropy (CFE) estimator, allowing for the first rigorous theoretical comparison between CFE and STL.

Limitations and Future Directions

While this work provides a major theoretical leap, several constraints remain:

  1. Realizability: The linear convergence guarantee is contingent on perfect model specification.
  2. Log-Concavity: The proofs rely on the target posterior being strongly log-concave, an assumption that may not hold in complex, non-convex landscapes.
  3. Gap in Bounds: A small constant factor gap (approximately 4) exists between the upper and lower bounds due to potential "anti-correlated" gradient scenarios, suggesting room for even more refined analysis.

In conclusion, this research provides the first rigorous justification for the efficiency of the STL estimator, demonstrating that with the right control variates and parameterization, Black-Box Variational Inference can be far faster than previously assumed.

Summary updated

Abstract

We prove that black-box variational inference (BBVI) with control variates, particularly the sticking-the-landing (STL) estimator, converges at a geometric (traditionally called “linear”) rate under perfect variational family specification. In particular, we prove a quadratic bound on the gradient variance of the STL estimator, one which encompasses misspecified variational families. Combined with previous works on the quadratic variance condition, this directly implies convergence of BBVI with the use of projected stochastic gradient descent. For the projection operator, we consider a domain with triangular scale matrices, which the projection onto is computable in $\theta(d)$ time, where $d$ is the dimensionality of the target posterior. We also improve existing analysis on the regular closed-form entropy gradient estimators, which enables comparison against the STL estimator, providing explicit non-asymptotic complexity guarantees for both.
BibTeX
@inproceedings{kim2024linear,
  author = {Kyurae Kim and Yi-An Ma and Jacob R. Gardner},
  title = {{Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=8UjE8j8zm0},
}
Figure