Understanding Time Complexity in Machine Learning: Training vs. Testing Phases

Machine Learning (ML) algorithms are the foundation of modern artificial intelligence applications, ranging from image recognition to predictive modeling. Whether you're building a machine learning model to recommend products or forecast energy consumption, every ML algorithm goes through two critical phases: the training phase and the testing (or inference) phase. The time it takes for an algorithm to complete these phases can vary greatly, and this is where time complexity comes into play. In this blog post, we will break down these two phases and delve into how to interpret time complexity formulas for common ML algorithms using Big "O" notation.

1. The Training Phase vs. the Testing Phase in Machine Learning

In any supervised machine learning workflow, we can identify two main phases: training and testing. These phases are distinct but complementary, each playing a vital role in building and using a predictive model.

• Training Phase: This is where the algorithm learns from the data. During training, the model is fed data (input) along with the corresponding labels (output), and it optimizes its parameters to minimize the error between predicted and actual outputs. This phase can be computationally expensive as it requires the algorithm to process a large amount of data and adjust its internal parameters accordingly. The training complexity refers to how long it takes the algorithm to build this model.

• Testing Phase (Inference): Once the model is trained, it is tested on new, unseen data to evaluate its performance. The goal of the testing phase is to use the trained model to make predictions. The complexity of the testing phase often determines how fast the model can provide predictions in real-time.

Understanding the computational complexity in both phases helps in optimizing the choice of algorithm depending on the problem at hand, the size of the data, and the need for real-time predictions.

2. What is Complexity? Big "O" Notation Explained

Time complexity is a way to describe how the computational resources required for an algorithm scale as the size of the input increases. The most common notation to describe time complexity is Big "O" notation. Big "O" focuses on the upper bound, describing the worst-case scenario for how an algorithm behaves as the input size increases.

• n: Typically represents the size of the dataset, i.e., the number of training examples.
• p: Represents the number of features (or dimensions) in each data point.
• T: The number of trees in ensemble methods like Random Forest or Gradient Boosting.
• l: The number of iterations (often seen in iterative algorithms like K-Means or neural networks).
• k: The number of clusters (for K-Means) or the number of neighbors (for K-Nearest Neighbors).
• m: The number of components (for methods like Principal Component Analysis).

For example, if an algorithm has a time complexity of $O(n^2)$, it means that doubling the size of the input data approximately quadruples the time it will take to run.

3. Complexity of Common Machine Learning Algorithms

Let's now explore the time complexity of several popular machine learning algorithms, both for the training and testing phases, to give you a clearer understanding of how to interpret these complexities.

Linear Regression

• Training Time: $O(np^2 + p^3)$
• Inference Time: $O(p)$

Explanation: During training, Linear Regression solves a system of linear equations, often by inverting a matrix. Matrix inversion contributes to the $O(p^3)$ complexity, while calculating the normal equations requires $O(np^2)$, which depends on the number of data points $n$ and features $p$. Once the model is trained, making predictions (inference) only requires a dot product between the input features and learned weights, which has a complexity of $O(p)$.

Logistic Regression

• Training Time: $O(np^2 + p^3)$
• Inference Time: $O(p)$

Explanation: Logistic Regression uses iterative methods like gradient descent or the Newton-Raphson method to optimize its cost function. The complexity is similar to Linear Regression because each iteration requires $O(np^2)$, and solving the normal equations can take $O(p^3)$. For inference, the complexity remains $O(p)$, as predicting the class probability also involves a dot product.

Naive Bayes

• Training Time: $O(np)$
• Inference Time: $O(p)$

Explanation: Naive Bayes assumes conditional independence among features, making the training process very efficient. Each feature's probability is calculated individually, resulting in a linear complexity of $O(np)$. For inference, it computes the posterior probabilities for each class, which requires iterating over all features, hence the complexity $O(p)$.

Decision Tree

• Training Time: $O(T \cdot n \log n)$ (average), $O(n^2)$ (worst)
• Inference Time: $O(T \cdot \log n)$ (average), $O(n)$ (worst)

Explanation: Building a Decision Tree involves splitting the data recursively, where each split requires sorting the data, which has an average complexity of $O(n \log n)$. For balanced trees, this results in $O(n \log n)$ complexity, but in the worst case (unbalanced trees), the complexity can degrade to $O(n^2)$. During inference, making a prediction involves traversing the tree, which takes $O(\log n)$ for balanced trees but could be as bad as $O(n)$ for unbalanced trees.

Random Forest

• Training Time: $O(T \cdot n \log n)$
• Inference Time: $O(T \cdot \log n)$

Explanation: Random Forest is an ensemble of decision trees, and each tree is built with complexity $O(n \log n)$. Since there are $T$ trees in the forest, the overall complexity is $O(T \cdot n \log n)$. Inference time is also proportional to the number of trees, as predictions need to be aggregated from each tree, giving $O(T \cdot \log n)$.

Gradient Boosted Trees

• Training Time: $O(T \cdot n \log n)$
• Inference Time: $O(T \cdot \log n)$

Explanation: Similar to Random Forest, Gradient Boosted Trees iteratively train $T$ decision trees. However, each tree is trained on the residuals of the previous one. The complexity remains $O(T \cdot n \log n)$, and inference also involves traversing each of the $T$ trees, resulting in $O(T \cdot \log n)$.

Principal Component Analysis (PCA)

• Training Time: $O(np^2 + p^3)$
• Inference Time: $O(pm)$

Explanation: PCA computes the covariance matrix, which has complexity $O(np^2)$, and then performs eigenvalue decomposition, which costs $O(p^3)$. After training, projecting a data point onto the top $m$ principal components requires $O(pm$), making inference relatively efficient.

K-Nearest Neighbors (K-NN)

• Training Time: $O(1)$
• Inference Time: $O(np)$

Explanation: K-NN does not have an explicit training phase; it simply stores the dataset. For inference, K-NN computes the distance between the query point and all $n$ data points, with each distance calculation requiring $O(p)$ operations, leading to a total complexity of $O(np)$.

K-Means

• Training Time: $O(l \cdot k \cdot n \cdot p)$
• Inference Time: $O(k \cdot p)$

Explanation: K-Means is an iterative clustering algorithm where $l$ is the number of iterations, $k$ is the number of clusters, $n$ is the number of data points, and $p$ is the number of features. Each iteration involves calculating distances and updating the cluster centroids, resulting in $O(l \cdot k \cdot n \cdot p)$ complexity. Inference involves assigning new points to the nearest cluster, which has complexity $O(k \cdot p)$.

Dense Neural Networks

• Training Time: $O(l \cdot n \cdot p \cdot h)$
• Inference Time: $O(p \cdot h)$

Explanation: Training a dense neural network involves multiple forward and backward passes through the network, with $h$ representing the number of hidden units. Each pass involves calculating activations and gradients, giving $O(l \cdot n \cdot p \cdot h)$ complexity. During inference, only the forward pass is required, leading to $O(p \cdot h)$ complexity.

 

Reading&watching

Andrew Ng - An Introduction to Machine Learning

GeeksforGeeks Team - Understanding Time Complexity in Algorithms

Dheeraj Singh Tomar - Big O Notation in Machine Learning

Marc Peter Deisenroth, A. Aldo Faisal, and Cheng Soon Ong - Mathematics for Machine Learning

Analytics Vidhya Team - Understanding Random Forest

Scikit-learn Documentation - K-Means Clustering Explained