0

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.

user3086871
  • 287
  • I think that this strongly depends on the algorithm and on the objective of the algorithm itself. You need to add more details, otherwise it is impossible to provide a good answer for this question. – the_candyman Apr 10 '18 at 20:27
  • @the_candyman Thank you for your comment. I have added a specific algorithm. – user3086871 Apr 10 '18 at 20:32
  • Thanks for having improved your question. Now, what are your efforts? Please, share with us what you have tried before getting stuck. – the_candyman Apr 10 '18 at 20:35

1 Answers1

1

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".

user247327
  • 18,710