5 ms·

I have always heard that a focused gradient descent outperforms genetic algorithms in every application domain.

deleted 12y ago
[deleted]
jimfleming 12y ago
I'd love for someone who knows more to chime in but its my understanding that gradient descent does not perform well on non-differentiable functions and only finds local optima. Wikipedia seems to confirm this: http://en.wikipedia.org/wiki/Gradient_descent#Limitations http://en.wikipedia.org/wiki/Gradient_descent#Limitations
- j2kun 12y ago
  I spoke with an optimization expert from Argonne National Lab and he gave me the same impression, that gradient descent techniques far outperform evolutionary ones. They're more specialized, make it easier to incorporate domain knowledge, and using stochasticity compensates for local optima.
  - irishtier 12y ago
    Technically combining stochasticity with gradient descent is not pure gradient descent. As for the domain knowledge - this is not specific to gradient descent either, genetic algorithms and their problem encoding can be adapted to a domain to minimise the search space considered - therefore improving performance of the algorithm.
    - j2kun 12y ago
      > Technically combining stochasticity with gradient descent is not pure gradient descent. Sounds like you're picking a nit. Stochastic gradient descent is included in "gradient descent techniques."
  - ppj606 12y ago
    Outperform on what? Can you give specific examples? There are a large number of Combinatorial Optimisation Problems. It is a very sweeping statement to say 'gradient descent techniques far outperform evolutionary ones'.
    - j2kun 12y ago
      He said something along the lines of "I have yet to see an application where evolutionary techniques outperform gradient descent approaches." His talk was about parameter optimization for costly experiments (e.g., manufacturing and testing a vehicle), so his emphasis was on optimization that minimizes the number of function applications. But he seemed to be an expert with a lot of experience.
  - randomsearch 12y ago
    > I spoke with an optimization expert from Argonne National Lab and he gave me the same impression, that gradient descent techniques far outperform evolutionary ones. To rephrase this, you might say that "for conventional, well-understood, combinatorial problems, a gradient descent technique may be the best approach." It's worth noting that in the optimisation community (and often, in the wider Computer Science community) evolutionary algorithms are often looked down upon. I think the main reason for this is the lack of a solid theoretical foundation. Whilst approaches such as schema theory have proposed some explanations for the way GAs solve problems, they remain somewhat "black-box" and gradient descent methods are much more easily understood. I'm not an expert in GAs, but I am an expert in Genetic Programming. A simple local search approach to the kind of problems GP is regularly used to solve would be useless in most cases, due to the nature of the search space. I would imagine the competitiveness of a GA very much depends on the interaction between decision variables in the genome.
    - verdverm 12y ago
      I wrote a non-evolutionary algorithm for symbolic regression, the main and most tractable of the GP applications. PGE outperofms GP by several orders of magnitude. https://github.com/verdverm/go-pge https://github.com/verdverm/go-pge
      - randomsearch 12y ago
        "PGE outperofms GP by several orders of magnitude." [edit] -- just noticed the referenced paper... The above is not a fair conclusion to draw from your paper. I haven't looked at it in detail, but comparing an algorithm on a set of benchmarks for one domain doesn't mean that it outperforms "GP". It does claim that your algorithm outperforms some published results on 22 (sensibly chosen) benchmarks. Don't want to get into a huge debate here, but you should have recreated those results yourself rather than relying on previously published results. Maybe I misunderstood -- I don't have time to go through the paper in detail. If you did recreate them, great, but what about other forms of GP and parameter settings? How does your system do when turned to the problem of, say, bug-fixing, or circuit board optimisation? Generally speaking, any domain-specific approach that uses more knowledge about the search space is going to outperform a vanilla optimisation algorithm. I'm not disagreeing that GP isn't a good algorithm for symbolic regression, only that your results do not support your sweeping statement above. [/edit] I'm not here to defend GP. I think it has many flaws and I'm working on alternative algorithms. However, GP has an established track record of solutions to problems in specific domains unmatched by other methods. A good place to start is to look at the GECCO Human-Competitive awards.
  - reyman 12y ago
    Some evolutionary algorithm use gradient descent, like cma-es algorithm. Population based EA can resolve Multi Objective problem, i'm not sure simple gradient descent can.
  - Gibbon1 12y ago
    I didn't read the article, but did read a book about twenty five years ago. My take away was that the big deal with genetic algorithms is they work without much/any domain specific knowledge. That is one of the great underpinning of biological evolution.
