Global linear convergence of evolution strategies with recombination on scaling-invariant functions. (English) Zbl 1518.90108
Summary: Evolution Strategies (ESs) are stochastic derivative-free optimization algorithms whose most prominent representative, the CMA-ES algorithm, is widely used to solve difficult numerical optimization problems. We provide the first rigorous investigation of the linear convergence of step-size adaptive ESs involving a population and recombination, two ingredients crucially important in practice to be robust to local irregularities or multimodality. We investigate the convergence of step-size adaptive ESs with weighted recombination on composites of strictly increasing functions with continuously differentiable scaling-invariant functions with a global optimum. This function class includes functions with non-convex sublevel sets and discontinuous functions. We prove the existence of a constant \(r\) such that the logarithm of the distance to the optimum divided by the number of iterations converges to \(r\). The constant is given as an expectation with respect to the stationary distribution of a Markov chain – its sign allows to infer linear convergence or divergence of the ES and is found numerically. Our main condition for convergence is the increase of the expected log step-size on linear functions. In contrast to previous results, our condition is equivalent to the almost sure geometric divergence of the step-size on linear functions.
MSC:
| 90C30 | Nonlinear programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
Keywords:
evolution strategies; linear convergence; CMA-ES; scaling-invariant functions; Foster-Lyapunov drift conditionsReferences:
| [1] | Akimoto, Y., Auger, A., Glasmachers, T.: Drift theory in continuous search spaces: expected hitting time of the (1+1)-ES with 1/5 success rule. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 801-808 (2018) |
| [2] | Akimoto, Y.; Auger, A.; Glasmachers, T.; Morinaga, D., Global linear convergence of evolution strategies on more than smooth strongly convex functions, SIAM J. Optim., 32, 2, 1402-1429 (2022) · Zbl 1509.65044 · doi:10.1137/20M1373815 |
| [3] | Akimoto, Y., Auger, A., Hansen, N.: Convergence of the continuous time trajectories of isotropic evolution strategies on monotonic \(\cal{C}^2 \)-composite functions. In: International Conference on Parallel Problem Solving from Nature, pp. 42-51. Springer (2012) |
| [4] | Akimoto, Y.; Auger, A.; Hansen, N., An ODE method to prove the geometric convergence of adaptive stochastic algorithms, Stoch. Process. Appl., 145, 269-307 (2022) · Zbl 1485.90128 · doi:10.1016/j.spa.2021.12.005 |
| [5] | Akimoto, Y., Nagata, Y., Ono, I., Kobayashi, S.: Bidirectional relation between CMA evolution strategies and natural evolution strategies. In: International Conference on Parallel Problem Solving from Nature, pp. 154-163. Springer (2010) |
| [6] | Akimoto, Y., Nagata, Y., Ono, I., Kobayashi, S.: Theoretical analysis of evolutionary computation on continuously differentiable functions. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 1401-1408 (2010) |
| [7] | Akimoto, Y.; Nagata, Y.; Ono, I.; Kobayashi, S., Theoretical foundation for CMA-ES from information geometry perspective, Algorithmica, 64, 4, 698-716 (2012) · Zbl 1314.62091 · doi:10.1007/s00453-011-9564-8 |
| [8] | Arnold, D.V.: Optimal weighted recombination. In: International Workshop on Foundations of Genetic Algorithms, pp. 215-237. Springer (2005) · Zbl 1078.68682 |
| [9] | Arnold, DV, Weighted multirecombination evolution strategies, Theor. Comput. Sci., 361, 1, 18-37 (2006) · Zbl 1097.68029 · doi:10.1016/j.tcs.2006.04.003 |
| [10] | Arnold, D.V., Beyer, H.G.: Random dynamics optimum tracking with evolution strategies. In: International Conference on Parallel Problem Solving from Nature, pp. 3-12. Springer (2002) |
| [11] | Auger, A., Convergence results for the \((1, \lambda )\)-SA-ES using the theory of \(\phi \)-irreducible Markov chains, Theor. Comput. Sci., 334, 1-3, 35-69 (2005) · Zbl 1080.68113 · doi:10.1016/j.tcs.2004.11.017 |
| [12] | Auger, A., Hansen, N.: A restart CMA evolution strategy with increasing population size. In: 2005 IEEE Congress on Evolutionary Computation, vol. 2, pp. 1769-1776. IEEE (2005) |
| [13] | Auger, A., Hansen, N.: Linear convergence on positively homogeneous functions of a comparison based step-size adaptive randomized search: the (1+1)-ES with generalized one-fifth success rule. arXiv preprint arXiv:1310.8397 (2013) |
| [14] | Auger, A.; Hansen, N., Linear convergence of comparison-based step-size adaptive randomized search via stability of Markov chains, SIAM J. Optim., 26, 3, 1589-1624 (2016) · Zbl 1346.65030 · doi:10.1137/140984038 |
| [15] | Bienvenüe, A.; François, O., Global convergence for evolution strategies in spherical problems: some simple proofs and difficulties, Theor. Comput. Sci., 306, 1-3, 269-289 (2003) · Zbl 1060.68100 · doi:10.1016/S0304-3975(03)00284-6 |
| [16] | Billingsley, P., Convergence of Probability Measures (1999), New York: Wiley, New York · Zbl 0944.60003 · doi:10.1002/9780470316962 |
| [17] | Bosman, PA; Grahl, J.; Thierens, D., Benchmarking parameter-free AMaLGaM on functions with and without noise, Evol. Comput., 21, 3, 445-469 (2013) · doi:10.1162/EVCO_a_00094 |
| [18] | Bouter, A.; Alderliesten, T.; Bosman, PA, Achieving Highly Scalable Evolutionary Real-Valued Optimization by Exploiting Partial Evaluations, Evol. Comput., 29, 1, 129-155 (2021) · doi:10.1162/evco_a_00275 |
| [19] | Chotard, A.; Auger, A., Verifiable conditions for the irreducibility and aperiodicity of Markov chains by analyzing underlying deterministic models, Bernoulli, 25, 1, 112-147 (2019) · Zbl 1440.60068 · doi:10.3150/17-BEJ970 |
| [20] | Chotard, A., Auger, A., Hansen, N.: Cumulative step-size adaptation on linear functions. In: International Conference on Parallel Problem Solving from Nature, pp. 72-81. Springer (2012) |
| [21] | Diouane, Y.; Gratton, S.; Vicente, LN, Globally convergent evolution strategies, Math. Progr., 152, 1, 467-490 (2015) · Zbl 1334.90209 · doi:10.1007/s10107-014-0793-x |
| [22] | Feoktistov, V.: Differential Evolution. Springer (2006) · Zbl 1136.90001 |
| [23] | García-Martínez, C.; Gutiérrez, PD; Molina, D.; Lozano, M.; Herrera, F., Since CEC 2005 competition on real-parameter optimisation: a decade of research, progress and comparative analysis’s weakness, Soft Comput, 21, 19, 5573-5583 (2017) · doi:10.1007/s00500-016-2471-9 |
| [24] | Glasmachers, T.; Krause, O., Convergence analysis of the Hessian estimation evolution strategy, Evol. Comput., 30, 1, 27-50 (2022) · doi:10.1162/evco_a_00295 |
| [25] | Glasmachers, T., Schaul, T., Yi, S., Wierstra, D., Schmidhuber, J.: Exponential natural evolution strategies. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 393-400 (2010) |
| [26] | Hansen, N., An analysis of mutative \(\sigma \)-self-adaptation on linear fitness functions, Evol. Comput., 14, 3, 255-275 (2006) · doi:10.1162/evco.2006.14.3.255 |
| [27] | Hansen, N.: The CMA evolution strategy: a comparing review. In: Towards a New Evolutionary Computation pp. 75-102 (2006) |
| [28] | Hansen, N.: Benchmarking a BI-Population CMA-ES on the BBOB-2009 function testbed. In: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, pp. 2389-2396 (2009) |
| [29] | Hansen, N.: The CMA evolution strategy: a tutorial. arXiv preprint arXiv:1604.00772 (2016) |
| [30] | Hansen, N., Arnold, D.V., Auger, A.: Evolution strategies. In: Springer Handbook of Computational Intelligence, pp. 871-898. Springer, Berlin (2015) |
| [31] | Hansen, N., Auger, A.: Principled design of continuous stochastic search: from theory to practice. In: Theory and principled methods for the design of metaheuristics, pp. 145-180. Springer (2014) · Zbl 1328.68195 |
| [32] | Hansen, N., Auger, A., Ros, R., Finck, S., Pošík, P.: Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009. In: Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation, pp. 1689-1696 (2010) |
| [33] | Hansen, N., Gemperle, F., Auger, A., Koumoutsakos, P.: When do heavy-tail distributions help? In: Parallel Problem Solving from Nature-PPSN IX, pp. 62-71. Springer (2006) |
| [34] | Hansen, N., Kern, S.: Evaluating the CMA evolution strategy on multimodal test functions. In: International Conference on Parallel Problem Solving from Nature, pp. 282-291. Springer (2004) |
| [35] | Hansen, N.; Müller, SD; Koumoutsakos, P., Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evol. Comput., 11, 1, 1-18 (2003) · doi:10.1162/106365603321828970 |
| [36] | Hansen, N.; Ostermeier, A., Completely derandomized self-adaptation in evolution strategies, Evol. Comput., 9, 2, 159-195 (2001) · doi:10.1162/106365601750190398 |
| [37] | Hansen, N.; Ros, R.; Mauny, N.; Schoenauer, M.; Auger, A., Impacts of invariance in search: when CMA-ES and PSO face ill-conditioned and non-separable problems, Appl. Soft Comput., 11, 8, 5755-5769 (2011) · doi:10.1016/j.asoc.2011.03.001 |
| [38] | Igel, C., Suttorp, T., Hansen, N.: A computational efficient covariance matrix update and a (1+ 1)-CMA for evolution strategies. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 453-460 (2006) |
| [39] | Jägersküpper, J.: Analysis of a simple evolutionary algorithm for minimization in euclidean spaces. In: International Colloquium on Automata, Languages, and Programming, pp. 1068-1079. Springer (2003) · Zbl 1039.68586 |
| [40] | Jägersküpper, J.: Rigorous runtime analysis of the (1+1)-ES: 1/5-rule and ellipsoidal fitness landscapes. In: International Workshop on Foundations of Genetic Algorithms, pp. 260-281. Springer (2005) · Zbl 1078.68701 |
| [41] | Jägersküpper, J., How the (1+1)-ES using isotropic mutations minimizes positive definite quadratic forms, Theor. Comput. Sci., 361, 1, 38-56 (2006) · Zbl 1103.68147 · doi:10.1016/j.tcs.2006.04.004 |
| [42] | Jägersküpper, J., Algorithmic analysis of a basic evolutionary algorithm for continuous optimization, Theor. Comput. Sci., 379, 3, 329-347 (2007) · Zbl 1149.90147 · doi:10.1016/j.tcs.2007.02.042 |
| [43] | Jamieson, K.G., Nowak, R., Recht, B.: Query complexity of derivative-free optimization. Adv. Neural Inf. Process. Syst. 25 (2012) |
| [44] | Jastrebski, G.A., Arnold, D.V.: Improving evolution strategies through active covariance matrix adaptation. In: 2006 IEEE International Conference on Evolutionary Computation, pp. 2814-2821. IEEE (2006) |
| [45] | Jensen, S.T., Rahbek, A.: On the law of large numbers for (geometrically) ergodic Markov chains. In: Econometric Theory, pp. 761-766 (2007) · Zbl 1237.60023 |
| [46] | Kappler, C.: Are evolutionary algorithms improved by large mutations? In: International Conference on Parallel Problem Solving from Nature-PPSN IV, pp. 346-355. Springer (1996) |
| [47] | Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of ICNN’95-International Conference on Neural Networks, vol. 4, pp. 1942-1948. IEEE (1995) |
| [48] | Kern, S.; Müller, SD; Hansen, N.; Büche, D.; Ocenasek, J.; Koumoutsakos, P., Learning probability distributions in continuous evolutionary algorithms-a comparative review, Nat. Comput., 3, 1, 77-112 (2004) · Zbl 1074.68063 · doi:10.1023/B:NACO.0000023416.59689.4e |
| [49] | Meyn, SP; Caines, P., Asymptotic behavior of stochastic systems possessing Markovian realizations, SIAM J. Control Optim., 29, 3, 535-561 (1991) · Zbl 0725.60070 · doi:10.1137/0329031 |
| [50] | Meyn, S.P., Tweedie, R.L.: Markov Chains and Stochastic Stability. Springer Science & Business Media (2012) · Zbl 0925.60001 |
| [51] | Morinaga, D., Akimoto, Y.: Generalized drift analysis in continuous domain: linear convergence of (1+1)-ES on strongly convex functions with lipschitz continuous gradients. In: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, pp. 13-24 (2019) · Zbl 1433.68648 |
| [52] | Nesterov, Y.: Introductory lectures on convex optimization: a basic course, vol. 87. Springer Science & Business Media (2003) |
| [53] | Ollivier, Y.; Arnold, L.; Auger, A.; Hansen, N., Information-geometric optimization algorithms: a unifying picture via invariance principles, J. Mach. Learn. Res., 18, 1, 564-628 (2017) · Zbl 1433.90196 |
| [54] | Rechenberg, I.: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution Dr.-Ing. Dissertation. Tech. rep., Verlag Frommann-Holzboog, Stuttgart-Bad Cannstatt (1973) |
| [55] | Rechenberg, I.: Evolutionsstrategie’94. frommann-holzboog (1994) |
| [56] | Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 3, 1247-1293 (2013) · Zbl 1272.90116 · doi:10.1007/s10898-012-9951-y |
| [57] | Ros, R., Hansen, N.: A simple modification in CMA-ES achieving linear time and space complexity. In: International Conference on Parallel Problem Solving from Nature, pp. 296-305. Springer (2008) |
| [58] | Schaul, T.: Natural evolution strategies converge on sphere functions. In: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, pp. 329-336 (2012) |
| [59] | Schaul, T., Glasmachers, T., Schmidhuber, J.: High dimensions and heavy tails for natural evolution strategies. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 845-852 (2011) |
| [60] | Schwefel, H.P.: Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie: mit einer vergleichenden Einführung in die Hill-Climbing-und Zufallsstrategie, vol. 1. Springer (1977) · Zbl 0347.65035 |
| [61] | Schwefel, HP, Evolution and Optimum Seeking (1995), New York: John Wiley & Sons Inc, New York |
| [62] | Storn, R.; Price, K., Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, J. Glob. Optim., 11, 4, 341-359 (1997) · Zbl 0888.90135 · doi:10.1023/A:1008202821328 |
| [63] | Stout, W.F., Stout, W.F.: Almost sure convergence, vol. 24. Academic press (1974) · Zbl 0321.60022 |
| [64] | Suttorp, T.; Hansen, N.; Igel, C., Efficient covariance matrix update for variable metric evolution strategies, Mach. Learn., 75, 2, 167-197 (2009) · Zbl 1470.68183 · doi:10.1007/s10994-009-5102-1 |
| [65] | Teytaud, O., Gelly, S.: General lower bounds for evolutionary algorithms. In: Parallel Problem Solving from Nature-PPSN IX, pp. 21-31. Springer (2006) |
| [66] | Touré, C.; Gissler, A.; Auger, A.; Hansen, N., Scaling-invariant functions versus positively homogeneous functions, J. Optim. Theor. Appl., 191, 1, 363-383 (2021) · Zbl 1486.26022 · doi:10.1007/s10957-021-01943-7 |
| [67] | Tweedie, R., The existence of moments for stationary Markov chains, J. Appl. Probab., 20, 1, 191-196 (1983) · Zbl 0513.60067 · doi:10.2307/3213735 |
| [68] | Yao, X., Liu, Y.: Fast evolution strategies. In: International Conference on Evolutionary Programming, pp. 149-161. Springer (1997) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
