Predicting Runtime Distributions using Deep Neural Networks
Katharina Eggensperger and Marius Lindauer and Frank Hutter

arXiv:1709.07615v2 [] 24 Oct 2017

University of Freiburg
{eggenspk, lindauer, fh}@cs.uni-freiburg.de

Abstract
Many state-of-the-art algorithms for solving hard combinatorial problems include elements of stochasticity that lead
to high variations in runtime, even for a fixed problem instance, across runs with different pseudo-random number
seeds. Knowledge about the runtime distributions (RTDs) of
algorithms on given problem instances can be exploited in
various meta-algorithmic procedures, such as algorithm selection, portfolios, and randomized restarts. Previous work
has shown that machine learning can be used to individually
predict mean, median and variance of RTDs. To establish a
new state-of-the-art in predicting RTDs, we demonstrate that
the parameters of an RTD should be learned jointly and that
neural networks can do this well by directly optimizing the
likelihood of an RTD given runtime observations. In an empirical study involving four algorithms for SAT solving and AI
planning, we show that our neural networks predict the true
RTDs of unseen instances better than previous methods. As
an exemplary application of RTD predictions, we show that
our RTD models also yield good predictions of running these
algorithms in parallel.

Introduction
Algorithms for solving hard combinatorial problems often
rely on random choices and decisions to improve their performances. For example, randomization helps to escape local optima, enforces stronger exploration and diversifies the search
strategy by not only relying on heuristic information. In particular, most local search algorithms are randomized (Hoos
and Stützle 2004), but structured search (such as tree-based
algorithms) can also benefit from randomization (Gomes et
al. 2000).
The runtimes of randomized algorithms for hard combinatorial problems are well-known to vary substantially, often
by orders of magnitude, even when running the same algorithm multiple times on the same instance (Gomes et al. 2000;
Hoos and Stützle 2004; Hurley and O’Sullivan 2015). Hence,
the central object of interest in the analysis of a randomized
algorithm on an instance is its runtime distribution (RTD), in
contrast to a single scalar for deterministic algorithms. Knowing these RTDs is important in many practical applications,
such as computing optimal restart strategies (Luby, Sinclair,
and Zuckerman 1993), optimal algorithm portfolios (Gomes
and Selman 2001) and the speedups obtained by executing
multiple independent runs of randomized algorithms (Hoos

and Stützle 2004). It is trivial to measure an algorithm’s
empirical RTD on an instance by running it many times to
completion, but for new instances that one would like to
solve, this is of course not practical. Instead, one would like
to estimate the RTD for a new instance without running the
algorithm on it.
There is a rich history in artificial intelligence that shows
that the runtime of algorithms for solving hard combinatorial problems can indeed be predicted to a certain degree (Brewer 1995; Roberts and Howe 2007; Fink 1998;
Leyton-Brown, Nudelman, and Shoham 2009; Hutter et
al. 2014). These runtime predictions have enabled a wide
range of meta-algorithmic procedures, such as algorithm
selection (Xu et al. 2008), model-based algorithm configuration (Hutter, Hoos, and Leyton-Brown 2011), generating
hard benchmarks (Leyton-Brown, Nudelman, and Shoham
2009), gaining insights into instance hardness (Smith-Miles
and Lopes 2012) and algorithm performance (Hutter, Hoos,
and Leyton-Brown 2013), and creating cheap-to-evaluate
surrogate benchmarks (Eggensperger et al. 2017).
Given a method for predicting RTDs of randomized algorithms, all of these applications could be extended by an
additional dimension. Indeed, predictions of RTDs have already enabled dynamic algorithm portfolios (Gagliolo and
Schmidhuber 2006b), adaptive restart strategies (Gagliolo
and Schmidhuber 2006a; Haim and Walsh 2009), and predictions of the runtime of parallelized algorithms (Arbelaez,
Truchet, and O’Sullivan 2016), and many more applications
are possible given effective methods for RTD prediction. To
advance the underlying foundation of all these applications,
in this paper we focus on better methods for predicting RTDs.
Specifically, our contributions are as follows:
1. We propose a principled pipeline to build RTD predictors
for new problem instances based on observed runtimes on
a set of training instances.
2. We compare different ways of predicting RTDs and demonstrate that neural networks (NN) can jointly predict all
parameters of various parametric RTDs, yielding RTD predictions that are superior to those of previous approaches
that predict the RTD’s parameters independently.
3. We propose DistNet, a practical NN for predicting RTDs,
and discuss the bells and whistles that make it work.
4. To illustrate the use of our NN-based RTD predictions in

an application, we demonstrate that they can effectively
predict the performance that can be obtained by running
multiple independent copies of a randomized algorithm in
parallel (Arbelaez, Truchet, and O’Sullivan 2016).

