Successive Halving with Learning Curve Prediction via Latent Kronecker Gaussian Processes

Jihao Andreas Lin, Nicolas Mayoraz, Steffen Rendle, Dima Kuzmin, Emil Praun, Berivan Isik · 2025

Read Successive Halving with Learning Curve Prediction via Latent Kronecker Gaussian Processes by Jihao Andreas Lin, Nicolas Mayoraz, Steffen Rendle, Dima Kuzmin, Emil Praun, Berivan Isik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-14818.txt.

Introduction

Jihao Andreas Lin and five co-authors present a study from twenty twenty-five on faster tuning of neural networks. A known method, successive halving, gives more compute to the best early runners and cuts the rest. Its flaw is that slow starters may be cut too soon, though they could win in the end. The team tests if forecasts of full learning curves can fix that flaw.

Their curves come from a latent Gaussian process with a Kronecker form. In a large test on many network types and a click data set, the forecast route did about as well as the plain route. It did not beat just spending more on the plain route, since it needs full curves to train on. Old curve data could ease that cost.

Catalog record

CREATORJihao Andreas Lin, Nicolas Mayoraz, Steffen Rendle, Dima Kuzmin, Emil Praun, Berivan Isik
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-14818

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Successive Halving with Learning Curve Prediction via Latent Kronecker Gaussian Processes Jihao Andreas Lin, Nicolas Mayoraz, Steffen Rendle, Dima Kuzmin, Emil Praun, Berivan Isik Abstract Successive Halving is a popular algorithm for hyperparameter optimization which allocates exponentially more resources to promising candidates. However, the algorithm typically relies on intermediate performance values to make resource allocation decisions, which can cause it to prematurely prune slow starters that would eventually become the best candidate. We investigate whether guiding Successive Halving with learning curve predictions based on Latent Kronecker Gaussian Processes can overcome this limitation. In a large-scale empirical study involving different neural network architectures and a click prediction dataset, we compare this predictive approach to the standard approach based on current performance values. Our experiments show that, although the predictive approach achieves competitive performance, it is not Pareto optimal compared to investing more resources into the standard approach, because it requires fully observed learning curves as training data. However, this downside could be mitigated by leveraging existing learning curve data. 1 Introduction Hyperparameter optimization (HPO) is a critical but computationally expensive part of the machine learning workflow. To address this problem, Successive Halving (SH) ( Karnin et al. 2013 ; Jamieson & Talwalkar 2016 ) allocates computational resources efficiently across many hyperparameter candidates by operating in a series of rungs . In each rung, a fraction of the candidates are discarded, typically based on their current intermediate performances. The surviving candidates are promoted to the next rung and provided with an exponentially larger resource budget. However, SH typically assumes that intermediate performance values are indicate of future performance values, which is a notable weakness. The heuristic fails for slow starters with seemingly unpromising intermediate performance, because SH would incorrectly discard them (see Figure 1 , middle). This raises the question of whether we can improve SH by making more informed pruning decisions based on predicted performance values, instead of relying on current performance values. In this work, we investigate SH using learning curve predictions based on Latent Kronecker Gaussian Processes (LKGPs) ( Lin et al. 2024 ; Lin et al. 2025 ) , a scalable probabilistic method, to predict future performance values given a set of fully and partially observed learning curves as training data. Our hypothesis is that using these predictions to guide SH could lead to more robust and reliable identification of the best hyperparameter configurations (see Figure 1 ). We test our hypothesis via a large-scale empirical study using the 1TB Criteo click prediction dataset ( Criteo 2023 ) . By simulating thousands of SH runs, we compare the standard approach based on current performance values to predictions based on LKGPs. Our experiments show that, although SH with predictions based on LKGPs achieves competitive performance, the approach is not Pareto optimal compared to investing more resources into the standard SH algorithm, because it relies on additional fully observed learning curves which are used as training data. Nonetheless, we believe that this drawback can be overcome by leveraging existing learning curve data, which opens avenues for future research. 2 Background Figure 1: Visualization of Successive Halving with predictions based on current performance values (left, middle) and LKGPs ( Lin et al. 2024 ; Lin et al. 2025 ) (right). If intermediate performance values are indicative of future performance values, Successive Halving based on current performance values will identify the best possible run (left). However, sometimes the best possible run is discarded because its intermediate performance seems unpromising compared to other candidates at the same stage (middle). Using LKGPs to predict future performance values can identify the best possible run, despite unpromising intermediate performance values (right). Let there be N candidates, identified by their index i=1,...,N and corresponding hyperparameters x_{i}\in\mathcal{X} . Each candidate is a machine learning model which is trained using iterative optimization on a fixed sequence of data that is shared across all candidates. In particular, the iterative training procedure generates performance metrics y_{i,t} for each candidate i and time steps t=1,...,T . We define the best candidate and its performance as i_{*}=\arg\min_{i}\,\mathrm{perf}(i) and y_{*}=\min_{i}\,\mathrm{perf}(i) where \mathrm{perf}(i)=\frac{1}{\Delta}\sum_{t=T-\Delta}^{T}y_{i,t} . In other words, the best candidate minimizes the performance metric averaged over a final window of size \Delta . Our goal is to identify the best candidate i_{*} while minimizing the number of observed performance metrics, because the latter corresponds to consumed resources. For simplicity, we assume that all time steps are shared across all candidates and spaced uniformly, and that it takes the same amount of resources to produce any performance metric y_{i,t} . Successive Halving Successive Halving (SH) was originally proposed to identify the best arm in a stochastic multi-armed bandit setting ( Karnin et al. 2013 ) . The algorithm was later applied to perform hyperparameter optimization in a non-stochastic setting ( Jamieson & Talwalkar 2016 ) . The core principle of SH is to allocate fewer resources to unpromising candidates and exponentially more resources to promising ones. In particular, the allocation schedule operates in discrete rungs . At each rung, 1/\eta of the remaining candidates are promoted to the next rung and provided with more resources (see Algorithm 1 ). Typically, decisions about candidate promotions are made based on current performance values. However, current performance values are not always indicative of future performance values given more resources. For example, a slow starter which improves steadily may eventually overtake other candidates which converge quickly. Therefore, the ability to accurately predict future performances could potentially improve the performance of SH. Latent Kronecker Gaussian Processes Recently, Lin et al. 2024 ; Lin et al. 2025 proposed Latent Kronecker Gaussian Processes (LKGPs), a scalable probabilistic regression method which can be used to predict learning curves by considering the function f:\mathcal{X}\times\mathcal{T}\to\mathcal{Y} , mapping the Cartesian product space of hyperparameters \mathcal{X} and time steps \mathcal{T} to performance metrics. In particular, LKGPs model f using a product kernel k((x,t),(x^{\prime},t^{\prime}))=k_{X}(x,x^{\prime})k_{T}(t,t^{\prime}) and make nonparametric predictions based on correlations with observed training data instead of relying on specific parametric functions ( Domhan et al. 2015 ) or suitable synthetic data ( Adriaensen et al. 2023 ) . Algorithm 1 Successive Halving Initial number of candidates N , final number of candidates F , reduction rate \eta S\leftarrow\lceil\log_{\eta}(N/F)\rceil \triangleright Calculate total number of rungs for s=1,\dots,S do R\leftarrow(\eta^{s}-1)/(\eta^{S}-1)\times 100\% \triangleright Calculate relative resource budget for the current rung Train remaining candidates until R\% of the maximum resource budget per candidate Rank remaining candidates based on their current or predicted performance values Promote top N/(\eta^{s-1}) candidates to the next rung end for return Top F candidates 3 Contributions In this paper, we compare the downstream performance of SH with promotion decisions based on current performance values to learning curve prediction via LKGPs. To this end, we first create learning curve data by training neural networks, and then use the resulting data to simulate SH. Creating Learning Curve Data We train neural networks on a fixed sequence of data, which consists of chronological click feedback data from online advertisements. In particular, we use the Criteo 1TB dataset ( Criteo 2023 ) which contains a subset of Criteo’s traffic over 24 days. Each data point indicates whether or not a certain display advertisement has been clicked. We consider Factorization Machines (FMs)

Read the complete text