acceptodds
Under review as a conference paper at ICLR 2027

Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs

Abstract

Approximate message passing on factor graphs underlies two dominant families of probabilistic inference algorithms: expectation propagation (EP) and variational message passing (VMP). Both methods approximate the marginal at each factor edge, forcing an iterative round-robin schedule, risking negative-precision messages, and, for VMP, collapsing to point estimates at Dirac-delta factors. We introduce Direct Message Approximation (DMA), which approximates factor-to-variable messages directly rather than the marginal. For normalisable factors, we define a consistency condition (requiring exactness when all other incoming messages are Dirac deltas) to guide message construction. We prove a master theorem (proper messages, any graph) bounding marginal KL from message KL, with three structural corollaries: Dirac-input consistency, no EP-style inner-loop iteration, and no negative-precision messages. Further, we prove a complementary guarantee for the inherently improper backward message of the product factor, whose closed-form treatment has resisted prior work. As a concrete instantiation, we derive explicit DMA messages for the product and leaky-ReLU factors and assemble a Bayesian neural network (BNN) inference algorithm with one forward/backward sweep per training example and no gradient learning-rate hyperparameter, validating that the structural guarantees translate to predictive uncertainty that widens in data-sparse regions, including under model mismatch.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
direct message approximation, factor graphs, approximate message passing, product factor, probabilistic inference, uncertainty quantification

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_kNebOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+2)
Read review
Paper summary

This paper introduces DMA an alternative to EP and VMP that formulates factor-to-variable messages directly, bypassing the traditional edge-marginal projection and cavity-message division steps. By enforcing a Dirac input consistency condition and applying Gaussian moment matching, the authors establish Theorem 2.3, an edge local KL divergence inequality for proper messages, and derive explicit update operators for product and leaky-ReLU factors. To handle the improper exact backward message of product factors, the paper proposes a log-normal approximation backed by an O(1/r2)O(1/r^2) error bound in the concentrated input regime. These operators are integrated via Algorithm 1 into a single sweep BNN inference scheme, and benchmarked against Adam, AdamW, IVON, and diagonal Laplace across 1D synthetic regression, a model-mismatch test, and a larger synthetic network.

Critical strengths
  1. Definition 2.1 provides a clear principle for constructing approximate messages directly. Theorem 2.3 appears valid under its stated assumptions and bounds how much an error in one message can affect the resulting local marginal distribution.
  2. Propositions 3.1, 3.4, and 3.5 give explicit formulas for the means and variances of the product factor’s forward message and the leaky-ReLU factor’s messages. Algorithm 1 and the Appendix explain the order of message updates, how stored mini-batch messages are replaced, and how messages are parameterised. These details make the method concrete to implement.
Critical weaknesses
  1. Equation (7) does not match the derivation in Appendix B.4. Its predicted mean is independent of (σz\sigma_z), whereas the appendix’s formula depends on it. The proof of Theorem 3.3 analyzes a different distribution from the reference defined in Eq. (24). Also, the theorem bounds error against a truncated reference without showing how this controls the actual marginal error. These gaps leave the claimed (O(1/r2)O(1/r^2)) guarantee for the proposed update insufficiently justified.
  2. Two distributions can both shrink toward the same point without their KL divergence approaching zero. This happens for leaky-ReLU when the input concentrates at zero. The smooth case proof also assumes that linear effects dominate nonlinear effects, which can fail when input variances shrink at different rates. Standard ReLU places positive probability exactly at zero, while a continuous Gaussian does not, making their forward KL infinite. Table 2 therefore incorrectly lists this case as covered by Theorem 2.3.
  3. The evaluation focuses on small synthetic regression problems, with the larger network having only 1,932 weights and no direct EP baseline available. Comparisons are made against Adam and AdamW, which partly highlight the advantages of modeling uncertainty rather than specifically demonstrating the benefits of DMA. DMA achieves predictive NLL and calibration comparable to diagonal Laplace on the small synthetic task. This supports its competitiveness, with the main reported advantage being computational efficiency rather than improved predictive quality. However, the small synthetic experiment does not establish that this advantage generalises.
Questions for authors
  1. While local message errors are well-bounded, feedforward neural networks act as highly composition heavy loopy structures when message passing interacts across multiple layers and mini-batch epochs. Without a global convergence guarantee or a compositional error bound across layers, what empirical or theoretical evidence suggests that local errors do not compound exponentially or lead to drift as network depth increases?
  2. Equation (7) and the log-normal derivation in Appendix B.4 give different moments. Which formula is intended and used in the implementation? Please provide a consistent derivation and validate the approximation numerically against a clearly specified proper reference distribution or normalized marginal.
  3. What additional assumptions or restrictions are needed for the KL convergence claimed in Corollary 2.4? Please address the leaky-ReLU kink at zero and the smooth example (g(x1,x2)=x1+x22)g(x_1,x_2)=x_1+x_2^2)), with independent centered Gaussian inputs having standard deviations (σ1=t3\sigma_1=t^3) and (σ2=t\sigma_2=t) as (t→0t\to 0). In the latter case, the quadratic term dominates despite the nonzero gradient.
4 comments
AuthorsOpenReview ↗

Response to Reviewer kNeb, part 1 of 2

Summary. We thank the reviewer for a careful technical check, which pointed us to details in our proofs that needed correction and helped to improve the paper. All of them are corrected; the message formula and the released code are unchanged (G1).

R4.1 (Eq. (7) and its proof). We agree on all three points, and all three are resolved.

