Solved – what does one mean by numerical integration is too expensive

Question

I am reading about Bayesian inference and I came across the phrase "numerical integration of the marginal likelihood is too expensive"

I do not have a background in mathematics and I was wondering what exactly does expensive mean here? Is it just in terms of computation power or is there something more.

Answer 1

In the context of computational problems, including numerical methods for Bayesian inference, the phrase "too expensive" generally could refer to two issues

1. a particular problem is too "large" to compute for a particular "budget"
2. a general approach scales badly, i.e. has high computational complexity

For either case, the computational resources comprising the "budget" may consist of things like CPU cycles (time complexity), memory (space complexity), or communication bandwidth (within or between compute nodes). In the second instance, "too expensive" would mean intractable.

In the context of Bayesian computation, the quote is likely referring to issues with marginalization over a large number of variables.

For example, the abstract of this recent paper begins

Integration is affected by the curse of dimensionality and quickly becomes intractable as the dimensionality of the problem grows.

and goes on to say

We propose a randomized algorithm that ... can in turn be used, for instance, for marginal computation or model selection.

(For comparison, this recent book chapter discusses methods considered "not too expensive".)