As other users have mentioned, a formula is certainly out of the question because there are too many variables influencing training/predicting computational time. However, there are some general rules of thumb.
Changing the size of your train/predict dataset is the most direct way to change how long your model takes to run.
- More samples in your train dataset always means your model will take longer to train.
- More classes in your train/predict dataset always means your model will take longer to train and predict.
- More features in your train/predict dataset always means your model will take longer to train and predict.
Models train faster on data that takes up less memory. Don't save data as a 64-bit integer if it can be represented by an 8-bit integer or save integer data as a float, etc.
Machine Learning Model
Different ML models have different computational complexities.
n is the number of samples in the training data,
p is the number of features,
t is the number of trees, and
v is the number of support vectors:
KNNs are the fastest models, requiring no training time and there prediction time is $ O(np) $.
Nearest Centroid and
Naive Bayes train at $ O(np) $ and predict at $ O(p) $, making them the second fastest.
Decision tree models train at $ O(n^2p) $ and predict at $ O(p)$, making them a robust, fast predictor.
Random Forest models train at $ O(n^2pt) $ and predict at $ O(pt) $.
Gradient Boosting Trees train at $ O(npt)$ and predict at $ O(pt) $.
Linear Regression models train at $ O(np^2+p^3) $ and predict at $ O(p) $.
Kernel SVM models train at $ O(n^3+n^2p) $ and predict at $ O(vp) $.
Metaparameters are values you input to your ML algorithm that tell it how to behave (thereby influencing the training/predicting time of your algorithm). Not all models have the same metaparameters.
- Learning Rate (eta): As your learning rate increases, the computational time of your model decreases.
- Number of Features: As the number of features in your model increases, the computational time of your model also increases. (In XGB, this can be number of trees, max_depth; in NNs, this can be number of layers; in KNNs, the value of k; etc.)
- Number of Rounds/Epochs: This rule is strict: if you increase the number of rounds or epochs for a machine learning model, it will take longer to train (but the prediction time is the same).
- Objective: Some ML models are adaptable for different objectives (ie XGBoost has reg:logistic, bin:logistic, count:poisson, etc). Different objectives have different train and prediction times (usually regression is longer than binary is longer than count).
- Early Stopping: Some ML implementations allow you to stop training your model early (automatically) if your model performs well enough on a validation dataset. Adding this early-stopping functionality will never hurt run time.
- Others: Every ML model has different metaparameters which can influence training time that must be attended to.
Changing the hardware your model runs on is an expensive though simple way to make your model run faster. There are three main processing units: CPUs, GPUs, and TPUs:
- As a 99% accurate rule of the thumb: TPU > GPU > CPU
- Tensor Processing Units (TPUs) are proprietary property of Google that can be accessed through Google Cloud and are constantly being improved. They run blazingly fast for neural networks. They are the chosen processing unit of DeepMind.
- TPUs have higher input/output operations per Joule than any existing GPU.
- GPUs are faster than CPUs.
- If you increase the number of processing units your model runs on, your model will train and predict faster.
- Most image recognition algorithms run especially fast on GPUs.
- Some GANs for image generation only run on GPUs (thanks Nvidia...)
ML models can be run on a variety of frameworks, all of which run at different speeds. The most popular are Keras, TensorFlow, Caffe, Apache, AWS, Theano, Microsoft CNTK, PyTorch, and scikit-learn. Each framework is different from the next and was created to suit different needs. In my experience, TensorFlow, Keras and Theano run neural networks very fast, AWS is generally robust, and scikit-learn is best for tabular data. Some frameworks allow you to pay to get faster results.
I've worked with Python, R, Java, Julia, and Scala (briefly) for ML. Python is, in my experience, the fastest. The rest are mostly equal.