Evolutionary Algorithms Vs. Gradient Optimization: Comparing Costs

Question

When it comes to optimizing objective functions belonging to Statistical and Machine Learning Models, there seems to be a general rule:

High dimensional objective functions with many parameters are "computationally expensive" to optimize As such, there tends to be two general types of algorithms that are used to optimize objective functions:

• Gradient Descent: Gradient Descent tries to find the minimum point (i.e. "optimize") of these objective functions by repeatedly calculating the derivatives of these objective functions, and moving in the direction of these derivatives.

• Evolutionary Algorithms: Evolutionary Algorithms (e.g. Genetic Algorithm) also try to find the minimum point of these objective functions, but instead of repeatedly evaluating the derivatives of the function, they work by "randomly moving in many directions at the same time, and probabilistically moving more in those directions that are producing lesser values of the function". This is called "mutation and crossover" - I have greatly simplified the process.

My Question: As the number of dimensions in the objective function increases, it becomes more and more computationally expensive to repeatedly evaluate the derivatives of the objective function- since Evolutionary Algorithms do not need to repeatedly evaluate these derivatives, they are said to be "computationally cheaper" compared to Gradient Based Methods. Although there have been no major results established on the convergence of Evolutionary Algorithms (whereas many theoretical results have been established on the convergence of Gradient Based Methods) : For the exact same objective function - do we know precisely how much cheaper "Crossover and Mutation" costs us compared to "Evaluating Second Derivatives"?

There still seems to be some costs associated with "Crossover and Mutation" (e.g. randomly storing, sorting and permuting well-performing "chromosomes" i.e. past solutions) - but do we know how much cheaper this costs us compared to evaluating derivatives (e.g. can we bound this using some Big-O Landau Notation or using Linear vs. Polynomial Time)?

Thanks!

Extra: Comparison of Gradient Descent and Genetic Algorithm for Optimizing the Rastrign Function using the R Programming language

1) Genetic Algorithm

library(GA)

start.time <- Sys.time()



  #define function to be optimized
Rastrigin <- function(x1, x2)
{
  20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
}

x1 <- x2 <- seq(-5.12, 5.12, by = 0.1)

#run optimization through the genetic algorithm (with constraints)
GA <- ga(type = "real-valued", 
         fitness =  function(x) -Rastrigin(x[1], x[2]),
         lower = c(-5.12, -5.12), upper = c(5.12, 5.12), 
         popSize = 50, maxiter = 1000, run = 100)

end.time <- Sys.time()
time.taken <- end.time - start.time

Results:

 time.taken

Time difference of 1.266233 secs

GA@solution
                x1          x2
[1,] -4.947186e-06 3.72529e-07

2) Gradient Descent

library(pracma)

start.time <- Sys.time()

Rastrigin <- function(x)
    {
        return(20 + x[1]^2 + x[2]^2 - 10*(cos(2*pi*x[1]) + cos(2*pi*x[2])))
    }

 steep_descent(c(1, 1), Rastrigin)

end.time <- Sys.time()
    time.taken <- end.time - start.time
    
    time.taken

Results:

time.taken
Time difference of 0.01959896 secs

$xmin
[1] 0.9949586 0.9949586

$fmin
[1] 1.989918

$niter
[1] 3

References:

• https://cran.r-project.org/web/packages/GA/vignettes/GA.html
• https://rdrr.io/rforge/pracma/man/steep_descent.html

Answer 1

I think this is an overgeneralization. For cases with very expensive objective functions (i.e. multiphysics simulations), genetic algorithms are basically unusable and they use the adjoint method to get the sensitivities at a cost independent of the number of design variables. We can also use the direct adjoint method for second derivatives at reduced cost. I would hesitate to use a smooth and cheap function as the basis of a more general comparison between genetic and gradient based methods.