×

Output space entropy search framework for multi-objective Bayesian optimization. (English) Zbl 1522.68444

Summary: We consider the problem of black-box multi-objective optimization (MOO) using expensive function evaluations (also referred to as experiments), where the goal is to approximate the true Pareto set of solutions by minimizing the total resource cost of experiments. For example, in hardware design optimization, we need to find the designs that trade-off performance, energy, and area overhead using expensive computational simulations. The key challenge is to select the sequence of experiments to uncover high-quality solutions using minimal resources. In this paper, we propose a general framework for solving MOO problems based on the principle of output space entropy (OSE) search: select the experiment that maximizes the information gained per unit resource cost about the true Pareto front. We appropriately instantiate the principle of OSE search to derive efficient algorithms for the following four MOO problem settings: 1) The most basic single-fidelity setting, where experiments are expensive and accurate; 2) Handling black-box constraints which cannot be evaluated without performing experiments; 3) The discrete multi-fidelity setting, where experiments can vary in the amount of resources consumed and their evaluation accuracy; and 4) The continuous-fidelity setting, where continuous function approximations result in a huge space of experiments. Experiments on diverse synthetic and real-world benchmarks show that our OSE search based algorithms improve over state-of-the-art methods in terms of both computational-efficiency and accuracy of MOO solutions.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
90C29 Multi-objective and goal programming
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arellano-Valle, R. B., CONTRERAS-REYES, J. E., & Genton, M. G. (2013). Shannon entropy and mutual information for multivariate skew-elliptical distributions.Scandinavian Journal of Statistics,40(1). · Zbl 1259.62002
[2] Ariyarit, A., & et al. (2017). Multi-fidelity multi-objective efficient global optimization applied to airfoil design problems.Applied Sciences,7(12).
[3] Azzalini, A. (1985). A class of distributions which includes the normal ones.Scandinavian Journal of Statistics. · Zbl 0581.62014
[4] Output Space Entropy Search Framework for Multi-Objective Bayesian Optimization · Zbl 1522.68444
[5] Belakaria, S., Deshwal, A., & Doppa, J. R. (2019). Max-value entropy search for multiobjective Bayesian optimization. InConference on Neural Information Processing Systems, pp. 7823-7833.
[6] Belakaria, S., Deshwal, A., & Doppa, J. R. (2020a). Multi-fidelity multi-objective Bayesian optimization: An output space entropy search approach.. InAAAI, pp. 10035-10043.
[7] Belakaria, S., Deshwal, A., Jayakodi, N. K., & Doppa, J. R. (2020b). Uncertainty-aware search framework for multi-objective Bayesian optimization. InAAAI conference on artificial intelligence.
[8] Belakaria, S., Jackson, D., Cao, Y., Doppa, J. R., & Lu, X. (2020c). Machine learning enabled fast multi-objective optimization for electrified aviation power system design. InIEEE Energy Conversion Congress and Exposition (ECCE).
[9] Belakaria, S., Zhou, Z., Deshwal, A., Doppa, J. R., Pande, P., & Heo, D. (2020d). Design of multi-output switched-capacitor voltage regulator via machine learning. In Proceedings of the Twenty-Third IEEE/ACM Design Automation and Test in Europe Conference (DATE).
[10] Che, S., Boyer, M., Meng, J., Tarjan, D., Sheaffer, J. W., Lee, S., & et al. (2009). Rodinia: A benchmark suite for heterogeneous computing. In2009 IEEE international symposium on workload characterization (IISWC).
[11] Choi et al. (2018). On-chip communication network for efficient training of deep convolutional networks on heterogeneous manycore systems.IEEE Transactions on Computers (TC),67(5), 672-686. · Zbl 1395.68013
[12] Cover, T. M., & Thomas, J. A. (2012).Elements of information theory. John Wiley and Sons. · Zbl 1140.94001
[13] Das et al. (2017). Design-space exploration and optimization of an energy-efficient and reliable 3D small-world network-on-chip.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD),36(5), 719-732.
[14] Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., & Fast, A. (2002a). Nsga-ii.IEEE Transactions on Evolutionary Computation,6(2), 182-197.
[15] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002b). A fast and elitist multiobjective genetic algorithm: Nsga-ii.IEEE transactions on evolutionary computation,6(2), 182- 197.
[16] Deshwal, A., Belakaria, S., & Doppa, J. R. (2021a). Bayesian optimization over hybrid spaces.InProceedings of the 38th International Conference on Machine Learning (ICML), Vol. 139 ofProceedings of Machine Learning Research, pp. 2632-2643. PMLR.
[17] Deshwal, A., Belakaria, S., & Doppa, J. R. (2021b). Mercer features for efficient combinatorial bayesian optimization. InThirty-Fifth AAAI Conference on Artificial Intelligence (AAAI), pp. 7210-7218. AAAI Press.
[18] Deshwal, A., Belakaria, S., Doppa, J. R., & Fern, A. (2020). Optimizing discrete spaces via expensive evaluations: A learning to search framework. InThe Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI), pp. 3773-3780. AAAI Press.
[19] Deshwal, A., Simon, C., & Doppa, J. R. (2021). Bayesian optimization of nanoporous materials.ChemRxiv.
[20] Deshwal et al. (2019). MOOS: A multi-objective design space exploration and optimization framework for NoC enabled manycore systems.ACM Transactions on Embedded Computing Systems (TECS),18(5s), 77:1-77:23.
[21] Doppa, J. R. (2021). Adaptive experimental design for optimizing combinatorial structures. InProceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), pp. 4940-4945.
[22] Emmerich, M., & Klinkenberg, J.-w. (2008). The computation of the expected improvement in dominated hypervolume of pareto front approximations.Technical Report, Leiden University,34.
[23] Feliot, P., Bect, J., & Vazquez, E. (2017). A Bayesian approach to constrained single-and multi-objective optimization.Journal of Global Optimization,67(1-2), 97-133. · Zbl 1390.90441
[24] Fern´andez-S´anchez, D., Garrido-Merch´an, E. C., & Hern´andez-Lobato, D. (2020). Maxvalue entropy search for multi-objective bayesian optimization with constraints.arXiv preprint arXiv:2011.01150v1.
[25] Garrido-Merch´an, E. C., & Hern´andez-Lobato, D. (2019). Predictive entropy search for multi-objective Bayesian optimization with constraints.Neurocomputing,361, 50-68.
[26] Habib, A., Singh, H. K., & et al. (2019). A multiple surrogate assisted multi/many-objective multi-fidelity evolutionary algorithm.Information Sciences.
[27] Hasbun, J. E. (2012).Classical mechanics with MATLAB applications. Jones & Bartlett Publishers.
[28] Hennig, P., & Schuler, C. J. (2012). Entropy search for information-efficient global optimization.Journal of Machine Learning Research (JMLR),13(Jun), 1809-1837. · Zbl 1432.65073
[29] Hern´andez-Lobato, D., Hernandez-Lobato, J., Shah, A., & Adams, R. (2016). Predictive entropy search for multi-objective Bayesian optimization. InProceedings of International Conference on Machine Learning (ICML), pp. 1492-1501.
[30] Hern´andez-Lobato, J. M., Hoffman, M. W., & Ghahramani, Z. (2014). Predictive entropy search for efficient global optimization of black-box functions. InAdvances in Neural Information Processing Systems, pp. 918-926.
[31] Hoffman, M. W., & Ghahramani, Z. (2015). Output-space predictive entropy search for flexible global optimization. InNIPS workshop on Bayesian Optimization.
[32] Hong, W., & et al (2019). A dual-output step-down switched-capacitor voltage regulator with a flying capacitor crossing technique for enhanced power efficiency.IEEE Transactions on Very Large Scale Integration (VLSI) Systems,27(12).
[33] Huang, D., Allen, T. T., Notz, W. I., & Miller, R. A. (2006). Sequential kriging optimization using multiple-fidelity evaluations.Structural and Multidisciplinary Optimization.
[34] Joardar et al. (2018). Learning-based application-agnostic 3D NoC design for heterogeneous manycore systems.IEEE Transactions on Computers,68(6), 852-866. · Zbl 07093724
[35] Output Space Entropy Search Framework for Multi-Objective Bayesian Optimization · Zbl 1522.68444
[36] Jones, D. R., Perttunen, C. D., & Stuckman, B. E. (1993). Lipschitzian optimization without the lipschitz constant.Journal of Optimization Theory and Applications,79(1), 157- 181. · Zbl 0796.49032
[37] Kandasamy, K., Dasarathy, G., Oliva, J. B., & et al (2016). Gaussian process bandit optimisation with multi-fidelity evaluations. InConference on Neural Information Processing Systems. · Zbl 1437.90167
[38] Kandasamy, K., Dasarathy, G., Schneider, J., & Poczos, B. (2017). Multi-fidelity Bayesian optimisation with continuous approximations.ICML. · Zbl 1437.90167
[39] Kennedy, M. C., & O’Hagan, A. (2000). Predicting the output from a complex computer code when fast approximations are available.Biometrika. · Zbl 0974.62024
[40] Klein, A., Falkner, S., Bartels, S., Hennig, P., & Hutter, F. (2017). Fast Bayesian optimization of machine learning hyperparameters on large datasets. InInternational Conference on Artificial Intelligence and Statistics. · Zbl 1421.62027
[41] Knowles, J. (2006). Parego: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems.IEEE Transactions on Evolutionary Computation,10(1), 50-66.
[42] Kontogiannis, S. G., Demange, J., Kipouros, T., & et al. (2018). A comparison study of two multifidelity methods for aerodynamic optimization. In56th AIAA/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference.
[43] Kotthoff, L., Thornton, C., Hoos, H. H., Hutter, F., & Leyton-Brown, K. (2017). Auto-weka 2.0: Automatic model selection and hyperparameter optimization in weka.Journal of Machine Learning Research (JMLR),18(1), 826-830.
[44] Lam, R., Allaire, D. L., & et al (2015). Multifidelity optimization using statistical surrogate modeling for non-hierarchical information sources. In56th AIAA/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference.
[45] McLeod, M., Osborne, M. A., & Roberts, S. J. (2017). Practical Bayesian optimization for variable cost objectives.arXiv preprint arXiv:1703.04335.
[46] Michalowicz, J. V., Nichols, J. M., & Bucholtz, F. (2013).Handbook of differential entropy. Chapman and Hall/CRC. · Zbl 1275.60001
[47] Moss, H. B., Leslie, D. S., & Rayson, P. (2020). Mumbo: Multi-task max-value Bayesian optimization.The European Conference on Machine Learnin.
[48] Oh, C., Gavves, E., & Welling, M. (2018). BOCK : Bayesian optimization with cylindrical kernels. In Dy, J. G., & Krause, A. (Eds.),Proceedings of the 35th International Conference on Machine Learning (ICML), Vol. 80 ofProceedings of Machine Learning Research, pp. 3865-3874. PMLR.
[49] Oh, C., Tomczak, J., Gavves, E., & Welling, M. (2019). Combinatorial Bayesian Optimization using the Graph Cartesian Product. InNeurIPS.
[50] Picheny, V. (2015). Multi-objective optimization using Gaussian process emulators via stepwise uncertainty reduction.Statistics and Computing,25(6), 1265-1280. · Zbl 1331.90102
[51] Picheny, V., Ginsbourger, D., & et al. (2013a). Quantile-based optimization of noisy computer experiments with tunable precision.Technometrics.
[52] Picheny, V., Wagner, T., & Ginsbourger, D. (2013b). A benchmark of kriging-based infill criteria for noisy optimization.Structural and Multidisciplinary Optimization,48(3), 607-626.
[53] Ponweiser, W., Wagner, T., Biermann, D., & Vincze, M. (2008). Multiobjective optimization on a limited budget of evaluations using model-assisted s-metric selection. InInternational Conference on Parallel Problem Solving from Nature, pp. 784-794. Springer.
[54] Rahimi, A., & Recht, B. (2008). Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pp. 1177-1184.
[55] Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., & De Freitas, N. (2016). Taking the human out of the loop: A review of Bayesian optimization.Proceedings of the IEEE, 104(1), 148-175.
[56] Shu, L., Jiang, P., Zhou, Q., Shao, X., Hu, J., & Meng, X. (2018). An on-line variable fidelity metamodel assisted multi-objective genetic algorithm for engineering design optimization.Applied Soft Computing,66.
[57] Snoek, J., Larochelle, H., & Adams, R. P. (2012). Practical Bayesian optimization of machine learning algorithms. InAdvances in Neural Information Processing Systems, pp. 2951-2959.
[58] Song, J., Chen, Y., & Yue, Y. (2019). A general framework for multi-fidelity Bayesian optimization with Gaussian processes.International Conference on Artificial Intelligence and Statistics.
[59] Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. (2009). Gaussian process optimization in the bandit setting: No regret and experimental design.arXiv preprint arXiv:0912.3995. · Zbl 1365.94131
[60] Surjanovic, S., & Bingham, D. (2020). Virtual library of simulation experiments: Test functions and datasets.Retrieved January 21, 2020, fromhttp://www.sfu.ca/  ssurjano.
[61] Swersky, K., Snoek, J., & Adams, R. P. (2013). Multi-task Bayesian optimization. In Conference on Neural Information Processing Systems.
[62] Takeno, S., Fukuoka, H., Tsukada, Y., Koyama, T., Shiga, M., Takeuchi, I., & Karasuyama, M. (2019). Multi-fidelity Bayesian optimization with max-value entropy search.arXiv:1901.08275.
[63] Wang, Z., & Jegelka, S. (2017). Max-value entropy search for efficient Bayesian optimization. InProceedings of International Conference on Machine Learning (ICML).
[64] Wang, Z., Zhou, B., & Jegelka, S. (2016). Optimization as estimation with Gaussian processes in bandit settings. InProceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1022-1031.
[65] Williams, C. K., & Rasmussen, C. E. (2006).Gaussian processes for machine learning, Vol. 2. MIT Press. · Zbl 1177.68165
[66] Wu, J., & Frazier, P. I. (2018). Continuous-fidelity Bayesian optimization with knowledge gradient.NIPS Workshop on Bayesian Optimization.
[67] Output Space Entropy Search Framework for Multi-Objective Bayesian Optimization · Zbl 1522.68444
[68] Yang, K. K., Wu, Z., & Arnold, F. H. (2019). Machine-learning-guided directed evolution for protein engineering.Nature methods,16(8), 687-694.
[69] Zhang, Q., & Li, H. (2007). Moea/d: A multiobjective evolutionary algorithm based on decomposition.IEEE Transactions on Evolutionary Computation,11(6), 712-731.
[70] Zhang, Y., Hoang, T. N., & et al (2017). Information-based multi-fidelity Bayesian optimization. InConference on Neural Information Processing Systems Workshop on Bayesian Optimization.
[71] Zhu, J., Wang, Y.-J., & Collette, M. (2014). A multi-objective variable-fidelity optimization method for genetic algorithms.Engineering Optimization,46(4), 521-542.
[72] Zitzler, E. (1999).Evolutionary algorithms for multiobjective optimization: Methods and applications, Vol. 63. Ithaca: Shaker.
[73] Zuluaga, M., Sergent, G., Krause, A., & P¨uschel, M. (2013). Active learning for multiobjective optimization. InProceedings of International Conference on Machine Learning (ICML), pp. 462-470
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.