The convergence of estimators, e.g. maximum likelihood estimators, for increasing sample size is well understood in many cases. However, even when the rate of convergence of the estimator is known, practical application is hampered by the fact, that the estimator cannot always be obtained at tenable computational cost. This paper combines the analysis of convergence of the estimator itself with the analysis of the convergence of stochastic optimization algorithms, e.g. threshold accepting, to the theoretical estimator. We discuss the joint convergence of estimator and algorithm in a formal framework. An application to a GARCH-model demonstrates the approach in practice by estimating actual rates of convergence through a large scale simulation study. Despite of the additional stochastic component introduced by the use of an optimization heuristic, the overall quality of the estimates turns out to be superior compared to conventional approaches.