2
$\begingroup$

I was watching the following video (https://www.youtube.com/watch?v=-GWze-wtu60 @ 9:30) and came across the following graph:

enter image description here

This graph is meant to show the number of iterations required to achieve similar results on the same function for different optimization algorithms. As we can see in this graph, it appears that "Gradient Free Algorithms" (e.g. Genetic Algorithm) seems to require far more iterations than "Gradient Based Algorithms" - especially as the number of variables increase.

I have always heard the opposite remark being made. Especially in higher dimension problems (i.e. where there are more variables), evaluating the derivatives of complicated loss functions (e.g. the loss functions in machine learning models, neural networks) can become very expensive. This fact is supposed to be one of the main advantages of Gradient Free Algorithms - Gradient Free Algorithms make a sacrifice in terms of their ability to converge, but instead do not require as much computational costs when compared to Gradient Based Algorithms. However, the above graph seems to be negating this fact.

In general, are Gradient Free Algorithms really said to scale as poorly to higher dimensional problems as indicated in the above graph?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Those are function evaluations, not algorithm iterations. Finite difference algorithms may not take many or any more iterations than analytic, but require (at least) an extra "number of design variables" number of function evaluations for each gradient evaluation (usually one gradient evaluation per iteration). If reverse mode automatic (algorithmic) differentiation(a.k.a. backpropagation in neural networks) is used, the time to evaluate entire gradient is roughly independent of number of design variables, so it can scale well up to very large problem sizes (before eventually memory issues) $\endgroup$
    – Mark L. Stone
    Feb 2, 2022 at 17:13

1 Answer 1

Reset to default
3
$\begingroup$

I don't recall ever seeing a claim that gradient-free algorithms had lower computational costs than gradient-based algorithms. The reasons I recall for introducing gradient-free algorithms had to do with (a) cases where the function is not smooth and the gradient simply does not exist, (b) cases where the gradient exists (at least piecewise) but gradient-based algorithms tend to oscillate or get stuck and (c) cases where the gradient may exist but you do not know how to calculate it (for instance, optimizing the output of a simulation program without approximating the response surface).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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