Related Work
The rich history in predicting algorithm runtimes mentioned
in the introduction focuses on predicting mean runtimes,
with only a few exceptions. Hutter et al. (2006) predicted
the single distribution parameter of an exponential RTD and
Arbelaez, Truchet, and O’Sullivan (2016) predicted the two
parameters of log-normal and shifted exponential RTDs with
independent models. In contrast, we jointly predict multiple
RTD parameters (and also show that the resulting predictions
are better than those by independent models).
The work most closely related to ours is by Gagliolo and
Schmidhuber (2005), who proposed to use NNs to learn
a distribution of the time left until an algorithm solves a
problem based on features describing the algorithm’s current
state and the problem to be solved; they used these predictions
to dynamically assign time slots to algorithms. In contrast,
we use NNs to predict RTDs for unseen problem instances.
A final related field of study on predicting distributions
uses non-parametric estimators. Very recently, Eggensperger
et al. (2017) used quantile regression forests (Meinshausen
2006) as a non-parametric model that enables sampling from
predicted runtime distributions. Also very recently, Ambrogioni et al. (2017) showed that NNs can be used as a nonparametric estimator for arbitrary conditional distributions.
In contrast to that, we focus on a parametric approach, using NNs to predict distribution parameters for non-Gaussian
distributed target values.
All existing methods for predicting runtime on unseen instances base their predictions on instance features that numerically characterize problem instances. In particular in the context of algorithm selection, these instance features have been
proposed for many domains of hard-combinatorial problems,
such as propositional satisfiability (Nudelman et al. 2004),
AI planning (Fawcett et al. 2014), mixed integer programming (Xu et al. 2011) and answer set programming (Hoos,
Lindauer, and Schaub 2014). To avoid this manual step of feature construction, Loreggia et al. (2016) proposed to directly
use the text format of an instance as the input to a neural
network to obtain a numerical representation of the instance.
Since this approach performed a bit worse than manually
constructed features, in this work we use traditional features,
but our framework will work with any type of features.

A Pipeline for Predicting RTDs
The problem we address in this work can be formally described as follows:
Problem Statement (Predicting RTDs). Given
• a randomized algorithm A
• a set of instances Πtrain = {π1 , . . . , πn }
• for each instance πj ∈ Πtrain :
– m instance features f (πj ) = [f (πj )1 , . . . , f (πj )m ]

Distribution

Param.

Normal (N)

µ, σ

Lognormal (LOG)

s, σ

Exponential (EXP)

β

PDF
(x−µ)2

Inverse Gaussian (INV) µ, λ

−
√ 1
e 2σ2
2πσ 2

log(x)−log(s) 2
1
−2
1
σ
√
e
σx 2π


x
−β
1
e
β 

λ
2πx3

 12

e

−λ(x−µ)2
2xµ2

Table 1: Considered RTD families
– runtime observations t(πj ) = ht(πj )1 , . . . , t(πj )kj i obtained by executing A on πj with kj different seeds,
the goal is to learn a model that can predict A’s RTD well
for unseen instances πn+1 with given features f (πn+1 ).
Following the typical approach in the literature (Hutter
et al. 2006; Arbelaez, Truchet, and O’Sullivan 2016), we
address this problem in two steps:
1. Determine a parametric family D of RTDs with parameters
θ that fits well across training instances;
2. Fit a machine learning model that, given a new instance
and its features, predict D’s parameters θ on that instance.
Figure 1 illustrates the pipeline we use for training these
RTD predictors and using them on new instances. In the
following, we first discuss the various RTD families we considered; explain how we measure the goodness of our RTD
fits (i.e., our loss function); and finally discuss different ways
of predicting RTDs, including our new approach of jointly
learning RTD parameters using NNs.

Parametric Families of RTDs
We considered a set of 4 parametric continuous probability
distributions (shown in Table 1 with exemplary instantiations
shown in Figure 2), most of which have been widely studied
to describe the RTDs of combinatorial problem solvers (Frost,
Rish, and Vila 1997; Gagliolo and Schmidhuber 2006a;
Hutter et al. 2006). As a baseline we consider the normal (aka
Gaussian) distribution, due to its widespread use throughout
in the sciences; assumptions of Gaussian observation noise
also underlie many machine learning methods, such as Gaussian processes.
Since the runtimes of hard combinatorial solvers often vary
on an exponential scale (likely due to the N P-hardness of
the problems studied), a much better fit of empirical RTDs is
typically achieved by a lognormal distribution; this distribution is attained if the logarithm of the runtimes is Gaussiandistributed and has been shown to fit empirical RTDs well in
previous work (Frost, Rish, and Vila 1997).
Another popular parametric family from the literature on
RTDs is the exponential distribution, which tends to describe
the RTDs of many well-behaved stochastic local search algorithms well (Hoos and Stützle 2004). It is the unique family
with the property that the probability of finding a solution in
the next time interval (conditional on not having found one
yet) remains constant over time. This distribution, like the lognormal distribution, can therefore model the relatively long

Algorithm A

Run A kj times on
each πj ∈ Πtrain

Training instances
πj ∈ Πtrain

Compute instance
features f (πj ) for
each πj ∈ Πtrain

Data:
hf (πj ), t(πj ){1...kj } i

Estimate RTD
family D

Fit RTD model
m̂ : f (π) 7→ θ

New instance
πn+1

Compute features
f (πn+1 )

Use m̂ to predict
D’s parameters
θ for πn+1

