A trust-region method for stochastic variational inference with applications to streaming data

Lucas Theis, Matthew D. HoffmanICML 2015 · OpenReview

Stochastic Variational Inference (SVI) has long been considered the "gold standard" for scaling complex Bayesian models—like Topic Models or Mixture Models—to massive datasets. However, the algorithm is notoriously prone to getting stuck in local optima and requires meticulous hyperparameter tuning.

In their ICML 2015 paper, Lucas Theis and Matthew Hoffman tackle these persistent headaches by replacing the standard natural gradient steps in SVI with a more robust "trust-region" update. This modification makes the algorithm significantly less sensitive to initialization and enables a powerful new strategy for performing inference on continuous, infinite streams of data.

The Achilles' Heels of Standard SVI

While highly scalable, standard SVI suffers from three major limitations:

  1. Local Optima: SVI frequently gets trapped in poor local solutions. For instance, when training a mixture model, a bad initial step might cause the algorithm to "starve" certain components, leaving them entirely unused (or "dead").
  2. Hyperparameter Sensitivity: Practitioners often have to perform exhaustive grid searches to find the perfect learning rate and initialization to make SVI converge properly.
  3. Streaming Limitations: Standard SVI assumes the total number of data points ($N$) is known in advance. In true streaming scenarios—like processing a live news feed—$N$ is unknown and potentially infinite, which breaks standard SVI formulations.

The Trust-Region Solution

In standard SVI, updates are made by taking a step in the direction of the "natural gradient." This can be viewed as a basic trust-region method where the objective is linearized and the step size is kept very small. Theis and Hoffman argue that this approach is too myopic.

Instead, they propose a stochastic update that maximizes the Evidence Lower Bound (ELBO) while explicitly penalizing the Kullback-Leibler (KL) divergence between the new parameters and the old ones:

$$\lambda_{t+1} = \text{argmax}_\lambda \{ \mathcal{L}_n(\lambda) - \xi_t D_{KL}(\lambda, \lambda_t) \}$$

This seemingly simple shift provides several massive benefits:

  • Non-linearized Optimization: The authors solve this sub-problem using alternating coordinate ascent rather than relying on a linearized gradient step.
  • Smart Re-initialization: Because the method solves an optimization problem at each step, it can re-initialize "local" variables (the model's beliefs about specific data points). This allows the model to "jump" out of the local optima that typically trap gradient-based approaches.
  • True Streaming SVI: By adding new data points to a persistent "database" and continuously optimizing the ELBO over this growing set, the algorithm uses empirical Bayes to update the model's priors on the fly, seamlessly handling infinite data streams.

Key Insights and Results

The authors evaluated their trust-region (TR) method against standard natural gradient (NG) SVI across several benchmarks, including MNIST, Van Hateren Natural Image Patches, Wikipedia articles, and the Netflix Prize dataset.

Escaping Local Optima

On the MNIST dataset (used for testing mixture models), the trust-region method found solutions with significantly higher ELBOs.

Comparison of Trust-Region (TR) and Natural Gradient (NG) on MNIST. TR achieves a higher ELBO and utilizes all cluster components, avoiding the "dead" clusters seen in NG.

Qualitatively, the difference was stark: the TR method successfully utilized all available mixture components to represent the digits. In contrast, the standard NG method left more than half of its components "dead" (represented by empty gray squares) due to poor local optima.

Robustness and Streaming Success

  • Hyperparameter Robustness: In Latent Dirichlet Allocation (LDA) experiments on Wikipedia, the TR method performed well across almost the entire grid of hyperparameters. The standard NG method's performance was highly erratic, failing completely under certain batch sizes or learning rates.
  • Recommendation Performance: On the Netflix dataset, the TR method consistently outperformed natural gradient ascent in both precision and recall for collaborative filtering.
  • Streaming "Persistence": Most streaming algorithms process a data point once and discard it. By maintaining a database and continuously re-visiting data while integrating new points, the TR method successfully integrated streaming Wikipedia data at the word level. It reached an average log-likelihood comparable to models trained on the entire static dataset—a feat where standard SVI and Streaming Variational Bayes (SVB) lagged behind.

Limitations and Future Directions

While a significant step forward, the trust-region method is not without trade-offs. Each update involves an "inner loop" of optimization, which carries a higher computational cost than a single gradient update (though the authors note this overhead is often small compared to data processing costs).

Furthermore, while the method is less sensitive to hyperparameters, it still requires a defined learning rate schedule. Finally, the current derivation relies heavily on models with conjugate priors. Extending this robust trust-region approach to non-conjugate models—perhaps via Black Box Variational Inference—remains an exciting frontier for future research.

Summary updated

Abstract

Stochastic variational inference allows for fast posterior inference in complex Bayesian models. However, the algorithm is prone to local optima which can make the quality of the posterior approxim...
BibTeX
@inproceedings{theis2015trust,
  author = {Lucas Theis and Matthew D. Hoffman},
  title = {{A trust-region method for stochastic variational inference with applications to streaming data}},
  booktitle = {International Conference on Machine Learning},
  year = {2015},
  url = {https://openreview.net/forum?id=r1V1Sn-dWr},
}
Figure