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.
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)$:
Algorithm B time complexity $O(n^2)$:
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$.
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.
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.
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$ – Nathan Toubiana Feb 25 at 17:32