23
$\begingroup$

Recently there was a ML-like question over on cstheory stackexchange, and I posted an answer recommending Powell's method, gradient descent, 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").

Do others agree with that? Also, it seems to me there is a sense of 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 haven't seen that in a paper. Does anyone know if this has been shown or proven in a paper? (if not for a large class of algorithms maybe for a small class say NNs etc.)

$\endgroup$
  • $\begingroup$ on further thought on this question it seems the related/relevant area of research is called global optimization methods/variants on top of local-type algorithms eg gradient descent... $\endgroup$ – vzn Dec 5 '12 at 6:29
  • $\begingroup$ eg "global optimization for neural network training" by shang & wah $\endgroup$ – vzn Dec 5 '12 at 6:43
29
$\begingroup$

I think you're mixing multiple important concepts. Let me try to clarify a couple of things:

  • There are metaheuristic methods, which are methods that iteratively try to improve a candidate solution. Examples of this are tabu search, simulated annealing, genetic algorithms, etc. Observe that while there can be many cases where these methods work nicely, there isn't any deep understanding of when these methods work and when they don't. And more importantly when they don't get to the solution, we can be arbitrarily far from it. Problems solved by metaheuristic methods tend to be discrete in nature, because there are far better tools to handle continuous problems. But every now and then you see metaheuristics for continuous problems, too.

  • There are numerical optimization methods, people in this community carefully examine the nature of the function that is to be optimized and the restrictions of the solution (into groups like convex optimization, quadratic programming, linear programming, etc) and apply algorithms that have been shown to work for that type of function, and those type of restrictions. When people in this area say "shown to work" they mean a proof. The situation is that these types of methods work in continuous problems. But when your problem falls in this category, this is definitely the tool to use.

  • There are discrete optimization methods, which tend to be things that in nature are connected to algorithms to well studied discrete problems: such as shortest paths, max flow, etc. People in this area also care that their algorithms really work (proofs). There are a subset of people in this group that study really hard problems for which no fast algorithm is expected to exist. They then study approximation algorithms, which are fast algorithms for which they are able to show that their solution is within a constant factor of the true optimum. This is called "approximation algorithms". These people also show their results as proofs.

So... to answer your question, I do not think that metaheuristics are approximation algorithms. It doesn't seem to me as something connected to opinion, it is just fact.

$\endgroup$
  • $\begingroup$ re "numerical optimization methods", "discrete optimization methods", it seems many ML techniques could be proven to be within a constant factor of the true optimum if their "initial search space" is forced to be large, but I havent seen a ref on this. $\endgroup$ – vzn Feb 10 '12 at 22:10
  • 2
    $\begingroup$ I disagree. * for numerical optimization you can get into local minimum (of course you can also apply procedures that make this unprobrable). * The same is for Neural Networks (at least it can happen during training of perceptron). * Genetic algorithms can also get into local minimum, moreover if you choose to big mutation rates you will get no sensible evolution! II also strongly suspect that there are datasets that will always make certain models have arbitralily big errors. $\endgroup$ – jb. Feb 11 '12 at 13:21
  • 2
    $\begingroup$ @vzn many people choose models for which the optimal solution can be found. This is because the use convex loss functions, as SVMs do. Finding the true optimum here means "finding the optimal solution in your search space", so that has nothing to do with how the search space looks like. As jb said, for general loss functions, finding the true optimum is usually impossible / infeasible. $\endgroup$ – Andreas Mueller Feb 14 '12 at 8:44
  • $\begingroup$ accepting this answer as a description of current state of affairs & general categories of applications but still think there are some bridge thms that exist & remain to be proven that link up the separate areas. the proof that NNs can model or "approximate" any continuous mathematical fn to arbitrary degree of accuracy is closely related... ie kolmogorovs thm $\endgroup$ – vzn Dec 5 '12 at 6:42
3
$\begingroup$

Machine learning often deals with optimization of a function which has many local minimas. Feedforward neural networks with hidden units is a good example. Whether these functions are discrete or continuous, there is no method which achieves a global minimum and stops. It is easy to prove that there is no general algorithm to find a global minimum of a continuous function even if it is one-dimensional and smooth (has infinitely many derivatives). In practice, all algorithms for learning neural networks stuck into a local minimum. It is easy to check this: create a random neural network, make a big set of its responses to random inputs, then try to learn another neural network with the same architecture to copy the responses. While the perfect solution exists, neither backpropagation not any other learning algorithm will be able to discover it, starting from a random set of weights.

Some learning methods, like simulated annealing or genetic algorithms, explore many local minimas. For continuous functions there are methods like gradient descent, which find the closest local minimum. They are much faster, thats why they are widely used in practice. But given enough time, the former group of methods outperforms the later in terms of training set error. But with reasonable time constraints, for real world problems, the latter group is usually better.

For some models, like logistic regression, there is one local minimum, the function is convex, the minimization converges to the minimum, but the models themselves are simplistic.

Thats the bitter truth.

Note also that proof of convergence and proof of convergence to the best solution are two different things. K-means algorithm is an example of this.

Finally, for some models we don't know how to learn at all. For example, if the output is an arbitrary computable function of inputs, we don't know good algorithms which, in reasonable time, find a Turing or equivalent machine implementing this function. For instance, if f(1)=2, f(2)=3, f(3)=5, f(4)=7, ..., f(10)=29 (ten first primes), we don't know any learning algorithm which would be able to predict, in reasonable time, that f(11)=31, unless it already knows the concept of prime numbers.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.