Optimizing Expensive Functions I'm trying some different techniques to optimise a Boosted Gradient Regressor by using an evolutionary programming technique to try and find the most efficient set of features. So far I've been having some good results (Been able to remove 65% of the features with an increase in accuracy), but I'm not impressed with how expensive each epoch is to run (in terms of time). Currently, this is a very expensive problem to optimise, 2^79 as there are a maximum of 79 features to choose from, which is 6.0446291e+23 possible feature permutations.

So far, each individual in my population has a binary encoded gene, where 1 = use this feature, and 0 = do not use this feature. Each individual in a population is evaluated by running the boosted regressor with the selected features, and then the RMSLE is calculated. I start to see good results around 3 hours into the optimisation function (I'm not doing any parallel computing).

I've been doing a little bit of research into how I can attempt to "predict" how good my boosted regressor will be without actually needing to evaluate its performance. So far I've found the following techniques:


Problem Approximation. I can see how this would be useful in some specific cases, but as I'm not really able to reduce the complexity of evaluating how accurate my boosted regressor is it seems irrelevant. 
Functional Approximation. I think this is quite an interesting technique. They whole premise is to approximate the fitness of an individual without actually needing to evaluate the function
Fitness Inheritance. This also seems rather interesting, and perhaps the most efficient of the methods listed above? Individuals are clustered into specific groups, and then the "represented" individual of each cluster has its fitness evaluated, and then the remaining individual's fitness are approximated by upon a distance measurement. 


I could see some issues with these techniques though. If the combination of features used don't have a linear relationship with the output, then surely the function approximation would have a hard time approximating the potential fitness of an individual? I'm a bit stumped on what to further look at.
According to the two papers (Limited Evaluation Evolutionary Algorithm (LEEA) and Limited Evaluation Cooperative Co-evolutionary Differential Evolution Algorithm (LECCDE)) you can approximate the result of the evolutionary algorithms by applying the algorithm not on the whole dataset but on mini-batches like in SGD (Stochastic Gradient Descent). This significantly reduces computation time (about 25 times in LECCDE paper for an ANN on MNIST dataset).

According to Prellberg 2018 Limited Evaluation Evolutionary Optimization the training times of LE algorithms is still 10 times longer than the Adam variation of stochastic gradient descent. In your case it is not possible to calculate gradients.

The following changes to the evolutionary algorithm are proposed in the first paper (LEEA):


Use mini-batching while ensuring the diversity of the expected outputs.



  Ideal mini-batch size in LEEA was determined experimentally to be 2. ...To apply the idea of diversity in minibatches, the output range is divided into two equally sized sections, and examples selected so that each mini-batch contains
  one example for both sections of the range. A new mini-batch is randomly generated at the beginning of each generation.



Use ancestor fitness for evaluation. 



  f'=(f_p1 + f_p2)/2*(1-d) + f.
  
  Where f' is the individual's modified fitness. f is the fitness of the
  individual against the current mini-batch. f_pn is the fitness of
  parent n. d is a constant decay value.


The second paper (LECCDE) points to the following speed-up using Limited Evaluation algorithms:

LECCDE vs CCDE for different datasets:

Dataset    Parameters   Speedup             Accuracy
WBC        1652          1.10 times faster  1.2% worse
ESR        9052          2.05 times faster  0.3% worse
HAR        28406         4.00 times faster  0.2% worse
MNIST      47710        25.3  times faster  unknown