Figure 1: Our pipeline for predicting runtime distributions. Upper part: training; lower part: test.

−logLD (θ | t(π)1 , . . . , t(π)k ) = −

k
X

log pD (t(π)i |θ). (2)

i=1

Since each instance π ∈ Π results in an RTD, we measure the quality of a parametric family of RTDs for a given
instance set by averaging over the negative log-likelihoods
of all instances. To obtain comparable likelihoods across the
instances, we normalize them by multiplying the likelihoods
with the maximal observed runtime of each instance:2

Figure 2: Different RTD families.

tails of typical RTDs of randomized combinatorial problem
solvers quite well.
By empirically studying a variety of alternative parametric
families, we also found that an inverse Gaussian distribution
(INV) tends to fit RTDs very well.1 Like the lognormal and
exponential distribution, this flexible distribution can also
model long tails well. By setting its λ parameter close to
infinity, it can also be made to resemble a normal distribution.

Quantifying the Quality of RTDs
To measure how well a parametric distribution D with parameters θ fits our empirical runtime observations t(π) =
ht(π)1 , . . . , t(π)k i (the empirical RTD), we use the likelihood of parameters θ given all observations t(π), which is
equal to the probability of the observations under distribution
D with parameters θ:
LD (θ | t(π)1 , . . . , t(π)k ) =

k
Y

pD (t(π)i | θ).

(1)

i=1

Consequently, when estimating the parameters of a given
empirical RTD, we use a maximum-likelihood fit. For numerical reasons, as is common in machine learning, we use the
negative log-likelihood as a loss function to be minimized:
1
The name of the inverse Gaussian distribution can be misleading in the sense that it is not the inverse of a Gaussian distribution.



1 X
− log LD (θ | t(π)1 , . . . , t(π)k ) · max t(π)i
(3)
|Π|
i∈{1...k}
π∈Π
!
n
1 X X
log pD (t(π)i |θ) + log max t(π)i (4)
=−
|Π|
i∈{1...n}
i=1
π∈Π

An alternative is to use a goodness of fit statistical test,
such as the Kolmogorov-Smirnov (KS) test. The KS-statistic
is based on the maximal distance between an empirical distribution and the cumulative distribution function of a reference
distribution. To aggregate the test results across instances,
we count the number of times for which the KS-test rejected
the null-hypothesis that our measured t(π)i are drawn from
a reference RTD.

Predicting RTDs
Having selected a parametric family of distributions, the last
part of our pipeline is to fit an RTD predictor to efficiently obtain RTDs for new instances. Formally, the problem is to find
a predictive model that maps from instance features f (π) to
the parameters θ of the selected RTD family. In the following,
we briefly discuss how traditional regression models have
been used for this problem, and why this optimizes the wrong
loss function. We then show how to obtain better predictions
with neural networks and introduce our practical DistNet for
this task.
2
When this is not done, easy instances are weighted more heavily: if two RTDs “look” the same but differ in scale by a factor
of 10 due to one instance being 10 times harder, the pdf for the
easier instance is 10 times larger (in order to still integrate to 1);
our normalization removes this bias towards fitting easy instances
better.

Input
Layer

Hidden
Layer #1

Hidden
Layer #n

Output
Layer

θ1πi

f (πi )1
...

...

f (πi )m

...
θpπi

Figure 3: Deep neural network used to model RTDs.

Generalizing from Training RTDs
A straightforward approach for predicting parametric RTDs
based on standard regression models is to fit the RTD’s
parameters θ(π) for each training instance π, and to then
train a regression model on data points hf (π), θ(π)iπ∈Πtrain
that directly maps from instance features to RTD parameters. This approach has been used before based on Gaussian
processes (Hutter et al. 2006) and random forests (Arbelaez, Truchet, and O’Sullivan 2016). There are two variants to extend these approaches to the problem of predicting multiple parameters of RTDs governed by p > 1
parameters: (1) fitting p independent regression models,
or (2) fitting a multi-output model with p outputs. Since
random forests have been shown to perform very well
for standard runtime prediction tasks (Hutter et al. 2014;
Hurley and O’Sullivan 2015), we experimented with them
in variant (1), but also in variant (2), using the multi-output
random forest implementation in scikit-learn (Pedregosa et al.
2011) (which learns the mapping jointly by minimizing the
errors across the p output variables). However, we note that
this multi-output variant, although in principle more powerful
than p independent models, does not optimize the loss function from Equation 2 we care about. We also note that both
variants require fitting RTDs on each training instance, making the approach inapplicable if we, e.g., only have access to
one run for each of a million instances. Now, we show how
neural networks can be used to solve both of these problems.

Joint Predictions with Neural Networks
Neural networks have recently been shown to achieve stateof-the-art performance for many supervised machine learning problems as large data sets became available, e.g., in
image classification and segmentation, speech processing
and natural language processing. For a thorough introduction,
we refer the interested reader to Goodfellow, Bengio, and
Courville (2016). Here, we apply NNs to RTD prediction.

