# Fast and Informative Model Selection using Learning Curve Cross-Validation

Felix Mohr, Jan N. van Rijn

###### Abstract

Common cross-validation (CV) methods like k-fold cross-validation or Monte-
Carlo cross-validation estimate the predictive performance of a learner by
repeatedly training it on a large portion of the given data and testing on the
remaining data. These techniques have two major drawbacks. First, they can be
unnecessarily slow on large datasets. Second, beyond an estimation of the
final performance, they give almost no insights into the learning process of
the validated algorithm. In this paper, we present a new approach for
validation based on learning curves (LCCV). Instead of creating train-test
splits with a large portion of training data, LCCV iteratively increases the
number of instances used for training. In the context of model selection, it
discards models that are very unlikely to become competitive. We run a large
scale experiment on the 67 datasets from the AutoML benchmark and empirically
show that in over 90% of the cases using LCCV leads to similar performance (at
most 1.5% difference) as using 5/10-fold CV. However, it yields substantial
runtime reductions of over 20% on average. Additionally, it provides important
insights, which for example allow assessing the benefits of acquiring more
data. These results are orthogonal to other advances in the field of AutoML.

##  1 Introduction

Model selection is the process of picking from a given set of machine learning
models the one that is believed to exhibit the best predictive performance. An
important sub-task of model selection is to estimate the performance of each
candidate model, which is done by so-called _validation methods_. For example,
tools for automated machine learning (AutoML) make excessive use of validation
techniques to assess the performance of machine learning pipelines [33, 8, 26,
24]. The validation procedure can often be considered just an interchangeable
function that provides some estimate for the quality of a model. Typical
choices to implement such a validation function are k-fold cross-validation
(kCV), and Monte-Carlo Cross-Validation (MCCV).

Those validation methods are often unnecessarily slow on large datasets. They
use a large portion of the data for learning a model, and the size of this
portion is a constant that is independent of the data over which is evaluated.
For example, kCV and MCCV typically use between 70% and 90% of the data for
training. While large training portions are _sometimes_ necessary to estimate
the generalization performance of a learner, in many cases the number of data
points required to build the best possible model of a class is much lower.
Then, large train folds unnecessarily slow down the validation process,
sometimes substantially. For example, the error rate of a linear SVM on the
numerai28.6 dataset is 48% when training with $4\,000$ instances but also when
training with $90\,000$ instances. However, in the latter case, the evaluation
is almost 50 times slower.

Additionally, vanilla validation procedures provide little additional
information to the data owner. Data owners usually need to ask themselves the
question which of the conventional options would improve the quality of their
current model: (i) gather more data points, (ii) gather more attributes, or
(iii) apply a wider range of models. Common validation techniques only provide
information for (iii).

In this paper, we propose a cross-validation approach based on the notion of
learning curves. Learning curves express the predictive performance of the
models produced by a learner for different numbers of instances available for
learning. The validation of a learner is now done as follows. Instead of
evaluating it just for one number of training instances (say 80% of the
original dataset size), it is evaluated, in increasing order, at different so-
called _anchor points_ of training fold sizes, e.g. for 64, 128, 256, 512, …
instances. At each anchor point, several evaluations are conducted until a
stability criterion is met. We dub this approach learning-curve-based cross-
validation (LCCV). Other authors also utilized learning curves [1, 6, 17, 19,
34] or sub-sampling [15, 20, 28, 30, 31] to speed-up model selection by
discarding unpromising candidates early. The main contribution of LCCV is that
it _combines_ empirical learning curves with an _convexity assumption_ on
learning curves to early prune candidates only if they are unlikely to be an
optimal solution. LCCV does not rely on a learning curve model like an inverse
power law (IPL) for this, even though such a model is used for other decisions
in the evaluation process.

Our work focuses on the scenario in which learners are trained in a non-
incremental way. At first sight, LCCV may seem a natural fit when the
portfolio from which a model is to be selected contains incremental learners.
Learning curves essentially come for free for such learners since we can build
them during the training process over the different iterations. This seems
like an advantage over observation-based learning curves, which may require
training from scratch at each anchor and hence more time to be computed.
However, there are some issues with incremental learning curves on both the
practical and theoretical side. First, even though incremental versions have
been proposed for many learners, these are often not realized in widely used
implementations like WEKA [13] or scikit-learn [27] and hence not available
for data scientists using those libraries. Second, incremental learning curves
are of a different _type_ than the observation-based learning curves [6].
There is empirical evidence that suggests that observation-based learning
curves are convex (see Appendix E in the supplement), whereas this is less
clear for the iteration-based learning curves [36]. Since our work relies on
the convexity assumption, we focus on non-incremental training.

In such scenarios, LCCV is an interesting alternative to classical validation
techniques. At first sight, it seems to suffer from the drawback that it
builds models at different anchors from scratch and hence to be even _slower_
than classical validation techniques. However, we show in Sec. 5.1 that this
is rarely the case. In fact, we consider that LCCV has three advantages over
those techniques specifically in the context of AutoML [8, 26, 23]:

  1. 1.

When used for model selection without or with moderate timeouts, LCCV exploits
a convexity assumption to early discard candidates that are unlikely to become
competitive. Thereby, it chooses in almost all cases a model that is equally
good as the one chosen by common cross-validation but usually in substantially
less time.

  2. 2.

When used for model selection with tight timeouts, LCCV is more reliable in
its ability to produce _any_ result for a candidate. Even with a very limited
time budget, LCCV yields at least an _estimate_ of the reference model
performance even if not with the same confidence as if no timeout is applied.
In particular, LCCV can return estimates in situations where there is _no_
score obtained using common cross-validation techniques.

  3. 3.

Instead of a single-point observation, LCCV gives insights about the learning
_behaviour_ of a candidate. This is very useful to answer the question of
whether more data would help to obtain better results; information that cannot
at all be provided by any of the above validation techniques. Note that this
information cannot generally be obtained via standard cross-validation, e.g.,
by afterwards computing the learning curve of the learner that was best in
cross-validation on, say, 80% of the training data. This is because there is
no guarantee that this learner (or even only any of the $k$ best learners)
would also be the best if more data were available; this is precisely
something that can be revealed with LCCV since it computes the learning curves
of _all_ learners.

We sustain these claims empirically by comparing LCCV against kCV, the
arguably most popular validation technique. First, we show that LCCV is
superior to both 5CV and 10CV in terms of runtime in most situations. Our
experiments compare the runtimes of a random search using LCCV or kCV for
validation and confirm that LCCV most often yields similar results as 5CV and
10CV while reducing runtime on average by 20%, in an experiment where the task
is to select a learner from a portfolio of 200 machine learning pipelines. In
absolute numbers, in this experiment the runtime of a single model selection
process is be reduced, on average, by 1.5h compared to 5CV and even 2.75h
compared to 10CV. In addition, the experiments show that the learning curves
obtained using LCCV can be directly used to assert whether or not more data
could improve the overall result of the model selection process.

##  2 Problem Statement

Our focus is on supervised machine learning. For an _instance space_
$\mathit{\mathcal{X}}$ and a _label space_ $\mathit{\mathcal{Y}}$, a _dataset_
$\mathit{d}\subset\\{(x,y)~{}|~{}x\in\mathit{\mathcal{X}},y\in\mathit{\mathcal{Y}}\\}$
is a _finite_ relation between the two spaces. We denote as $\mathit{D}$ the
set of all possible datasets. A _learning algorithm_ is a function
$\mathit{a}:\mathit{D}\rightarrow\mathit{H}$, where
$\mathit{H}=\\{h~{}|~{}h:\mathit{\mathcal{X}}\rightarrow\mathit{\mathcal{Y}}\\}$
is the space of hypotheses. The performance of a hypothesis is its _out-of-
sample error_

$\mathit{\mathcal{R}}(h)=\int\limits_{\mathit{\mathcal{X}},\mathit{\mathcal{Y}}}{loss(y,h(x))}\,d\mathbb{P}(x,y),$
(1)

and the performance of a learner $\mathit{a}$ when trained with some data
$\mathit{d}$ is $\mathit{\mathcal{R}}(\mathit{a}(\mathit{d}))$. Here,
$loss(y,h(x))\in\mathbb{R}$ is the penalty for predicting $h(x)$ for instance
$x\in\mathit{\mathcal{X}}$ when the true label is $y\in\mathit{\mathcal{Y}}$,
and $\mathbb{P}$ is a joint probability measure on
$\mathit{\mathcal{X}}\times\mathit{\mathcal{Y}}$ from which the available
dataset $\mathit{d}$ has been generated.

Since the performance in Eq. (1) cannot be evaluated, an estimate is needed.
The only known feasible way to do this is by validation, i.e. by splitting the
data $\mathit{d}$ into $\mathit{d}_{train}$ and $\mathit{d}_{validate}$, to
run the learning algorithm (learner) only with $\mathit{d}_{train}$, and to
use $\mathit{d}_{validate}$ to _estimate_ the risk. Formally, we then have a
_validation_ function

$\mathit{\nu}:\mathit{D}\times\mathit{A}\rightarrow\mathbb{R},$ (2)

such that $\mathit{\nu}(\mathit{d},\mathit{a})$ is an estimate of the out-of-
sample error of the hypothesis produced by the learner $\mathit{a}$ based on
the available data $\mathit{d}$. Typically, $\mathit{\nu}$ will not only
create one but several splits, train the learner several times and aggregate
the prediction results into an overall estimate.

Several learning algorithms use such a validation function as a _sub-routine_
to select a model among a set of candidates it has produced. For example,
AutoML tools generate and evaluate sequences of models. Formally, such
learners produce a sequence $\mathit{A}=(\mathit{a}_{1},\mathit{a}_{2},...)$
of learners, each of which is validated with $\mathit{\nu}$, and eventually
the (hypothesis produced by the) learner with the lowest empirical risk is
returned in the hope that this also minimizes the out-of-sample error in Eq.
(1).

We follow the idea that the score of a non-competitive candidate does not even
need to be computed exactly [6]. In other words, we do not even need to know
the concrete score $\mathit{\nu}(\mathit{d},\mathit{a})$ if
$\mathbb{E}[\mathit{\mathcal{R}}(\mathit{a}(\mathit{d}_{train}))]>\mathit{r}$,
where the expectation is taken with respect to the train data sets
$\mathit{d}_{train}$ with the same size as being used by $\mathit{\nu}$ and
where $\mathit{r}$ is the currently best observed performance. This scenario
motivates an _informed_ validation function

$\mathit{\tilde{\nu}}:\mathit{D}\times\mathit{A}\times\mathbb{R}\rightarrow\mathbb{R}\cup\\{\mathit{\bot}\\},$
(3)

which takes as an additional argument the reference score and is allowed to
return a result $\mathit{\bot}$ to indicate that the candidate can be
discarded. Even if there is some tentative performance estimate of the
candidate, $\mathit{\tilde{\nu}}$ should not return that estimate as it is not
necessarily comparable to previous results and could be potentially misleading
the search.

While the exact validation result of non-competitive candidates can be
important for some search algorithms, there are many situations where this is
not the case. Indeed, several search strategies _steer_ the search process
based on the outcome of earlier validations (e.g., Bayesian optimization,
evolutionary algorithms, or tree search). So returning an uninformative value
$\mathit{\bot}$ that leads to discarding of the candidate might have
undesirable side effects. On the other hand, existing state of the art
approaches using Bayesian optimization adopting such a technique have
apparently not been affected by it [6], and other (tree-based) approaches are
even invariant to this issue by concept [24]. As such, we do not focus on
issues possibly caused by returning a void value $\mathit{\bot}$ in this
paper.

The goal is to find an implementation of $\mathit{\tilde{\nu}}$ that
contributes to some external objectives such as runtime minimization or
generating interesting insight while providing a reasonably good estimate of
the out-of-sample error. The quality of $\mathit{\tilde{\nu}}$ with respect to
this constraint is operationalized by a base validation function
$\mathit{\nu}$ considered as ground truth so that

$\mathit{\tilde{\nu}}(\mathit{d},\mathit{a},\mathit{r})=\begin{cases}\bot&\text{only
if }\mathit{\nu}(\mathit{d},\mathit{a})>\mathit{r}\\\ \in
B_{\mathit{q}}(\mathit{\nu}(\mathit{d},\mathit{a}))&\text{else}\end{cases},$
(4)