Changes.

  • Derivation. The submitted appendix replaced both YY and ZZ by log-normals, giving a mean that depends on σz\sigma_z. Eq. (7) is instead exactly the first two moments of Z/YLNZ/Y_{\mathrm{LN}}, with ZZ Gaussian and only YY replaced by its moment-matched log-normal: 1/YLN1/Y_{\mathrm{LN}} is log-normal with mean (1+η2)/μy(1+\eta^2)/\mu_y and squared coefficient of variation η2=σy2/μy2\eta^2=\sigma_y^2/\mu_y^2, and the product with the independent ZZ gives mean (μz/μy)(1+η2)(\mu_z/\mu_y)(1+\eta^2) and the variance of Eq. (7). Appendix B.4 now derives it this way (in our check, agreement to 2.8⋅10−152.8\cdot10^{-15} over 10610^6 inputs).
  • Description. Section 3.1 and the introduction, which also described both inputs as log-normal, now describe this construction.
  • Proof. The submitted proof weighed each yy by N(y;μy,σy2)\mathcal{N}(y; \mu_y, \sigma_y^2), the law of the ratio, while the truncated message (26) weighs it by N(y;μy,σy2)/∣y∣\mathcal{N}(y; \mu_y, \sigma_y^2)/|y|. The new proof writes the truncated message as the law of Z/YZ/Y with YY reweighted by 1/∣y∣1/|y| and bounds both terms of the Pythagorean split for Eq. (7) (Lemmas B.3–B.5); the O(1/r2)O(1/r^2) rate holds, the moment term being at most 1/(2ry2)+O(ry−4)1/(2r_y^2)+O(r_y^{-4}).
  • Marginal. Added Corollary B.6: for a Gaussian incoming message qq, the exact marginal splits into the marginal of the truncated message and an excluded part of weight at most Cq rz Φ(−ry/2)C_q\thinspace r_z\thinspace \Phi(-r_y/2); convexity of the divergence, Theorem 3.3 and explicit bounds on both parts give KL[p ∥ p^]≤Cκ,q/r2\mathrm{KL}[p \thinspace \Vert \thinspace \hat{p}]\leq C_{\kappa,q}/r^2, with constants that grow when qq conflicts with the backward evidence, i.e. puts little mass near μz/μy\mu_z/\mu_y.
  • Validation. By quadrature, r2r^2 times the divergence stays below 3.93.9 for rr from 22 to 6464 (Appendix C.4).

R4.2 (Corollary 2.4). We agree on all three points, and all three are resolved. At the leaky-ReLU kink the output of N(x;0,σ2)\mathcal{N}(x; 0, \sigma^2) is σ ReLUα(U)\sigma\thinspace \mathrm{ReLU}_\alpha(U), a scale family, so δ\delta does not depend on σ\sigma and does not vanish; with different rates the quadratic term can dominate, as the reviewer's example shows (R4.6); and the standard ReLU's forward message has an atom at zero, so δ=∞\delta=\infty.

Changes.

  • Restated Corollary 2.4 with a common rate of concentration and explicit bounds for every factor; at a kink or a zero gradient δ\delta is a positive constant, given explicitly (0.660.66, 0.130.13 and 0.00850.0085 nats for α=0.1\alpha=0.1, 0.40.4 and 0.80.8), and Theorem 2.3 still applies (Appendix B.3).
  • Marked the standard ReLU's forward message as not covered in Table 2.
  • Corrected Appendix C.8, which spoke of a point mass for α>0\alpha>0.

R4.3 (evaluation and EP). We agree with this reading: in the submission DMA is comparable to diagonal Laplace in predictive quality, and its advantages are its cost and the absence of tuning. Whether this generalizes is what the new experiments test, with every method on the same data and batches, from 83 to 1 932 and 52K weights (G3). In fit, every method's mean, DMA's included, is close to the truth at plot scale; DMA's error is at the noise level. In uncertainty, its band stays reasonable over the epochs at every size, while PBP's shrinks with every pass and IVON's is narrow outside the data; at 1 932 weights diagonal Laplace with the exact Hessian has the better band. In runtime, that Laplace needs 6 to 10 minutes per seed at 1 932 weights, against DMA's seconds, and is out of reach at 52K weights, where DMA's band covers the true function at 0.620.62 of the points outside the training range, against 0.260.26 for PBP and 0.200.20 for IVON. The advantage thus grows with the network: the exact methods drop out, and the cheap ones lose their uncertainty (Table 7). The tasks are synthetic by design: with the true function drawn from the model's own prior, the exact posterior is the target and an HMC reference can measure every method against it, which real data with an unknown truth would not allow (R1.4).

Changes.

  • Added PBP and an HMC reference, diagonal Laplace and IVON at 1 932 weights, and a 52K-weight network (G3, R1.4).
  • Showed why EP is not a usable baseline here: its message in the failure example has negative precision, and with the usual safeguard, which rejects such an update, EP can stop at the prior, while DMA learns (Appendix E.9, Figure 18).
AuthorsOpenReview ↗

Response to Reviewer kNeb, part 2 of 2

R4.4 (error over depth). These are two important aspects, and the revision addresses both. Over depth, we measure the error of each layer's marginal against a Monte Carlo reference, since with two or more hidden layers the factor graph has cycles even for one example and a tree argument does not apply: the error grows at most linearly with depth, not exponentially. Over epochs, the new Lemma D.2 gives how far one replacement of a batch's message moves the beliefs, and we measure the drift it causes.

Changes.

  • Added the divergence of each layer's marginal from a Monte Carlo reference, with the weight beliefs held fixed, for networks of width 16 and up to 12 layers (Appendix C.5). In the first two layers the propagated moments are exact; from the third on, where units share inputs, the error of the propagated moments grows at most linearly with depth, by about 0.010.01 nats per layer for well-determined weights and more slowly for prior-like ones, not exponentially. For prior-like weights the larger part of the remaining error is the non-Gaussianity of the true marginal, which no Gaussian message removes.
  • Measured and stated the behavior of the batch iteration over epochs (R3.2).
  • Derived how far one replacement of a batch's message moves the beliefs, and measured the drift over an epoch: with randomly ordered data the means stay within 0.30.3 to 0.70.7 standard deviations of their values at the start of the epoch, for every number of batches (Lemma D.2, Table 3).

R4.5 (derivation of Eq. (7)). Eq. (7) is the intended formula, and it was implemented correctly and used in all experiments; we corrected the inconsistent derivation in Appendix B.4 (R4.1).

