A provably convergent alternating minimization method for mean field inference

Pierre Baqué, Jean-Hubert Hours, François Fleuret, Pascal FuaarXiv 2015 · arXiv

Abstract

Mean Field inference is a cornerstone of Bayesian machine learning, yet its standard "alternating minimization" algorithm lacks a formal proof of convergence and can theoretically fall into infinite loops. This paper introduces a proximal regularization term—specifically a KL divergence between successive steps—that guarantees convergence to a critical point while preserving the "closed-form" update math that makes the method so popular in practice.

Introduction

In Bayesian inference, calculating the posterior distribution $P$ is often mathematically intractable. Variational Inference (VI) addresses this by approximating $P$ with a simpler distribution $Q$, typically chosen from a family of independent variables known as the "Mean Field." The objective is to find a $Q$ that is as close to $P$ as possible by minimizing their Kullback-Leibler (KL) divergence.

The standard approach to this minimization is coordinate descent: fixing all variables except one, updating it, and iterating through the set. While computationally efficient and easy to implement, the underlying optimization landscape is non-convex. In such environments, standard coordinate descent can oscillate or loop endlessly between local minima without ever settling on a single point. This paper addresses this "conceptual weakness" in the field by providing a formal guarantee of convergence.

Methodology: Proximal Alternate Minimization

The authors propose a Proximal Alternate Minimization algorithm. The core innovation is the addition of a proximal regularization term to each optimization step.

Proximal Regularization

Instead of simply minimizing the KL divergence at each step, the algorithm minimizes the KL divergence plus a penalty term $\lambda l(q, q^t)$. This penalty is defined as the KL divergence between the current distribution and the distribution from the previous iteration. This term effectively "leashes" the variables, preventing drastic jumps and dampening potential oscillations that plague standard methods.

Preserving Closed-Form Updates

A significant challenge in optimization is that adding complexity to an objective function often destroys the ability to solve it analytically. However, by selecting a KL-based penalty, the authors derived a new update rule that remains in closed form. This ensures that the algorithm remains as computationally efficient as the standard, unregularized version, making it a drop-in replacement for existing implementations.

The Kurdyka-Łojasiewicz (KL) Property

To prove convergence in a non-convex setting, the authors utilize the Kurdyka-Łojasiewicz (KL) property. This mathematical framework analyzes the behavior of functions near critical points. By proving that the Mean Field objective function is a real analytic function, the authors satisfy the necessary conditions to apply the KL framework and guarantee that the sequence of distributions actually settles.

Theoretical Results

The paper is primarily theoretical, focusing on mathematical proofs rather than empirical benchmarks.

Guaranteed Convergence

The authors formally prove that the sequence of distributions generated by the Proximal Alternate Minimization algorithm converges to a first-order critical point. This is a crucial distinction from standard methods where only the objective value (the loss) is known to decrease, while the variables themselves might oscillate forever.

Convergence Rates

Using the KL inequality, the authors derived asymptotic convergence rates. They demonstrate that if the Hessian matrix (the matrix of second derivatives) is positive definite at the local minimum, the algorithm achieves a linear convergence rate. This provides a theoretical expectation for how quickly the model will reach its final state.

Discussion and Limitations

The primary strength of this work is the bridge it builds between the practical efficiency of Mean Field inference and the rigorous requirements of optimization theory. By choosing a penalty parameter $\lambda$ that is sufficiently small, the algorithm's trajectory can be made arbitrarily close to standard alternating minimization while maintaining the safety net of guaranteed convergence.

However, the work remains purely theoretical. There are no empirical benchmarks to demonstrate whether this regularization improves convergence speed or model quality in practical applications like computer vision or natural language processing. Furthermore, while the method guarantees convergence to a critical point (like a local minimum), it does not solve the fundamental challenge of finding the global minimum in a non-convex landscape.

Conclusion

This paper provides a long-overdue theoretical foundation for a widely used class of algorithms in Bayesian machine learning. By introducing a geometrically appropriate proximal term, the authors ensure convergence without sacrificing the simplicity of the Mean Field approach. Future work should investigate the empirical benefits of this scheme in complex learning problems where standard methods are known to struggle with stability.

Summary updated

Abstract

Mean-Field is an efficient way to approximate a posterior distribution in complex graphical models and constitutes the most popular class of Bayesian variational approximation methods. In most applications, the mean field distribution parameters are computed using an alternate coordinate minimization. However, the convergence properties of this algorithm remain unclear. In this paper, we show how, by adding an appropriate penalization term, we can guarantee convergence to a critical point, while keeping a closed form update at each step. A convergence rate estimate can also be derived based on recent results in non-convex optimization.
BibTeX
@misc{baque2015provably,
  author = {Pierre Baqué and Jean-Hubert Hours and François Fleuret and Pascal Fua},
  title = {{A provably convergent alternating minimization method for mean field inference}},
  year = {2015},
  eprint = {1502.05832},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1502.05832},
}
Figure