where $B_{\mathit{q}}$ is some $\mathit{q}$-neighbourhood around the actual
validation score $\mathit{\nu}(\mathit{d},\mathit{a})$. In practice,
$\mathit{\nu}$ can be realized through an MCCV with a high number of repeats.

Note that the proposed $\mathit{\tilde{\nu}}$ is a simplification of a normal
validation method $v$. However, utilizing this simplification, we will show
that we can obtain better runtimes, which is the main contribution of this
work. In Section 4, we will present an algorithm that utilizes learning curves
to achieve this, and as a side product gives additional insights into the
learning procedure.

##  3 Related Work

Model selection is at the heart of many data science approaches. When provided
with a new dataset, a data scientist is confronted with the question of which
model to apply to this. This problem is typically abstracted as the _combined
algorithm selection and hyperparameter optimization problem_ [33]. To properly
deploy model selection methods, there are three important components:

  1. 1.

A _configuration space_ , which specifies the set of algorithms to be
considered and, perhaps, their hyperparameter domains

  2. 2.

A _search procedure_ , which determines the order in which these algorithms
are considered

  3. 3.

An _evaluation mechanism_ , which assesses the quality of a certain algorithm

Most research addresses the question how to efficiently search the
configuration space, leading to a wide range of methods such as random search
[3], Bayesian optimization [4, 14, 32], evolutionary optimization [22], meta-
learning [5, 29] and planning-based methods [24].

Our work aims to make the evaluation mechanism faster, while at the same time
not compromising the performance of the algorithm selection procedure. As
such, it can be applied orthogonal to the many advances made on the components
of the configuration space and the search procedure.

The typical methods used as evaluation mechanisms are using classical methods
such as a holdout set, cross-validation, leave-one-out cross-validation, and
bootstrapping. This can be sped up by applying racing methods, i.e., to stop
evaluation of a given model once a statistical test lets the possibility of
improving over the best seen so far appear unlikely. Some notable methods that
make use of this are ROAR [14] and iRace [21]. The authors of [7] focus on
setting the hyperparameters of AutoML methods, among others selecting the
evaluation mechanism. Additionally, model selection methods are accelerated by
considering only subsets of the data. By sampling various subsets of the
dataset of increasing size, one can construct a learning curve. While these
methods at their core have remained largely unchanged, there are two
directions of research building upon this basis: (i) model-free learning
curves, and (ii) learning curve prediction models.

Model-free learning curves: The simplest thing one could imagine is training
and evaluating a model based upon a small fraction of the data [28]. The
authors of [30] propose progressive sampling methods using batches of
increasing sample sizes (which we also leverage in our work) and propose
mechanisms for detecting whether a given algorithm has already converged.
However, the proposed convergence detection does not take into account
randomness from selecting a given set of sub-samples, making the method fast
but at risk of terminating early.

The authors of [37] introduce FLAML, which uses multiple sample sizes, by
adding a sample size hyperparameter to the configuration space. The reasoning
behind this design choice is to allow low complexity learners to be tested on
small amounts of data, and high complexity learners to be tested on larger
amounts of data. FLAML starts with evaluating configurations on low sample
sizes and gradually extends this to larger sample sizes.

Successive halving addresses the model selection problem as a bandit-based
problem, that can be solved by progressive sampling [15]. All models are
evaluated on a small number of instances, and the best models get a
progressively increasing number of instances. While this method yields good
performance, it does not take into account the development of learning curves,
e.g., some learners might be slow starters, and will only perform well when
supplied with a large number of instances. For example, the extra tree
classifier [10] is the best algorithm on the PhishingWebsites dataset when
training with all ($10\,000$) instances but the _worst_ when using $1\,000$ or
fewer instances; it will be discarded by successive halving (based on all
scikit-learn algorithms with default hyperparameters). Hyperband aims to
address this by building a loop around successive halving, allowing learners
to start at various budgets [20]. While the aforementioned methods all work
well in practice, these are all greedy in the fact that they might disregard a
certain algorithm too fast, leading to fast model selection but sometimes sub-
optimal performances.

Another important aspect is that the knowledge of the whole portfolio plays a
key role in successive halving and Hyperband. Other than our approach, which
is a _validation_ algorithm and does not have knowledge about the portfolio to
be evaluated (and makes no global decisions on budgets), successive halving
assumes that the portfolio is already defined and given, and Hyperband
provides such portfolio definitions. In contrast, our approach will just
receive a sequence of candidates for validation, and this gives more
flexibility to the approaches that want to use it.

The authors of [31] define the cost-sensitive training data allocation
problem, which is related to the problem that we aim to address. They also
introduce an algorithm that solves this problem, i.e., Data Allocation using
Upper Bounds. Given a set of configurations, it first runs all configurations
on two subsamples of the dataset, effectively building the initial segment of
the learning curve. Based on this initial segment per configuration, it
determines for each an optimistic upper bound. After that, it goes into the
following loop: It runs the most promising configuration on a larger sample
size and updates the performance bound. It reevaluates which configuration has
the most potential at that moment, and continues with assigning more budget to
the most promising configuration until one configuration has been run on the
entire dataset. Similar to Hyperband and in contrast to LCCV, it needs to know
the entire portfolio of learners at the start.

Learning curve prediction models:  A model can be trained based on the
learning curve, predicting how it will evolve. The authors of [6] propose a
set of parametric formulas to which can be fitted so that they model the
learning curve of a learner. They employ the method specifically to neural
networks, and the learning curve is constructed based on epochs, rather than
instances. This allows for more information about earlier stages of the
learning curve without the need to invest additional runtime. By selecting the
best fitting parametric model, they can predict the performance of a certain
model for a hypothetical increased number of instances. The authors of [17]
build upon this work by incorporating the concept of Bayesian neural networks.

When having a set of historic learning curves at disposition, one can
efficiently relate a given learning curve to an earlier seen learning curve,
and use that to make predictions about the learning curve at hand. The authors
of [19] employ a k-NN-based model based on learning curves for a certain
dataset to determine which datasets are similar to the dataset at hand. This
approach was later extended by the authors of [34], to also select algorithms
fast.

Similar to our approach, the authors of [1] proposed a model-based version of
Hyperband. They train a model to predict, based on the performance of the last
sample, whether the current model can still improve upon the best-seen model
so far. Like all model-based learning curve methods, this requires vast
amounts of meta-data, to train the meta-model. And like the aforementioned
model-free approaches, these model-based approaches are at risk of terminating
a good algorithm too early. In contrast to these methods, our method is model-
free and always selects the optimal algorithm based on a small set of
reasonable assumptions.

##  4 Learning-Curve-Based Cross-Validation

Learning-curve-based cross-validation (LCCV) estimates the performance of a
learner based on empirical learning curves. LCCV evaluates the learner on
ascendingly ordered so-called _anchor (points)_ $S=(s_{1},..,s_{T})$, which
are training set sizes. Several such evaluations are made on each anchor. The
idea is to early recognize whether or not a candidate can be competitive. Sec.
4.1 explains how we use the convexity of the learning curve to decide on this
question, and Sec. 4.2 details how we make sure that this process only
discards candidates that are sub-optimal with high probability. Sec. 4.3
explains how we use inverse power law (IPL) estimates to skip anchor points
and directly jump to $s_{T}$ for presumably competitive candidates. The
algorithm is formalized in Sec. 4.4. That section also outlines that, even if
the early stopping or skipping mechanisms fail, the runtime of LCCV is in the
worst case twice as high as the one of a kCV.

###  4.1 Aborting a Validation

The idea of LCCV is that we can discard a candidate early with high confidence
if it is unlikely to be competitive. For this, we assume that its learning
curve is _convex_. It is known that not all learning curves are convex, but we
conducted an extensive empirical study (see Appendix E in the supplementary
material) justifying this assumption for the large majority of (the analyzed
but presumably also other) cases. Convexity is important because it implies
that the _slope_ of the learning curve is an _increasing_ function that, for
increasing training data sizes, approximates 0 from below (and sometimes even
exceeds it). Recall that we assume error curves in this paper; for accuracy
curves or F1 curves etc., the curve slopes would be decreasing of course. The
convexity implies that we can take the observations of the last two anchors of
our _empirical_ learning curve, compute the slope, and extrapolate the
learning curve with this slope. From this, we obtain a _bound_ (not an
estimate opposed to [6]) for the performance at the full data size and can
prune if this bound will be worse than threshold value $\mathit{r}$. This is
in line with the work of [31].

More formally, denote the learning curve as a function
$\mathit{p}(\mathit{s})$, where $\mathit{p}$ is the _true average_ performance
of the learner when trained with a train set of size $\mathit{s}$. Convexity
of $\mathit{p}$ implies that
$\mathit{p}^{\prime}(\mathit{s})\leq\mathit{p}^{\prime}(\mathit{s}^{\prime})$
if $\mathit{s}^{\prime}>\mathit{s}$, where $\mathit{p}^{\prime}$ is the
derivative of $\mathit{p}$. Of course, as a learning curve is a sequence, it
is not derivable in the strict sense, so we rather sloppily refer to its slope
$\mathit{p}^{\prime}$ as the slope of the line that connects a point with its
predecessor, i.e.,
$\mathit{p}^{\prime}(\mathit{s}):=\mathit{p}(\mathit{s})-\mathit{p}(\mathit{s}-1)$
for all $\mathit{s}\in\mathbb{N}_{+}$; note that based on the convexity
assumption $\mathit{p}^{\prime}\leq 0$. If we find, for some $\mathit{s}$,
that
$\mathit{p}(\mathit{s})+\mathit{p}^{\prime}(\mathit{s})\cdot(\mathit{s}_{T}-\mathit{s})>\mathit{r}$,
where $\mathit{s}_{T}$ is the maximum size on which we can train, then we have
evidence that the learner is not relevant.

The problem is of course that we can compute neither $\mathit{p}(\mathit{s})$
nor $\mathit{p}^{\prime}(\mathit{s})$, because it refers to the _true_
learning curve. That is, $\mathit{p}$ realizes Eq. (1) for the hypotheses
produced by a learner on different sample sizes. So we can only try to
_estimate_ the values of $\mathit{p}$ and $\mathit{p}^{\prime}$ at selected
anchor points.

Given a sequence of anchor points $\mathit{s}_{1},..,\mathit{s}_{t}$ for which
we already observed performance values of a learner, we need to estimate
$\mathit{p}(\mathit{s}_{t})$ and $\mathit{p}^{\prime}(\mathit{s}_{t})$ in
order to conduct the prune check for the performance at the full dataset size.
A canonical estimate of $\mathit{p}(\mathit{s}_{t})$ is the empirical mean
$\mathit{\hat{\mu}}_{t}$ of the observations at $\mathit{s}_{t}$. For the
slope, we could rely on these estimates and use convexity to bound the slope
with

$\displaystyle\mathit{p}^{\prime}(\mathit{s}_{t})=\mathit{p}(\mathit{s}_{t})-\mathit{p}(\mathit{s}_{t}-1)$
$\displaystyle\overset{conv}{\geq}\frac{\mathit{p}(\mathit{s}_{t})-\mathit{p}(\mathit{s}_{t-1})}{\mathit{s}_{t}-\mathit{s}_{t-1}}$
(5)
$\displaystyle\approx\frac{\mathit{\hat{\mu}}_{t}-\mathit{\hat{\mu}}_{t-1}}{\mathit{s}_{t}-\mathit{s}_{t-1}}$

However, replacing $\mathit{p}^{\prime}$ in the above decision rule by this
bound is admissible _only if_ the estimates $\mathit{\hat{\mu}}_{t}$ and
$\mathit{\hat{\mu}}_{t-1}$ are accurate (enough). This calls for the usage of
_confidence intervals_ to obtain a notion of probabilities (here, from a
frequentist viewpoint, the probability to observe a mean close to the true
one). To compute such confidence bounds, we follow the common assumption that
observations at each anchor follow a normal distribution [6, 17, 16]. Since
the true standard deviation is not available for the estimate, we use the
empirical one.

