6 ms·

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 fi

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.

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.