Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing

Abstract

In statistical learning for real-world large-scale data problems, one must often resort to "streaming" algorithms which operate sequentially on small batches of data. In this work, we present an analysis of the information-theoretic limits of mini-batch inference in the context of generalized linear models and low-rank matrix factorization. In a controlled Bayes-optimal setting, we characterize the optimal performance and phase transitions as a function of mini-batch size. We base part of our results on a detailed analysis of a mini-batch version of the approximate message-passing algorithm (Mini-AMP), which we introduce. Additionally, we show that this theoretical optimality carries over into real-data problems by illustrating that Mini-AMP is competitive with standard streaming algorithms for clustering.

19 pages, 4 figures

References in corpus (11)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Statistical physics of inference: Thresholds and algorithms
• Universality in polytope phase transitions and message passing algorithms
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Mutual Information in Rank-One Matrix Estimation
• Statistical and computational phase transitions in spiked tensor estimation
• Variational Free Energies for Compressed Sensing
• Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
• Online compressed sensing

Cited by in corpus (2)

• An Approximate Message Passing Framework for Side Information
• Bayesian reconstruction of memories stored in neural networks from their connectivity