Collecting enough samples to shrink such confidence intervals to a minimum can
be prohibitive, so we propose an alternative method, which estimates the slope
in Eq. (5) optimistically from the confidence bounds. To this end, we connect
the upper end of the interval at $\mathit{s}_{t-1}$ with the lower end of the
interval of $\mathit{s}_{t}$. This gives us the slope of the most _optimistic_
learning curve compatible with the observed performances up to a reasonable
probability. Formally, let $C_{i}$ be the confidence intervals at anchor
$\mathit{s}_{i}$. Extrapolating from the _last_ anchor $\mathit{s}_{t}$, the
best possible performance of this particular learner at the final anchor
$\mathit{s}_{T}$ is

$\mathit{p}(\mathit{s}_{T})\geq\inf
C_{t}-(\mathit{s}_{T}-\mathit{s}_{t})\left(\frac{\sup C_{t-1}-\inf
C_{t}}{\mathit{s}_{t-1}-\mathit{s}_{t}}\right),$ (6)

which can now be compared against the performance of the best evaluated
learner so far $\mathit{r}$ to decide on pruning.

###  4.2 Calibrating the Width of Confidence Intervals

Given the above approach based on confidence intervals, the next question is
on how many samples these intervals should be based on. Clearly, at least two
observations are needed to obtain a standard deviation and hence to create a
meaningful interval. However, apart from this restriction, the number of
samples per anchor is a factor that is under our control. We should determine
it carefully as a too low number might imply inaccurate or large confidence
intervals while a high number would maybe unnecessarily slow down the
validation process.

The behaviour of LCCV can here be controlled via four parameters. The first
and the second parameters are simply the minimum and the maximum number of
evaluations at each anchor point, respectively. A minimum of other than 2 can
make sense if we either want to allow greediness (1) or to be a bit more
conservative about the reliability of small samples ($>2$). To enable a
dynamic approach between the two extremes, we consider a stability criterion
$\mathit{\varepsilon}$. As soon as the confidence interval width drops under
$\mathit{\varepsilon}$, we consider the observation set to be stable. Since
error rates reside in the unit interval in which we consider results basically
identical if they differ on an order of less than $10^{-4}$, this value could
be a choice for $\mathit{\varepsilon}$. While this is indeed an arguably good
choice at the last anchor, the “inner” anchors do not require such a high
degree of certainty. The goal is not to approximate the learning curve at all
anchor points with high precision but only to get a rough grasp on its shape.
To achieve this objective, a loose confidence interval of size even 0.1 might
be perfectly fine. Otherwise, the validation routine might spend a lot of time
on ultimately not so relevant anchors. Hence, we distinguish between the
standard $\mathit{\varepsilon}$ and a parameter $\mathit{\varepsilon}_{max}$
applied only for the last anchor. Appendix D in the supplementary material
provides a sensitivity analysis over these hyperparameters.

Since the stability criterion $\mathit{\varepsilon}$ could be rather loose, it
makes sense to adopt an additional sanity check that assures that the
observation set is _convexity-compatible_. We call a set of observations
convexity-compatible if there exists a convex function that takes at each
anchor point a value that is in the confidence interval of the respective
anchor. In other words, we do not consider a single empirical learning curve
but _all_ (convex) learning curves that are compatible with the current
confidence bounds at the anchors.

There is an easy-to-check necessary and sufficient condition of the convexity-
compatible property. To this end, one tries to construct a curve backward
starting from the last two intervals and to decrease the slope as little as
possible from each anchor point to the next one. Formally, let
$C_{1},..,C_{t}$ be the confidence intervals at the $t$ ascendingly ordered
anchor points. We set $u_{t}=\sup C_{t}$ as the _worst_ possible learning
curve value at the _last_ anchor point and then consider a minimum possible
negative slope $\sigma_{i}$ at each anchor $i$. Starting with $\sigma_{t}=0$,
we can inductively define

$\displaystyle u_{i-1}$ $\displaystyle=\min\\{x\in C_{i-1}~{}|~{}x\geq
u_{i}-(\mathit{s}_{i}-\mathit{s}_{i-1})\sigma_{i}\\}~{}~{}~{}\text{ and }$ (7)
$\displaystyle\sigma_{i-1}$
$\displaystyle=\frac{u_{i}-u_{i-1}}{\mathit{s}_{i}-\mathit{s}_{i-1}}$

Starting off with the worst value in the last confidence interval is important
to impose the least possible slope in the beginning, since the slope must keep
(negatively) increasing.

If the set from which $u_{i-1}$ is chosen is non-empty for all anchor points,
we have constructed a convex curve inside the confidence bands (necessary
condition), and it is also easy to see that there cannot be a convex curve if
we fail to produce one in this way (sufficient condition). In other words, one
can simply check for convexity compatibility by checking whether the sequence
of slopes of the lines that connect the upper bound of $C_{i}$ with the lower
bound of $C_{i+1}$ is _increasing_.

If an observation set is not convexity compatible, we need to “repair” it in
order to be able to prune in a legitimate way. Our repair technique is to
simply step back one anchor. Stepping back from anchor $s_{t}$ to $s_{t-1}$,
the algorithm will typically only re-sample once at anchor $s_{t-1}$ since the
confidence bound is already small enough. Two cases are possible now. Either
the convexity-compatibility now is already lost at anchor $s_{t-1}$, in which
case the same procedure is applied recursively stepping back to anchor
$s_{t-2}$. Otherwise, it will return to anchor $s_{t}$ and also re-sample a
point at that anchor. In many cases, the convexity compatibility will have
recovered at this time. If not, the procedure is repeated until the problem
has been resolved or the maximum number of evaluations for the anchors has
been reached.

###  4.3 Skipping Intermediate Evaluations

Unless we insist on evaluating at all anchor points for obtaining insight
about the learning process, we should evaluate a learner on the full data once
it becomes evident that it is definitely competitive. This is obviously the
case if we have a _stable_ (small confidence interval) anchor point score that
is at least as good as the best observed performance $\mathit{r}$; in
particular, it is automatically true for the first candidate. Of course, this
only applies to non-incremental learners; for incremental learners, we just
keep training to the end or stop at some point if the condition of Sec. 4.1
applies.

Note that, in contrast to abortion, we cannot lose a relevant candidate by
jumping to the full evaluation. We might waste some computational time, but,
unless a timeout applies, we cannot lose relevant candidates. Hence, we do not
need strict guarantees for this decision.

With this observation in mind, it indeed seems reasonable to _estimate_ the
performance of the learner on the full data and to jump to the full dataset
size if this estimate is at least as good as reference value $\mathit{r}$. A
dozen of function classes have been proposed to model the behaviour of
learning curves (see, e.g., [6]), but one of the most established ones is the
inverse power law (IPL) [2]. The inverse power law allows us to model the
learning curve as a function
$\hat{}\mathit{p}(\mathit{s})=a-b\mathit{s}^{-c}$, where
$a,b,c\in\mathbb{R}_{+}$. Given observations for at least three anchor points,
we can fit a non-linear regression model using, for example, the Levenberg-
Marquardt algorithm [2]. After the sampling at an anchor has finished, we can
fit the parameters of the above model and check whether
$\hat{}\mathit{p}(\mathit{s}_{T})\leq\mathit{r}$. In that case, we can
immediately skip to the final anchor.

###  4.4 The LCCV Algorithm

The LCCV algorithm is sketched in Alg. 1 and puts all of the above steps
together. The algorithm iterates over anchors in a fixed schedule $\mathit{S}$
(in ascending order). At anchor point $\mathit{s}$ (lines 1-1), the learner is
validated by drawing folds of training size $\mathit{s}$, training the learner
on them, and computing its predictive performance on data not in those folds.
These validations are repeated until a stopping criterion is met (cf. Sec.
4.2). Then it is checked whether the observations are currently compatible
with a convex learning curve model. If this is not the case, the algorithm
steps back one anchor and gathers more observations in order to get a better
picture and “repair” the currently non-convex view (l. 1); details are
described in Sec. 4.2. Otherwise, a decision is taken with respect to the
three possible interpretations of the current learning curve. First, if it can
be inferred that the performance at $\mathit{s}_{T}$ will not be competitive
with the best observed performance $\mathit{r}$, LCCV returns $\mathit{\bot}$
(l. 1, cf. Sec. 4.1). Second, if extrapolation of the learning curve gives
rise to the belief that the learner is competitive, then LCCV directly jumps
to validation on the full dataset of the candidate (l. 1, cf. Sec. 4.3). In
any other case, we just keep evaluating at the next anchor (l. 1). In the end,
the estimate for $\mathit{s}_{T}$ is returned together with the confidence
intervals for all anchor points.

1 $(\mathit{s}_{1},..,\mathit{s}_{T})\leftarrow$ initialize anchor points from
min_exp and data size;

2 $(C_{1},..,C_{T})\leftarrow$ initialize confidence intervals as $[0,1]$
each;

3 $t\leftarrow 1$;

4 while  _$t\leq T\land(\sup{C_{T}}-\inf{C_{T}}
>\mathit{\varepsilon})\land|O_{T}|<n$_ do

5 repair_convexity $\leftarrow$ false;

6

/* gather samples at current anchor point $\mathit{s}_{t}$ */

7 while  _$\sup{C_{t}}-\inf{C_{t}}
>\mathit{\varepsilon}\land|O_{t}|<n\land\neg$ repair_convexity_ do

8 add sample for $s_{t}$ training points to $O_{t}$;

9 update confidence interval $C_{t}$;

10 if  _$t >1$_ then
$\sigma_{t-1}=(\sup{C_{t-1}-\inf{C_{t}})/(\mathit{s}_{t-1}-\mathit{s}_{t})}$ ;

11 if  _$t >2\land\sigma_{t-1}<\sigma_{t-2}\land|O_{t-1}|<n$_ then

12 repair_convexity $\leftarrow$ true;

13

14

15

/* Decide how to proceed from this anchor */

16 if  _repair_convexity_ then

17 $t\leftarrow t-1$;

18

19 else if  _projected bound for $\mathit{s}_{T}$ is $>\mathit{r}$_ then

20 return $\mathit{\bot}$

21 else if  _$r=1\lor(t\geq 3~{}\land\text{\sc
ipl\\_estimate}(\mathit{s}_{T})\leq\mathit{r})$_ then

22 $t\leftarrow T$;

23

24 else

25 $t\leftarrow t+1$

26

27return $\mathit{\langle mean(C_{T}),(C_{1},..,C_{T})\rangle}$

Algorithm 1 LCCV: LearningCurveCrossValidation

We observe that the runtime of LCCV is at most twice as much as the one of kCV
in the worst case, if we assume a computational complexity that is at least
linear in the number of data points (proof in Appendix A of the supplement):

###### Theorem 1

Let $\mathit{d}$ be a dataset, $T=\log_{2}|\mathit{d}|$ and
$\rho\in\mathbb{N},\rho\leq T$. For anchor points
$S=(2^{\rho},2^{\rho+1}..,2^{\lfloor T\rfloor},2^{T})$ and with a maximum
number of $k$ samples per anchor point, the runtime of LCCV is at most twice
as high as the one of kCV, where $2^{d}$ is the training size applied by kCV.

A runtime bound of twice the runtime of kCV seems not very exciting. However,
this is a _worst case_ bound, and empirical results will show that most of the
time LCCV is even faster than kCV due to its pruning mechanism. Besides, the
quality of insights obtained from LCCV substantially augment what is learned
from kCV, because it allows us to make recommendations to the user of whether
to acquire more instances or to find better features; we discuss this in more
detail in Sec. 5.2.

##  5 Evaluation

This evaluation addresses two main questions:

  1. 1.

How does the runtime performance of a model selection process employing LCCV
compare to the usage of 5CV and 10CV, and does the usage of LCCV produce
competitive results? These questions are considered in Sec. 5.1.

  2. 2.

Can we use the collected empirical learning curves to make correct
recommendations on the question of whether more data will improve the overall
result? This is subject of Sec. 5.2.

To enable full reproducibility, the implementations of all experiments
conducted here alongside the code to create the result figures and tables,
detailed log files of the experiment runs, and result archives are available
for the public111github.com/fmohr/lccv/tree/master/publications/2022TPAMI.

###  5.1 LCCV for Model Selection

In this evaluation, we compare the effect of using LCCV instead of 5CV or 10CV
as validation method inside a simple AutoML tool based on random search.

####  5.1.1 Benchmark Setup

