Add support for generic surrogate framework

[beniz]

A surrogate (machine) learning model replaces some of the calls to the true objective function by learning from past calls, and delivering an approximate ranking of objective function values.

[beniz]

I am moving forward on this front, questions on implementation details will be posted here.

My current understanding is that all variants are using a pre-selection scheme. Does it make sense to also support a simpler scheme where calls to the surrogates and the objective functions are simply alternated every \hat{n} steps. This has some consequences on the code architecture.

I am following the pre-selection scheme from page 112 of http://hal.archives-ouvertes.fr/docs/00/82/38/82/PDF/Thesis.pdf and steps 5 & 6 from Figure 4.8-D:

• using abs(a) instead of a
• how is it guaranteed that 'a' remains bounded to \lambda_pre and \lambda, especially if sel0 and sel1 are parameters exposed to the user ? I'd like to avoid looping over until getting satisfying values.

I have more questions, but let's solve one issue at a time!

[beniz]

This is the first ready-to-run surrogate support for the libcmaes. See the features, results and what come next below.

I am considering that this ticket is for the main surrogate structural support, so depending on activity for remarks and comments over the next few days, I will close it and open new tickets for more detailed features.

What is implemented now:

• generic surrogate support within the ask/eval/tell framework
• surrogate learning from genotype: I don't see disadvantages from learning directly from the genotype, as opposed as learning the surrogate from the phenotype, but let me know if you do see potential difficulties
• ACM surrogate learning with pre-selection/pre-screening of candidates and controllable ratio of surrogate exploitation
• ability to test surrogate learning with no exploitation
• provides Ranking SVM code as a ready to use ranker + sample code
• ability to visualize the surrogate's training / testing errors / smoothed test error

What comes next:

• support for separable algorithms
• exposition of surrogates to Python bindings (will be another ticket)
• control of surrogate lifelength (another ticket)
• learning/optimization of surrogate hyperparameters (another ticket)
• additional tricks from the 2013 papers ? (additional tickets)

Results

Main testing tools:

• Ranking SVM:

./examples/test_rsvm

• CMA-ES + Ranking SVM as surrogate:

./examples/sample_code_surrogate_svm --help
./examples/sample_code_surrogate_svm -fname rosenbrock -ftarget 1e-10 -sigma0 0.5 -x0 2 -dim 10

• Fsphere no exploitation
  
  To reproduce:

./examples/sample_code_surrogate_rsvm -fname fsphere -ftarget 1e-10 -sigma0 0.5 -x0 2 -dim 10 -fplot surr.dat --no_exploit
python tests/cma_multiplt_surr.py surr.dat

• Fsphere with surrogate exploitation
  
  To reproduce:

./examples/sample_code_surrogate_rsvm -fname fsphere -ftarget 1e-10 -sigma0 0.5 -x0 2 -dim 10 -fplot surr.dat
python tests/cma_multiplt_surr.py surr.dat

• Rosenbrock no exploitation
  
  To reproduce:

./examples/sample_code_surrogate_rsvm -fname rosenbrock -ftarget 1e-10 -sigma0 0.5 -x0 2 -dim 10 -fplot surr.dat --no_exploit
python tests/cma_multiplt_surr.py surr.dat

• Rosenbrock with surrogate exploitation
  

To reproduce:

./examples/sample_code_surrogate_rsvm -fname rosenbrock -ftarget 1e-10 -sigma0 0.5 -x0 2 -dim 10 -fplot surr.dat
python tests/cma_multiplt_surr.py surr.dat

• Elli no exploitation
  
  To reproduce:

./examples/sample_code_surrogate_rsvm -fname elli -ftarget 1e-10 -sigma0 2 -x0 2 -dim 10 -fplot surr.dat --no_exploit
python tests/cma_multiplt_surr.py surr.dat

• Elli with surrogate exploitation
  
  To reproduce:

./examples/sample_code_surrogate_rsvm -fname elli -ftarget 1e-10 -sigma0 0.5 -x0 2 -dim 10 -fplot surr.dat
python tests/cma_multiplt_surr.py surr.dat

Note: noisyness of test error in surrogate exploitation is due to the use of testing against 3 new samples at every iteration.

[beniz]

First version of the documentation is available here: https://github.com/beniz/libcmaes/wiki/Using-Surrogates-for-expensive-objective-functions
It is available from the main documentation page https://github.com/beniz/libcmaes/wiki

[beniz]