Background on Neural Networks. NNs can approximate
arbitrary functions by defining a mapping y = f (x; W )
where W are the weights to be learnt during training to approximate the function. In this work we use a fully-connected
feedforward network, which can be described as an acyclic
graph that connects nonlinear transformations g in a chain,
from layer to layer. For example, a NN with two hidden layers
that predicts y for some input x can be written as:3






y = g out g (2) g (1) xW (1) W (2) W (3) , (5)
with W (j) denoting trainable network weights and g (j) (the
so-called activation function) being a nonlinear transformation applied to the weighted outputs of the j-th layer. The
last activation function, g (out) is special, and in our case is
exp(·) to constrain all outputs to be positive.
NNs are usually trained with stochastic gradient descent
(SGD) methods using backpropagation to effectively obtain
gradients of a task-specific loss function for each weight.
Neural Networks for predicting RTDs. Figure 3 shows
the general architecture of our NNs for the joint prediction of
multiple RTD parameters. We have one input neuron for each
instance feature f (π)j , and we have one output neuron for
each distribution parameter θk . To this end, we assume that
we know the best-fitting distribution family from the previous
step of our pipeline.
In contrast to RFs, we train our networks to directly minimize the negative log-likelihood of the predicted distribution
parameters given our observed runtimes. Formally, for a given
set of observed runtimes t(π)j and instance features f (π)j ,
we minimize the following loss function in an end-to-end
fashion:
J(W ) = −

kj
X X

logLD (θW |f (πj ), t(πj )i )

(6)

πj ∈Πtrain i=1

Here, θW denotes the values of the distribution parameters
obtained in the output layer given an instantiation W of the
NN’s weights. This optimization process, which targets exactly our loss function of interest (Equation 2), allows to
effectively predict all p distribution parameters jointly. Since
predicted combinations are judged directly by their resulting
negative log-likelihood, the optimization process is driven to
find combinations that work well together (rather than penalizing distance from a prescribed ground truth as was the case
with the random variants (1) and (2) above). This end-to-end
optimization process is also more general as it removes the
need of fitting an RTD on each training instance and thereby
enables using an arbitrary set of algorithm performance data
for fitting the model.
DistNet: RTD predictions with NNs in practice. Unfortunately, training an accurate NN in practice can be tricky
and requires manual attention to many details, including the
3

We ignore bias terms for simplicity of exposition.

network architecture, training procedure, and other hyperparameter settings.4 We call the resulting neural network with
the following considerations DistNet.
To preprocess our runtime data hf (πi ), t(πi ){1...k} i, we
performed the following steps:
1. We removed all (close to be) constant features.
2. For each instance feature type, we imputed missing values
(e.g., because of resource limitations during feature computation) by the median of the known instance features.
3. We normalized each feature f (π)j to mean 0 and standard
deviation 1 because the weights of a neural network are
typically initialized by random samples from a normal
distribution with mean 0 and standard deviation 1.
4. We scaled the observed runtimes in a range of [0, 1] by
dividing it by the maximal observed runtime across all
instances. This also helps the neural network training to
converge faster.
For training DistNet, we considered the following aspects:
1. Our first networks tended to overfit the training data if the
training data set was too small and the network too large.
Therefore, we recommend to use a sufficiently large number of instances and runtime observations, and we chose
a fairly small neural network with two hidden layers each
with 16 neurons. We believe that far better performance
could be achieved with larger and deeper networks when
more training instances are available.
2. We considered each runtime observation as an individual
data sample. Hence, we increased the number of training
samples to the number of instances |Π| times the number
of observations k—the training set size for the random
forest equals the number of instances.
3. We shuffled the runtime observations (as opposed to, e.g.,
using only data points from a single instance in each batch)
and use a fairly small batch size to reduce the correlation
of the training data points in each batch.
4. Our loss function can have very large gradients because
slightly suboptimal RTD parameters can lead to likelihoods
close to zero (or a very large negative log-likelihood).
Therefore, we used a fairly small initial learning rate and
used gradient clipping (Pascanu, Mikolov, and Bengio
2013) on top of it with an exponentially decaying learning
rate.
Table 2 shows all architectural choices and hyperparameters
of DistNet.

Experiments
In our experiments, we study the following research questions:
Q1 Which of the parametric RTD families we considered
best describe the empirical RTDs of our algorithms and
instances?
4
Automated machine learning tools, such as AutoNet (Mendoza
et al. 2016), can help with this process, but AutoNet so far does not
support distributions; we aim to contribute this feature to it in the
future.

parameter

value

# hidden layers
# neurons per layer
batch size
activation function
output act. function

2
16
16
tanh
exp

parameter

value

optimization algo.
init. learn. rate
final learn. rate
batch normalization
L2-regularization
gradient clipping

SGD
1e-3
1e-5
True
1e-4
1e-2

Table 2: Configuration of DistNet.
Scenario
Saps-CV-VAR
LPG-Zenotravel
ProbSAT-7SAT
Clasp-K5

#instances

#features

10011
3999
242
550

46
165
94
83

Table 3: Characteristics of the used data sets.
Q2 How do DistNet’s joint predictions of RTD parameters
compare to those of popular random forest models?
Q3 Can DistNet be used to predict the runtime achieved by
multiple-independent-run parallelization?

