How to estimate training time prior to training? (Machine Learning & Neural Networks)

Question

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.

Answer 1

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).

Answer 2

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.

Answer 3

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.