Fearless Stochasticity in Expectation Propagation

Summary

The authors introduce two methods for Expectation Propagation [EP] (which itself can be understood as a method for approximate Bayesian inference) that are robust to the stochastic noise introduced by using approximate expectations in the inner loop of EP. To do so the authors re-interpret the moment-matching update as a particular Natural Gradient Descent (NGD) step. While stochasticity remains due to the expectation, by moving to natural parameters MCMC estimates of the expectation do not suffer from bias-introducing non-linearities. By significantly reducing bias (to zero in the case of EP-$\eta$) the authors show that stable and computationally efficient EP is possible with single-sample moment-matching updates. In experiments the authors show that the method is easier to tune than alternatives and exhibits promising empirical performance.

Strengths

- To my mind the major strength of this submission is that it offers a well-reasoned technical improvement to a class of algorithms (EP) that are arguably underexplored in the literature (probably in large part due to the dominance of variational inference). - Moreover, empirical results support the effectiveness of the proposed algorithms. Since the authors work hard to reduce dependence on tricky hyperparameter choices, the reader has reason to be confident in the basic validity of the presented empirical results. - It is conceivable that the (novel, to the best of my knowledge) NGD interpretation offered by the authors could help motivate yet other EP variants.

Weaknesses

To my mind the major weakness of this submission is that the exposition is rather dense and at times hard to follow. This may be somewhat inherent in the technical nature of the topic, but I believe the authors could do a better job of guiding the reader. In particular a lot of space is devoted to somewhat extraneous modeling details ("...between diffuse galactic far ultraviolet radiation and 100-μm infrared emission in various sectors of the observable universe, using data obtained from the Galaxy Evolution Explorer..."), and this space in the main text could be re-purposed to offer more details on the algorithm, discuss the implications of the experimental results in more detail, or give more color on the "unified" EP presentation.

Questions

- math typos: line 804 - NIW is undefined where first introduced - i guess in sec. 2.1 you should emphasize more that the domain of $\theta_i$ is $\Omega$, since $\theta_i \notin \Theta_i$ as one might expect? similarly i guess in practice given the form of the outer update $\theta_i = \theta_j$ for all $i, j > 0$? maybe this should be emphasized? can you please clarify? - i understand that this is a paper about EP, but wouldn't it be valuable to benchmark against variational inference in at least one case? whether the authors like it or not, this remains a relevant comparison in my opinion.

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

To my mind the major limitation is the lack of comparison to alternative methods for approximate inference like variational inference.

Summary

This work addresses the sensitivity of expectation propagation (EP) to the randomness of Monte Carlo (MC) estimates involved in its update steps. It tackles this issue by recasting the moment matching step in EP as natural gradient descent (NGD) in the mean space of an exponential family distribution. The author identifies that the instability of EP to MC noise is due to the nonlinearity of the mirror map defined by the log partition function of the exponential family. By cleverly moving the NGD from the mean space to the natural parameter space, this issue is bypassed. The author also studies the influence of the stepsize on the accumulation of MC error, finding that decreasing the stepsize of the NGD updates helps to reduce the bias.

Strengths

- This is a well-written work. It starts with a succinct overview of the expectation propagation (EP) algorithm and summarizes several variants of EP updates in a unified manner (in Algorithm 1). This review also makes the contribution of this work very clear. It provides a sufficient discussion on why EP is sensitive to stochasticity and clearly motivates the design of the methodology. I also appreciate the self-contained review of the exponential family, natural gradient descent, and detailed derivation of EP updates provided in the appendix. Although these materials are standard, they help to make the work more accessible to a general audience. - The feasibility of performing unbiased NGD updates in the natural space of $\tilde p_i$ (Prop1) is a smart observation, and this simple modification makes the inner loop significantly more robust to the stochasticity in MC est. This simple modification (from mean space to natural parameter space) makes the inner loop significantly more robust to the stochasticity in Monte Carlo estimation. I'm indeed impressed that EP can work with single-sample estimation in the inner loop. - I also appreciate the rigorous investigation of the effect of $\alpha$ and $\epsilon$ to the bias of estimated mean parmaeter. - The empirical performance of proposed methods are superior; it outperforms the standard EP by a significant margin (as shown in Fig2).

Weaknesses

The technical side of this work is very strong in my perspective, and I don't observe many weakness on this regard. However, I think the novelty of this NGD perspective is overclaimed. To my knowledge, the relationship between moment matching in the exponential family and NGD is very well known (e.g., [1][2][3]). Once it is identified that $\tidle p_i$ is in the exponential family, the derivation of NGD (in either mean space Prop1 or natural parameter space) becomes quite straightforward. I hope the authors can elaborate on this point, and include discussion on some relavant literature arolund prop 1. I believe the real contribution of this work lies in the rigorous understanding of the influence of the stepsize on the accumulation of Monte Carlo (MC) error and the identification of the nonlinearity of the mirror map that leads to this error accumulation, which is already impactful to me. - [1]: Conjugate-Computation Variational Inference : Converting Variational Inference in Non-Conjugate Models to Inferences in Conjugate Models, 2018 - [2]: MCMC-driven learning, 2024 - [3]: Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server

Questions

- How do you estimate the KL divergence in the experiments? Maybe I'm missing something, but the target posterior is only known up to a constant, so unbiased KL est is not feasible? - I'm curious to see the relative performance of this work to NGVI [1] (specified in the Weakness section).

Rating

8

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitation is well discussed.

Summary

This paper considers new inference algorithms for EP. By framing the moment-matching equations of EP as a natural gradient update of a variational objective, they propose two new algorithms that are better suited for reducing/removing the bias introduced when sampling is required.

Strengths

I like the attempt at generalising and encapsulating the EP literature, and I find the `trick’ of mitigating the sampling inducing bias through a change of parameterisation is clever.

Weaknesses

1) In general I find the paper quite hard to follow and of course this is not helped by the form of the standard EP equations. For example the main point of the paper is to handle the bias introduced by using sampling to estimate certain quantities within the EP equations. However the source of this sampling is only explicitly mentioned on line 132 in text. It would be much clearer if this was explicitly in Alg 1, and would also make it more convincing that Alg. 1 actually encapsulated many EP style algorithms. 2) Following above some terms are not defined until later on in the paper. For example the convex conjugate in eqn 4, and on line 100 only defined one page later on line 123. 3) The paper is very descriptive but does not explain results. For example, the experiments only describe the set up, but all results and any conclusions are pushed into the appendix. This makes it hard to actually assess the contributions.

Questions

1) What is c_samp? 2) In Eqn 24 should there be a $beta_i$ scaling term? 3) In fig 1 a) why do most of the curves have a `u’ shape? Additionally why do the dashed orange/green curves not? 4) Does sequential update (instead of in parallel) affect the bias? 5) Why do you fix alpha to 1 and introduce a new step size eps? This looks like the only difference between Eqn 10 and the natural gradient part of 11. 6) The link between natural gradient steps and EP updates has been established previously (in Heskes and also in Hasenclever). Why is the view taken in paper a novel perspective compared to these previous works? 7) How does this work relate to `Bayes-Newton Methods for Approximate Bayesian Inference with PSD Guarantees’ Wilkinson et al, 2021 ? Which consider EP style algorithms with a natural gradient framework.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

yes