Changes.

  • Validated it by quadrature against the truncated message over rr and $r_y/r_z\in\lbrace 1/2,1,2\rbrace $: r2r^2 times the divergence stays below 3.93.9 and tends to 2.82.8, 1.761.76 and 0.1750.175; most of it is the message's own non-Gaussianity, which no Gaussian removes, and for r≥8r\geq8 Eq. (7) is within 3535% of the best Gaussian (Appendix C.4). The formula of the submitted derivation, with both inputs log-normal, is about as accurate at ry=rzr_y=r_z (Figure 6, dashed).
  • Validated it against the normalized marginal below r=2r=2 and at zero mean (R1.1).

R4.6 (assumptions of Corollary 2.4). Thank you for the comment. Corollary 2.4 needs two additional assumptions: the inputs concentrate at a common rate, σk=ckt\sigma_k=c_kt with fixed ck>0c_k>0, under which the linear term is O(t)O(t) and the quadratic term O(t2)O(t^2); and the point is one where the factor is differentiable with a nonzero gradient. In the reviewer's example the linear term's share of V[g]\mathbb{V}[g] is t6/(t6+2t4)→0t^6/(t^6+2t^4)\to0, so gg tends to the shape of the scaled x22x_2^2 and δ\delta to a positive constant; at the leaky-ReLU kink δ\delta is the constant of R4.2 for every σ\sigma.

Changes.

  • Corollary 2.4 now states both assumptions and gives explicit bounds for every factor of the paper (Appendix B.3).

Dear Reviewer kNeb,

Thanks again for your time and effort. As the deadline for the discussion period is approaching, we would greatly appreciate it if you could kindly let us know whether our responses solve your concerns and/or there are any further questions.

Thank you so much for your attention to our work.

Warmest regards,

Authors

Thank you for your reply. I consider q1–q3 addressed and have therefore raised my soundness score. The two weight example shows that EP can stall, while DMA learns. Given DMA’s positioning as an alternative to EP, a matched comparison on the main BNN benchmarks would help establish its practical gains.

Reviewer_p3uyOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces Direct Message Approximation (DMA), a novel approximate inference framework for factor graphs that bypasses the marginal-projection step of EP and VMP by directly approximating outgoing messages. DMA resolves common failure modes in standard message passing by guaranteeing no negative-precision messages, eliminating iterative inner loops, and maintaining consistency at Dirac-delta factors. The framework is supported by theorems. When instantiated for BNNs, DMA enables highly scalable, single-sweep inference that requires no gradient learning-rate tuning. It achieves wall-clock speeds comparable to Adam while delivering robust epistemic uncertainty, yielding well-calibrated predictive intervals for data-sparse extrapolation and model mismatch scenarios where standard gradient methods fail.

Critical strengths

The paper has a clear structure and makes a theoretical breakthrough by directly approximating messages to eliminate classic EP/VMP failure modes, featuring a novel closed-form bound for product-factor backward messages.

Critical weaknesses

While the theoretical framework and product-backward construction are solid, the empirical evaluation is flawed. It fails to compare DMA against its direct marginal-based counterpart (PBP), omits trivially available gold-standard posteriors, and unjustifiably excludes all Bayesian baselines in larger-scale tests.

Questions for authors
  1. The marginal-projection step of EP is replaced with an approximation. I want to know if this will affect the convergence property.
  2. The only example in experiments is the BNN. Maybe giving more examples is better.
  3. I think more implementation details are needed. For example, which product-backward formula does the released code implement?
  4. How the hyper-parameters, e.g., leaky-ReLU slopes, are chosen in the experiment? What effect will they have?
4 comments
AuthorsOpenReview ↗

Response to Reviewer p3uy, part 1 of 2

Summary. We thank the reviewer for the assessment of the theory and the product-backward construction. Bayesian neural networks are the target application (R3.3); we studied the product factor and the convergence in more detail (G1, R3.2), and added new baselines, including PBP and an HMC reference, and ran all baselines on the larger tasks, as far as they scale (R3.1, G3).

R3.1 (baselines). Agreed on all three counts. PBP is the closest method for neural networks: like DMA it sweeps once per example and has no learning rate; unlike DMA it updates the beliefs by assumed density filtering through the derivatives of log⁡Z\log Z, without removing earlier contributions, and undoes updates that would make a variance negative (R2.1). The exclusion of the Bayesian baselines at 1 932 weights was not justified: diagonal Laplace with the exact Hessian is expensive there, 12 to 18 s for one Hessian diagonal, but feasible, and the reason given for leaving out IVON cited a sweep that does not match Appendix E.6.

Changes.

  • Added PBP on every task, with the known noise level and the same prior as every other Bayesian method, so that all share one model (Appendix E.4). It fits the mean best, but each pass counts the data again, so its variances shrink with every epoch: at 1 932 weights its coverage of the true function outside the training range falls from 0.740.74 at epoch 3 to 0.190.19 at epoch 100.
  • Added an HMC reference (R1.5).
  • Added diagonal Laplace, IVON and PBP at 1 932 weights, and removed the unjustified exclusion from Appendix G. The comparison shows a trade-off rather than a winner (Table 7): Laplace with the exact Hessian has the best band, but costs minutes per seed and is out of reach at 52K weights; PBP and IVON fit best, but PBP's band shrinks with every pass and IVON's is narrow outside the data; DMA's mean fits the truth to within the noise level, and it is the only method that combines a reasonable predictive variance that it keeps over the epochs, a runtime that scales with the network, and no tuning.

