hi all recently there was a ML-like question over on cstheory stackexchange & I posted an answer recommending powells method, gradient descent or genetic algorithms or other "approximation algorithms". in a comment someone told me these methods were "heuristics" and not "approximation algorithms" and frequently did not come close to the theoretical optimum (because they "frequently get stuck in local minima").
my question, do others agree with that? also it seems to me there is a sense in which heuristic algorithms can be guaranteed to come close to theoretical optimums if they are set up to explore a large part of the search space (eg setting parameters/step sizes small), although I havent seen that in a paper. does anyone know if this has been shown or proven in a paper somewhere? (if not for a large class of algorithms maybe for a small class say NNs etc)