open-problem

Status: open (2026-10-25; revised the same day after Codex’s review, which showed the tree case solved). Area: variational inference, risk measures · Prerequisites: Bethe free energy, convex risk measures · Related: Unusual Wirings §4, L-SPEC-003 Exposed Parameters and Energy Channels §3, Bethe Free Energy, Scalar and Multivariate Energy, Energies and Entropies.

Sources: Donsker & Varadhan, CPAM 28(1), 1975; Artzner, Delbaen, Eber & Heath, Coherent Measures of Risk, Math. Finance 9(3), 1999; Rockafellar & Uryasev, Optimization of Conditional Value-at-Risk, J. Risk 2(3), 2000 (Theorem 1, continuous losses), and Conditional Value-at-Risk for General Loss Distributions, J. Banking & Finance 26(7), 2002; Föllmer & Schied, Stochastic Finance, 4th ed., 2016, ch. 4; Yedidia, Freeman & Weiss, IEEE Trans. Inf. Theory 2005; the question is original to this vault.

Bibliography: Donsker & Varadhan 1975 · Artzner et al. 1999 · Rockafellar & Uryasev 2000 · Rockafellar & Uryasev 2002 · Föllmer & Schied 2016 · Yedidia et al. 2005

Question

A factor graph’s free energy scalarises energies by their expectation, which is additive over factors. If the total energy is instead scalarised by a risk measure (the entropic risk, CVaR), how well can be computed, bounded and optimised by local message passing on a loopy graph, and with how large messages? On a tree the entropic risk is exact (below); the question is what survives on loops, for CVaR, and under optimisation.

Setting

Variables , factors with energies , and a normalised joint law on (the model, or a belief of that form). A Bethe approximation alone, with locally consistent pseudomarginals , does not define a joint law, so is undefined for it unless a reconstruction is specified (on a tree, the pseudomarginals determine ). Under , is a random variable; its parts may be dependent.

  • Entropic risk: , .
  • CVaR: , .

“Local” means computed by messages on the graph’s edges; the size of a message is part of the answer.

What is known

  • The expectation is additive, , without any independence. That is the energy part of the Bethe free energy ; the entropy part is Bethe’s approximation, exact on trees (Yedidia et al. 2005).
  • The entropic risk at a fixed is a ratio of partition functions (derivation): with , the partition function of the tilted potentials. So . On a tree sum-product computes both exactly (when the integrals are tractable; when is), with messages of the same size as for . (Codex checked tree elimination against enumeration on a finite tree in its review; not a test in the repository yet.)
  • On a loopy graph each partition function has a Bethe approximation, so is a natural local estimate. It is a difference of two approximations, with no sign or error guarantee known here. Open.
  • Additivity of the entropic risk holds for independent parts and fails in general under dependence; shared variables can, but need not, make the parts dependent.
  • CVaR is coherent, hence subadditive, (Artzner et al. 1999; the minimisation formula for general distributions is Rockafellar & Uryasev 2002, the 2000 paper’s Theorem 1 assuming continuous losses). The sum of local CVaRs is a local upper bound; its gap is open.
  • CVaR on a chain is exact with larger messages: carry the accumulated cost in the state, so each forward message is a distribution over , and the terminal message gives the law of , hence every risk measure of it. Exact, but the message size grows with the support of (derivation, after Codex’s review).
  • Donsker–Varadhan: for a probability law, , and with , , attained at . Restricting to a factorised family gives a lower bound, the variational counterpart of the tilted partition function above.
  • Heavy tails: if the total has a heavier-than-exponential right tail, for every . A single heavy-tailed part suffices when the other parts are bounded below; in general parts can cancel (, ). CVaR is finite when .

What would count as an answer

Additive, translation-invariant error bounds (energies may be negative, so ratios are not meaningful) for the loopy estimate or the local CVaR bound, in terms of the graph’s loops and the dependence of the parts; classes of loopy graphs where they are exact; for CVaR, lower bounds on the message size any exact local method needs; and for optimisation, a message-passing method for with its stationary points characterised. A measurement on Gaussian graphs (below), with a test, would be a first step.

Why it matters here

It decides whether L-SPEC-003 Exposed Parameters and Energy Channels §3’s risk scalarisations can be used inside message passing or only as an outer objective over sampled energies, and which of them makes sense for heavy-tailed energies.

Leads

  • Gaussian graphs with quadratic energies. If each is quadratic in its own variables, the tilted model has precision with the sparsity of the original graph, so it is again a Gaussian graph on the same edges (proper while ). Its partition function, hence , is a log-determinant; for a centred and , . On loops, Gaussian BP gives exact means when it converges but not exact log-determinants, which makes this the cleanest place to measure the loopy estimate’s error.
  • Risk-sensitive control has the entropic risk of a quadratic cost on a chain (risk-sensitive LQG) with a Riccati recursion; a dynamic-programming relative of the tree case. To be checked and cited before use.
  • CVaR by an outer scalar. For fixed , is not additive over factors, but the outer minimisation is one-dimensional; combined with the chain construction above, the cost is one augmented forward pass per .