Our evaluation measures the runtime of a random search AutoML tool that
evaluates $200$ classification pipelines from the scikit-learn library [27]
using different validation techniques to assess candidate performance. The
pipelines consist of a classification algorithm, which may be preceded by up
to two pre-processing algorithms. The behaviour of the random search is
simulated by creating a sequence of $200$ random pipelines (including the
hyperparameter values for the contained algorithms); the considered algorithms
and the exact procedure are explained in Appendix B of the supplement and the
resulting pipelines are published in the resources. The model selection
technique iterates over this sequence, in each iteration it calls the
validation method for the candidate and updates the currently best candidate
based on the result. For LCCV, the currently best observation is passed as
parameter $\mathit{r}$, and a candidate is discarded if $\mathit{\bot}$ is
returned.

We compare 5CV and 10CV with two different configurations of LCCV. When
comparing with 5CV, we suppose that the goal is to find the pipeline with the
best performance estimate when using 80% of the data for training. For LCCV,
we set $s_{T}:=0.8|\mathit{d}|$ for a dataset $\mathit{d}$ and dub this
80LCCV. When comparing with 10CV, we suppose that the goal is to optimize for
training on 90% of the data, set $s_{T}:=0.9|\mathit{d}|$ and dub this 90LCCV.
That is, we conduct two pairwise comparisons, once comparing 5CV against
80LCCV and once 10CV against 90LCCV.

The _runtime_ of a validation method on a given dataset is the average total
runtime of the random search using this validation method. Of course, the
concrete runtime can depend on the concrete set of candidates but also, in the
case of LCCV, their order. Hence, over 10 seeds, we generate different
classifier _portfolios_ to be validated by the techniques, measure their
overall runtime (of course using the same classifier portfolio and identical
order for both techniques), and form the average over them.

The _performance_ of the chosen learner of each run is computed by an
exhaustive MCCV. To this end, we form 100 bi-partitions of split size 90%/10%
and use the 90% for training and 10% for testing in all of the 100 repetitions
(the split is 80%/20% when comparing 5CV against 80LCCV). The average error
rate observed over these 100 partitions is used as the validation score. Note
that we do not need anything like “test” data in this evaluation, because we
are only interested in whether the LCCV can reproduce the same model selection
as kCV. More precisely, we do not try to estimate the true learning curve
value at the target train size but the value one would obtain in expectation
when using only the _available_ data. While this value tends to be an
optimistically biased estimate of the true value, the true value itself is
just not of interest for the validation mechanism. This is a problem that
falls into the responsibility of an anti-over-fitting mechanism, which is not
part of the validation mechanism and hence not part of the experiments.

As common in AutoML, we configured a timeout per validation. In these
experiments, we set the timeout per validation to 5 minutes. This timeout
refers to the _full_ validation of a learner and not, for instance, to the
validation of a single fold. Put differently, 5 minutes after the random
search invoked the validation method, it interrupts validation and receives a
partial result. For the case of kCV this result is the mean performance among
the evaluated folds or nan if not even the first fold could be evaluated. For
LCCV, the partial result is the average results of the biggest evaluated
anchor point if any and nan otherwise.

To obtain insights over different types of datasets, we ran the above
experiments for all of the 67 datasets of the AutoML benchmark suite [11].
These datasets offer a broad spectrum of numbers of instances and attributes.
All the datasets are published on the openml.org platform [9, 35]. As a means
of general pre-processing, missing values are replaced by the median for
numerical and the mode for categorical attributes. After that, all categorical
attributes are binarized.

####  5.1.2 Parametrization of LCCV

LCCV was configured as follows. Following the behaviour of kCV, the upper
sample limit per anchor is 5 for 80LCCV and 10 for 90LCCV. The minimum number
of samples was set to 3. The minimum exponent $\mathit{\rho}$ was set to 6 to
train over at least 64 instances. The maximum width parameter
$\mathit{\varepsilon}$ for the confidence intervals was set according to the
anchor. For the last anchor of the maximum exponent it was configured with
$\mathit{\varepsilon}_{max}=0.001$. For intermediate anchors it was configured
with $\mathit{\varepsilon}=0.1$. We have conducted a sensitivity analysis for
some of the parameters, which can be found in Appendix D of the supplementary
material.

####  5.1.3 Technical Specification

The computations were executed in a compute center with Linux machines, each
of them equipped with 2.6Ghz Intel Xeon E5-2670 processors and 20GB memory. In
spite of the technical possibilities, we did _not_ parallelize evaluations in
the interest of minimizing potential confounding factors. That is, all the
experiments were configured to run with a single CPU core.

####  5.1.4 Results

The results are summarized in Fig. 1. We first consider the top row. The
boxplots capture, in this order, the average runtimes of LCCV and kCV on each
of the 67 datasets (leftmost figure), the absolute and relative _reductions_
of runtimes in minutes when using LCCV compared to kCV (central plots), and
the deviations in the error rate of the eventually chosen model when using
LCCV compared to kCV (rightmost figure). While the absolute reduction (middle
left) is in terms of saved minutes (more is better from the LCCV viewpoint),
the relative runtime reduction refers to the _ratio_ between the runtime of
LCCV and kCV (less is better from the LCCV viewpoint). More detailed insights,
e.g., visualizations per dataset, can be found in Appendix C of the
supplementary material.

Figure 1: Comparison between LCCV and kCV as validators in a random search.
Top panel: results over all the 67 datasets. Bottom panel: results over the 19
datasets with runtimes of at least 6 hours.

The first observation is that LCCV comes with a useful average runtime
reduction over kCV. Looking at the absolute reductions (top panel, left centre
plot), we see that the mean reduction (dashed line) is around 91 minutes over
5CV and 165 minutes over 10CV. More precisely, this is an average absolute
reduction from 5.5h for 5CV to 4h for 80LCCV and from roughly 7h for 10CV to
4.5h for 90LCCV. In relative numbers, the runtime of 80LCCV is only 83% the
runtime of 5CV and the one of 90LCCV is only 65% of the runtime of 10CV on
average. The median reduction ratios are even better than that.

Of course, the time savings are less relevant on small datasets but all the
more impacting on the bigger ones. The bottom panel of Fig. 1 shows the same
results but only for the 19 out of the 67 datasets on which the runtime of
80LCCV is above 6h. If limiting the analysis to those datasets, the absolute
average runtime reduction is from 11h for 5CV (a reduction to 76%) to 8h for
80LCCV and from 12h for 10CV to 8h for 90LCCV (a reduction to 70%).

LCCV does not always improve runtime. There is a handful of cases in the
comparison between 5CV and 80LCCV in which 80LCCV is slightly slower (time
difference of under 10 minutes) but also two cases of runtime differences of
an hour or more. In any case, the runtimes are _far_ away from the worst-case
factor of 2 derived in Sec. 4.4. The increase occurs in fact due to a higher
number of evaluations that, in total, exceeds the time that would have been
required for evaluating using all data right away. In particular, we found
LCCV to be inefficient on datasets with few instances and many attributes like
Amazon. While intuition already suggests that building learning curves for
model selection is not beneficial in those cases, the learning curves are all
the more important here for dataset management and in order to estimate
potential gains with more instances as discussed in Sec. 5.2. This can be
considered the price for the additional insights produced with LCCV as will be
discussed in Sec. 5.2. In the comparison between 10CV and 90LCCV this effect
does almost not occur.

Increased runtime can also have negative effects on the performance. In fact,
the performance of LCCV can even get _worse_ in such cases. For example, in
the latter two cases of substantially increased runtime of 80LCCV, we also
observe substantially worse results compared to 5CV. The reason for this
behaviour is that, in those cases, 80LCCV eventually neither prunes nor skips
and tries to evaluate all anchor points (high runtime) and then often runs
into the timeout and cuts the candidate that would be competitive (bad
performance). This is clearly an undesirable situation that should be avoided.
Specifically in the timeout scenarios, one can hope to resolve the problem
with a different parametrization of LCCV, but it is clearly desirable to
achieve higher robustness that does not depend on parameters in future work.

The final observation is dedicated to the last plot and the performance loss
we need to pay by using LCCV instead of kCV. In 90% of the cases, the
performance of LCCV is in a range of 0.015 of the one of kCV, and in 83% of
the cases, the gap is even under 0.01. These numbers are encouraging and, in
fact, the performance differences are negligible in most of the cases.
Nevertheless, from a strict viewpoint, LCCV falls a bit short with respect to
the constraints defined in Eq. (4) of Sec. 2, because it occasionally
underperforms the kCV. There is no general explanation that covers all cases.
We have above discussed the problem of timeouts on optimal candidates, which
explains some of the cases. Another explanation can be illegal pruning due to
situations in which the convexity assumption is violated.

To summarize, in our interpretation, LCCV is in spite of some exceptions
largely superior to kCV with respect to runtimes. LCCV is particularly strong
on the “hard” datasets with high training runtimes. While LCCV is also
competitive in terms of performance most of the time, it occasionally
underperforms kCV, which gives rise to improvements of the LCCV technique in
future work.

###  5.2 LCCV for Data Acquisition Recommendations

We analyze whether the promise of LCCV to give more insights than kCV is
justified. We use the produced empirical learning curves to derive an IPL
model with which we answer the question of whether more instances will lead to
_sufficiently_ better results or not. Of course, in practice, we will be
interested not in any marginal improvement at any cost but will require a
reasonable ratio between additional instances and improvement.

####  5.2.1 Research Question

We want to assess how suitable the empirical learning curves collected with
LCCV are for predicting whether or not more data would be useful for the user.
While more instances typically imply better results, additional instances also
come at additional costs; this question is hence not trivial. In the most
general case, we can define a _utility_ function over the sample size and try
to find the optimal sample size [38, 18]. Since the return on investment
decreases for increasing sample sizes, the utility assumes its global optimum
at the _economic stopping point_ and strictly decreases thereafter.

Since the concrete utility function depends on application contexts, we adopt
a simplifying approach in this paper to address the above question. Instead of
introducing a concrete utility function, which is everything but trivial [38],
we reduce the problem to a binary decision situation: The user has the option
to double the number of available instances and can choose to do so or not.
Since there are only two possible situations, we only need to express a
condition under which accepting the additional instances is advantageous over
staying with the current set. To this end, a threshold $\mathit{\beta}$
expresses how much the performance (here error rate) must improve in order to
have a utility gain by accepting the additional data. In other words, the
utility function is, ordinally and only for the two possible states,
characterized by $\mathit{\beta}$.

Importantly, the question about improvement does typically not refer to a
specific learner but to the improvement that _any_ learner of a considered
portfolio could achieve over the _currently best_ one if more data was
available. That is, we are not necessarily interested in whether a learner can
improve by at least $\mathit{\beta}$ on its own result but whether the result
of the _best_ learner can be improved by at least $\mathit{\beta}$ by the
_portfolio_. Note that this is not the same question, because it could be that
the currently best learner has a stalling learning curve but that a runner-up
learner has a still dropping learning curve and would take the lead given that
more instances were available.

We answer the following two research questions: Modelling learning curves with
the inverse power law (IPL, cf. Sec. 4.3) fitted from the empirical curves
produced by LCCV,

  1. 1.

how well can we predict the _performance improvement_ (regression problem) of
both each learner and a whole portfolio when the available data is doubled?

  2. 2.

how well can we predict, for different values of $\mathit{\beta}$, the
utility-maximizing decision (binary classification problem)?

####  5.2.2 Realization

To assess the performance of a recommender for these questions on a dataset
$\mathit{d}$, we hold a substantial portion of $\mathit{d}$ apart that will
then serve as “new” data. Of course, new data here does not mean untouched
validation data but additional training instances that are pretended to be not
available before. First, we sample two subsets of the data,
$\mathit{\mathit{d}_{\mathit{full}}}$ and
$\mathit{\mathit{d}_{\mathit{half}}}$, of size
$|\mathit{\mathit{d}_{\mathit{full}}}|=10/9\cdot
2^{\lfloor\log_{2}(0.9|\mathit{d}|)\rfloor}$, and
$|\mathit{\mathit{d}_{\mathit{half}}}|=10/9\cdot
2^{\lfloor\log_{2}(0.9|\mathit{d}|)\rfloor-1}$, respectively, where
$\mathit{\mathit{d}_{\mathit{half}}}$ is sampled as a subset from
$\mathit{\mathit{d}_{\mathit{full}}}$. These perhaps weird-looking sizes are
chosen so that using 90% of the data for training will correspond to a power
of 2; here the highest power(s) possible for the train set of the dataset.
Then, using only the data of $\mathit{\mathit{d}_{\mathit{half}}}$, we
validate all classifiers in the portfolio with LCCV without cancellation and
skipping (cf. Sec. 4.1, 4.3), so that we have full evaluations at all anchor
points; the runtime is still bound by a factor of two (cf. Sec. 4.4).

