Leveraging memory effects and gradient information in consensus-based optimisation: on global convergence in mean-field law. (English) Zbl 07930520
Summary: In this paper, we study consensus-based optimisation (CBO), a versatile, flexible and customisable optimisation method suitable for performing nonconvex and nonsmooth global optimisations in high dimensions. CBO is a multi-particle metaheuristic, which is effective in various applications and at the same time amenable to theoretical analysis thanks to its minimalistic design. The underlying dynamics, however, is flexible enough to incorporate different mechanisms widely used in evolutionary computation and machine learning, as we show by analysing a variant of CBO which makes use of memory effects and gradient information. We rigorously prove that this dynamics converges to a global minimiser of the objective function in mean-field law for a vast class of functions under minimal assumptions on the initialisation of the method. The proof in particular reveals how to leverage further, in some applications advantageous, forces in the dynamics without loosing provable global convergence. To demonstrate the benefit of the herein investigated memory effects and gradient information in certain applications, we present numerical evidence for the superiority of this CBO variant in applications such as machine learning and compressed sensing, which en passant widen the scope of applications of CBO.
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 90C26 | Nonconvex programming, global optimization |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
| 35Q90 | PDEs in connection with mathematical programming |
| 35Q84 | Fokker-Planck equations |
Keywords:
high-dimensional global optimisation; metaheuristics; consensus-based optimisation; mean-field limit; Fokker-Planck equationsReferences:
| [1] | Albi, G., Bongini, M., Cristiani, E. & Kalise, D. (2015) Invisible sparse control of self-organizing agents leaving unknown environments. SIAM J. Appl. Math. 76(4), 1683-1710. · Zbl 1415.91230 |
| [2] | Ambrosio, L., Gigli, N. & Savaré, G. (2008) Gradient Flows in Metric Spaces and in the Space of Probability Measures, , 2nd ed., Birkhäuser Verlag, Basel. · Zbl 1145.35001 |
| [3] | Arnold, L. (1974) Stochastic Differential Equations: Theory and Applications, Wiley-Interscience [John Wiley & Sons], New York/London/Sydney. Translated from the German. · Zbl 0278.60039 |
| [4] | Back, T., Fogel, D. B. & Michalewicz, Z. (1997) Handbook of Evolutionary Computation, Institute of Physics Publishing, Bristol; Oxford University Press, New York. · Zbl 0883.68001 |
| [5] | Bae, H.-O., Ha, S.-Y., Kang, M., Lim, H., Min, C. & Yoo, J. (2022) A constrained consensus based optimization algorithm and its application to finance. Appl. Math. Comput.416, PaperNo.126726,10. · Zbl 1510.90208 |
| [6] | Blum, C. & Roli, A. (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv.35(3), 268-308. |
| [7] | Borghi, G., Herty, M. & Pareschi, L. (2022) A consensus-based algorithm for multi-objective optimization and its mean-field description. In: 2022 IEEE 61st Conference on Decision and Control (CDC), IEEE, pp. 4131-4136. |
| [8] | Borghi, G., Herty, M. & Pareschi, L. (2023) An adaptive consensus based method for multi-objective optimization with uniform Pareto front approximation. Appl. Math. Optim.88(2), 1-43. · Zbl 07730259 |
| [9] | Borghi, G., Herty, M. & Pareschi, L. (2023) Constrained consensus-based optimization. SIAM J. Optim.33(1), 211-236. · Zbl 1517.35227 |
| [10] | Bungert, L., Wacker, P. & Roith, T. (2022) Polarized consensus-based dynamics for optimization and sampling. arXiv: 2211.05238. |
| [11] | Candès, E. J., Romberg, J. K. & Tao, T. (2006) Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math.59(8), 1207-1223. · Zbl 1098.94009 |
| [12] | Carrillo, J. A., Choi, Y.-P., Totzeck, C. & Tse, O. (2018) An analytical framework for consensus-based global optimization method. Math. Models Methods Appl. Sci.28(6), 1037-1066. · Zbl 1397.35311 |
| [13] | Carrillo, J. A., Hoffmann, F., Stuart, A. M. & Vaes, U. (2022) Consensus-based sampling. Stud. Appl. Math.148(3), 1069-1140. |
| [14] | Carrillo, J. A., Jin, S., Li, L. & Zhu, Y. (2021) A consensus-based global optimization method for high dimensional machine learning problems. ESAIM Control Optim. Calc. Var.27, Paper No.S5,22. · Zbl 1480.60195 |
| [15] | Carrillo, J. A., Totzeck, C. & Vaes, U. (2023) Consensus-based optimization and ensemble Kalman inversion for global optimization problems with constraints. In: Modeling and Simulation for Collective Dynamics, World Scientific, Singapore, pp. 195-230. |
| [16] | Carrillo, J. A., Trillos, N. G., Li, S. & Zhu, Y. (2023). FedCBO: reaching group consensus in clustered federated learning through consensus-based optimization. arXiv: 2305.02894. |
| [17] | Chen, J., Jin, S. & Lyu, L. (2020) A consensus-based global optimization method with adaptive momentum estimation. arXiv: 2012.04827. |
| [18] | Cipriani, C., Huang, H. & Qiu, J. (2022) Zero-inertia limit: from particle swarm optimization to consensus-based optimization. SIAM J. Appl. Math.54(3), 3091-3121. · Zbl 1500.90088 |
| [19] | Couzin, I. D., Krause, J., Franks, N. R. & Levin, S. A. (2005) Effective leadership and decision-making in animal groups on the move. Nature433(7025), 513-516. |
| [20] | Cristiani, E., Piccoli, B. & Tosin, A. (2011) Multiscale modeling of granular flows with application to crowd dynamics. Multiscale Model. Simul.9(1), 155-182. · Zbl 1221.35232 |
| [21] | Dembo, A. & Zeitouni, O. (1998) Large Deviations Techniques and Applications, Applications of Mathematics (New York), Vol. 38, 2nd ed., Springer-Verlag, New York. · Zbl 0896.60013 |
| [22] | Donoho, D. L. (2006) Compressed sensing. IEEE Trans. Inf. Theory52(4), 1289-1306. · Zbl 1288.94016 |
| [23] | Dorigo, M. & Blum, C. (2005) Ant colony optimization theory: a survey. Theor. Comput. Sci.344(2-3), 243-278. · Zbl 1154.90626 |
| [24] | Fogel, D. B. (2000) Evolutionary Computation. Toward a New Philosophy of Machine Intelligence, 2nd ed., IEEE Press, Piscataway, NJ. |
| [25] | Fornasier, M., Huang, H., Pareschi, L. & Sünnen, P. (2020) Consensus-based optimization on hypersurfaces: well-posedness and mean-field limit. Math. Models Methods Appl. Sci.30(14), 2725-2751. · Zbl 1467.90039 |
| [26] | Fornasier, M., Huang, H., Pareschi, L. & Sünnen, P. (2021) Consensus-based optimization on the sphere: convergence to global minimizers and machine learning. J. Mach. Learn. Res.22, PaperNo.237,55. · Zbl 07626752 |
| [27] | Fornasier, M., Huang, H., Pareschi, L. & Sünnen, P. (2022) Anisotropic diffusion in consensus-based optimization on the sphere. SIAM J. Optim.32(3), 1984-2012. · Zbl 1509.65047 |
| [28] | Fornasier, M., Klock, T. & Riedl, K. (2021). Consensus-based optimization methods converge globally. arXiv: 2103.15130. |
| [29] | Fornasier, M., Klock, T. & Riedl, K. (2022) Convergence of anisotropic consensus-based optimization in mean-field law. In: Jiménez Laredo, J. L., Hidalgo, J. I. & Babaagba, K. O. (editors), Applications of Evolutionary Computation, Springer International Publishing, Cham, pp. 738-754. |
| [30] | Foucart, S. & Rauhut, H. (2013) A mathematical introduction to compressive sensing. In: Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York. · Zbl 1315.94002 |
| [31] | Grassi, S., Huang, H., Pareschi, L. & Qiu, J. (2023). Mean-field particle swarm optimization. In: Modeling and Simulation for Collective Dynamics (pp. 127-193). |
| [32] | Grassi, S. & Pareschi, L. (2021) From particle swarm optimization to consensus based optimization: stochastic modeling and mean-field limit. Math. Models Methods Appl. Sci.31(8), 1625-1657. · Zbl 1473.35570 |
| [33] | Ha, S.-Y., Jin, S. & Kim, D. (2020) Convergence of a first-order consensus-based global optimization algorithm. Math. Models Methods Appl. Sci.30(12), 2417-2444. · Zbl 1467.90040 |
| [34] | Ha, S.-Y., Jin, S. & Kim, D. (2021) Convergence and error estimates for time-discrete consensus-based optimization algorithms. Numer. Math.147(2), 255-282. · Zbl 1467.65064 |
| [35] | Ha, S.-Y., Kang, M. & Kim, D. (2022) Emergent behaviors of high-dimensional Kuramoto models on Stiefel manifolds. Automatica136, PaperNo.110072. · Zbl 1479.34068 |
| [36] | Hegselmann, R. & Krause, U. (2002) Opinion dynamics and bounded confidence models, analysis, and simulation. J. Artif. Soc. Soc. Simul.5(3). |
| [37] | Higham, D. J. (2001) An algorithmic introduction to numerical simulation of stochastic differential equations. SIAM Rev.43(3), 525-546. · Zbl 0979.65007 |
| [38] | Holland, J. H. (1975) Adaptation in Natural and Artificial Systems. An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, Ann Arbor, MI. · Zbl 0317.68006 |
| [39] | Huang, H. & Qiu, J. (2022) On the mean-field limit for the consensus-based optimization. Math. Methods Appl. Sci.45(12), 7814-7831. |
| [40] | Huang, H., Qiu, J. & Riedl, K. (2022) Consensus-based optimization for saddle point problems. arXiv:2212.12334. |
| [41] | Huang, H., Qiu, J. & Riedl, K. (2023) On the global convergence of particle swarm optimization methods. Appl. Math. Optim.88(2), 30. · Zbl 1515.65037 |
| [42] | Kalise, D., Sharma, A. & Tretyakov, M. V. (2023) Consensus-based optimization via jump-diffusion stochastic differential equations. Math. Models Methods Appl. Sci.33(02), 289-339. · Zbl 1515.60198 |
| [43] | Kennedy, J. & Eberhart, R. (1995) Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks, Vol. 4, IEEE, pp. 1942-1948. |
| [44] | Kim, J., Kang, M., Kim, D., Ha, S.-Y. & Yang, I. (2020). A stochastic consensus method for nonconvex optimization on the Stiefel manifold. In: 2020 59th IEEE Conference on Decision and Control (CDC), IEEE, pp. 1050-1057. |
| [45] | Klamroth, K., Stiglmayr, M. & Totzeck, C. (2022) Consensus-based optimization for multi-objective problems: a multi-swarm approach. arXiv: 2211.15737. |
| [46] | Lecun, Y., Bottou, L., Bengio, Y. & Haffner, P. (1998) Gradient-based learning applied to document recognition. Proc. IEEE86(11), 2278-2324. |
| [47] | Lecun, Y., Cortes, C. & Burges, C. (2010) MNIST handwritten digit database. http://yann.lecun.com/exdb/mnist/ |
| [48] | Miller, P. D. (2006) Applied Asymptotic Analysis, , Vol. 75, American Mathematical Society, Providence, RI. · Zbl 1101.41031 |
| [49] | Moulines, E. & Bach, F. (2011) Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In: Advances in Neural Information Processing Systems 24. |
| [50] | Øksendal, B. (2003) Stochastic Differential Equations: An Introduction with Applications, 6th ed., Springer-Verlag, Berlin. · Zbl 1025.60026 |
| [51] | Parrish, J. K. & Edelstein-Keshet, L. (1999) Complexity, pattern, and evolutionary trade-offs in animal aggregation. Science284(5411), 99-101. |
| [52] | Pinnau, R., Totzeck, C., Tse, O. & Martin, S. (2017) A consensus-based model for global optimization and its mean-field limit. Math. Models Methods Appl. Sci.27(1), 183-204. · Zbl 1388.90098 |
| [53] | Riedl, K., Klock, T., Geldhauser, C. & Fornasier, M. (2023) Gradient is all you need?arXiv: 2306.09778. |
| [54] | Schillings, C., Totzeck, C. & Wacker, P. (2023) Ensemble-based gradient inference for particle methods in optimization and sampling. SIAM/ASA J. Uncertain. Quantif.11(3), 757-787. · Zbl 1518.65142 |
| [55] | Totzeck, C. & Wolfram, M.-T. (2020) Consensus-based global optimization with personal best. Math. Biosci. Eng.17(5), 6026-6044. · Zbl 1473.90132 |
| [56] | Vicsek, T. & Zafeiris, A. (2012) Collective motion. Phys. Rep.517(3-4), 71-140. |
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.
