Noisy Blackbox Optimization Using Multi-Fidelity Queries: A Tree Search Approach

Details

• Alternative Title:
  Sensing and Communications in V2V and V2I Settings Project Title, from cover
• Creators:
  Sen, Rajat ; Kandasamy, Kirthevasan ; Shakkottai, Sanjay
• Corporate Creators:
  University of Texas at Austin. Data-Supported Transportation Operations & Planning Center (D-STOP)
• Corporate Contributors:
  United States. Department of Transportation. University Transportation Centers (UTC) Program
• Subject/TRT Terms:
  • Algorithms
  • Connected vehicles
  • Mobile communication systems
  • Optimization
  • Validation
• Publication/ Report Number:
  D-STOP/2020/159
• Resource Type:
  Tech Report
• Geographical Coverage:
  United States
• Corporate Publisher:
  University of Texas at Austin. Data-Supported Transportation Operations & Planning Center (D-STOP)
• Abstract:
  We study the problem of black-box optimization of a noisy function in the presence of low-cost approximations or fidelities, which is motivated by problems like hyper-parameter tuning. In hyper-parameter tuning evaluating the black-box function at a point involves training a learning algorithm on a large dataset at a particular hyper-parameter and evaluating the validation error. Even a single such evaluation can be prohibitively expensive. Therefore, it is beneficial to use low cost approximations, like training the learning algorithm on a sub-sampled version of the whole data-set. These low-cost approximations/ fidelities can however provide a biased and noisy estimate of the function value. In this work, we combine structured state-space exploration through hierarchical partitioning with querying these partitions at multiple fidelities, and develop a multi-fidelities bandit based tree-search algorithm for noisy blackbox optimization. We derive simple regret guarantees for our algorithm and validate its performance on real and synthetic datasets.
• Format:
  PDF
• Funding:
  DTRT13-G-UTC58
• Download URL:
  https://rosap.ntl.bts.gov/view/dot/55861/dot_55861_DS1.pdf
• File Type:
  [PDF - 727.14 KB]
• Collection(s):
  University Transportation Centers ; US Transportation Collection
• Main Document Checksum:
  urn:sha256:cc10eb1425a5b6e2174528ac45ab5b1543f57cf3d3057da619ce87a5719745f0