# An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization

Source: [An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization](<https://www.sota2.com/research/paper/68fa579e1e209131ce9a6da6>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:55:55.946Z

Authors: Yimin Huang, Yujun Li, Hanrong Ye, Zhenguo Li, Zhihua Zhang

Published: 2020-07-11T03:15:21.000Z

## Abstract

The evaluation of hyperparameters, neural architectures, or data augmentation policies becomes a critical model selection problem in advanced deep learning with a large hyperparameter search space. In this paper, we propose an efficient and robust bandit-based algorithm called Sub-Sampling (SS) in the scenario of hyperparameter search evaluation. It evaluates the potential of hyperparameters by the sub-samples of observations and is theoretically proved to be optimal under the criterion of cumulative regret. We further combine SS with Bayesian Optimization and develop a novel hyperparameter optimization algorithm called BOSS. Empirical studies validate our theoretical arguments of SS and demonstrate the superior performance of BOSS on a number of applications, including Neural Architecture Search (NAS), Data Augmentation (DA), Object Detection (OD), and Reinforcement Learning (RL).

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2007.05670>)

[PDF](<https://arxiv.org/pdf/2007.05670.pdf>)
