In the context of variational autoencoders, we want to maximize the evidence lower bound and this is typically done using Stochastic Gradient Variational Bayes (SGVB). I was curious if there is any work out there or ways to determine the time complexity of SGVB.
Asymptotic running time analysis is not terribly useful for gradient descent used to train machine learning models. In practical machine learning, we run gradient descent for some fixed number of epochs, e.g., 200 epochs; which takes time proportional to 200 times the size of the training set times the time per evaluation of the neural network. That value 200 is arbitrary and set based on what achieves the best accuracy results, and there is little theoretical basis for choosing it.