To make and qualify a prediction of whether doubling the number of instances
will yield an improvement by at least $\mathit{\beta}$, we proceed as follows.
We denote the performance of algorithm $i$ trained on 90% and validated
against 10% of the data in $\mathit{\mathit{d}_{\mathit{half}}}$ and
$\mathit{\mathit{d}_{\mathit{full}}}$ as
$P^{i}_{\mathit{\mathit{d}_{\mathit{half}}}}$ and
$P^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}$, respectively. The performance
of the _best_ performing algorithm is denoted as
$P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}$ for
$\mathit{\mathit{d}_{\mathit{half}}}$ and
$P^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}$ for
$\mathit{\mathit{d}_{\mathit{full}}}$. Pretending that
$\mathit{\mathit{d}_{\mathit{half}}}$ is the actually available data, the
quantities $P^{i}_{\mathit{\mathit{d}_{\mathit{half}}}}$ and hence
$P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}$ are known after having applied
LCCV to the portfolio, but $P^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}$ and
$P^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}$ are _unknown_ and must be
estimated. The correct answer is “yes” if
$P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}-P^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}\geq\mathit{\beta}$
and “no” otherwise. Given the learning curves of a portfolio of classifiers
validated with LCCV, an IPL model (cf. Sec. 4.3) is built for each of them
using non-linear regression; this model is called the _IPL-regressor_. We
denote the _predicted_ performance of this model for algorithm $i$ on
$\mathit{\mathit{d}_{\mathit{full}}}$ as
$\hat{P}^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}$. Then, we compute
$\hat{P}^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}:=\min_{i}\hat{P}^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}$
and return “yes” if this value is at most
$P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}-\mathit{\beta}$ and “no”
otherwise. The implementation of this last decision rule is called the _IPL-
classifier_ for threshold $\mathit{\beta}$.

In this evaluation, we consider a simple portfolio of 17 classifiers. These
are the same classifiers from scikit-learn library [27] as considered for the
pipelines in Sec. 5.1: BernoulliNB, GaussianNB, Decision Tree, Extra Trees
(ensemble), Random Forest, GradientBoosting, kNN, SVC (with four different
kernels), MLP, MultinomialNB, PassiveAggressive, LDA, QDA, SGD. We refer to
Appendix B.1 of the supplement for details.

Figure 2: Correlation between the extrapolated learning curve and the actual
prediction.

####  5.2.3 Results

The results are presented in Fig. 2 and Fig. 3. In both figures, results in
the left column refer to (actual and predicted) improvements for individual
classifiers over themselves, and the results in the right column refer to
improvements over the _best_ classifier in the portfolio. For the left column
plots, we have included only the insights of 5 out of the 17 classifiers for
readability, which are Linear SVC (blue), Gradient Boosting (orange), LDA
(green), QDA (red), Random Forest (purple).

To assess the first research question, we consider Fig. 2. We first focus on
the top row of the figure, which shows the correlation between the predicted
improvement and the actual improvement. Each data point represents the
performance of an algorithm on a dataset; all points of the same colour belong
to the same algorithm. The x-value of a point is the _predicted improvement_
for an algorithm $i$ when increasing the data from
$\mathit{\mathit{d}_{\mathit{half}}}$ to some
$\mathit{\mathit{d}_{\mathit{full}}}$ with twice as much instances, i.e.
$P^{i}_{\mathit{\mathit{d}_{\mathit{half}}}}-\hat{P}^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}$.
The y-axis shows the _actual improvement_ , i.e.
$P^{i}_{\mathit{\mathit{d}_{\mathit{half}}}}-P^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}$.
Hence, points close to the diagonal indicate reliable predictions. In the
right plot, we show how this generalizes towards the portfolio setting. That
is, the x-axis represents the _predicted_ improvement of the _portfolio_ ,
i.e.
$P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}-\hat{P}^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}$,
and the y-axis representing the _true_ improvement of the portfolio, i.e.
$P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}-P^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}$.
Here, the portfolio consists of all 17 classifiers.

The correlation plots show that for most classifiers the predicted improvement
is correlated to the actual improvement. The points of the various classifiers
are evenly spread around the diagonal, indicating that the individual learning
curves of the various algorithms are predictable. This was also mentioned by
various other authors, e.g., [6, 17]. The predictions per portfolio are often
optimistic.

The bottom row of Fig. 2 shows a more aggregated view on the same data. For
different values of the tolerance parameter $\mathit{\gamma}$ (x-axis), it
shows the _portion_ of points whose discrepancy between the predicted and the
true value is at most $\mathit{\gamma}$; one could say that it shows the
“accuracy” of the IPL-_regressor_ with respect to tolerance $\mathit{\gamma}$.
Formally, the y-axis show the percentage of cases where
$|P^{i}_{\mathit{\mathit{d}_{\mathit{half}}}}-\hat{P}^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}|\leq\mathit{\gamma}$
for the left plot and
$|P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}-\hat{P}^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}|\leq\mathit{\gamma}$
for the right plot. Relating this graph to the top row, it shows the relative
frequency of points whose horizontal distance to the dashed line in the upper
plot is at most $\mathit{\gamma}$. Note that these curves are by definition
strictly increasing. The dashed horizontal line is a visual aid to indicate
the 90% threshold.

The interpretation of the here interesting right plot is as follows. If we
accept a mistake of up to 0.025 for the prediction of _how much_ we can
improve over the best learner at $\mathit{\mathit{d}_{\mathit{half}}}$ when
doubling the data, we will get a “correct” answer in roughly 50% of the cases.
If we accept a mistake of 0.07 or more instead, the answer will be correct in
over 90% of the cases.

With respect to the research question under consideration, namely, whether we
can well predict the improvement achieved when doubling the data, the results
are, depending on the expectations, a bit mediocre. On the positive side, the
model is precise up to 0.01 on over 40% of the analyzed cases. On the
downside, being precise up to 0.025 (which may be an acceptable range) in only
50% of the cases might seem an unacceptable gamble. It is worth mentioning
that better results might be achievable under other learning curve models than
the IPL, e.g. using exponential laws [12].

However, for the decision situation at hand, the above precision is
unnecessarily strict. In fact, being able to accurately predict the learning
curve value for data acquisition questions is only important if (i) we can
control the exact number of instances to be gathered and (ii) indeed have a
very detailed concept of utility, which is often not the case in practice. In
our decision situation, we only need to know whether, based on the
recommendation, we take the correct _decision_ in accepting the additional
batch of data or not. In other words, if the true improvement is much more
than $\mathit{\beta}$ and we predict just a value slightly above
$\mathit{\beta}$, then we might make a rather big mistake from the regression
point of view but _no_ mistake from the classification point of view. The same
holds for values below $\mathit{\beta}$. So one might argue that the
prediction error is not so severe as long as we act in the correct way.

Inversely, great regression performance does not even necessarily imply
substantially better decisions. If we make a mistake in the performance
prediction, then the crucial question is whether this mistake will lead to a
decision that is different from the decision one should take if the
performance was _known_. But if the true performance improvement is very close
to $\mathit{\beta}$, then even a very small mistake in the performance
prediction can lead to a wrong decision. This fact also explains the
“oscillation” in Fig. 3, which we discuss below in more depth; a similar
effect was described in [25] when predicting whether the execution of a
learning algorithm will time out. To summarize, both performances
(classification and regression) are of interest and even though great
regression results would be desirable, neither are they necessary nor
sufficient for good classification performance.

Figure 3: Accuracy of the inverse power law model extrapolating the learning
curve.

Motivated by these observations, we can address the second research question
with the plots in Fig. 3. This figure shows the accuracy of the IPL-
_classifier_ (y-axis) when the task is to predict whether the double amount of
data will improve the performance at least by a certain percentage point
$\mathit{\beta}$ (x-axis). On the left, this is the percentage of cases where
$(P^{i}_{\mathit{\mathit{d}_{\mathit{half}}}}-\hat{P}^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}<\mathit{\beta})\equiv(P^{i}_{\mathit{\mathit{d}_{\mathit{half}}}}-P^{i}_{\mathit{\mathit{d}_{\mathit{full}}}}<\mathit{\beta})$
holds. In other words, the fraction of cases where the recommended action is
indeed the one that maximizes the utility. In the right plot, this is done for
the portfolio, i.e., the percentage of cases where
$(P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}-\hat{P}^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}<\mathit{\beta})\equiv(P^{*}_{\mathit{\mathit{d}_{\mathit{half}}}}-P^{*}_{\mathit{\mathit{d}_{\mathit{full}}}}<\mathit{\beta})$
holds. The dashed line is a visual aid for an accuracy score of 95%.

Maybe the first observation here is that, in contrast to the plots in Fig. 2,
the curves in this figure are not monotone. The reason for this is precisely
that the response is likely to be correct if the required improvement
$\mathit{\beta}$ is very low (close to 0) or very high (close to 1). In the
first case, always predicting that the improvement will be achieved will most
of the time be correct while predicting that it will not be achieved for high
values of $\mathit{\beta}$ is likewise a safe prediction. Hence, the difficult
cases are those in which the true improvement is, incidentally, close to the
required threshold $\mathit{\beta}$. In fact, in those cases, even a very
small prediction error can cause a wrong binary prediction. For this reason,
the accuracy drops a bit in the range of $\beta\in[0.05,0.2]$.

However, these performance drops are still at a quite high level and much
better than what the regression task suggested. Looking at the right plot for
the portfolios, we can see that for _any_ value $\mathit{\beta}$ of a required
improvement over the _best_ learner, we predict with over 80% accuracy
correctly whether or not such an improvement will be realized when doubling
the data. For most thresholds, this score is even above 90%. We hence conclude
that the IPL-classifier has a good probability to predict whether or not a
required improvement $\mathit{\beta}$ will be realized _regardless_ the
concrete value of $\mathit{\beta}$ and the true improvement.

To summarize, the empirical learning curves produced as a _side product_ of
LCCV, give great insights into the learning behaviour of the considered
algorithms and can be an important resource for decision making in data
acquisition. Even though the potential improvements of a portfolio cannot
always be predicted with high precision, the predictions are mostly still
sufficiently exact to recommend correctly about whether or not acquiring a
fixed number of additional data points if the required improvement to obtain a
positive net utility is defined. While this type of analysis can at least
partially also be realized by a-posteriori constructing learning curves of the
best candidates in the portfolio according to a kCV, such a technique is not
complete and could miss a learner that will turn the lead on more data while
LCCV takes all the learners in the portfolio into account.

##  6 Conclusion

In this paper, we presented LCCV, a technique to validate learning algorithms
based on learning curves. In contrast to other evaluation methods that
leverage learning curves, LCCV is designed to not prune candidates that can
potentially still outperform the current best candidate. Based on a convexity
assumption, which turns out to hold almost always in practice, candidates are
pruned once they are unlikely to improve upon the current best candidate. This
makes LCCV potentially slower, but more reliable than other learning-curve-
based approaches, whereas it is faster and mostly equally reliable as vanilla
cross-validation methods.

We have empirically shown that LCCV outperforms both 5CV and 10CV in many
cases in terms of the runtime of a random-based model selection algorithm that
employs these methods for validation. Reductions are on the order of up to
between 20% and 50%, which corresponds to 90 minutes reduction on average (160
minutes for 10CV) and up to over 5 hours in some cases. We emphasize that LCCV
is a contribution that is complementary to other efforts in AutoML and can be
used with many of the tools in this field.

Moreover, the learning curves can be used to give additional information to
the data owner. When applying machine learning methods, data owners are often
confronted with the choice of whether they should invest in getting more data,
more attributes, or more model evaluations. LCCV has the ability to support
the decision-maker. We showed that it gives good confidence recommendations
($>80\%$ accuracy) of whether the acquisition of new data will enable a given
desired reduction of the error rate.