- randomsearch 12y ago
  Yes, this is more or less correct.
SeanLuke 12y ago
That is absurd. Gradient descent assumes you can compute the gradient of your objective function. For a great many functions you cannot define the gradient: indeed you can't even define the objective function well. Genetic algorithms belong to a family of metaheuristics, algorithms designed to tackle such ill-defined functions where gradient descent is simply impossible to use. My concern with this webpage is that it is a far too simplistic treatment of genetic algorithms, to the point of being misleading, and has quite a number of outright errors. I wouldn't use it.
- irishtier 12y ago
  Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima. The point of evolutionary algorithms, or any naturally inspired algorithm for that matter, is that it does not tend to converge upon local optima and has the possibility of moving out of this space towards the global optima. The fact that most problems it is applied to are NP-Complete means that it is unlikely it will find the optimal solution in polynomial time.
  - SeanLuke 12y ago
    > Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima Well... just as evolutionary algorithms are essentially elaborate versions of hill-climbing which enable global search, likewise there are many well-established forms of gradient descent which are global searchers as well. I think the key distinguishing feature is that gradient descent makes strong assumptions about the nature of the space being searched; and metaheuristics make much more general assumptions.
    - GordyMD 12y ago
      Good point. This is key, as you say. Meta-heuristics have the flexibility of providing good performance on all Combinatorial Optimisation Problems. But meta-heuristics, can also be given domain knowledge. and/or be combined with a a heuristic. E.g. Ant Colony Optimisation techniques for Travelling Salesman Problems that combines ACO with Local Search.
tlarkworthy 12y ago
Yes. Gradient descent with random restarts is the pragmatists first optimizations technique. GA's often don't converge to anything useful and require tons of unsubstantiated unintuiative tuning.
yid 12y ago
Your statement contradicts the No Free Lunch theorem because of the word "every".

deleted 12y ago

[deleted]

I'd love for someone who knows more to chime in but its my understanding that gradient descent does not perform well on non-differentiable functions and only finds local optima. Wikipedia seems to confirm this: http://en.wikipedia.org/wiki/Gradient_descent#Limitations http://en.wikipedia.org/wiki/Gradient_descent#Limitations

j2kun 12y ago
I spoke with an optimization expert from Argonne National Lab and he gave me the same impression, that gradient descent techniques far outperform evolutionary ones. They're more specialized, make it easier to incorporate domain knowledge, and using stochasticity compensates for local optima.
- irishtier 12y ago
  Technically combining stochasticity with gradient descent is not pure gradient descent. As for the domain knowledge - this is not specific to gradient descent either, genetic algorithms and their problem encoding can be adapted to a domain to minimise the search space considered - therefore improving performance of the algorithm.
  - j2kun 12y ago
    > Technically combining stochasticity with gradient descent is not pure gradient descent. Sounds like you're picking a nit. Stochastic gradient descent is included in "gradient descent techniques."
- ppj606 12y ago
  Outperform on what? Can you give specific examples? There are a large number of Combinatorial Optimisation Problems. It is a very sweeping statement to say 'gradient descent techniques far outperform evolutionary ones'.
  - j2kun 12y ago
    He said something along the lines of "I have yet to see an application where evolutionary techniques outperform gradient descent approaches." His talk was about parameter optimization for costly experiments (e.g., manufacturing and testing a vehicle), so his emphasis was on optimization that minimizes the number of function applications. But he seemed to be an expert with a lot of experience.
