How the Duration of the Learning Period Affects the Performance of Random Gradient Selection Hyper-Heuristics
Abstract
Recent analyses have shown that a random gradient hyper-heuristic (HH) using randomised local search (RLSk) low-level heuristics with different neighbourhood sizes k can optimise the unimodal benchmark function LeadingOnes in the best expected time achievable with the available heuristics, if sufficiently long learning periods τ are employed. In this paper, we examine the impact of the learning period on the performance of the hyper-heuristic for standard unimodal benchmark functions with different characteristics: Ridge, where the HH has to learn that RLS1 is always the best low-level heuristic, and OneMax, where different low-level heuristics are preferable in different areas of the search space. We rigorously prove that super-linear learning periods τ are required for the HH to achieve optimal expected runtime for Ridge. Conversely, a sub-logarithmic learning period is the best static choice for OneMax, while using super-linear values for τ increases the expected runtime above the asymptotic unary unbiased black box complexity of the problem. We prove that a random gradient HH which automatically adapts the learning period throughout the run has optimal asymptotic expected runtime for both OneMax and Ridge. Additionally, we show experimentally that it outperforms any static learning period for realistic problem sizes.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Bayes beats Cross Validation: Efficient and Accurate Ridge Regression via Expectation MaximizationShu Yu Tew, Mario Boley, Daniel F. SchmidtNeurIPS 2023 · 6 citations
- Breadth-First Search vs. Restarting Random Walks for Escaping Uninformed Heuristic RegionsDaniel Platnick, Dawson Tomasz, Eamon Earl, Sourena Khanzadeh et al.AAAI 2026
- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-SearchZiyad Benomar, Lorenzo Croissant, Vianney Perchet, Spyros AngelopoulosICML 2025
- A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level SingletonRisheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng et al.ICML 2020 · 153 citations
- On the Optimality of Misspecified Kernel Ridge RegressionHaobo Zhang, Yicheng Li, Weihao Lu, Qian LinICML 2023 · 19 citations