Future work should be concerned with several refinements of the technique.
First, it would be highly desirable to detect non-convexities to disable
pruning in those cases. Second, it would be interesting to adopt a more
dynamic and curve-dependent manner of choosing anchor points instead of fixing
these as constants before. Finally, it would be interesting to integrate LCCV
in various AutoML toolboxes, such as ML-Plan [24], Auto-sklearn [8], and Auto-
Weka [33]. Indeed, enabling these toolboxes to speed up the individual
evaluations, has the potential to further push the state-of-the-art of machine
learning research.

## References

  * Baker et al. [2018] B. Baker, O. Gupta, R. Raskar, and N. Naik.  Accelerating neural architecture search using performance prediction.  In _6th International Conference on Learning Representations – Workshop Track Proceedings_ , ICLR’18, 2018.
  * Bard [1974] Y. Bard.  _Nonlinear parameter estimation_.  Academic press, 1974.
  * Bergstra and Bengio [2012] J. Bergstra and Y. Bengio.  Random search for hyper-parameter optimization.  _Journal of Machine Learning Research_ , 13(Feb):281–305, 2012.
  * Bergstra et al. [2011] J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl.  Algorithms for hyperparameter optimization.  In _Advances in Neural Information Processing Systems 24_ , NIPS’11, pages 2546–2554. Curran Associates, Inc., 2011.
  * Brazdil et al. [2008] P. Brazdil, C. Giraud-Carrier, C. Soares, and R. Vilalta.  _Metalearning: Applications to Data Mining_.  Cognitive Technologies. Springer, 1 edition, 2008.
  * Domhan et al. [2015] T. Domhan, J. T. Springenberg, and F. Hutter.  Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves.  In _Proceedings of the 24th International Joint Conference on Artificial Intelligence_ , IJCAI’15, 2015.
  * Feurer and Hutter [2018] M. Feurer and F. Hutter.  Towards further automation in automl.  In _5th ICML Workshop on Automated Machine Learning (AutoML)_ , 2018\.
  * Feurer et al. [2015] M. Feurer, A. Klein, K. Eggensperger, J. Springenberg, M. Blum, and F. Hutter.  Efficient and robust automated machine learning.  In _Advances in Neural Information Processing Systems_ , pages 2962–2970, 2015.
  * Feurer et al. [2021] M. Feurer, J. N. van Rijn, A. Kadra, P. Gijsbers, N. Mallik, S. Ravi, A. Müller, J. Vanschoren, and F. Hutter.  Openml-python: an extensible python api for openml.  _Journal of Machine Learning Research_ , 22(100):1–5, 2021.
  * Geurts et al. [2006] P. Geurts, D. Ernst, and L. Wehenkel.  Extremely randomized trees.  _Machine learning_ , 63(1):3–42, 2006.
  * Gijsbers et al. [2019] P. Gijsbers, E. LeDell, J. Thomas, S. Poirier, B. Bischl, and J. Vanschoren.  An open source automl benchmark.  _arXiv preprint arXiv:1907.00909_ , 2019.
  * Gu et al. [2001] B. Gu, F. Hu, and H. Liu.  Modelling classification performance for large data sets.  In X. S. Wang, G. Yu, and H. Lu, editors, _Advances in Web-Age Information Management, Second International Conference, WAIM 2001, Xi’an, China, July 9-11, 2001, Proceedings_ , volume 2118 of _Lecture Notes in Computer Science_ , pages 317–328. Springer, 2001.
  * Hall et al. [2009] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten.  The weka data mining software: an update.  _ACM SIGKDD Explorations_ , 11, 2009.
  * Hutter et al. [2011] F. Hutter, H. H. Hoos, and K. Leyton-Brown.  Sequential model-based optimization for general algorithm configuration.  In _Proceedings of the conference on Learning and Intelligent Optimization_ , LION 5, pages 507–523, 2011.
  * Jamieson and Talwalkar [2016] K. Jamieson and A. Talwalkar.  Non-stochastic best arm identification and hyperparameter optimization.  In _Artificial Intelligence and Statistics_ , AISTATS’16, pages 240–248, 2016.
  * Klein et al. [2017a] A. Klein, S. Falkner, S. Bartels, P. Hennig, and F. Hutter.  Fast bayesian optimization of machine learning hyperparameters on large datasets.  In A. Singh and X. J. Zhu, editors, _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54 of _PMLR_ , pages 528–536, 2017a.
  * Klein et al. [2017b] A. Klein, S. Falkner, J. T. Springenberg, and F. Hutter.  Learning curve prediction with Bayesian neural networks.  In _International Conference on Learning Representations_ , ICLR’17, 2017b.
  * Last [2009] M. Last.  Improving data mining utility with projective sampling.  In _Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28 - July 1, 2009_ , pages 487–496. ACM, 2009.
  * Leite and Brazdil [2010] R. Leite and P. Brazdil.  Active testing strategy to predict the best classification algorithm via sampling and metalearning.  In _Proceedings of the 19th European Conference on Artificial Intelligence_ , ECAI’10, pages 309–314, 2010.
  * Li et al. [2017] L. Li, K. G. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar.  Hyperband: A novel bandit-based approach to hyperparameter optimization.  _Journal of Machine Learning Research_ , 18:185:1–185:52, 2017.
  * López-Ibáñez et al. [2016] M. López-Ibáñez, J. Dubois-Lacoste, L. P. Cáceres, M. Birattari, and T. Stützle.  The irace package: Iterated racing for automatic algorithm configuration.  _Operations Research Perspectives_ , 3:43–58, 2016.
  * Loshchilov and Hutter [2016] I. Loshchilov and F. Hutter.  CMA-ES for hyperparameter optimization of deep neural networks.  _ArXiv [cs.NE]_ , 1604.07269, 2016.
  * Mohr and van Rijn [2021] F. Mohr and J. N. van Rijn.  Towards model selection using learning curve cross-validation.  In _8th ICML Workshop on Automated Machine Learning (AutoML)_ , 2021\.
  * Mohr et al. [2018] F. Mohr, M. Wever, and E. Hüllermeier.  ML-Plan: Automated machine learning via hierarchical planning.  _Machine Learning_ , 107(8):1495–1515, 2018.
  * Mohr et al. [2021] F. Mohr, M. Wever, A. Tornede, and E. Hüllermeier.  Predicting machine learning pipeline runtimes in the context of automated machine learning.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 43(9):3055–3066, 2021.
  * Olson et al. [2016] R. S. Olson, N. Bartley, R. J. Urbanowicz, and J. H. Moore.  Evaluation of a tree-based pipeline optimization tool for automating data science.  In _Proceedings of the Genetic and Evolutionary Computation Conference 2016_ , GECCO’16, pages 485–492. ACM, 2016.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al.  Scikit-learn: Machine learning in python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Petrak [2000] J. Petrak.  Fast Subsampling Performance Estimates for Classification Algorithm Selection.  In _Proceedings of ECML-00: Workshop on Meta-Learning_ , 2000.
  * Pinto et al. [2016] F. Pinto, C. Soares, and J. Mendes-Moreira.  Towards automatic generation of metafeatures.  In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_ , pages 215–226. Springer, 2016.
  * Provost et al. [1999] F. Provost, D. Jensen, and T. Oates.  Efficient progressive sampling.  In _Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD’99, page 23–32. ACM, 1999.
  * Sabharwal et al. [2016] A. Sabharwal, H. Samulowitz, and G. Tesauro.  Selecting near-optimal learners via incremental data allocation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, 2016.
  * Snoek et al. [2012] J. Snoek, H. Larochelle, and R. P. Adams.  Practical bayesian optimization of machine learning algorithms.  In _Advances in neural information processing systems 25_ , NIPS’12, pages 2951–2959. Curran Associates, Inc., 2012.
  * Thornton et al. [2013] C. Thornton, F. Hutter, H. H. Hoos, and K. Leyton-Brown.  Auto-WEKA: combined selection and hyperparameter optimization of classification algorithms.  In _The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD’13, pages 847–855, 2013.
  * van Rijn et al. [2015] J. N. van Rijn, S. M. Abdulrahman, P. Brazdil, and J. Vanschoren.  Fast algorithm selection using learning curves.  In _International symposium on intelligent data analysis_ , pages 298–309. Springer, 2015.
  * Vanschoren et al. [2013] J. Vanschoren, J. N. van Rijn, B. Bischl, and L. Torgo.  OpenML: Networked science in machine learning.  _SIGKDD Explorations_ , 15(2):49–60, 2013.
  * Viering and Loog [2021] T. J. Viering and M. Loog.  The shape of learning curves: a review.  _CoRR_ , abs/2103.10948, 2021.
  * Wang et al. [2021] D. Wang, J. Andres, J. Weisz, E. Oduor, and C. Dugan.  Autods: Towards human-centered automation of data science.  _arXiv preprint arXiv:2101.05273_ , 2021.
  * Weiss and Tian [2008] G. M. Weiss and Y. Tian.  Maximizing classifier utility when there are data acquisition and modeling costs.  _Data Mining and Knowledge Discovery_ , 17(2):253–282, 2008.

|  Felix Mohr is a professor in the Faculty of Engineering at Universidad de
la Sabana in Colombia. His research focus lies in the areas of Stochastic Tree
Search as well as Automated Software Configuration with a particular
specialization on Automated Machine Learning. He received his PhD in 2016 from
Paderborn University in Germany.
---|---
|  Jan N. van Rijn is assistant professor at Leiden Institute of Advanced
Computer Science (LIACS), Leiden University (the Netherlands). During his PhD,
he (co-)founded and developed OpenML, an open science platform for machine
learning. After obtaining his PhD, he worked as a postdoctoral researcher in
the Machine Learning lab at University of Freiburg (Germany), and Columbia
University in the City of New York (USA). His research interests include
artificial intelligence, AutoML and metalearning.
---|---

Fast and Informative Model Selection using Learning Curve Cross-Validation —
Supplemetary Material

##  Appendix A Proof of Runtime Bound

Here we show that the worst-case runtime of LCCV is at most twice as high as
the one of a standard kCV under the following assumptions. First, we assume
that all considered anchor points are potentials of 2, and (here simplifying)
that the full evaluation is also some such potential $2^{d}$. Second, we
assume that LCCV is configured to draw at most k samples at each anchor point.
Finally, we assume super-linearity of the runtime of the learners in the
number of training instances. Given the observations in [25], this can be
taken for granted for almost all learners, even though for very low runtimes,
the overhead in the evaluation code could break this relationship in some
cases. To summarize, this means that the overall runtime of the validation
function $\mathit{\nu}$ for a learner is $\mathit{\tau_{cv}}=kg(2^{d})$, where
$g:\mathbb{N}\rightarrow\mathbb{R}$ is the runtime function of that learner.

Now let $\mathit{\tau_{lccv}}$ be the time consumed by the LCCV algorithm. For
a number $c$ of considered anchors, a minimum exponent $\mathit{\rho}$ we want
to use to learn, and $a_{i}$ being the _number_ of evaluations made at the
anchor corresponding to exponent $i$, we have that

$\mathit{\tau_{lccv}}=\sum_{i=\mathit{\rho}}^{c}a_{i}g(2^{i})=g(1)\frac{k2^{d}}{k2^{d}}\sum_{i=\mathit{\rho}}^{c}a_{i}2^{i}=kg(2^{d})\sum_{i=\mathit{\rho}}^{c}\frac{a_{i}}{k2^{d-i}}.$
(8)

For example, we could set $\mathit{\rho}=6$ to start with the anchor at 64
training instances. The last term implies that the relationship between the
two runtimes is

$\mathit{\tau_{lccv}}=\mathit{\tau_{cv}}\sum_{i=\mathit{\rho}}^{c}\frac{a_{i}}{k2^{d-i}}\leq\mathit{\tau_{cv}}\sum_{i=0}^{d-\mathit{\rho}}\frac{1}{2^{i}}<2\mathit{\tau_{cv}},$
(9)

where the first inequality is based on the assumptions that

  1. 1.

$k$ is also a natural upper bound on the number of evaluations per anchor
point and we hence have that $a_{i}\leq k$, and

  2. 2.

we run over all possible anchors.

The last inequality simply follows from a comparison to the geometric series.

##  Appendix B Pipelines used in the Evaluation

