# Provably Reduced Sample Cost in Prior-Guided Hyperparameter Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 3 Jun 2026.

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [AutoGluon-Tabular: Robust and Accurate AutoML for Structured Data](https://mlsanity.com/paper/2003.06505/) (2020)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [Auto-Sklearn 2.0: Hands-free AutoML via Meta-Learning](https://mlsanity.com/paper/2007.04074/) (2020)
- [Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges](https://mlsanity.com/paper/2107.05847/) (2021)
- [HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO](https://mlsanity.com/paper/2109.06716/) (2021)
- [PACOH: Bayes-Optimal Meta-Learning with PAC-Guarantees](https://mlsanity.com/paper/2002.05551/) (2020)
- [PFNs4BO: In-Context Learning for Bayesian Optimization](https://mlsanity.com/paper/2305.17535/) (2023)
- [πBO: Augmenting Acquisition Functions with User Beliefs for Bayesian Optimization](https://mlsanity.com/paper/2204.11051/) (2022)
- [Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control](https://mlsanity.com/paper/1906.01376/) (2019)
- [Hyperparameter Importance Across Datasets](https://mlsanity.com/paper/1710.04725/) (2017)
- [YAHPO Gym -- An Efficient Multi-Objective Multi-Fidelity Benchmark for Hyperparameter Optimization](https://mlsanity.com/paper/2109.03670/) (2021)
- [Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning](https://mlsanity.com/paper/1909.12552/) (2019)
- [PriorBand: Practical Hyperparameter Optimization in the Age of Deep Learning](https://mlsanity.com/paper/2306.12370/) (2023)
- [A Survey of Methods for Automated Algorithm Configuration](https://mlsanity.com/paper/2202.01651/) (2022)
- [In-Context Freeze-Thaw Bayesian Optimization for Hyperparameter Optimization](https://mlsanity.com/paper/2404.16795/) (2024)
- [Towards Green Automated Machine Learning: Status Quo and Future Directions](https://mlsanity.com/paper/2111.05850/) (2021)
- [PASHA: Efficient HPO and NAS with Progressive Resource Allocation](https://mlsanity.com/paper/2207.06940/) (2022)
- [Bayesian Fixed-Budget Best-Arm Identification](https://mlsanity.com/paper/2211.08572/) (2022)
- [Naive Automated Machine Learning](https://mlsanity.com/paper/2111.14514/) (2021)
- [Interactive Hyperparameter Optimization in Multi-Objective Problems via Preference Learning](https://mlsanity.com/paper/2309.03581/) (2023)
- [AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration](https://mlsanity.com/paper/2212.00333/) (2022)
- [Hyperparameter Optimization via Interacting with Probabilistic Circuits](https://mlsanity.com/paper/2505.17804/) (2025)

## Abstract (arXiv)

Large-scale hyperparameter optimization (HPO) in automated machine learning (AutoML) consumes substantial computational resources, raising growing concerns about scalability and energy efficiency. Existing methods use prior information heuristically to accelerate both black-box and multi-fidelity settings, but they lack a characterization of how prior informativeness quantitatively reduces sample complexity. In this work, we provide the first distribution-dependent sample complexity bounds for multi-fidelity HPO with priors through the formal lens of fixed-budget best-arm identification. By modeling priors directly over arm means as configuration performance, we derive explicit, distribution-dependent error bounds that quantify the relationship between priors and evaluation budget. Our analysis shows that informative priors, which concentrate probability mass on near-optimal arms, yield reductions in the number of required evaluations, whereas baseline performance is recovered with uninformative or misleading priors. We conduct proof-of-concept experiments on a synthetic benchmark and on LCBench, a common multi-fidelity HPO benchmark for deep learning, to confirm our theoretical results, achieving up to 90% budget reduction while retaining solution quality. Together, our results provide a principled foundation for prior-guided and compute-efficient green AutoML.