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

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.

3 Likes

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