Experimental Setup
We focus on 4 well-studied algorithms, each evaluated on
a different set of problem instances from two different domains:
Saps-CV-VAR is based on the dynamic local search SAT
solver Saps (Hutter, Tompkins, and Hoos 2002). The SAT
instances are randomly generated with a varying clausevariable ratio (CV-VAR).
LPG-Zenotravel is based on the local search AI-planning
solver LPG (Gerevini and Serina 2002). The instances are
from the zenotravel planning domain (Penberthy and Weld
1994), which arise in a version of route planning.
ProbSAT-7SAT is based on the local search SAT solver
ProbSAT (Balint and Schöning 2012). We ran this on 7SAT
random instances.
Clasp-K5 is based on the tree-based CDCL solver
Clasp (Gebser, Kaufmann, and Schaub 2012). In our experiments, Clasp is randomized by using a randomly-selected
split variable with a probability of 5%. The instances are
randomly generated unsatisfiable SAT instances.
The sizes of our instance sets are shown in Table 3. To gather
training data, we ran each algorithm with 100 different seeds
on each instance. All runs were performed on a compute
cluster with nodes equipped with two Intel Xeon E5-2630v4
and 128GB memory running CentOS 7. We used the opensource neural network library keras (Chollet and others 2015)
for our neural networks, scikit-learn (Pedregosa et al. 2011)
for the RF implementation and scipy (Jones et al. 2001) for
fitting the distributions.

Q1: Best RTD Families
Figure 4 shows some exemplary CDFs of our empirical
RTDs; each line is the RTD on one of the instances. The

Saps-CV-VAR

LPG-Zenotravel

ProbSAT-7SAT

Clasp-K5

Figure 4: Empirical CDFs observed when running the default configuration of an algorithms 100 times. Blue indicates satisfiable
instances, red indicates unsatisfiable instances.
−logLD (θ | t(π))
LOG
-0.88
LOG
LPG-Zenotravel
-0.90
EXP
ProbSAT-7SAT
-0.58
INV
Clasp-K5
-1.36
Saps-CV-VAR

INV
-0.88
INV
-0.90
LOG
-0.50
LOG
-1.36

N
-0.75
N
-0.62
N
-0.20
N
-1.36

EXP
0.26
EXP
-0.08
INV
-0.19
EXP
0.81

KS: (%p) ≤ 0.01
LOG
0.1
LOG
12.7
EXP
0.0
INV
0.0

INV
4.0
INV
20.2
LOG
0.8
LOG
0.0

N
20.1
N
79.2
N
59.1
N
0.0

EXP
87.5
EXP
100.0
INV
93.4
EXP
100.0

Table 4: Results for fitted distributions: average negative
log-likelihood across instances and percentage of rejected
distributions according to a KS-test (α = 0.1 without multiple testing correction). For each scenario, we report result for
the top-3 distributions ranked by the negative log-likelihood.
For both metrics, smaller numbers are better.

Scenario

dist
LOG

Saps-CV-VAR
INV
LOG
LPG-Zenotravel
INV
EXP
ProbSAT-7SAT
LOG
INV
Clasp-K5
LOG

different algorithms’ RTDs show different characteristics. On
Saps-CV-VAR, most RTDs are very similar and have short
right tails. On LPG-Zenotravel, the RTDs have a long right
tail and a short left tail. In contrast, the RTDs of ProbSAT7SAT have a very long right tail and no left tail. On Clasp-K5,
the RTDs are nearly symmetric.
Table 4 shows a quantitative evaluation of the different
RTD families we considered (see Section Quantifying the
Quality of RTDs). Overall, our fitted distributions closely
resembled the true empirical RTDs, with a rejection rate of
the KS test for the best fitting distribution of at most 12.7%.
Hence, on most instances our best distributions were not
statistically significantly different from the observed ones.
Not surprisingly, different parametric RTD families performed best on each scenario, with LOG and INV showing
overall good performance, followed by N. EXP performed
worst in 3 out of 4 cases, but best for ProbSAT-7SAT. On
LPG-Zenotravel the KS-test showed the most statistically
significant differences for the best fitting distribution since
the CDFs start with a small shift (see Figure 4) and therefore
cannot be approximated perfectly by our distributions. Still,
these distributions achieved good negative log-likelihood values. On Clasp-K5 all distributions except EXP achieved good
results.

Q2: Predicting RTDs
Next, we turn to the empirical evaluation of our models,
comparing the predictive negative log-likelihood obtained
by DistNet, a multi-output random forest (RF) and fitting

fitted

RF

iRFs DistNet

train
test
train
test

-0.88 0.84 -0.69
-0.88 1.05 -0.30
-0.88 -0.58 -0.36
-0.88 -0.07 0.04

-0.59
-0.59
-0.53
-0.52

train
test
train
test

-0.90
-0.90
-0.90
-0.90

-0.88
-0.85
-0.87
-0.79

-0.89
-0.84
-0.83
-0.77

-0.85
-0.85
-0.84
-0.84

train
test
train
test

-0.58
-0.58
-0.50
-0.50

-0.53
-0.46
-0.47
-0.39

