# Random Search Hyper-Parameter Tuning: Expected Improvement Estimation and the Corresponding Lower Bound

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 17 Aug 2022.

## Builds on (most cited first, 8 of 8)

- [On Hyperparameter Optimization of Machine Learning Algorithms: Theory and Practice](https://mlsanity.com/paper/2007.15745/) (2020)
- [Show Your Work: Improved Reporting of Experimental Results](https://mlsanity.com/paper/1909.03004/) (2019)
- [Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges](https://mlsanity.com/paper/2107.05847/) (2021)
- [Hyper-Parameter Optimization: A Review of Algorithms and Applications](https://mlsanity.com/paper/2003.05689/) (2020)
- [Machine learning pipeline for battery state of health estimation](https://mlsanity.com/paper/2102.00837/) (2021)
- [Easy Hyperparameter Search Using Optunity](https://mlsanity.com/paper/1412.1114/) (2014)
- [Expected Validation Performance and Estimation of a Random Variable's Maximum](https://mlsanity.com/paper/2110.00613/) (2021)
- [Showing Your Work Doesn't Always Work](https://mlsanity.com/paper/2004.13705/) (2020)

## Abstract (arXiv)

Hyperparameter tuning is a common technique for improving the performance of neural networks. Most techniques for hyperparameter search involve an iterated process where the model is retrained at every iteration. However, the expected accuracy improvement from every additional search iteration, is still unknown. Calculating the expected improvement can help create stopping rules for hyperparameter tuning and allow for a wiser allocation of a project's computational budget. In this paper, we establish an empirical estimate for the expected accuracy improvement from an additional iteration of hyperparameter search. Our results hold for any hyperparameter tuning method which is based on random search citebergstra2012random and samples hyperparameters from a fixed distribution. We bound our estimate with an error of Oleft(√fraclog kkright) w.h.p. where k is the current number of iterations. To the best of our knowledge this is the first bound on the expected gain from an additional iteration of hyperparameter search. Finally, we demonstrate that the optimal estimate for the expected accuracy will still have an error of frac1k.