R3.2 (convergence). It does, and two loops have to be told apart. Within one example, DMA's messages do not depend on the incoming message at their own edge, so each message is computed once per sweep, without an inner fixed-point iteration (Corollary 2.5). Across epochs, the stored message of each batch is replaced on every pass, a fixed-point iteration at the level of batches; as for EP there is no convergence guarantee, and its fixed points need not be EP's, since EP matches the moments of each marginal and DMA those of each message. Run on past its stopping rule, the iteration need not reach a fixed point, and in our runs it travels between modes of the posterior. The cause is the replacement: each pass swaps a batch's stored message for one computed from the current beliefs, which pulls the beliefs towards a mode that fits this batch. How far one replacement moves them grows with the batch's share of the data and with how much the batch differs from the rest (Lemma D.2); with randomly ordered data, as in the revision, the moves of consecutive batches largely cancel and the iteration cycles among modes of similar fit, while with sorted data, where consecutive batches cover the same part of the input range, they add up to jumps between modes, for every number of batches from 5 on (Table 3). Without damping no global convergence guarantee can hold from the construction alone: in a two-batch reduction the derivative of one epoch at a fixed point is set by the sensitivities of the batches' likelihoods, which DMA's messages do not bound; damping makes every fixed point with derivative below one locally attracting, but on a multimodal posterior no more (Proposition D.4). Our runs reflect this travel over a multimodal landscape: the training log-likelihood mostly stays near its value at the stopping epoch, and in some correctly specified runs the iteration also passes through clearly worse modes.

Changes.

  • Derived the size of one replacement, showed why the undamped iteration has no global convergence guarantee, and measured both over batch sizes and orders of the data (Lemma D.2, Proposition D.4, Appendix D.2).
  • Stated this in Section 4.2 and corrected Appendix F, whose claim that four mismatch runs did not stop does not reproduce.
  • Trained every method for a fixed epoch budget, as for Adam, with whole learning curves. With the data in random order, as in the revision, the stopping rule fires at epoch 4 to 6 in the median on every task, where DMA's fit is as accurate as after the full budget, so DMA keeps it; after it the training log-likelihood falls slightly, at 1 932 weights from 0.560.56 at epoch 3 to 0.480.48 at epoch 100 in the median, and further on a few seeds (Appendices D.2 and G).
AuthorsOpenReview ↗

Response to Reviewer p3uy, part 2 of 2

R3.3 (beyond neural networks). Agreed, as also raised by Reviewer 2: DMA is a method for factor graphs whose non-conjugate factors are deterministic, and neural networks are its main instance, whose structure it exploits for closed-form, proper messages in one sweep without tuning (R2.5); the paper derives and evaluates messages for neural networks only. Within this class we broadened the evaluation instead, with a new network of 52K weights, 27 times the size of the largest network of the submission (R1.4).

Changes.

  • Scoped the claims to neural networks and stated other models as a direction (Section 6).
  • Added a network of 51 84051\thinspace 840 weights trained on 25 00025\thinspace 000 examples, 27 times the size of the 1 932-weight task (Appendix G.3).

R3.4 (implemented formula). We apologize for the confusion. Eq. (7) is correct, and it is the formula the released code implements and every experiment uses: one function, _dma_msg_backward, computes the message to every weight and every activation. It evaluates the equation in an algebraically equal order that never forms τy5\tau_y^5 or τy8\tau_y^8, which overflow for confident inputs, and returns the uninformative message where a denominator underflows; over 10610^6 random inputs it matches the printed formula to a relative 1.4⋅10−151.4\cdot10^{-15}. What was wrong is the proof sketch in Appendix B.4 of the submission, as Reviewer 4 also found (R4.1, R4.5): it did not derive Eq. (7). The revision replaces it with a correct derivation. We thank the reviewer for this constructive technical feedback, which helped to clarify and improve the paper.

Changes.

  • Appendix B.4 now derives Eq. (7), the formula the code implements (R4.1).

R3.5 (hyperparameters). The slopes are part of the architecture, like the layer widths: they are neither learned nor parameters of the inference, and in the correctly specified experiments they are those of the network that generates the data (0.40.4, 0.80.8; and 0.50.5, 0.50.5, 0.80.8, 0.10.1 at 1 932 weights, chosen to mix equal and different slopes). They have two effects: on the model, they set how nonlinear the network is (α=1\alpha=1 is linear); on the inference, they set the accuracy of the ReLU messages, which are exact for α=1\alpha=1 and approach the improper message of the standard ReLU as α→0\alpha\to0 (Appendix C.2, panel b). The revised Corollary 2.4 quantifies the second: the forward message's error is at most log⁡(1/α) Φ(−u)\log(1/\alpha)\thinspace \Phi(-u) for an input mean of u≥0u\geq0 standard deviations, and at the kink 0.660.66, 0.130.13 and 0.00850.0085 nats for α=0.1\alpha=0.1, 0.40.4 and 0.80.8.

Changes.

  • Stated the slopes' role in Appendices E.1 and G.

Thank you for the detailed response and revisions. I believe my main concerns regarding the experimental comparisons, convergence behavior, and implementation details have been adequately addressed. Although the evaluation beyond Bayesian neural networks remains limited, I appreciate the clearer scope and positioning of the work. I therefore maintain my rating.

Thank you!

Reviewer_p36nOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The authors describe a method of approximate message passing most closely related to expectation propagation. Their main variation is that while EP approximates the belief at a variable, then uses division to define its outgoing messages, the authors’ approach approximates each message individually using the standard belief propagation message form.

Critical strengths

The proposed method seems to work well and is of practical interest as a possible alternative to EP.

Critical weaknesses

The current version of the paper seems to be missing context of past methods, and presents their work as more novel and significant than it actually is.

First, the authors seem to present the message division (1) as being fundamental to message passing methods, but eventually note at the end of the introduction the similarity of their approach to generic assumed density filtering (ADF). In fact, many implementations of belief propagation and approximate message passing operate on the messages themselves. See e.g. Koller et al. (1999), nonparametric belief propagation (Sudderth et al. 2003), stochastic message passing (Noorshams & Wainwright 2012), structured message passing (Gogate & Domingos 2013), and many more.

The authors differentiate their approach from ADF through two theoretical contributions; however, both of these seem very limited in scope. First, they claim a “formal consistency axiom”, that as the input messages approach point estimates, the output message approaches the normalized factor. This can be difficult to attain for arbitrary factors, but the authors’ construction looks at delta functions, for which it is trivial.

