Running time of vb using Big O notation?

[srtaheri]

Does anyone know what is the complexity of the vb algorithm in terms of big O notation? I couldn’t find it anywhere.

[avehtari]

@cgoold

This paper says its O(N2T)\mathcal{O}(N^2T) , with NN latent states and TT time points.

That paper discusses Viterbi algorithm, but I guess vb in the question refers to ADVI algorithm in Stan.

For ADVI the time complexity is O(T). The computational cost depends also on the number of Monte Carlo draws in each step of ADVI, and the cost of computing log density which depends on the model.

[cgoold]

@avehtari

That paper discusses Viterbi algorithm, but I guess vb in the question refers to ADVI algorithm in Stan.

Ah, of course. I had been doing some HMM work and implicitly read it as Viterbi.