Most non-convex optimization algorithms I have come across so far rely basically on random restart to find a better solution. e.g. Genetic Algorithm, Simulated Annealing, Metropolis Hastings Monte Carlo. Even in Stochastic Gradient Descent we can think of training each batch as a random perturbation.

There are some non-statistical algorithms in Dynamic Programming and Backtracking which can guarantee global optima, but I havent found any literature that works on noisy data.

What are the strategies which algorithms use (other than random restart) to get out of the local optima and search for the global optima for noisy data?

  • $\begingroup$ It is relatively rare for optimization algorithms used in practice to come with any guarantees. $\endgroup$ – D.W. Jul 8 at 16:00
  • $\begingroup$ Is random restart my only hope of getting out of the local optima, or are there other strategies? $\endgroup$ – Souradeep Nanda Jul 9 at 2:25
  • $\begingroup$ It depends on what optimization problem you're solving. For instance, linear programming and semidefinite programming don't suffer from local optima and don't use random restarts. $\endgroup$ – D.W. Jul 9 at 6:14
  • 1
    $\begingroup$ @D.W. The title says "non convex", so LP and SDP are out. $\endgroup$ – Rodrigo de Azevedo Jul 9 at 6:56
  • $\begingroup$ I think I realize that, what I am demanding, might be NP-Hard. For many optimization problems, only exhaustive search guarantees a global optima. Unless there are problem specific or domain specific hacks. Regardless, what are the commonly used hacks other than random restart and hill climbing? $\endgroup$ – Souradeep Nanda Jul 10 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.