14
$\begingroup$

I'd like to know ahead of time if my training will take 8 hours, 8 days or 8 weeks. (The 8 was an arbitrary number I chose obviously).

Is there a reliable way to estimate the time it will take? Can I extrapolate the time it takes to train 200,000 as roughly double the time it takes to train 100,000?

It would be helpful to be able to estimate whether it will take a couple hours or a couple days or even weeks because then I can tweak the parameters ahead of time.

$\endgroup$
2
  • 2
    $\begingroup$ We're actually working on a package that gives runtime estimates of scikit-learn fits. Feel free to take a look! github.com/nathan-toubiana/scitime $\endgroup$ Feb 25 '19 at 17:32
  • 1
    $\begingroup$ The main function in this package is called “time”. Given a matrix vector X, the estimated vector Y along with the Scikit Learn model of your choice, time will output both the estimated time and its confidence interval. Let’s say you wanted to train a kmeans clustering for example, given an input matrix X. Here’s how you would compute the runtime estimate: from sklearn.clusters import KMeans from scitime import Estimator kmeans = KMeans() estimator = Estimator(verbose=3) # Run the estimation estimation, lower_bound, upper_bound = estimator.time(kmeans, X) Feel free to take a look! https $\endgroup$ Feb 25 '19 at 17:32
8
$\begingroup$

This question does not really depend on what type of an algorithm you run, it deals with computational complexity of algorithms and as such, it would be better suited for StackOverflow. The computer science guys live for these questions and they are very good at them...

In either case, the complexity of an algorithm is reported using the big-O notation. Usually, if you look at the wikipedia description of the algo, you can find the information if the bound is known. Alternatively, it is usually reported by the authors of the algorithm, when they publish it.

For example for SVM, the complexity bound is between $\mathit{O}(dn^2)$ and $\mathit{O}(dn^3)$, where n is the number of your data points and d is the number of your features, or dimensionality of the data. (see libSVM implementation in Python Scikit)

The scenario you describe above would occur if an algorithm has $O(n)$ time complexity. (Complexity of algorithms is measured separately for both time and storage). It means that the run-time scales with the number of examples $\textit{n}$.

Example (starting with $\textit{n}$ inputs for your algorithm):

Algorithm A time complexity $O(n)$:

  • old input size $\textit{n}$
  • old run time $\textit{t}$
  • new input size $\textit{3n}$,
  • new run time will be $\textit{3t}$

Algorithm B time complexity $O(n^2)$:

  • old input size $\textit{n}$
  • old run time $\textit{t}$
  • new input size $\textit{3n}$,
  • new run time will be $\mathit{9t}$

You can apply the same rule for $\mathit{O}(n^3)$, $\mathit{O}(n\log(n))$, or $\mathit{O}(n!)$. Using these rules, you can make a rough (worst-case) estimation of your run-time.

Now, things are a bit more tricky than that, as the $\mathit{O}$ is an upper bound, but not necessarily a tight upper bound (see this StackOverflow thread). That means that the $\mathit{O}$ will tell you the worst case run-time, which, depending on your application might prove useless to you, as it will be too large for any sensible planning and you will notice that your average run-times are in fact much lower.

In that case you might want to look whether there is a ${\Theta}$ for your algorithm (see Bachman-Landau notation), which is the asymptotically tight upper bound. For many algorithms, the best, worst and average time complexity is reported. For many others, we have only a very loose upper bound. Many machine learning algorithms involve a costly operation such as matrix inversion, or the SVD at some point, which will effectively determine their complexity.

The other issue is that complexity ignores constant factors, so complexity $\mathit{O}(kn)$ is in fact $\mathit{O}(n)$ as long as $\mathit{k}$ doesn't depend on $\mathit{n}$. But obviously, in practice it can make a difference whether $k=2$ or $k=1e6$.

EDIT 1: Fixed a mistake in runtime based on comment from @H_R

EDIT 2: Re-reading this reply after some years of working with neural networks, it seems quite educational, but unfortunately, utterly useless given the question.

Yes, we can quantify the complexity of an algorithm. In the case of a neural networks it is the number of operations required for a forward and backward pass. However, the question asks about the total training time and not how much longer a forward pass will take if we increase the input.

The training time depends on how long it takes to approximate the relationship between your inputs and outputs sufficiently, i.e. the number of gradient descent iterations you need to make to achieve a sufficiently small loss. This depends completely on how complex is the function you are trying to approximate and how useful and noisy is the sample data you have.

