Convergence of Proximal-Gradient Stochastic Variational Inference under Non-Decreasing Step-Size Sequence

Mohammad Emtiyaz Khan, Reza Babanezhad, Wu Lin, Mark Schmidt, Masashi Sugiyama

Abstract

Several recent works have explored stochastic gradient methods for variational inference that exploit the geometry of the variational-parameter space. However, the theoretical properties of these methods are not well-understood and these methods typically only apply to conditionally-conjugate models. We present a new stochastic method for variational inference which exploits the geometry of the variational-parameter space and also yields simple closed-form updates even for non-conjugate models. We also give a convergence-rate analysis of our method and many other previous methods which exploit the geometry of the space. Our analysis generalizes existing convergence results for stochastic mirror-descent on non-convex objectives by using a more general class of divergence functions. Beyond giving a theoretical justification for a variety of recent methods, our experiments show that new algorithms derived in this framework lead to state of the art results on a variety of problems. Further, due to its generality, we expect that our theoretical analysis could also apply to other applications.

Introduction

Variational Inference (VI) is a cornerstone of Bayesian machine learning, used to approximate complex posterior distributions. However, practitioners often face a frustrating trade-off: standard Stochastic Gradient (SG) methods are flexible but ignore the underlying geometry of the probability space, leading to slow convergence. Conversely, Natural Gradient methods exploit this geometry but are typically restricted to "conditionally-conjugate" models. For non-conjugate models, such as Gaussian Processes with non-Gaussian likelihoods, natural gradients become computationally prohibitive. This paper introduces PG-SVI to bridge this gap, providing a method that is fast, flexible, and theoretically sound.

Methodology

The authors propose Proximal-Gradient Stochastic Variational Inference (PG-SVI). The core innovation involves splitting the Evidence Lower Bound (ELBO) into a "difficult" non-conjugate term and an "easy" conjugate term. The difficult term is linearized and optimized using stochastic gradients, while a general divergence function—rather than standard Euclidean distance—is used to penalize step size. This allows the algorithm to respect the curvature of the parameter space (e.g., via KL divergence).

PG-SVI demonstrates superior efficiency and robustness to step size compared to standard gradient descent (GD) and other variants.

Crucially, for many models like Gaussian Processes, this setup results in closed-form updates, eliminating the need for expensive inner optimization loops.

Experimental Evaluation

The framework was evaluated on Binary Gaussian Process (GP) Classification using the Sonar, Ionosphere, and USPS datasets, as well as Correlated Topic Modeling (CTM) on the NIPS and Associated Press (AP) datasets. Baselines included standard SGD and adaptive methods like ADAM and Adagrad.

Results and Discussion

PG-SVI consistently outperformed baselines in both speed and stability. In GP classification experiments, PG-SVI converged in fewer than 10 passes through the data, whereas standard SGD and ADAM often required over 100 passes to reach comparable performance.

Comparison of PG-SVI against standard stochastic optimizers across three datasets, showing significantly faster convergence in both ELBO (Negative Lower Bound) and Test Log-Loss.

The proximal-gradient approach also allowed for larger step sizes without divergence. In CTM tasks, PG-SVI achieved better negative log-likelihoods faster than specialized methods like the Delta or Laplace methods, without requiring their specific Taylor series approximations.

Conclusion

This work provides the first formal convergence-rate analysis for this class of geometric optimization methods, proving an $O(1/t)$ rate even for non-convex objectives. While step-size tuning remains a practical challenge, PG-SVI represents a significant step forward in making geometry-aware variational inference applicable to a broader range of complex models.

Summary updated

Abstract

Several recent works have explored stochastic gradient methods for variational inference that exploit the geometry of the variational-parameter space. However, the theoretical properties of these methods are not well-understood and these methods typically only apply to conditionally-conjugate models. We present a new stochastic method for variational inference which exploits the geometry of the variational-parameter space and also yields simple closed-form updates even for non-conjugate models. We also give a convergence-rate analysis of our method and many other previous methods which exploit the geometry of the space. Our analysis generalizes existing convergence results for stochastic mirror-descent on non-convex objectives by using a more general class of divergence functions. Beyond giving a theoretical justification for a variety of recent methods, our experiments show that new algorithms derived in this framework lead to state of the art results on a variety of problems. Further, due to its generality, we expect that our theoretical analysis could also apply to other applications.
BibTeX
@inproceedings{khan2016convergence,
  author = {Mohammad Emtiyaz Khan and Reza Babanezhad and Wu Lin and Mark Schmidt and Masashi Sugiyama},
  title = {{Convergence of Proximal-Gradient Stochastic Variational Inference under Non-Decreasing Step-Size Sequence}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=M-uWB5Fgpx},
}
Figure