Linear Computational Complexity

These updates consume most of the computing time of the algorithm. Therefore the computational complexity is of interest. As seen in Section , the cost function can be split up in a sum of simple terms. If each of them can be computed in constant time, the overall computational complexity is linear with respect to the number of connections.

In general, the computation time is constant if the parents are independent according to $q(\boldsymbol{\theta})$. The independence is violated if any variable receives inputs from a latent variable through multiple paths or from two latent variables which are dependent according to $q(\boldsymbol{\theta})$.