  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.