- randomsearch 12y ago
  > I spoke with an optimization expert from Argonne National Lab and he gave me the same impression, that gradient descent techniques far outperform evolutionary ones. To rephrase this, you might say that "for conventional, well-understood, combinatorial problems, a gradient descent technique may be the best approach." It's worth noting that in the optimisation community (and often, in the wider Computer Science community) evolutionary algorithms are often looked down upon. I think the main reason for this is the lack of a solid theoretical foundation. Whilst approaches such as schema theory have proposed some explanations for the way GAs solve problems, they remain somewhat "black-box" and gradient descent methods are much more easily understood. I'm not an expert in GAs, but I am an expert in Genetic Programming. A simple local search approach to the kind of problems GP is regularly used to solve would be useless in most cases, due to the nature of the search space. I would imagine the competitiveness of a GA very much depends on the interaction between decision variables in the genome.
  - verdverm 12y ago
    I wrote a non-evolutionary algorithm for symbolic regression, the main and most tractable of the GP applications. PGE outperofms GP by several orders of magnitude. https://github.com/verdverm/go-pge https://github.com/verdverm/go-pge
    - randomsearch 12y ago
      "PGE outperofms GP by several orders of magnitude." [edit] -- just noticed the referenced paper... The above is not a fair conclusion to draw from your paper. I haven't looked at it in detail, but comparing an algorithm on a set of benchmarks for one domain doesn't mean that it outperforms "GP". It does claim that your algorithm outperforms some published results on 22 (sensibly chosen) benchmarks. Don't want to get into a huge debate here, but you should have recreated those results yourself rather than relying on previously published results. Maybe I misunderstood -- I don't have time to go through the paper in detail. If you did recreate them, great, but what about other forms of GP and parameter settings? How does your system do when turned to the problem of, say, bug-fixing, or circuit board optimisation? Generally speaking, any domain-specific approach that uses more knowledge about the search space is going to outperform a vanilla optimisation algorithm. I'm not disagreeing that GP isn't a good algorithm for symbolic regression, only that your results do not support your sweeping statement above. [/edit] I'm not here to defend GP. I think it has many flaws and I'm working on alternative algorithms. However, GP has an established track record of solutions to problems in specific domains unmatched by other methods. A good place to start is to look at the GECCO Human-Competitive awards.
- reyman 12y ago
  Some evolutionary algorithm use gradient descent, like cma-es algorithm. Population based EA can resolve Multi Objective problem, i'm not sure simple gradient descent can.
- Gibbon1 12y ago
  I didn't read the article, but did read a book about twenty five years ago. My take away was that the big deal with genetic algorithms is they work without much/any domain specific knowledge. That is one of the great underpinning of biological evolution.
randomsearch 12y ago
Yes, this is more or less correct.

SeanLuke 12y ago

That is absurd. Gradient descent assumes you can compute the gradient of your objective function. For a great many functions you cannot define the gradient: indeed you can't even define the objective function well. Genetic algorithms belong to a family of metaheuristics, algorithms designed to tackle such ill-defined functions where gradient descent is simply impossible to use. My concern with this webpage is that it is a far too simplistic treatment of genetic algorithms, to the point of being misleading, and has quite a number of outright errors. I wouldn't use it.

irishtier 12y ago
Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima. The point of evolutionary algorithms, or any naturally inspired algorithm for that matter, is that it does not tend to converge upon local optima and has the possibility of moving out of this space towards the global optima. The fact that most problems it is applied to are NP-Complete means that it is unlikely it will find the optimal solution in polynomial time.
- SeanLuke 12y ago
  > Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima Well... just as evolutionary algorithms are essentially elaborate versions of hill-climbing which enable global search, likewise there are many well-established forms of gradient descent which are global searchers as well. I think the key distinguishing feature is that gradient descent makes strong assumptions about the nature of the space being searched; and metaheuristics make much more general assumptions.
  - GordyMD 12y ago
    Good point. This is key, as you say. Meta-heuristics have the flexibility of providing good performance on all Combinatorial Optimisation Problems. But meta-heuristics, can also be given domain knowledge. and/or be combined with a a heuristic. E.g. Ant Colony Optimisation techniques for Travelling Salesman Problems that combines ACO with Local Search.

tlarkworthy 12y ago

Yes. Gradient descent with random restarts is the pragmatists first optimizations technique. GA's often don't converge to anything useful and require tons of unsubstantiated unintuiative tuning.

yid 12y ago

Your statement contradicts the No Free Lunch theorem because of the word "every".