An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization

2020/07/11 by Huang, Yimin, Li, Yujun, Ye, Hanrong +2 · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2007.05670

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).

Cited by

• A Review on Single-Problem Multi-Attempt Heuristic Optimization

Related

• HyperArm Bandit Optimization: A Novel approach to Hyperparameter Optimization and an Analysis of Bandit Algorithms in Stochastic and Adversarial Settings
• BOHB: Robust and Efficient Hyperparameter Optimization at Scale
• Hyperparameter Optimization in Machine Learning
• Fast Bayesian Optimization of Machine Learning Hyperparameters on Large Datasets
• Combination of Hyperband and Bayesian Optimization for Hyperparameter Optimization in Deep Learning