The long and short of it is:

a. I don't believe it is possible to tell in advance how long it will take to train a neural network, particularly a deep neural network (though I'm sure there is existing research trying to do this).

b. It is not even possible to extrapolate reliably the training duration after some training steps.

c. It is usually not possible to use a reduced set of inputs to train the network and extrapolate from this reduced training time to the full dataset as the network will typically fail to perform well when trained with few data.

This is why people either manually oversee their training loss when training neural networks (tensorflow-board), or use different heuristics to detect when the loss minimization starts to plateau out (early stopping).

$\endgroup$
3
  • $\begingroup$ Hey thank you! I already knew O(n) notation but never knew the complexity of matrix multiplication / inversion. That link helped so much! $\endgroup$
    – Chowza
    Jan 12 '14 at 15:58
  • $\begingroup$ Is that really how algorithm B works? For example, suppose the time it takes to run as a function of the number of inputs is $Cn^2$ for some constant $C$. Then say the time it takes to run for a specific $n$ is $t$, i.e., $t=Cn^2$. Then if we triple the input, we have $C(3n)^2 = C9n^2 = 9t$, rather than $9t^2$. In other words, tripling the input scales the time by 9, not by $9t$. $\endgroup$
    – H_R
    Mar 13 '20 at 22:48
  • $\begingroup$ Agree. Fixed it, thanks! I have some more fundamental issues with my original answer though - added a clarification at the bottom. $\endgroup$ Mar 15 '20 at 10:50
1
$\begingroup$

It depends on the complexity of the algorithm. If it is a linear algorithm, i.e. $O(n)$, then it is straight forward: If $n$ samples needed $t$ time for training, then $2n$ sample will need $2t$ time. If complexity is higher e.g. square $O(n^2)$ then you need to take the square of the time: for double size of samples you will need four times the time it took for n samples. So find out the complexity of your algorithm (google it), run on a small sample to get an estimate, and finally do your calculation to estimate how much time you need. Depending on the algorithm except size of samples, number of dimensions may also be important.

$\endgroup$
1
$\begingroup$

Some thoughts additional to @iliasfl's point:

  • If I think it's going to take long, I do some test runs, which basically allows me to check like @iliasfl suggests. In addition, I also look at memory, because for my data that often limits the parallelization I can ask for.

  • I use resampling validation for my models, I typically calculate in the order of magnitude $10^3$ surrogate models during this. That leaves me with a calculation that is embarassingly paralles and linear in both runtime and memory at the outermost level. The other way round: this means that a single model needs to have a calculation time that is well in the range of what one can try out.

  • If I'd have no idea how long calculations will take (on a scale covering 2 orders of magnitude), I'd start asking myself whether I know enough about the method to sucessfully apply it. Of course there are exceptions to this, e.g. during my Diplom (= Master's) thesis, the method I was to use was fixed.

  • The other question is: how much do weeks 2 - 8 of calculation time add to the quality of model and performance evaluation?
    If we are talking about that order of magnitude, I'd really do some preliminary calculations, e.g. of the learning curve. I'd also make doubly sure that all parameters are as they should be before starting the calculation. And I may give a second thought on whether I cannot use a faster method.

  • (Depending on your skills, tasks, and the algorithm you use:) If you find that the calculation is much slower than you expected, you may want to follow the saying that a better algorithm can speed up things by orders of magnitude or even reduce the complexity, while paralelization will only help linearly. Sometimes even just a better implementaion of the same algorithm can yield one or two orders of magnitude.

  • I often start the resampling calculation, and fetch preliminary results after a few iterations are through. That allows me to go on working (e.g. setting up the code that summarizes the results, draws the figures etc.), while the final results are refined. That way, it doesn't bother me that much if the whole resampling takes a week.


tweak parameters ahead of time

Just make sure then that your validation is independent of the parameter tweaking.

$\endgroup$
2
  • $\begingroup$ Excellent answer. Can you expand on doing preliminary calculations on the learning curve? Are you just running the ML on a much smaller batch and plotting the CV/training errors to determine if you have bias / variance? Or is there something else I can do? $\endgroup$
    – Chowza
    Jan 12 '14 at 16:12
  • $\begingroup$ @Chowza: that is basically the idea - if you anyways run on a (random) subset to get runtime and memory measurements, you can also look how the results look. Of course extrapolating is very uncertain, but you can hopefully get a rough idea. $\endgroup$ Jan 13 '14 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.