Main fixes to algorithms and default values, better performances and novel tiny program added for assessing performances on a range of functions for comparison with literature. Results have been assessed once, but I'll publish a final dataset of results here for identifying and informing about remaining weaknesses and for comparison with literature.

[beniz]

Theoretical fix. The selection sampling was using an identical Mersenne twister for two independent normal distributions, a consequence of C++ copying the initial twister (http://stackoverflow.com/questions/22987429/avoid-same-random-numbers-with-same-generator-random-c-11). At the moment there's no discernible effect on the results.

[beniz]

Results for ACM surrogates and comparison from https://www.lri.fr/~ilya/phd.html pages 95-96 (see image below) are below. For comparison all experiments uses the exact same parameters than the literature above.

• libcmaes

running surrogates on elli
D   fevals_avg
2   306.3 +/- 15.7293 (10)
4   670.5 +/- 28.2103 (10)
5   811.9 +/- 21.7419 (10)
8   1448.6 +/- 47.0342 (10)
10  2001.8 +/- 73.7147 (10)
16  5064.1 +/- 181.266 (10)
20  8336.4 +/- 137.94 (10)
32  20058 +/- 453.425 (10)
40  30180.5 +/- 450.763 (10)

running surrogates on rosenbrock
D       fevals_avg
2       573.667 +/- 357.795 (9)
4       952.667 +/- 360.211 (9)
5       1072.38 +/- 594.202 (8)
8       1384.1 +/- 111.025 (10)
10      1895.67 +/- 221.716 (9)
16      5556.33 +/- 1014.05 (9)
20      8150.4 +/- 681.513 (10)
32      27046 +/- 1550.77 (9)
40      41545 +/- 2852.78 (9)

running surrogates on ackley
D       fevals_avg
2       384 +/- 114.145 (6)
4       502 +/- 156.891 (9)
5       494.7 +/- 40.6534 (10)
8       677.4 +/- 18.4961 (10)
10      797.333 +/- 32.1913 (9)
16      1192.6 +/- 46.1569 (10)
20      1733.2 +/- 201.574 (10)
32      2494 +/- 59.1486 (10)
40      3355.5 +/- 50.5289 (10)

running surrogates on schwefel
D       fevals_avg
2       162.3 +/- 22.7862 (10)
4       289.6 +/- 14.6396 (10)
5       338.4 +/- 21.6172 (10)
8       527.7 +/- 25.1947 (10)
10      714.1 +/- 28.5063 (10)
16      2013.1 +/- 148.241 (10)
20      3187.6 +/- 125.106 (10)
32      9520.4 +/- 779.319 (10)
40      12752 +/- 336.346 (10)

running surrogates on schwefel14
D       fevals_avg
2       719.4 +/- 76.9054 (10)
4       -nan +/- inf (0)
5       987.75 +/- inf (8)
8       1353.9 +/- inf (10)
10      1750.6 +/- inf (10)
16      3615.7 +/- inf (10)
20      5644 +/- inf (10)
32      15430.4 +/- inf (10)
40      22428.5 +/- inf (10)

Literature:

All results are reproducible with:

./tests/surr_test -dims 2,4,5,8,10,16,20,32,40 -runs 10 -fname rosenbrock

Change -fname accordingly. Lower the number of runs and dimensions for a quick output.

(I am investigating the problem for schwefel14 in 4-D)

[beniz]

Schwefel14 in 4-D triggers ConditionCov, then tolX. When these stopping criteria are deactivated, sigma becomes nan at some point and yields the failure observed on all runs in 4-D.

[beniz]

Got rid of the call to rand() in rankingsvm which is not thread-safe and definitely deprecated, see http://cpp.indi.frih.net/blog/2014/12/the-bell-has-tolled-for-rand/

Also, re-closing this issue. My understanding is that the oddity with schwefel14 in 4-D is a numerical error, but I will definitely reopen if I need to reconsider this.

[nikohansen]

If I understand the experimental setup correctly, you should get the same results on schwefel and schwefel14 if you set the target f-value on the latter to be `sqrt(sqrt(10e-10)). This could just be an additional check.

[beniz]

Here is what I get when modifying the ftarget value as suggested:

./surr_tests -dims 4 -runs 10 -fname schwefel14
D   fevals_avg
4   283.3 +/- 18.7086 (10)
./surr_tests -dims 4 -runs 10 -fname schwefel
D   fevals_avg
4   131.2 +/- 13.891 (10)

[nikohansen]

Looks alright: what I meant was that the target 10**-10 for schwefel is equivalent with target 10**-(10/4) for schwefel14, which is what your result seem to suggest.