-0.55
-0.45
-0.45
-0.39

-0.57
-0.41
-0.48
-0.33

train
test
train
test

-1.36
-1.36
-1.36
-1.36

-0.98
-0.71
-1.32
-1.15

-1.24
-1.00
-1.28
-1.15

-1.34
-1.17
-1.34
-1.18

Table 5: Averaged negative log-likelihood achieved for predicting RTDs for unseen instances. We report the average
across a 10-fold cross-validation with the first line for each
dataset being the performance on the training data and the
second line being the performance on the test data. For each
scenario, we picked the two best-fitting RTD families (according to negative log-likelihood; see Table 4) and highlight
the best predictions.

multiple independent RFs, one for each distribution parameter (iRFs). For DistNet, we used the settings as described
in Table 2 and limit the training to take at most 1h or 1000
epochs, whichever was less. As a gold standard, we report the
negative log-likelihood obtained by a maximum likelihood
fit to the empirical RTD.
Table 5 shows the negative log-likelihood achieved using
a 10-fold cross-validation, i.e., we split the instances into
ten disjoint sets, train our models on all but one subset and
measure the test performance on the left out subset. We report
the average performance on train and test data across all splits
for the two best fitting distributions according to Table 4.
Overall our results show that it is possible to predict RTD
parameters for unseen instances, and that DistNet performed
best. For three out of four scenarios, our models achieved a
negative log-likelihood close to the gold standard of fitting
the RTDs to the observed data. Also, for most scenarios both
distribution families were similarly easy to predict for all

ProbSAT-7SAT

Clasp-K5

LPG-Zenotravel

Saps-CV-VAR

Figure 5: Estimated runtime for running algorithms in parallel. We compare the true runtime based on collected data to
the estimated runtime obtained with fitted distributions and
based on DistNet.
models. For the RF-based model, we observed slight overfitting for Saps-CV-VAR, LPG-Zenotravel, and Clasp-K5. For
DistNet, we only observed this on the smallest data sets,
ProbSAT-7SAT and Clasp-K5.
On Saps-CV-VAR, the multi-output RF yielded very poor
predictions for the LOG distribution; we believe this is due
to the fact that the ranges of its two distribution parameters
obtained by fitting the distributions vary greatly. This affects
the loss function the RF uses to fit the data (i.e., the sum of the
losses for all parameters). This does not happen when fitting
two RFs individually (as can be seen by the better negative
log-likelihood values obtained by iRFs), but it underlines the
importance of optimizing the right loss function as we do in
DistNet.
On ProbSAT-7SAT, the models basically only needed to
fit a single parameter: EXP only has a single parameter (β),
and although LOG has two parameters (µ and σ), only µ was
important for ProbSAT-7SAT since σ was almost constant.
Thus, in this case, the difference between RF and iRFs was
due to noise and DistNet could not profit from its joint model.
Overall, DistNet clearly yielded the most robust results. It
achieved the best test set predictions in 6/8 cases, sometimes
with substantial improvements over the RF baselines, and
only performed slightly worse for the smallest ProbSAT7SAT benchmark (for which also only one RTD parameter
was relevant).

Q3: DistNet for Parallel RTD prediction
Finally, we evaluate DistNet on a typical application: predicting the estimated runtime of a simple parallelization scheme.
In this setting, an algorithm is trivially parallelized by running
multiple independent copies with different random seeds in
parallel. Because of the randomization, one of the runs will
solve the instance faster than the others, at which point all
other runs can be terminated. Knowing in advance how many

parallel ressources are required to reach a certain speed-up allows for efficient trade-offs between computational resources
and the time needed to solve an instance.
Here, we approximate the runtime of n parallel runs by
drawing n samples from the sequential algorithm’s RTD 1000
times, and obtain the expected parallel runtime by taking the
average of the best out of n samples across all simulated
parallel runs.
We simulate running n = 1, 2, 4, 8, 16, 32 copies of the
same algorithm in parallel and compare the expected parallel runtime based on our empirical RTDs and based on the
predicted RTDs of DistNet. To aggregate the results, we used
the average estimated runtime across all problem instances
(by concatenating the results on all 10 test folds).
Figure 5 shows the expected runtime depending on the
number of parallel runs. For ProbSAT-7SAT and Clasp-K5,
we obtained estimated runtimes close to the true distribution. For LPG-Zenotravel, the KS-test already indicated that
LOG is not a perfectly-fitting distribution, and hence the
estimated runtimes of parallel algorithm runs obtained by
fitting distributions do not line up with the true parallel runtimes. Nevertheless, our DistNet perfectly matched the gold
standard of the fitted distribution. Finally, on Saps-CV-VAR,
DistNet overestimated the left tail of the RTD slightly, causing it to also underestimate the runtime of a parallel portfolio.
Nevertheless, the overall trend was predicted correctly. Overall, from these experiments, we conclude that the predictions
obtained with DistNet are suitable to estimate the runtime of
parallel algorithm runs.