The pipelines we arm in this paper are from the search space used by the auto-
sklearn tool [8].

Almost every considered algorithm has hyperparameters, which are subject to
optimization in our evaluation. Since we cannot reasonably report the exact
parameter setup even in the appendix, we refer the reader to the repository
coming along with this paper in which all used parameters can be found in the
searchspace.json JSON file.

###  B.1 Considered Algorithms

All applied algorithms are from the scikit-learn library [27].

data-pre-processors: MinMaxScaler, Normalizer, PowerTransformer,
QuantileTransformer, RobustScaler, StandardScaler, VarianceThreshold

feature-pre-processors: FastICA, FeatureAgglomeration,
GenericUnivariateSelect, KernelPCA, Nystroem, PCA, PolynomialFeatures,
RBFSampler, SelectPercentile

classifiers: BernoulliNB, DecisionTreeClassifier, ExtraTreesClassifier,
GaussianNB, GradientBoostingClassifier, KNeighborsClassifier,
LinearDiscriminantAnalysis, MLPClassifier, MultinomialNB,
PassiveAggressiveClassifier, QuadraticDiscriminantAnalysis,
RandomForestClassifier, SGDClassifier, SVC

###  B.2 Pipeline Sampling

From the above pool of algorithms, the pipeline sequence is sampled i.i.d.
where each candidate is sampled using the following routine:

  1. 1.

flip a fair coin to decide whether a data-pre-processor is used or not

  2. 2.

flip a fair coin to decide whether a feature-pre-processor is used or not

  3. 3.

for each slot of the pipeline that is supposed to be filled, sample one of the
available algorithms based on their weight. The weight is computed based on
the size of the hyperparameter-space of a component because we want to give
more weight to algorithms with a big parameter space. The weight of an
algorithm is the product of the weights of its parameters, which are

     * •

the number of possible values for categorical hyperparameters and

     * •

$\min\\{10,s\\}$ for a numeric parameter with $s$ possible values (typically
$s=\infty$ but not for integer parameters with small domain).

We used the same 10 sequences on all datasets, and the sequences can be found
at

https://github.com/fmohr/lccv/tree/master/publications/2022TPAMI/pipeline-
sequences

##  Appendix C Detailed Results of the Random Search

The detailed results of the four validation methods per dataset are shown in
Fig. 1 (5CV vs 80LCCV) and 2 (10CV vs 90LCCV), respectively. The semantics of
the figures is as follows. Each pair of points connected by a dashed line
stand for evaluations of a dataset. In this pair, the blue point shows the
mean runtime of the random search applying LCCV (x-axis) and the eventual mean
error rate (y-axis). The orange point shows the same information when
validating with 10CV. Note that the runtimes are shown on a log-scale. The
dashed lines connecting a pair of points are green if LCCV is faster than CV
and red otherwise. The line is labeled with the dataset id and the absolute
(and relative) difference in runtime. The _vertical_ black dashed lines are
visual aids in the log-scale to mark runtimes of 30 minutes, 1 hour, and 10
hours. Vertical colored lines connect the 10 and 90 percentiles for the
results of the respective approach.

The same results are also given in Tables I (5CV vs 80LCCV) and II (10CV vs
90LCCV). The table augments the information of the plot by listing the
standard deviations for the different observations. Additionally, we provide a
reference for each of the analyzed datasets.

##  Appendix D Sensitivity Analysis of LCCV Parameters

We show the results of the sensitivity analysis. We have selected several
hyperparameters of LCCV and instantiated LCCV with several values for them.
Each of those hyperparameters was considered in isolation; all other
hyperparameters were kept constant. The remaining setup was identical to the
one in the main evaluation: In each instantiation, LCCV evaluated 200
pipelines (the same pipelines as described in Appendix B.2). Each pipeline was
allocated 300 seconds of run time. After the best pipeline has been
determined, it is evaluated on MCCV to determine the final error rate. Figure
3 shows the results.

Confidence threshold $\varepsilon$ controls the tolerated uncertainty at a
certain anchor point. If the evaluations at a certain anchor point have
confidence bounds higher than this threshold, more evaluations at this anchor
point will be performed. Note that the number of evaluations at each anchor
point is also bounded by a minimum and a maximum, which can be set by
hyperparameters that are also visualized (second row). For these three
hyperparameters, the results seem to be as expected. Requiring higher
confidence per anchor point or more evaluations results in a higher runtime.
The error rate is hardly affected by this.

Finally, we defined a hyperparameter that determined the policy of a certain
configuration could not be finished due to run time restrictions. In case of a
time out, LCCV can of course always return the performance measured on the
last successful anchor point. Alternatively, it can use the IPL-model to
predict the final evaluation. The analysis revealed that this hyperparameter
has limited effect, but it should be noted that it was only evaluated on
relatively small datasets. On larger datasets, the effect might be larger.

##  Appendix E Convexity of Learning Curves

In the following, we show the learning curves for all learners on all examined
datasets. Note that the y-scale is not always $[0,1]$ but is sometimes
adjusted to make the behavior of the curves more visible. The code for
reproducing them can be found at github.com/fmohr/lccv.

The figures support the convexity claim for the large majority of cases. 92%
of the curves have a strictly convex behavior at _any_ observed points. Among
the rest, several curves are still convex in large parts, and only a tiny
portion of curves show a “heavily” non-convex behavior. None of these is even
close to being competitive.

