# Non-stochastic Best Arm Identification and Hyperparameter Optimization

arXiv: https://arxiv.org/abs/1502.07943 · HTML: https://mlsanity.com/paper/1502.07943/

## Key facts

- Cited by 221 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2015.

## Built on by (most cited first, 30 of 221)

- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer](https://mlsanity.com/paper/2203.03466/) (2022)
- [Efficient Deep Learning: A Survey on Making Deep Learning Models Smaller, Faster, and Better](https://mlsanity.com/paper/2106.08962/) (2021)
- [FederatedScope-LLM: A Comprehensive Package for Fine-tuning Large Language Models in Federated Learning](https://mlsanity.com/paper/2309.00363/) (2023)
- [Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges](https://mlsanity.com/paper/2107.05847/) (2021)
- [Neural Architecture Search: Insights from 1000 Papers](https://mlsanity.com/paper/2301.08727/) (2023)
- [HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO](https://mlsanity.com/paper/2109.06716/) (2021)
- [HyperMorph: Amortized Hyperparameter Learning for Image Registration](https://mlsanity.com/paper/2101.01035/) (2021)
- [Efficient Methods for Natural Language Processing: A Survey](https://mlsanity.com/paper/2209.00099/) (2022)
- [Using Large Language Models for Hyperparameter Optimization](https://mlsanity.com/paper/2312.04528/) (2023)
- [Automated Reinforcement Learning (AutoRL): A Survey and Open Problems](https://mlsanity.com/paper/2201.03916/) (2022)
- [YAHPO Gym -- An Efficient Multi-Objective Multi-Fidelity Benchmark for Hyperparameter Optimization](https://mlsanity.com/paper/2109.03670/) (2021)
- [On the Importance of Hyperparameter Optimization for Model-based Reinforcement Learning](https://mlsanity.com/paper/2102.13651/) (2021)
- [AMLB: an AutoML Benchmark](https://mlsanity.com/paper/2207.12560/) (2022)
- [Unbiased Gradient Estimation in Unrolled Computation Graphs with Persistent Evolution Strategies](https://mlsanity.com/paper/2112.13835/) (2021)
- [Learning the Effect of Registration Hyperparameters with HyperMorph](https://mlsanity.com/paper/2203.16680/) (2022)
- [PriorBand: Practical Hyperparameter Optimization in the Age of Deep Learning](https://mlsanity.com/paper/2306.12370/) (2023)
- [Learning Curves for Decision Making in Supervised Machine Learning: A Survey](https://mlsanity.com/paper/2201.12150/) (2022)
- [AutoPDL: Automatic Prompt Optimization for LLM Agents](https://mlsanity.com/paper/2504.04365/) (2025)
- [VolcanoML: Speeding up End-to-End AutoML via Scalable Search Space Decomposition](https://mlsanity.com/paper/2107.08861/) (2021)
- [Towards Green Automated Machine Learning: Status Quo and Future Directions](https://mlsanity.com/paper/2111.05850/) (2021)
- [Generalizing Few-Shot NAS with Gradient Matching](https://mlsanity.com/paper/2203.15207/) (2022)
- [Multi-objective Asynchronous Successive Halving](https://mlsanity.com/paper/2106.12639/) (2021)
- [FairTune: Optimizing Parameter Efficient Fine Tuning for Fairness in Medical Image Analysis](https://mlsanity.com/paper/2310.05055/) (2023)
- [Super Consistency of Neural Network Landscapes and Learning Rate Transfer](https://mlsanity.com/paper/2402.17457/) (2024)
- [Automated Discovery of Adaptive Attacks on Adversarial Defenses](https://mlsanity.com/paper/2102.11860/) (2021)
- [AUTOMATA: Gradient Based Data Subset Selection for Compute-Efficient Hyper-parameter Tuning](https://mlsanity.com/paper/2203.08212/) (2022)
- [Bayesian Generational Population-Based Training](https://mlsanity.com/paper/2207.09405/) (2022)
- [Bag of Baselines for Multi-objective Joint Neural Architecture Search and Hyperparameter Optimization](https://mlsanity.com/paper/2105.01015/) (2021)
- [Promoting Fairness through Hyperparameter Optimization](https://mlsanity.com/paper/2103.12715/) (2021)

## Abstract (arXiv)

Motivated by the task of hyperparameter optimization, we introduce the non-stochastic best-arm identification problem. Within the multi-armed bandit literature, the cumulative regret objective enjoys algorithms and analyses for both the non-stochastic and stochastic settings while to the best of our knowledge, the best-arm identification framework has only been considered in the stochastic setting. We introduce the non-stochastic setting under this framework, identify a known algorithm that is well-suited for this setting, and analyze its behavior. Next, by leveraging the iterative nature of standard machine learning algorithms, we cast hyperparameter optimization as an instance of non-stochastic best-arm identification, and empirically evaluate our proposed algorithm on this task. Our empirical results show that, by allocating more resources to promising hyperparameter settings, we typically achieve comparable test accuracies an order of magnitude faster than baseline methods.