PASS-GLM: polynomial approximate sufficient statistics for scalable Bayesian GLM inference
Generalized linear models (GLMs)-such as logistic regression, Poisson regression, and robust regression-provide interpretable models for diverse data types. Probabilistic approaches, particularly Bayesian ones, allow coherent estimates of uncertainty, incorporation of prior information, and sharing of power across experiments via hierarchical models. In practice, however, the approximate Bayesian methods necessary for inference have either failed to scale to large data sets or failed to provide theoretical guarantees on the quality of inference. We propose a new approach based on constructing polynomial approximate sufficient statistics for GLMs (PASS-GLM). We demonstrate that our method admits a simple algorithm as well as trivial streaming and distributed extensions that do not compound error across computations. We provide theoretical guarantees on the quality of point (MAP) estimates, the approximate posterior, and posterior mean and uncertainty estimates. We validate our approach empirically in the case of logistic regression using a quadratic approximation and show competitive performance with stochastic gradient descent, MCMC, and the Laplace approximation in terms of speed and multiple measures of accuracy-including on an advertising data set with 40 million data points and 20,000 covariates.
[EDIT] I have read the rebuttal and I have subsequently increased my score to 7. 
 
# Summary of the paper
When data are too numerous or streaming, the authors investigate using approximate sufficient statistics for generalized linear models. The crux is a polynomial approximation of the link function.
# Summary of the review
The paper is well written and the method is clear and simple. Furthermore, it is computationally super-cheap when the degree of the polynomial approximation is low, a claim which is backed by interesting experiments. I like the underlying idea of keeping it simple when the model allows it. My main concern is the theoretical guarantees, which 1) lack clarity, 2) involve strong assumptions that should be discussed in the main text, and 3) are not all applicable to the recommended experimental setting. 
# Major comments
- L47 "constant fraction": some subsampling methods have actually been found to use less than a constant fraction of the data when appropriate control variates are available, see e.g. [Bardenet et al, MCMC for tall data, Arxiv 2015], [Pollock et al., the scalable Langevin [...], Arxiv 2016]. Actually, could your polynomial approximation to the likelihood could be useful as a control variate in these settings as well? Your objection that subsampling requires random data access still seems to hold for these methods, though.
- L119 "in large part due to...": this is debatable. I wouldn't say MCMC is expensive 'because of' the normalizing constant. "Approximating this integral": it is not the initial purpose of MCMC to approximate the normalizing constant, this task is typically carried out by an additional level above MCMC (thermodynamic integration, etc.).
- Section 4: the theoretical results are particularly hard to interpret for several reasons. First, the assumptions are hidden in the appendix, and some of them are quite strong. The strongest assumptions at least should be part of the main text. Second, in -say- Corollary 4.1, epsilon depends on R, and then L207 there's a necessary condition involving R and epsilon, for which one could wonder whether it is ever satisfied. Overall, the bounds are hard to make intuitive sense of, so they should be either simplified or explained. Third, some results like Corollary 4.2 are "for M sufficiently large", while the applications later typically consider M=2 for computational reasons. This should be discussed.
- The computational issues of large d and large M should be investigated further.
- Corollary 4.2 considers a robust loss (Huber's) but with a ball assumption on all data points, and a log concave prior on theta. I would typically use Huber's loss in cases where there are potential outlier inner products of x and theta; is that not in contradiction with the assumptions?
- Corollary 4.3 Assumption (I) is extremely strong. The appendix mentions that it can be relaxed, I think it should be done explicitely.