Figure 1: Visual comparison of random search using 80LCCV (blue) and using 5CV (orange) as validation technique. The x-axis displays the runtime in seconds (log-scale!), the y-axes displays the error rate. The dashed lines link the two observations for 80LCCV and 5CV that refer to the same dataset respectively (denoted at the edge label). Vertical colored lines connect the 10 and 90 percentiles. Vertical black lines are aids for 30m, 1h and 10h runtimes. Figure 2: Visual comparison of random search using 90LCCV (blue) and using 10CV (orange) as validation technique. The x-axis displays the runtime in seconds (log-scale!), the y-axes displays the error rate. The dashed lines link the two observations for 90LCCV and 10CV that refer to the same dataset respectively (denoted at the edge label). Vertical colored lines connect the 10 and 90 percentiles. Vertical black lines are aids for 30m, 1h and 10h runtimes.  openmlid | LCCV Performance | LCCV Runtime | Baseline CV Perf | Baseline CV Runtime
---|---|---|---|---
3 |  0.01$\pm$0.00 |  2719$\pm$649 |  0.01$\pm$0.00 |  3068$\pm$765
12 |  0.02$\pm$0.00 |  10266$\pm$638 |  0.02$\pm$0.00 |  10639$\pm$1521
23 |  0.45$\pm$0.01 |  4812$\pm$744 |  0.44$\pm$0.00 |  4268$\pm$615
31 |  0.26$\pm$0.00 |  1425$\pm$432 |  0.26$\pm$0.01 |  1188$\pm$362
54 |  0.18$\pm$0.02 |  2867$\pm$513 |  0.17$\pm$0.01 |  2412$\pm$639
181 |  0.38$\pm$0.01 |  4805$\pm$750 |  0.38$\pm$0.00 |  4730$\pm$1205
188 |  0.53$\pm$0.01 |  1609$\pm$413 |  0.53$\pm$0.01 |  1644$\pm$559
1049 |  0.09$\pm$0.00 |  2746$\pm$489 |  0.09$\pm$0.00 |  2267$\pm$392
1067 |  0.14$\pm$0.00 |  3910$\pm$626 |  0.14$\pm$0.00 |  3280$\pm$675
1111 |  0.04$\pm$0.03 |  15443$\pm$1488 |  0.02$\pm$0.00 |  28824$\pm$6659
1457 |  0.21$\pm$0.03 |  26713$\pm$1798 |  0.18$\pm$0.02 |  42021$\pm$6654
1461 |  0.11$\pm$0.00 |  11199$\pm$1911 |  0.11$\pm$0.00 |  15791$\pm$4403
1464 |  0.23$\pm$0.01 |  1822$\pm$450 |  0.22$\pm$0.01 |  1329$\pm$394
1468 |  0.05$\pm$0.00 |  11119$\pm$643 |  0.04$\pm$0.00 |  13068$\pm$2284
1475 |  0.38$\pm$0.01 |  12992$\pm$1768 |  0.38$\pm$0.00 |  19384$\pm$3778
1485 |  0.15$\pm$0.01 |  8521$\pm$563 |  0.15$\pm$0.01 |  12818$\pm$1822
1486 |  0.05$\pm$0.00 |  21531$\pm$2946 |  0.05$\pm$0.00 |  41241$\pm$8726
1487 |  0.06$\pm$0.00 |  5109$\pm$658 |  0.06$\pm$0.00 |  4798$\pm$495
1489 |  0.09$\pm$0.00 |  5552$\pm$945 |  0.09$\pm$0.00 |  9377$\pm$2318
1494 |  0.13$\pm$0.01 |  2704$\pm$401 |  0.13$\pm$0.00 |  1996$\pm$290
1515 |  0.07$\pm$0.01 |  10234$\pm$932 |  0.07$\pm$0.01 |  11344$\pm$1960
1590 |  0.16$\pm$0.00 |  10652$\pm$2231 |  0.16$\pm$0.00 |  13772$\pm$2807
4134 |  0.2$\pm$0.00 |  19178$\pm$1337 |  0.2$\pm$0.00 |  25480$\pm$3971
4135 |  0.05$\pm$0.00 |  25669$\pm$5186 |  0.05$\pm$0.00 |  36459$\pm$6598
4534 |  0.03$\pm$0.00 |  7235$\pm$1456 |  0.03$\pm$0.00 |  12232$\pm$3274
4538 |  0.28$\pm$0.00 |  12220$\pm$1469 |  0.28$\pm$0.00 |  26149$\pm$4602
4541 |  0.42$\pm$0.00 |  23186$\pm$3544 |  0.42$\pm$0.00 |  19583$\pm$4706
23512 |  0.27$\pm$0.00 |  23085$\pm$2765 |  0.27$\pm$0.00 |  29928$\pm$5231
23517 |  0.48$\pm$0.00 |  23342$\pm$2841 |  0.48$\pm$0.00 |  28904$\pm$5655
40498 |  0.32$\pm$0.01 |  7896$\pm$862 |  0.33$\pm$0.05 |  11089$\pm$1530
40668 |  0.2$\pm$0.01 |  15640$\pm$2268 |  0.19$\pm$0.02 |  16700$\pm$2517
40670 |  0.05$\pm$0.00 |  4665$\pm$885 |  0.04$\pm$0.00 |  6735$\pm$1644
40685 |  0.0$\pm$0.00 |  12650$\pm$2009 |  0.0$\pm$0.00 |  21972$\pm$4829
40701 |  0.05$\pm$0.00 |  5462$\pm$949 |  0.04$\pm$0.00 |  9432$\pm$1563
40900 |  0.01$\pm$0.00 |  4879$\pm$921 |  0.01$\pm$0.00 |  7210$\pm$918
40975 |  0.0$\pm$0.00 |  3557$\pm$441 |  0.0$\pm$0.00 |  3275$\pm$602
40978 |  0.03$\pm$0.00 |  13958$\pm$1488 |  0.03$\pm$0.00 |  14331$\pm$3093
40981 |  0.13$\pm$0.01 |  1919$\pm$362 |  0.13$\pm$0.01 |  1543$\pm$471
40982 |  0.2$\pm$0.01 |  5068$\pm$547 |  0.2$\pm$0.01 |  5263$\pm$750
40983 |  0.01$\pm$0.00 |  4134$\pm$776 |  0.01$\pm$0.00 |  6140$\pm$947
40984 |  0.07$\pm$0.01 |  5402$\pm$772 |  0.06$\pm$0.00 |  5294$\pm$1232
40996 |  0.13$\pm$0.01 |  35647$\pm$1811 |  0.12$\pm$0.00 |  51214$\pm$8295
41027 |  0.12$\pm$0.02 |  15905$\pm$2470 |  0.11$\pm$0.02 |  20092$\pm$4308
41138 |  0.01$\pm$0.00 |  21020$\pm$4210 |  0.01$\pm$0.00 |  39950$\pm$8626
41142 |  0.26$\pm$0.01 |  20504$\pm$1226 |  0.26$\pm$0.01 |  34163$\pm$5912
41143 |  0.2$\pm$0.00 |  4457$\pm$779 |  0.19$\pm$0.00 |  5026$\pm$957
41144 |  0.13$\pm$0.01 |  8097$\pm$916 |  0.13$\pm$0.01 |  11666$\pm$1701
41145 |  0.22$\pm$0.01 |  13328$\pm$1060 |  0.22$\pm$0.01 |  20875$\pm$2270
41146 |  0.05$\pm$0.00 |  5097$\pm$702 |  0.05$\pm$0.00 |  9146$\pm$1898
41147 |  0.36$\pm$0.03 |  36794$\pm$3679 |  0.33$\pm$0.00 |  30966$\pm$0
41150 |  0.05$\pm$0.00 |  25190$\pm$2217 |  0.05$\pm$0.00 |  39296$\pm$5996
41156 |  0.14$\pm$0.00 |  6186$\pm$732 |  0.14$\pm$0.00 |  8682$\pm$1708
41157 |  0.24$\pm$0.04 |  13326$\pm$1148 |  0.19$\pm$0.03 |  10220$\pm$1658
41158 |  0.05$\pm$0.01 |  12591$\pm$835 |  0.04$\pm$0.00 |  20127$\pm$4137
41159 |  0.21$\pm$0.03 |  38455$\pm$2073 |  0.18$\pm$0.01 |  57982$\pm$10141
41161 |  0.0$\pm$0.00 |  38107$\pm$2105 |  0.0$\pm$0.00 |  53635$\pm$3355
41162 |  0.12$\pm$0.00 |  14920$\pm$1352 |  0.13$\pm$0.03 |  16137$\pm$2448
41163 |  0.02$\pm$0.01 |  28787$\pm$1586 |  0.03$\pm$0.04 |  46928$\pm$10320
41164 |  0.3$\pm$0.01 |  24875$\pm$2143 |  0.29$\pm$0.01 |  42334$\pm$11041
41165 |  0.55$\pm$0.01 |  39723$\pm$2033 |  0.55$\pm$0.00 |  59340$\pm$7449
41166 |  0.34$\pm$0.01 |  29502$\pm$2300 |  0.32$\pm$0.02 |  41780$\pm$9741
41167 |  0.22$\pm$0.01 |  41713$\pm$1992 | NaN | 86400
41168 |  0.28$\pm$0.02 |  26216$\pm$2170 |  0.28$\pm$0.00 |  39360$\pm$5874
41169 |  0.65$\pm$0.01 |  29847$\pm$2423 |  0.65$\pm$0.01 |  47628$\pm$8652
42732 |  0.5$\pm$0.38 |  31728$\pm$1350 | NaN | 86400
42733 |  0.17$\pm$0.00 |  27371$\pm$5504 |  0.17$\pm$0.00 |  25123$\pm$6305
42734 |  0.25$\pm$0.00 |  15167$\pm$2144 |  0.25$\pm$0.00 |  16884$\pm$2830
TABLE I: Error rates and runtimes (s) of the Random Search with 5CV and 80LCCV. openmlid | LCCV Performance | LCCV Runtime | Baseline CV Perf | Baseline CV Runtime
---|---|---|---|---
3 |  0.01$\pm$0.00 |  3814$\pm$801 |  0.01$\pm$0.00 |  6368$\pm$2295
12 |  0.02$\pm$0.01 |  13150$\pm$649 |  0.02$\pm$0.00 |  19676$\pm$4979
23 |  0.45$\pm$0.01 |  6620$\pm$805 |  0.44$\pm$0.01 |  8502$\pm$1981
31 |  0.26$\pm$0.01 |  2032$\pm$421 |  0.26$\pm$0.01 |  2362$\pm$736
54 |  0.17$\pm$0.01 |  4253$\pm$823 |  0.17$\pm$0.01 |  4871$\pm$1687
181 |  0.39$\pm$0.02 |  6309$\pm$792 |  0.38$\pm$0.01 |  8528$\pm$1873
188 |  0.54$\pm$0.01 |  2170$\pm$526 |  0.52$\pm$0.01 |  2603$\pm$1162
1049 |  0.09$\pm$0.00 |  4222$\pm$706 |  0.09$\pm$0.00 |  4615$\pm$924
1067 |  0.15$\pm$0.00 |  5532$\pm$636 |  0.14$\pm$0.00 |  6498$\pm$1454
1111 |  0.02$\pm$0.00 |  16796$\pm$3942 |  0.02$\pm$0.00 |  35830$\pm$13662
1457 |  0.19$\pm$0.03 |  28425$\pm$1892 |  0.17$\pm$0.02 |  48648$\pm$14121
1461 |  0.11$\pm$0.00 |  12866$\pm$1751 |  0.11$\pm$0.00 |  23141$\pm$11020
1464 |  0.24$\pm$0.02 |  2540$\pm$555 |  0.22$\pm$0.01 |  2546$\pm$734
1468 |  0.04$\pm$0.01 |  14258$\pm$956 |  0.04$\pm$0.00 |  21870$\pm$7024
1475 |  0.37$\pm$0.00 |  14834$\pm$1741 |  0.38$\pm$0.00 |  37304$\pm$10756
1485 |  0.15$\pm$0.02 |  10740$\pm$826 |  0.14$\pm$0.01 |  23574$\pm$6048
1486 |  0.05$\pm$0.00 |  19985$\pm$3222 |  0.05$\pm$0.00 |  33505$\pm$9037
1487 |  0.06$\pm$0.00 |  7786$\pm$1329 |  0.06$\pm$0.00 |  9123$\pm$1213
1489 |  0.08$\pm$0.00 |  7187$\pm$944 |  0.08$\pm$0.00 |  18143$\pm$6255
1494 |  0.13$\pm$0.01 |  4267$\pm$529 |  0.13$\pm$0.01 |  4202$\pm$890
1515 |  0.06$\pm$0.01 |  11769$\pm$1083 |  0.08$\pm$0.02 |  20764$\pm$6681
1590 |  0.16$\pm$0.00 |  12257$\pm$2578 |  0.16$\pm$0.00 |  19477$\pm$7185
4134 |  0.2$\pm$0.01 |  23783$\pm$1781 |  0.19$\pm$0.00 |  44151$\pm$13991
4135 |  0.05$\pm$0.00 |  31290$\pm$5924 |  0.05$\pm$0.00 |  51449$\pm$14106
4534 |  0.03$\pm$0.00 |  9018$\pm$1721 |  0.03$\pm$0.00 |  22702$\pm$10760
4538 |  0.27$\pm$0.01 |  13676$\pm$1654 |  0.27$\pm$0.00 |  44568$\pm$18258
4541 |  0.42$\pm$0.00 |  24387$\pm$3276 |  0.42$\pm$0.00 |  24549$\pm$7060
23512 |  0.27$\pm$0.00 |  24611$\pm$3028 |  0.27$\pm$0.00 |  41472$\pm$13729
23517 |  0.48$\pm$0.00 |  26976$\pm$3174 |  0.48$\pm$0.00 |  43414$\pm$12728
40498 |  0.31$\pm$0.01 |  9194$\pm$1025 |  0.3$\pm$0.01 |  20812$\pm$4968
40668 |  0.2$\pm$0.02 |  16783$\pm$2447 |  0.19$\pm$0.02 |  21041$\pm$4837
40670 |  0.05$\pm$0.01 |  6575$\pm$1120 |  0.04$\pm$0.00 |  11958$\pm$2691
40685 |  0.01$\pm$0.02 |  14447$\pm$2132 |  0.0$\pm$0.00 |  31041$\pm$8996
40701 |  0.05$\pm$0.00 |  7668$\pm$1448 |  0.05$\pm$0.00 |  17849$\pm$4633
40900 |  0.01$\pm$0.00 |  7391$\pm$1098 |  0.01$\pm$0.00 |  14121$\pm$2842
40975 |  0.0$\pm$0.00 |  5009$\pm$623 |  0.0$\pm$0.00 |  6467$\pm$1378
40978 |  0.03$\pm$0.00 |  16274$\pm$1429 |  0.03$\pm$0.00 |  24388$\pm$8456
40981 |  0.13$\pm$0.01 |  2635$\pm$499 |  0.12$\pm$0.00 |  2854$\pm$525
40982 |  0.19$\pm$0.01 |  7022$\pm$966 |  0.2$\pm$0.01 |  9883$\pm$1591
40983 |  0.01$\pm$0.00 |  6075$\pm$1156 |  0.01$\pm$0.00 |  12522$\pm$3087
40984 |  0.06$\pm$0.00 |  6823$\pm$898 |  0.06$\pm$0.01 |  10757$\pm$2836
40996 |  0.13$\pm$0.01 |  37418$\pm$1205 |  0.12$\pm$0.00 |  54525$\pm$8923
41027 |  0.1$\pm$0.02 |  18029$\pm$2216 |  0.11$\pm$0.04 |  28614$\pm$7346
41138 |  0.01$\pm$0.00 |  21440$\pm$4014 |  0.01$\pm$0.00 |  48473$\pm$16425
41142 |  0.26$\pm$0.01 |  24077$\pm$1628 |  0.26$\pm$0.00 |  36286$\pm$2687
41143 |  0.2$\pm$0.00 |  6597$\pm$1193 |  0.2$\pm$0.01 |  9998$\pm$2617
41144 |  0.13$\pm$0.01 |  11018$\pm$1508 |  0.13$\pm$0.01 |  21647$\pm$5049
41145 |  0.22$\pm$0.01 |  16103$\pm$1226 |  0.22$\pm$0.01 |  35455$\pm$8022
41146 |  0.04$\pm$0.00 |  6915$\pm$1145 |  0.04$\pm$0.00 |  17615$\pm$5001
41147 |  0.34$\pm$0.02 |  36872$\pm$1991 |  0.33$\pm$0.00 |  31924$\pm$0
41150 |  0.05$\pm$0.00 |  27072$\pm$2627 |  0.05$\pm$0.00 |  47412$\pm$12695
41156 |  0.14$\pm$0.00 |  8699$\pm$1113 |  0.14$\pm$0.00 |  16892$\pm$5729
41157 |  0.21$\pm$0.03 |  17644$\pm$1717 |  0.19$\pm$0.03 |  17073$\pm$3532
41158 |  0.04$\pm$0.00 |  15687$\pm$898 |  0.04$\pm$0.00 |  35441$\pm$11638
41159 |  0.21$\pm$0.04 |  39357$\pm$2688 |  0.17$\pm$0.00 |  58890$\pm$4620
41161 |  0.0$\pm$0.00 |  41060$\pm$1521 |  0.0$\pm$0.00 |  57535$\pm$5450
41162 |  0.12$\pm$0.00 |  17158$\pm$1553 |  0.14$\pm$0.04 |  21137$\pm$4880
41163 |  0.02$\pm$0.00 |  32752$\pm$2693 |  0.01$\pm$0.00 |  45077$\pm$2106
41164 |  0.3$\pm$0.01 |  27038$\pm$1511 |  0.28$\pm$0.01 |  36959$\pm$3353
41165 |  0.55$\pm$0.01 |  42028$\pm$1620 |  0.54$\pm$0.01 |  58794$\pm$3410
41166 |  0.33$\pm$0.01 |  30450$\pm$1840 |  0.33$\pm$0.01 |  35753$\pm$2358
41167 |  0.16$\pm$0.05 |  39846$\pm$1962 | NaN | 86400
41168 |  0.28$\pm$0.01 |  28294$\pm$2250 |  0.28$\pm$0.00 |  50759$\pm$13764
41169 |  0.65$\pm$0.01 |  29502$\pm$2115 |  0.64$\pm$0.01 |  49281$\pm$12972
42732 |  0.12$\pm$0.00 |  32240$\pm$0 | NaN | 86400
42733 |  0.17$\pm$0.00 |  16574$\pm$3090 |  0.17$\pm$0.00 |  28152$\pm$9530
42734 |  0.26$\pm$0.00 |  16452$\pm$1873 |  0.25$\pm$0.00 |  22749$\pm$6145
TABLE II: Error rates and runtimes (s) of the Random Search with 10CV and
90LCCV.

Figure 3: Sensitivity analysis of the hyperparameter of LCCV. Each dot
represents a configuration of the hyperparameters of LCCV, averaged over 10
random seeds.