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

Kyurae Kim, Yian Ma, Jacob R. Gardner

TL;DR

This paper proves that Black-Box Variational Inference (BBVI), specifically using the "sticking-the-landing" (STL) estimator, can achieve linear convergence rates under ideal conditions. This is a significant theoretical advancement, offering a more efficient convergence guarantee than previously established for BBVI, and provides a more rigorous comparison with existing methods.

What Problem Does This Paper Address?

Black-Box Variational Inference (BBVI) is a powerful technique for approximating complex probability distributions, widely used in machine learning. However, understanding its computational properties, particularly its convergence rate, has been a recent area of research. While BBVI has been shown to converge at a sublinear rate (specifically, $O(1/T)$), a key theoretical question remained: can BBVI achieve a faster, "linear" (geometric) convergence rate, similar to what's seen in some optimization algorithms? This paper tackles this question, aiming to establish linear convergence for BBVI and provide a clear comparison between different gradient estimators.

Methods

The authors leverage the "Quadratic Variance" (QV) condition, a framework for analyzing the convergence of stochastic gradient descent (SGD) methods. They prove that the sticking-the-landing (STL) estimator satisfies this condition, which, under certain assumptions (like a perfectly specified variational family), directly implies linear convergence for BBVI. A key contribution is a new, more efficient parameterization for the scale matrix in the variational family, using triangular matrices, which leads to a faster projection operator ($O(d)$ complexity compared to $O(d^3)$). They also provide improved theoretical bounds for the "closed-form entropy" (CFE) estimator, enabling a fairer comparison with STL.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • STL Achieves Linear Convergence: The paper provides the first theoretical proof that BBVI with the STL estimator can achieve linear convergence, a significant improvement over previous sublinear guarantees. This is achieved by showing STL satisfies the quadratic variance condition.
  • Misspecification Matters, But STL Still Behaves Well: The analysis extends to misspecified variational families, showing that the Fisher-Hyvärinen divergence quantifies the STL estimator's behavior, offering insights into why STL might perform differently in practice.
  • Efficient Parameterization is Key: The introduction of a triangular scale parameterization for the variational family is crucial. It not only simplifies computations but also leads to a more efficient projection operator, making BBVI more practical.
  • Fairer Comparisons: By improving the theoretical bounds for the CFE estimator, the paper allows for a more direct and rigorous comparison between CFE and STL, clarifying their relative strengths and weaknesses.

Key Results

  • Linear Convergence for STL: Under a perfectly specified variational family, BBVI with STL achieves a convergence rate of $O(d\kappa^2 \log(1/\epsilon))$, where $\kappa$ is the condition number of the posterior. This translates to a computational complexity of $O(d\kappa^2 \log(1/\epsilon))$.
  • Improved CFE Bounds: The paper provides tighter constants for the gradient variance bounds of the CFE estimator, making theoretical comparisons with STL more robust.
  • Efficient Projection: A new triangular scale parameterization leads to an $O(d)$ projection operator, a significant improvement over previous $O(d^3)$ methods.

Limitations and Future Work

  • Worst-Case Scenarios: The authors acknowledge that their upper bounds might be loose due to considering extreme worst-case scenarios where gradients are anti-correlated. They suggest that finding tighter bounds by ruling out these cases is a direction for future work.
  • Model Misspecification: While the paper analyzes misspecification, it notes that interpreting the Fisher-Hyvärinen divergence can be challenging. Further work could explore more intuitive characterizations of misspecification effects.
  • Comparing Control Variates: The paper suggests it would be interesting to analyze and compare other existing control variate methods for BBVI.

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. We also improve existing analysis on the regular closed-form entropy gradient estimators, which enables comparison against the STL estimator and provides explicit non-asymptotic complexity guarantees for both.
BibTeX
@inproceedings{kim2024linear,
  author = {Kyurae Kim and Yian 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},
}

Loading related content...

Figure