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