Next, they state a “master theorem”, which provides “local” error bound, i.e., that the error due to a message approximation m^\hat m is bounded. However, again, this is a fairly trivial result. The difficulty in analyzing approximate messages is not their immediate effect, but rather their accumulated effect as the approximations are passed through multiple factors and approximation steps. For example, they contrast with Ihler et al. (2005)’s requirement of contraction properties — but this requirement is to contain the growth of errors as they are propagated and combined with one another. The authors’ analysis looks at a far more limited setting.

The concept of normalizable and unnormalizable factors arises even in purely Gaussian models with belief propagation, in which convergence guarantees can be provided for “pairwise normalizable” models (see, e.g., Malioutov et al. 2006). How does the bound in 3.2 relate to this body of work?

While the authors describe their algorithm as a general approach and alternative to EP or VMP, it is unclear to me whether this is true. Their results often seem to assume the types of factors arising in their Bayesian neural network application, and it is hard to judge whether their approach makes sense in other settings.

Overall the approach seems practically interesting in the setting the authors envision, but the presentation is flawed by overly strong claims and missing context relating to prior work.

Questions for authors

No questions

3 comments
AuthorsOpenReview ↗

Response to Reviewer p36n, part 1 of 2

Summary. We thank the reviewer for the precise reading and the references. We agree that the submission overstated its novelty and the reach of its theory, and have revised the positioning and the claims (G2). The contribution, stated precisely: a construction of messages for factor graphs of deterministic factors that is exact at point-mass inputs and proper by construction, including the improper backward message of the product, with local guarantees, and the inference scheme for neural networks built from it.

R2.1 (prior work). Agreed: approximating the message itself is not new, and the division (1) is the defining step of EP and VMP, which the paper contrasts with, not of message passing in general. How DMA relates to the cited and the closest works:

  • Nonparametric, stochastic and structured message passing approximate messages by kernel density estimates from samples (Sudderth et al.), series expansions with Monte Carlo coefficients (Noorshams and Wainwright), or compact representations of discrete messages (Gogate and Domingos), and iterate to a fixed point. DMA gives closed-form Gaussian messages and needs one sweep per example.
  • Koller et al. discuss the choice DMA makes and argue against it: a message should be approximated in the context of the receiving potential, since a message of small divergence need not give a good product. DMA approximates the message alone, so that no message depends on the incoming message at its own edge; Theorem 2.3 bounds the price of this choice locally, by ∥mXj→f∥∞/Z\Vert m_{X_j\to f}\Vert _\infty/Z times the message's divergence.
  • ADF and PBP. ADF folds each factor into the belief instead of storing its message, so a factor cannot be removed or refined later. PBP applies ADF to neural networks through the derivatives of log⁡Z\log Z, repeats passes without removing earlier contributions, which its authors note can underestimate the variances, and undoes an update that would make a variance negative. DMA stores one message per batch, replaces it on every pass so that no data are counted twice, and is proper by construction.
  • The product factor. Matchbox uses a variational message, since the EP message's variance would always grow, at the cost of shrinking the uncertainty with every update; Infer.NET contains an experimental log-normal operator that matches both inputs to log-normals and keeps only the magnitude of the mean. Eq. (7) replaces only the conditioning input by a log-normal, so it keeps the sign of the mean and is exact as that input concentrates, and it comes with Theorem 3.3.

We no longer present valid messages where EP fails as a contribution of its own, since EP with a safeguard that sets negative precisions to zero sends the same message in the example of Appendix E.9; the difference is that DMA needs no safeguard.

Changes.

  • Added a related-work paragraph on message-level approximation with the cited works, Matchbox and Infer.NET (Section 5).
  • Corrected the introduction's presentation of the division (1) (Section 1).
  • Corrected the description of PBP as assumed density filtering, and added expectation backpropagation and Frey and Hinton (Section 5, Appendix A).

R2.2 (consistency condition). Agreed: for a deterministic factor projected by moment matching the condition holds by construction, as the paper's own verification in Section 2.2 shows in four lines; it is a design criterion and a check, not a result that sets DMA apart from ADF. It constrains the choice only where moment matching cannot be applied directly: the exact backward message of the product is improper, its moments do not exist, and the condition is what the log-normal construction must meet, which Theorem 3.3 quantifies.

Changes.

  • Presented the condition as a design criterion and removed “formal consistency axiom” and the rows of Table 1 built on it.

R2.3 (accumulated error). Agreed on all three counts. Theorem 2.3 bounds the effect of one approximate message on one marginal, and our contrast with Ihler et al. was misleading: their contraction condition controls how errors grow as they propagate through the graph, which our bound does not address. The accumulated error is the harder question, and it is not reducible to a tree argument here: the factor graph of a network with two hidden layers has cycles even for one example, since two hidden units of one layer both feed two units of the next.

Changes.

  • Presented the theorem as a local error bound and corrected the comparison (Sections 2.3 and 5).
  • Stated the limitation (Section 6), derived how far one replacement of a batch's message moves the beliefs (Lemma D.2), and measured the behavior of the iteration over epochs (R3.2).
  • Measured how the error grows with depth: at most linearly in the forward messages (R4.4, Appendix C.5).
AuthorsOpenReview ↗

Response to Reviewer p36n, part 2 of 2

R2.4 (pairwise normalizability). They concern different kinds of improperness and answer different questions. Pairwise normalizability is a property of the whole Gaussian model: its precision matrix is a sum of positive definite 2×22\times2 edge terms, equivalent to walk-summability, which guarantees that loopy belief propagation is well posed, that its means converge to the true means and that its variances converge. Theorem 3.3 concerns one non-Gaussian factor whose exact message has infinite mass, and bounds the accuracy of its proper Gaussian approximation against a truncated reference; it is not a convergence result. What they share is that no message passed along has negative precision, which DMA guarantees by construction (Corollary 2.6).

Changes.

  • Added Malioutov et al. and this distinction to Section 5.