Conclusion and Future Work
In this paper we showed that neural networks can be used
to jointly learn distribution parameters to predict runtime
distributions (RTDs). In contrast to previous random forest
models, we train our model on individual runtime observations, removing the need to fit RTDs on all training instances.
More importantly, our neural network – which we dub DistNet – directly optimizes the loss function of interest in an
end-to-end fashion, and by doing so obtains better predictive
performance than previously-used random forests models
that do not directly optimize this loss function.
One way to extend our work and increase the amount of
available training data would be to also consider censored
observations in the loss function of our neural network as proposed by Gagliolo and Schmidhuber (2006a). Furthermore,
so far, we only studied problems with either only satisfiable
or only unsatisfiable instances. In practice, we may face instances of both types, and each may follow a different RTD
family. We expect that using a mixture of models (Jacobs et al.
1991) to learn different distribution families could alleviate
this problem.
While in this paper we only briefly illustrated the suitability
of RTD predictions on one simple application, we note that
our methodology allows for better RTD predictions in general
and therefore may pave the way for improving many exciting
applications that currently rely on mean predictions only,
such as, e.g., algorithm selection (Xu et al. 2008) and modelbased algorithm configuration (Hutter, Hoos, and LeytonBrown 2011).

Acknowledgements
The authors acknowledge funding by the DFG (German Research Foundation) under Emmy Noether grant HU 1900/2-1.
K. Eggensperger additionally acknowledges funding by the
State Graduate Funding Program of Baden-Württemberg.
Furthermore, the authors acknowledge support by the state of
Baden-Württemberg through bwHPC and the DFG through
grant no INST 39/963-1 FUGG.

References
[Ambrogioni et al. 2017] Ambrogioni, L.; Güçlü, U.; van Gerven,
M.; and Maris, E. 2017. The kernel mixture network: A nonparametric method for conditional density estimation of continuous random
variables. arXiv [stat.ml] 1705.07111.
[Arbelaez, Truchet, and O’Sullivan 2016] Arbelaez, A.; Truchet, C.;
and O’Sullivan, B. 2016. Learning sequential and parallel runtime
distributions for randomized algorithms. In Proc. of ICTAI’16.
[Balint and Schöning 2012] Balint, A., and Schöning, U. 2012.
Choosing probability distributions for stochastic local search and
the role of make versus break. In Proc. of SAT’12, 16–29.
[Brewer 1995] Brewer, E. A. 1995. High-level optimization via
automated statistical modeling. In ACM SIGPLAN Notices, 80–91.
[Chollet and others 2015] Chollet, F., et al. 2015. Keras. https:
//github.com/fchollet/keras.
[Eggensperger et al. 2017] Eggensperger, K.; Lindauer, M.; Hoos,
H.; Hutter, F.; and Leyton-Brown, K. 2017. Efficient benchmarking
of algorithm configuration procedures via model-based surrogates.
arXiv [] 1703.10342v1:1–27.
[Fawcett et al. 2014] Fawcett, C.; Vallati, M.; Hutter, F.; Hoffmann,
J.; Hoos, H.; and Leyton-Brown, K. 2014. Improved features for
runtime prediction of domain-independent planners. In Proc. of
ICAPS’14. AAAI.
[Fink 1998] Fink, E. 1998. How to solve it automatically: Selection
among problem-solving methods. In Proc. of ICANN’08, 128–136.
AAAI Press.
[Frost, Rish, and Vila 1997] Frost, D.; Rish, I.; and Vila, L. 1997.
Summarizing CSP hardness with continuous probability distributions. In Proc. of AAAI’97, 327–333.
[Gagliolo and Schmidhuber 2005] Gagliolo, M., and Schmidhuber,
J. 2005. A neural network model for inter-problem adaptive online
time allocation. In Proc. of ICANN’05, 752–752.
[Gagliolo and Schmidhuber 2006a] Gagliolo, M., and Schmidhuber,
J. 2006a. Impact of censored sampling on the performance of restart
strategies. In Proc. of CP’06, volume 4204, 167–181.
[Gagliolo and Schmidhuber 2006b] Gagliolo, M., and Schmidhuber,
J. 2006b. Learning dynamic algorithm portfolios. AMAI 47(34):295–328.
[Gebser, Kaufmann, and Schaub 2012] Gebser, M.; Kaufmann, B.;
and Schaub, T. 2012. Conflict-driven answer set solving: From
theory to practice. AI 187-188:52–89.
[Gerevini and Serina 2002] Gerevini, A., and Serina, I. 2002. LPG:
A planner based on local search for planning graphs with action
costs. In Proc. of AIPS’02, 13–22.
[Gomes and Selman 2001] Gomes, C., and Selman, B. 2001. Algorithm portfolios. AIJ 126(1-2):43–62.
[Gomes et al. 2000] Gomes, C.; Selman, B.; Crato, N.; and Kautz,
H. 2000. Heavy-tailed phenomena in satisfiability and constraint
satisfaction problems. Journal of Automated Reasoning 24:67–100.

