Many iterative algorithms which have parameters start with random initialization. For any randomized algorithms, can we quantify how bad the random starting point will be? Or is there any loose upper bound?
Specifically, I am interested to know if there is any such bound for iterative algorithms for PCA. Thanks in advance.
That is called "dependence on initial values". There are examples of "sensitive dependence on initial values". For example the "Julia set", $j_c$, is the set of all initial values of the complex variable, z, such that the sequence, $z_{n+1}= z_n^2+ c$, for complex number c, converges. Here are some examples of Julia sets: https://en.wikipedia.org/wiki/Julia_set. They change sharply with "c" and the boundaries are extremely complex often being "fractal". There is no simple way to determine which initial points are "good" or "bad".