R2.5 (generality). We agree that DMA is not a general replacement for EP or VMP, and the revision no longer presents it as one. It is a principled method for a specific subclass that matters in practice: factor graphs of Gaussian variables whose non-conjugate factors are deterministic (Dirac) functions of their inputs. This is the structure of neural networks, and DMA is built on it in three ways.

  • A reference for every message. For a deterministic factor the exact message is tractable when its other inputs are point masses; DMA builds every message to be exact in that limit, which is the design criterion of R2.2.
  • Closed form, proper by construction. The output moments of the network's factors, sums, products and piecewise-linear activations, are available in closed form, so every message is a closed-form Gaussian; the one exact message that is improper, the product's backward message, gets a proper approximation with an error bound (Theorem 3.3).
  • One sweep, no tuning. No message depends on the incoming message at its own edge, so each message is computed once per sweep, without an inner iteration, damping or a learning rate (Corollary 2.5).

General-purpose methods do not use this structure and pay for it in this class: EP's messages through these factors can have negative precision and need safeguards (Appendix E.9), gradient-based variational methods need a learning rate and Monte Carlo gradients, and sampling does not scale to networks of practical size. Neural networks are the main instance of this class and the one we derive and evaluate; models that use the same factors, such as matrix factorization, are stated as a direction rather than claimed.

Changes.

  • Stated the method as one for factor graphs of deterministic factors, as they arise in neural networks (Sections 1 and 6).
  • Scoped the claims to that setting, and stated other models with the same product and sum factors as a direction (Section 6).

R2.6 (overstated claims). We apologize for the overstated claims and the missing references, and have corrected both. In line with the reviewer's view that the approach is practically interesting in its setting, we strengthened the evaluation, with new baselines and a network of 52K weights (G3), and now position the work as a principled Bayesian approach that exploits the structure of this class of models, deterministic factors as in neural networks, rather than as a general method for factor graphs. In detail:

Changes.

  • Renamed the “master theorem” a local error bound, without “on any graph” and “without a contraction condition”.
  • Removed “formal consistency axiom” and “whose closed-form treatment has resisted prior work”.
  • Added the missing prior work (R2.1) and corrected the descriptions of PBP and ADF.
  • Scoped the framework to deterministic factors as in neural networks, and stated the limitations (Section 6).

Dear Reviewer p36n,

Thanks again for your time and effort. As the deadline for the discussion period is approaching, we would greatly appreciate it if you could kindly let us know whether our responses solve your concerns and/or there are any further questions.

Thank you so much for your attention to our work.

Warmest regards,

Authors

Reviewer_oiKbOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents a new algorithm for approximate message passing on factor graphs. It addresses several issues with the classic algorithms (EP, VMP), which rely on approximating the marginal at each edge and recovering the message by dividing out the incoming message. The paper identifies a tractable limit of the message-passing equations, in which the incoming messages have zero variance (Dirac deltas) and the exact outgoing message is simply the factor evaluated at these points. From this limit the authors define a consistency condition, requiring that the approximate message agree with the exact one in this limit, and give a moment-matching recipe for approximating the message directly, which they show satisfies the condition. The authors prove a bound on the error of the marginal at a single edge, which is linear in the parameter delta, the KL divergence between the exact message and its approximation at that edge, and show that the algorithm does not require an inner-loop iteration or produce negative precisions, which are pathologies of the previous algorithms. The authors also describe a backward message for the product factor, whose exact message is improper, based on a log-normal approximation, with an error bound in the limit of large SNR. They specify the messages further for the leaky ReLU factor, and assemble the messages into an inference algorithm for the weights of a Bayesian neural network, which is tested on small synthetic regression tasks against Adam, AdamW, IVON and a diagonal Laplace approximation.

Critical strengths

The paper is clearly written and well organized, and the authors make sure to point out the implications of each mathematical statement they derive. The pathologies of previous algorithms that motivate this work are clearly stated and addressed directly. The mathematical statements are clear and clean, and come with detailed proofs that appear sound (apart from an issue pointed out in the weaknesses). The authors connect the general mathematical framework to a known ML problem, Bayesian neural network inference, although the experiments are limited to synthetic 1D regression tasks with small networks.

The resulting algorithm has practical appeal: it has no learning rate or other optimization hyperparameters, unlike gradient-based methods such as Adam. The authors also report results that do not favor their method, such as the comparable performance of the diagonal Laplace approximation and the better extrapolation of AdamW under model mismatch, and show explicitly where the Gaussian approximation degrades.

Critical weaknesses

The regime of small or zero-mean messages is not covered by the theory, although it is natural in the Bayesian neural network setup. The backward message of the product factor relies on a log-normal approximation (Section 3.1) that requires a large signal-to-noise ratio ∣μ∣/σ|\mu|/\sigma, not only a small σ\sigma. Theorem 3.3 explicitly excludes this regime (r≥2r \geq 2), and the paper does not test it directly. For instance, setting τy=0\tau_y = 0 in Equation 7 gives a message with zero precision, which is exactly the setting of the failure example given by the authors for EP in Appendix E.4. Similarly, Section 3.1 claims that δ=0\delta = 0 in the Dirac limit for the forward product message, but Corollary 2.4 requires ∇g≠0\nabla g \neq 0, which fails at zero means.

