Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2017 | OriginalPaper | Chapter

RAMBO: Resource-Aware Model-Based Optimization with Scheduling for Heterogeneous Runtimes and a Comparison with Asynchronous Model-Based Optimization

Authors : Helena Kotthaus, Jakob Richter, Andreas Lang, Janek Thomas, Bernd Bischl, Peter Marwedel, Jörg Rahnenführer, Michel Lang

Published in: Learning and Intelligent Optimization

Publisher: Springer International Publishing

share
SHARE

Abstract

Sequential model-based optimization is a popular technique for global optimization of expensive black-box functions. It uses a regression model to approximate the objective function and iteratively proposes new interesting points. Deviating from the original formulation, it is often indispensable to apply parallelization to speed up the computation. This is usually achieved by evaluating as many points per iteration as there are workers available. However, if runtimes of the objective function are heterogeneous, resources might be wasted by idle workers. Our new knapsack-based scheduling approach aims at increasing the effectiveness of parallel optimization by efficient resource utilization. Derived from an extra regression model we use runtime predictions of point evaluations to efficiently map evaluations to workers and reduce idling. We compare our approach to five established parallelization strategies on a set of continuous functions with heterogeneous runtimes. Our benchmark covers comparisons of synchronous and asynchronous model-based approaches and investigates the scalability.
Footnotes
1
Hutter, F., Ramage, S.: Manual for SMAC version v2.10.03-master. Department of Computer Science, UBC. (2015), www.​cs.​ubc.​ca/​labs/​beta/​Projects/​SMAC/​ v2.​10.​03/​manual.​pdf.
 
