No Cover Image

Journal article 758 views 227 downloads

Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation

George De Ath, Richard M. Everson, Jonathan E. Fieldsend, Alma Rahat Orcid Logo

ACM Transactions on Evolutionary Learning and Optimization, Volume: 1, Issue: 1, Pages: 1 - 22

Swansea University Author: Alma Rahat Orcid Logo

Check full text

DOI (Published version): 10.1145/3425501

Abstract

The performance of acquisition functions for Bayesian optimisation to locate the global optimum of continuous functions is investigated in terms of the Pareto front between exploration and exploitation. We show that Expected Improvement (EI) and the Upper Confidence Bound (UCB) always select solutio...

Full description

Published in: ACM Transactions on Evolutionary Learning and Optimization
ISSN: 2688-299X 2688-3007
Published: Association for Computing Machinery (ACM) 2021
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa55241
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2020-09-22T10:12:55Z
last_indexed 2021-06-03T03:20:44Z
id cronfa55241
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2021-06-02T17:50:53.6697262</datestamp><bib-version>v2</bib-version><id>55241</id><entry>2020-09-22</entry><title>Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation</title><swanseaauthors><author><sid>6206f027aca1e3a5ff6b8cd224248bc2</sid><ORCID>0000-0002-5023-1371</ORCID><firstname>Alma</firstname><surname>Rahat</surname><name>Alma Rahat</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2020-09-22</date><deptcode>SCS</deptcode><abstract>The performance of acquisition functions for Bayesian optimisation to locate the global optimum of continuous functions is investigated in terms of the Pareto front between exploration and exploitation. We show that Expected Improvement (EI) and the Upper Confidence Bound (UCB) always select solutions to be expensively evaluated on the Pareto front, but Probability of Improvement is not guaranteed to do so and Weighted Expected Improvement does so only for a restricted range of weights. We introduce two novel &#x3F5;-greedy acquisition functions. Extensive empirical evaluation of these together with random search, purely exploratory, and purely exploitative search on 10 benchmark problems in 1 to 10 dimensions shows that &#x3F5;-greedy algorithms are generally at least as effective as conventional acquisition functions (e.g. EI and UCB), particularly with a limited budget. In higher dimensions &#x3F5;-greedy approaches are shown to have improved performance over conventional approaches. These results are borne out on a real world computational fluid dynamics optimisation problem and a robotics active learning problem. Our analysis and experiments suggest that the most effective strategy, particularly in higher dimensions, is to be mostly greedy, occasionally selecting a random exploratory solution.</abstract><type>Journal Article</type><journal>ACM Transactions on Evolutionary Learning and Optimization</journal><volume>1</volume><journalNumber>1</journalNumber><paginationStart>1</paginationStart><paginationEnd>22</paginationEnd><publisher>Association for Computing Machinery (ACM)</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>2688-299X</issnPrint><issnElectronic>2688-3007</issnElectronic><keywords/><publishedDay>20</publishedDay><publishedMonth>5</publishedMonth><publishedYear>2021</publishedYear><publishedDate>2021-05-20</publishedDate><doi>10.1145/3425501</doi><url>http://dx.doi.org/10.1145/3425501</url><notes>Supplemental Material available as a zip file from acm.org via https://dl.acm.org/doi/10.1145/3425501</notes><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm>Not Required</apcterm><lastEdited>2021-06-02T17:50:53.6697262</lastEdited><Created>2020-09-22T11:09:38.5772199</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>George De</firstname><surname>Ath</surname><order>1</order></author><author><firstname>Richard M.</firstname><surname>Everson</surname><order>2</order></author><author><firstname>Jonathan E.</firstname><surname>Fieldsend</surname><order>3</order></author><author><firstname>Alma</firstname><surname>Rahat</surname><orcid>0000-0002-5023-1371</orcid><order>4</order></author></authors><documents><document><filename>55241__19773__0efe30dab0584563bcd0de663d1ac28c.pdf</filename><originalFilename>55241.pdf</originalFilename><uploaded>2021-04-28T15:21:40.4852292</uploaded><type>Output</type><contentLength>3353643</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><copyrightCorrect>true</copyrightCorrect><language>eng</language></document></documents><OutputDurs/></rfc1807>
spelling 2021-06-02T17:50:53.6697262 v2 55241 2020-09-22 Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation 6206f027aca1e3a5ff6b8cd224248bc2 0000-0002-5023-1371 Alma Rahat Alma Rahat true false 2020-09-22 SCS The performance of acquisition functions for Bayesian optimisation to locate the global optimum of continuous functions is investigated in terms of the Pareto front between exploration and exploitation. We show that Expected Improvement (EI) and the Upper Confidence Bound (UCB) always select solutions to be expensively evaluated on the Pareto front, but Probability of Improvement is not guaranteed to do so and Weighted Expected Improvement does so only for a restricted range of weights. We introduce two novel ϵ-greedy acquisition functions. Extensive empirical evaluation of these together with random search, purely exploratory, and purely exploitative search on 10 benchmark problems in 1 to 10 dimensions shows that ϵ-greedy algorithms are generally at least as effective as conventional acquisition functions (e.g. EI and UCB), particularly with a limited budget. In higher dimensions ϵ-greedy approaches are shown to have improved performance over conventional approaches. These results are borne out on a real world computational fluid dynamics optimisation problem and a robotics active learning problem. Our analysis and experiments suggest that the most effective strategy, particularly in higher dimensions, is to be mostly greedy, occasionally selecting a random exploratory solution. Journal Article ACM Transactions on Evolutionary Learning and Optimization 1 1 1 22 Association for Computing Machinery (ACM) 2688-299X 2688-3007 20 5 2021 2021-05-20 10.1145/3425501 http://dx.doi.org/10.1145/3425501 Supplemental Material available as a zip file from acm.org via https://dl.acm.org/doi/10.1145/3425501 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University Not Required 2021-06-02T17:50:53.6697262 2020-09-22T11:09:38.5772199 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science George De Ath 1 Richard M. Everson 2 Jonathan E. Fieldsend 3 Alma Rahat 0000-0002-5023-1371 4 55241__19773__0efe30dab0584563bcd0de663d1ac28c.pdf 55241.pdf 2021-04-28T15:21:40.4852292 Output 3353643 application/pdf Accepted Manuscript true true eng
title Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation
spellingShingle Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation
Alma Rahat
title_short Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation
title_full Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation
title_fullStr Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation
title_full_unstemmed Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation
title_sort Greed Is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation
author_id_str_mv 6206f027aca1e3a5ff6b8cd224248bc2
author_id_fullname_str_mv 6206f027aca1e3a5ff6b8cd224248bc2_***_Alma Rahat
author Alma Rahat
author2 George De Ath
Richard M. Everson
Jonathan E. Fieldsend
Alma Rahat
format Journal article
container_title ACM Transactions on Evolutionary Learning and Optimization
container_volume 1
container_issue 1
container_start_page 1
publishDate 2021
institution Swansea University
issn 2688-299X
2688-3007
doi_str_mv 10.1145/3425501
publisher Association for Computing Machinery (ACM)
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url http://dx.doi.org/10.1145/3425501
document_store_str 1
active_str 0
description The performance of acquisition functions for Bayesian optimisation to locate the global optimum of continuous functions is investigated in terms of the Pareto front between exploration and exploitation. We show that Expected Improvement (EI) and the Upper Confidence Bound (UCB) always select solutions to be expensively evaluated on the Pareto front, but Probability of Improvement is not guaranteed to do so and Weighted Expected Improvement does so only for a restricted range of weights. We introduce two novel ϵ-greedy acquisition functions. Extensive empirical evaluation of these together with random search, purely exploratory, and purely exploitative search on 10 benchmark problems in 1 to 10 dimensions shows that ϵ-greedy algorithms are generally at least as effective as conventional acquisition functions (e.g. EI and UCB), particularly with a limited budget. In higher dimensions ϵ-greedy approaches are shown to have improved performance over conventional approaches. These results are borne out on a real world computational fluid dynamics optimisation problem and a robotics active learning problem. Our analysis and experiments suggest that the most effective strategy, particularly in higher dimensions, is to be mostly greedy, occasionally selecting a random exploratory solution.
published_date 2021-05-20T04:09:19Z
_version_ 1763753652999159808
score 11.012678

Similar Items