The experimental evaluation is limited. All experiments are synthetic 1D regression tasks with very small networks (83 and 1932 weights), in which the data are generated from a network of the same kind (the model's own prior, or a wider network in the mismatch experiment), and there are no standard benchmarks such as the UCI regression datasets. Since the model is fully specified and the scale is small, a comparison with the exact posterior (e.g. via HMC) would directly measure the quality of the approximate inference, but no such reference is provided.

Questions for authors

Please address the zero-mean issue raised in the weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer oiKb, part 1 of 2

Summary. We thank the reviewer for an on-point and constructive review. The zero-mean regime (R1.1–R1.3, R1.6) is now covered in theory and measured numerically; the evaluation (R1.4, R1.5) gains baselines, an HMC reference and a larger experiment.

R1.1 (low SNR). Agreed; the revision covers this regime with three facts and a new measurement. First, in the first layer the input yy is observed, a point mass, and Eq. (7) with ρy→∞\rho_y\to\infty returns the exact message N(x;μz/yˉ,σz2/yˉ2)\mathcal{N}(x; \mu_z/\bar y, \sigma_z^2/\bar y^2) for every μz\mu_z, zero included. Second, at μy=0\mu_y=0 the backward message is uninformative, never worse than no message, and in the example of Appendix E.9 the best valid Gaussian message (R1.2). Third, as μy→0\mu_y\to0 it fades continuously to that message: both natural parameters fall to zero together (precision 0.060.06, 6⋅10−46\cdot10^{-4} and 2⋅10−92\cdot10^{-9} at μy=1\mu_y=1, 0.50.5 and 0.10.1 for y∼N(y;μy,1)y\sim\mathcal{N}(y; \mu_y, 1), z∼N(z;2,0.1)z\sim\mathcal{N}(z; 2, 0.1)). Whether it carries the right amount of information at intermediate SNR we now measure by quadrature, against the exact marginal.

Changes.

  • Added a quadrature study below r=2r=2 and at zero mean (Appendix C.4, Figure 6b): the DMA marginal is never farther from the exact marginal than with no message at all, and as far at μy=0\mu_y=0, where EP's message has negative precision; between μy≈0.5\mu_y\approx0.5 and 1.51.5 it is two to three times farther than the best Gaussian marginal (0.840.84 against 0.410.41 nats at μy=1\mu_y=1), and from μy≈2\mu_y\approx2 on close to it.
  • Stated the first-layer case in Section 3.1.
  • Reported how common the regime is in our runs, 2424% of the messages to weights and 4545% of those to activations, and stated that below r=2r=2 the message is safe but carries no accuracy guarantee (Appendix C.4).

R1.2 (zero precision). We agree, and this is where DMA differs from EP most clearly. In the example of Appendix E.9 the true marginal of xx has variance 2.332.33, wider than the incoming message's variance of 11, so no Gaussian message of nonnegative precision can reproduce it; EP's message has precision −0.57-0.57. DMA's message is uninformative, and among all valid Gaussian messages it is the best: the true marginal tt is symmetric, so the best Gaussian marginal has mean zero, and KL[t ∥ N(⋅;0,s2)]\mathrm{KL}[t \thinspace \Vert \thinspace \mathcal{N}(\cdot; 0, s^2)] decreases in s2s^2 up to s2=Vart=2.33s^2=\mathrm{Var}_t=2.33, while a valid message gives the marginal a variance 1/(1+ρ)≤11/(1+\rho)\leq1; the divergence is therefore smallest at ρ=0\rho=0 (0.730.73 nats, against 0.800.80 at ρ=0.1\rho=0.1). What no Gaussian can carry is that ∣x∣|x| is large while its sign is unknown: the true marginal is bimodal by the sign symmetry of the product.

Changes.

  • Added DMA's message and this argument to the example of Appendix E.9.
  • Stated the zero-mean case in Section 3.1.

R1.3 (zero-mean forward message). We agree: Corollary 2.4 needs ∇g≠0\nabla g\neq\mathbf{0}, and the sentence in Section 3.1 overstated it. Theorem 2.3 itself needs only δ<∞\delta<\infty, which holds at zero means, and δ\delta can be given exactly: with X=μx+σxUX=\mu_x+\sigma_xU and Y=μy+σyVY=\mu_y+\sigma_yV, Z/(σxσy)=(rx+U)(ry+V)Z/(\sigma_x\sigma_y)=(r_x+U)(r_y+V), and the divergence from the moment-matched Gaussian is scale-invariant, so δ\delta depends on the signal-to-noise ratios rx,ryr_x,r_y only. At zero means δ=0.2148\delta=0.2148 nats (the density of UVUV is K0(∣z∣)/πK_0(|z|)/\pi), and it falls as either ratio grows: 0.150.15 at (1,1)(1,1), 0.070.07 at (2,2)(2,2), 2.6⋅10−42.6\cdot10^{-4} at (0,10)(0,10).

Changes.

  • Corrected the sentence in Section 3.1.
  • Restated Corollary 2.4 with an explicit bound, δ≤b(max⁡(rx,ry))\delta\leq b(\max(r_x,r_y)) with b(r)=r−2+O(r−4)b(r)=r^{-2}+O(r^{-4}), proved by conditional Gaussianity and the data-processing inequality (Appendix B.3).
AuthorsOpenReview ↗

Response to Reviewer oiKb, part 2 of 2

R1.4 (synthetic evaluation). The synthetic design is deliberate: drawing the true weights from the model's own prior is the standard way to test Bayesian inference (simulation-based calibration; Cook, Gelman and Rubin, 2006; Talts et al., 2018). It guarantees that the model can represent the truth and makes the exact posterior under that prior the target, against which an approximation can be measured (R1.5); the mismatch experiment departs from it in a controlled way. We agree that tasks of this size do not show behavior at scale.

Changes.

  • Added a network of 51 84051\thinspace 840 weights trained on 25 00025\thinspace 000 examples, 27 times the size of the 1 932-weight task, with the baselines that scale there, PBP, IVON, Adam and AdamW, whose setting from the small task breaks down there; diagonal Laplace with the exact Hessian (about 40 to 60 hours for one Hessian diagonal) and HMC are out of reach (Appendix G.3). DMA reaches its stopping epoch within 4 to 7 epochs on every seed, and its band covers the true function at 0.900.90 of the points in the training range and 0.620.62 outside it, while PBP's coverage outside falls to 0.260.26 with the passes, IVON's band covers it at 0.200.20 outside, and Adam gives no band. An epoch takes DMA 1212 s on one core, about as long as PBP and 75 to 80 times as long as IVON and Adam.

R1.5 (HMC reference). Agreed; at this scale a sampling reference is the right measure of the approximation. We compare in function space, since the weight posterior is multimodal under the sign and permutation symmetries of the network and per-weight marginals are not comparable.

Changes.

  • Added an HMC (NUTS) reference on the 83-weight task, four chains per seed, checked on the function (largest R^\hat R 1.0121.012, smallest effective sample size 409409 of 800800 over 20 seeds), against which every method's predictive distribution is compared point by point, inside and outside the training range (Appendix E.2, Table 4). In the training range every method comes close to it (KL 0.0030.003 to 0.100.10); they differ outside the data, where HMC covers the true function at every point, Laplace and DMA at 7575% and 6161%, and IVON and PBP at about a fifth or less.

R1.6 (zero-mean issue). At zero means the forward message's error is bounded, δ=0.2148\delta=0.2148 nats, which Theorem 2.3 turns into a bound on the marginal (R1.3); the backward message is never worse than no message, and the best valid one in the example where EP's has negative precision (R1.2); and in the first layer it is exact for every mean (R1.1). Below r=2r=2 its accuracy is now measured (R1.1). The changes for the zero-mean case, collected:

Changes.

  • Restated Corollary 2.4 with explicit bounds that hold at zero means (Appendix B.3; R1.3).
  • Stated the zero-mean and the first-layer case in Section 3.1 (R1.1, R1.2).
  • Added DMA's message and why it is the best valid one to the example of Appendix E.9 (R1.2).
  • Added the quadrature study below r=2r=2 and at zero mean (Appendix C.4; R1.1).
  • Stated how often the regime occurs, and that it carries no guarantee, in Appendix C.4 (R1.1).

Dear Reviewer oiKb,

Thanks again for your time and effort. As the deadline for the discussion period is approaching, we would greatly appreciate it if you could kindly let us know whether our responses solve your concerns and/or there are any further questions.

Thank you so much for your attention to our work.

Warmest regards,

Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revision Summary

Summary of the reviews. The reviewers found the paper clearly written (Reviewers 1 and 3), the product-backward construction solid and of practical interest (Reviewers 2, 3 and 4), and valued that we report results that do not favor DMA (Reviewer 1). Their concerns fall into four groups, all addressed in the revision. We are grateful for these reviews: by asking for PBP, an exact reference and Bayesian baselines at scale, and by questioning the claims, they led to the comparison and the positioning the revised paper now has.

Positioning. DMA is a principled construction for factor graphs of deterministic (Dirac) factors, such as neural networks. For such a factor the exact message is always tractable when its other inputs are point masses; DMA builds every message to be exact in that limit and projects it onto a Gaussian otherwise. This gives closed-form messages, proper by construction, for every non-conjugate factor of a network, including the product's backward message, whose exact form is improper, and an inference scheme with one sweep per example and no learning rate. The revision states this contribution precisely, with corrected local guarantees, and removes the claims that overstated it. The reviews also sharpened the picture of the evaluation. DMA is not a new method to beat Adam at fitting the data; it is a principled approach for this specific, important class of models, and on it, the new comparison shows, it complements the existing Bayesian methods as the only one that combines a reasonable predictive variance that it keeps over the epochs, a runtime that scales with the network, and no tuning (Table 7). Each of the others falls short in at least one of the three: HMC and diagonal Laplace with the exact Hessian in runtime, both out of reach at 52K weights; PBP and IVON in uncertainty, PBP's shrinking with every pass and IVON's narrow outside the data; Adam and AdamW, which give no uncertainty, and IVON in tuning.

Shared concerns.

G1. Soundness of the product's backward message and of Corollary 2.4 (R1.3, R4.1, R4.2, R4.5, R4.6).

Changes.

  • Corrected the derivation of Eq. (7), which in the submission did not match the formula; the formula and the released code are unchanged (Section 3.1, Appendix B.4).
  • Re-proved Theorem 3.3 for Eq. (7) against the reference it states, and added Corollary B.6 for the marginal (Appendix B.5).
  • Restated Corollary 2.4 with the assumptions it needs and explicit bounds for every factor; corrected Table 2.
  • Validated Eq. (7) by quadrature (Appendix C.4).

G2. Positioning and claims (R2.1, R2.2, R2.3, R2.6).

Changes.

  • Added a related-work paragraph on message-level approximation and corrected the description of PBP (Section 5).
  • Presented Theorem 2.3 as a local error bound and removed the overstated claims (abstract, Sections 1, 2.3, 6).
  • Scoped the claims to factor graphs of deterministic factors as in neural networks.

G3. Evaluation (R1.4, R1.5, R3.1, R4.3).

Changes.

  • Added PBP and an HMC reference, added diagonal Laplace and IVON at 1 932 weights, and compared every method under one protocol: the same prior for every Bayesian method, each seed's own randomly ordered data and the same batches, a fixed budget with whole learning curves, settings selected on the evaluated seeds of the 83-weight task and carried over unchanged, and the fit and the coverage of the true function as the measures (Appendices E–G).
  • Added a 52K-weight network with 25 000 examples, with DMA, PBP, IVON, Adam and AdamW, where HMC and the exact Laplace approximation are out of reach: the picture of the 1 932-weight task holds, and DMA is the only remaining method whose band covers the true function outside the data (Appendix G.3).
  • Made the 83-weight task the check against HMC, where all methods behave much alike, and the two larger tasks the comparison, summarized per method and property (Appendix H).

G4. Convergence and accumulated error (R2.3, R3.2, R4.4).

Changes.

  • Stated that the iteration over epochs has no convergence guarantee, and measured that, run on, it need not reach a fixed point and in our runs keeps moving among solutions, mostly of similar fit (Section 4.2, Appendix D.2).
  • Derived how far one replacement of a batch's message moves the beliefs, and why without damping no global convergence guarantee holds (Lemma D.2, Proposition D.4, Appendix D.2).
  • Trained every method for a fixed epoch budget with whole learning curves; DMA's stopping rule fires where its fit is already as accurate as at the end of the budget (Appendices D.2 and E–G).
  • Measured the error's growth with depth: the error of the forward messages grows at most linearly with depth (Appendix C.5).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.