Literature
1.
go back to reference Ansótegui, C., Malitsky, Y., Samulowitz, H., Sellmann, M., Tierney, K.: Model-based genetic algorithms for algorithm configuration. In: International Joint Conference on Artificial Intelligence, pp. 733–739 (2015) Ansótegui, C., Malitsky, Y., Samulowitz, H., Sellmann, M., Tierney, K.: Model-based genetic algorithms for algorithm configuration. In: International Joint Conference on Artificial Intelligence, pp. 733–739 (2015)
2.
go back to reference Bischl, B., Lang, M., Kotthoff, L., Schiffner, J., Richter, J., Studerus, E., Casalicchio, G., Jones, Z.M.: mlr: Machine learning in R. J. Mach. Learn. Res. 17(170), 1–5 (2016) MATHMathSciNet Bischl, B., Lang, M., Kotthoff, L., Schiffner, J., Richter, J., Studerus, E., Casalicchio, G., Jones, Z.M.: mlr: Machine learning in R. J. Mach. Learn. Res. 17(170), 1–5 (2016) MATHMathSciNet
4.
go back to reference Bischl, B., Wessing, S., Bauer, N., Friedrichs, K., Weihs, C.: MOI-MBO: multiobjective infill for parallel model-based optimization. In: Pardalos, P.M., Resende, M.G.C., Vogiatzis, C., Walteros, J.L. (eds.) LION 2014. LNCS, vol. 8426, pp. 173–186. Springer, Cham (2014). doi: 10.​1007/​978-3-319-09584-4_​17 Bischl, B., Wessing, S., Bauer, N., Friedrichs, K., Weihs, C.: MOI-MBO: multiobjective infill for parallel model-based optimization. In: Pardalos, P.M., Resende, M.G.C., Vogiatzis, C., Walteros, J.L. (eds.) LION 2014. LNCS, vol. 8426, pp. 173–186. Springer, Cham (2014). doi: 10.​1007/​978-3-319-09584-4_​17
7.
go back to reference Chevalier, C., Ginsbourger, D.: Fast computation of the multi-points expected improvement with applications in batch selection. In: Nicosia, G., Pardalos, P. (eds.) LION 2013. LNCS, vol. 7997, pp. 59–69. Springer, Heidelberg (2013). doi: 10.​1007/​978-3-642-44973-4_​7 CrossRef Chevalier, C., Ginsbourger, D.: Fast computation of the multi-points expected improvement with applications in batch selection. In: Nicosia, G., Pardalos, P. (eds.) LION 2013. LNCS, vol. 7997, pp. 59–69. Springer, Heidelberg (2013). doi: 10.​1007/​978-3-642-44973-4_​7 CrossRef
8.
go back to reference Ginsbourger, D., Janusevskis, J., Le Riche, R.: Dealing with asynchronicity in parallel Gaussian process based global optimization. In: 4th International Conference of the ERCIM WG on Computing & Statistics (ERCIM 2011), pp. 1–27 (2011) Ginsbourger, D., Janusevskis, J., Le Riche, R.: Dealing with asynchronicity in parallel Gaussian process based global optimization. In: 4th International Conference of the ERCIM WG on Computing & Statistics (ERCIM 2011), pp. 1–27 (2011)
9.
go back to reference Ginsbourger, D., Le Riche, R., Carraro, L.: Kriging is well-suited to parallelize optimization. In: Tenne, Y., Goh, C.K. (eds.) Computational Intelligence in Expensive Optimization Problems, pp. 131–162. Springer, Heidelberg (2010). doi: 10.​1007/​978-3-642-10701-6_​6 CrossRef Ginsbourger, D., Le Riche, R., Carraro, L.: Kriging is well-suited to parallelize optimization. In: Tenne, Y., Goh, C.K. (eds.) Computational Intelligence in Expensive Optimization Problems, pp. 131–162. Springer, Heidelberg (2010). doi: 10.​1007/​978-3-642-10701-6_​6 CrossRef
10.
13.
go back to reference Janusevskis, J., Le Riche, R., Ginsbourger, D., Girdziusas, R.: Expected improvements for the asynchronous parallel global optimization of expensive functions: potentials and challenges. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 413–418. Springer, Heidelberg (2012). doi: 10.​1007/​978-3-642-34413-8_​37 CrossRef Janusevskis, J., Le Riche, R., Ginsbourger, D., Girdziusas, R.: Expected improvements for the asynchronous parallel global optimization of expensive functions: potentials and challenges. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 413–418. Springer, Heidelberg (2012). doi: 10.​1007/​978-3-642-34413-8_​37 CrossRef
14.
15.
go back to reference Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4), 455–492 (1998) CrossRefMATHMathSciNet Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4), 455–492 (1998) CrossRefMATHMathSciNet
16.
go back to reference Kotthaus, H., Korb, I., Lang, M., Bischl, B., Rahnenführer, J., Marwedel, P.: Runtime and memory consumption analyses for machine learning R programs. J. Stat. Comput. Simul. 85(1), 14–29 (2015) CrossRefMathSciNet Kotthaus, H., Korb, I., Lang, M., Bischl, B., Rahnenführer, J., Marwedel, P.: Runtime and memory consumption analyses for machine learning R programs. J. Stat. Comput. Simul. 85(1), 14–29 (2015) CrossRefMathSciNet
17.
go back to reference Kotthaus, H., Korb, I., Marwedel, P.: Performance analysis for parallel R programs: towards efficient resource utilization. Technical report 01/2015, Department of Computer Science 12, TU Dortmund University (2015) Kotthaus, H., Korb, I., Marwedel, P.: Performance analysis for parallel R programs: towards efficient resource utilization. Technical report 01/2015, Department of Computer Science 12, TU Dortmund University (2015)
18.
go back to reference Lang, M., Bischl, B., Surmann, D.: batchtools: Tools for R to work on batch systems. J. Open Source Softw. 2(10) (2017) Lang, M., Bischl, B., Surmann, D.: batchtools: Tools for R to work on batch systems. J. Open Source Softw. 2(10) (2017)
19.
go back to reference Richter, J., Kotthaus, H., Bischl, B., Marwedel, P., Rahnenführer, J., Lang, M.: Faster model-based optimization through resource-aware scheduling strategies. In: Festa, P., Sellmann, M., Vanschoren, J. (eds.) LION 2016. LNCS, vol. 10079, pp. 267–273. Springer, Cham (2016). doi: 10.​1007/​978-3-319-50349-3_​22 CrossRef Richter, J., Kotthaus, H., Bischl, B., Marwedel, P., Rahnenführer, J., Lang, M.: Faster model-based optimization through resource-aware scheduling strategies. In: Festa, P., Sellmann, M., Vanschoren, J. (eds.) LION 2016. LNCS, vol. 10079, pp. 267–273. Springer, Cham (2016). doi: 10.​1007/​978-3-319-50349-3_​22 CrossRef
20.
go back to reference Roustant, O., Ginsbourger, D., Deville, Y.: DiceKriging, DiceOptim: two R packages for the analysis of computer experiments by Kriging-based metamodeling and optimization. J. Stat. Softw. 51(1), 1–55 (2012) CrossRef Roustant, O., Ginsbourger, D., Deville, Y.: DiceKriging, DiceOptim: two R packages for the analysis of computer experiments by Kriging-based metamodeling and optimization. J. Stat. Softw. 51(1), 1–55 (2012) CrossRef
21.
go back to reference Snoek, J., Larochelle, H., Adams, R.P.: Practical Bayesian optimization of machine learning algorithms. In: Advances in Neural Information Processing Systems, vol. 25. pp. 2951–2959. Curran Associates, Inc. (2012) Snoek, J., Larochelle, H., Adams, R.P.: Practical Bayesian optimization of machine learning algorithms. In: Advances in Neural Information Processing Systems, vol. 25. pp. 2951–2959. Curran Associates, Inc. (2012)
22.
go back to reference Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints. Kluwer Academic Publishers, Dordrecht (2000) CrossRefMATH Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints. Kluwer Academic Publishers, Dordrecht (2000) CrossRefMATH
Metadata
Title
RAMBO: Resource-Aware Model-Based Optimization with Scheduling for Heterogeneous Runtimes and a Comparison with Asynchronous Model-Based Optimization
Authors
Helena Kotthaus
Jakob Richter
Andreas Lang
Janek Thomas
Bernd Bischl
Peter Marwedel
Jörg Rahnenführer
Michel Lang
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-69404-7_13

Premium Partner