How can one estimate compute requirements for Machine Learning algorithms? Has anyone developed formulas or rules of thumb for estimating CPU, memory and time requirements for running various Machine Learning algorithms (or families of algorithms), with respect to training and prediction–classification?
I realize algorithm implementations vary and a variety of parameters can be tuned, thus affecting the requirements, but I'm interested in ballpark estimates.
I'm aiming for a generalized view of the problem, e.g. constructing functions with parameters for size of the input-data, and so on.
 A: There are too many variables to get a generic formula. Variables include:


*

*ML method - from linear regression, through K means, to an NN

*data - number of features, number of categories, etc

*ML model - i.e for an NN - number of hidden layers & number of nodes per layer

*metaparameters - learning rate

*implementation/framework - Caffe, TensorFlow, Scikit Learn, etc


Inception 1 used "few high-end GPUs to train in a week" here, while Inception3 (if I understand correctly) uses 50 GPUs. Although training time is not given in this paper, I'd imagine it's at least a day or two.
A: 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.
Data Size
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.
Where 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 generally fastest models, requiring no training time. However, they require O(n^2) calculations, which are generally fairly fast. Their prediction time is $ O(np) $.

*Nearest Centroid and Naive Bayes train at $ O(np) $ and predict at $ O(p) $, making them about equal in speed to KNNs.

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

Source.
Metaparameters
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.

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

Framework
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.
Language
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.