[Goodfellow, Bengio, and Courville 2016] Goodfellow, I.; Bengio,
Y.; and Courville, A. 2016. Deep Learning. MIT Press.
[Haim and Walsh 2009] Haim, S., and Walsh, T. 2009. Restart
strategy selection using machine learning techniques. In Proc. of
SAT’09.
[Hoos and Stützle 2004] Hoos, H., and Stützle, T. 2004. Stochastic
Local Search: Foundations & Applications. Morgan Kaufmann
Publishers Inc.
[Hoos, Lindauer, and Schaub 2014] Hoos, H.; Lindauer, M.; and
Schaub, T. 2014. claspfolio 2: Advances in algorithm selection for
answer set programming. TPLP 14:569–585.
[Hurley and O’Sullivan 2015] Hurley, B., and O’Sullivan, B. 2015.
Statistical regimes and runtime prediction. In Proc. of IJCAI’15,
318–324.
[Hutter et al. 2006] Hutter, F.; Hamadi, Y.; Hoos, H. H.; and LeytonBrown, K. 2006. Performance prediction and automated tuning of
randomized and parametric algorithms. In Proc. of CP’06, 213–228.
[Hutter et al. 2014] Hutter, F.; Xu, L.; Hoos, H.; and Leyton-Brown,
K. 2014. Algorithm runtime prediction: Methods and evaluation.
AIJ 206:79–111.
[Hutter, Hoos, and Leyton-Brown 2011] Hutter, F.; Hoos, H.; and
Leyton-Brown, K. 2011. Sequential model-based optimization for
general algorithm configuration. In Proc. of LION’11, 507–523.
[Hutter, Hoos, and Leyton-Brown 2013] Hutter, F.; Hoos, H.; and
Leyton-Brown, K. 2013. Identifying key algorithm parameters
and instance features using forward selection. In Proc. of LION’13.
364–381.
[Hutter, Tompkins, and Hoos 2002] Hutter, F.; Tompkins, D.; and
Hoos, H. 2002. Scaling and probabilistic smoothing: Efficient
dynamic local search for SAT. In Proc.of CP’02, 233–248.
[Jacobs et al. 1991] Jacobs, R.; Jordan, M.; Nowlan, S.; and Hinton,
G. 1991. Adaptive mixtures of local experts. Neural Computation
3(1):79–87.
[Jones et al. 2001] Jones, E.; Oliphant, T.; Peterson, P.; et al. 2001.
SciPy: Open source scientific tools for Python. http://www.
scipy.org/.
[Leyton-Brown, Nudelman, and Shoham 2009] Leyton-Brown, K.;
Nudelman, E.; and Shoham, Y. 2009. Empirical hardness models:
Methodology and a case study on combinatorial auctions. Journal
of ACM 56(4).
[Loreggia et al. 2016] Loreggia, A.; Malitsky, Y.; Samulowitz, H.;
and Saraswat, V. 2016. Deep learning for algorithm portfolios. In
Proc. of AAAI’16, 1280–1286.
[Luby, Sinclair, and Zuckerman 1993] Luby, M.; Sinclair, A.; and
Zuckerman, D. 1993. Optimal speedup of las vegas algorithms. Inf.
Process. Lett. 47(4):173–180.
[Meinshausen 2006] Meinshausen, N. 2006. Quantile regression
forests. JMLR 7:983–999.
[Mendoza et al. 2016] Mendoza, H.; Klein, A.; Feurer, M.; Springenberg, J.; and Hutter, F. 2016. Towards automatically-tuned
neural networks. In ICML 2016 AutoML Workshop.
[Nudelman et al. 2004] Nudelman, E.; Leyton-Brown, K.; Devkar,
A.; Shoham, Y.; and Hoos, H. 2004. Understanding random SAT:
Beyond the clauses-to-variables ratio. In Proc. of CP’04, 438–452.
[Pascanu, Mikolov, and Bengio 2013] Pascanu, R.; Mikolov, T.; and
Bengio, Y. 2013. On the difficulty of training recurrent neural
networks. In Proc. of ICML’13, 1310–1318.
[Pedregosa et al. 2011] Pedregosa, F.; Varoquaux, G.; Gramfort, A.;
Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.;
Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.;

Brucher, M.; Perrot, M.; and Duchesnay, E. 2011. Scikit-learn:
Machine learning in Python. JMLR 12:2825–2830.
[Penberthy and Weld 1994] Penberthy, J., and Weld, D. 1994. Temporal planning with continuous change. In Proc. of AAAI’94, 1010–
1015.
[Roberts and Howe 2007] Roberts, M., and Howe, A. 2007. Learned
models of performance for many planners. In ICAPS 2007 Workshop
AI Planning and Learning.
[Smith-Miles and Lopes 2012] Smith-Miles, K., and Lopes, L. 2012.
Measuring instance difficulty for combinatorial optimization problems. Computers and Operations Research 39(5):875–889.
[Xu et al. 2008] Xu, L.; Hutter, F.; Hoos, H.; and Leyton-Brown, K.
2008. SATzilla: Portfolio-based algorithm selection for SAT. JAIR
32:565–606.
[Xu et al. 2011] Xu, L.; Hutter, F.; Hoos, H.; and Leyton-Brown, K.
2011. Hydra-MIP: Automated algorithm configuration and selection
for mixed integer programming. In Proc. of RCRA workshop at
IJCAI.

