Answers.Body: <p>Indeed if the ML model you employed is kept as a blackbox, you cannot estimate its theoretical time complexity for your input at inference time. So you need to have some knowledge about your model's <em>inference mechanism</em> to estimate, and the more exact knowledge you gain the more accurate your estimation will achieve.</p>
  <p>For the example of common MLPs, it just has the forward pass mechanism at inference time which doesn't depend on the size of your input data (your input data is just represented by the input layer which is usually fixed in size) but instead on the modal parameters such as the number of total layers, the number of input neurons to a layer and the number of output neurons from the same layer.</p>
  <p>However, for stacked-transformer models with <span class="math-container">$L$</span> total layers like GPT, though they're also neural networks, due to their inherent <em>self-attention mechanism</em> it's well known that the time complexity of your input sequence with length <span class="math-container">$n$</span> is <span class="math-container">$O(L(n^2d+nd^2))$</span> where <span class="math-container">$d$</span> is the dimension of the embedding space. Similarly for <span class="math-container">$K$</span>-NNs, your input at inference time directly affects the time complexity because its <em>inference mechanism</em> involves computing distances between the input and all the <span class="math-container">$N$</span> training samples which depends on the number of features <span class="math-container">$d$</span> of your input in addition to the model's parameters such as <span class="math-container">$K$</span> and <span class="math-container">$N$</span>.</p>
  <p>Finally in practice you could use tools like TensorFlow or PyTorch's Profiler to measure time complexity empirically even with a blackbox ML model you're agnostic about.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-19T01:25:48.417Z
Answers.LastActivityDate: 2024-12-19T01:25:48.417Z
Answers.UserDisplayName: cinch
Answers.Body: <p>Analyzing the time complexity of the prediction algorithm of an ML model depends on the algorithm and model. For example, in the case of neural networks, prediction starts with a forward pass, which is a series of matrix multiplications.</p>
  <p><a href="https://ai.stackexchange.com/a/13626/2444">Here</a> I explain how you can compute the time complexity of the forward pass of an FFNN, <a href="https://ai.stackexchange.com/a/22929/2444">here</a> the same for a CNN and <a href="https://ai.stackexchange.com/a/33930/2444">here</a> for an LSTM.</p>
  <p>For other neural networks, you will need to perform a similar reasoning.</p>
  <p>In general, neural networks perform matrix multiplications and a single matrix multiplication can be done in <span class="math-container">$O(n^3)$</span>, although there are matrix multiplication algorithms with a better time complexity. See e.g. <a href="https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication" rel="nofollow noreferrer">the Wikipedia article</a>. If you multiply a matrix by a vector, that can be done in <span class="math-container">$O(n^2)$</span>, assuming a square matrix.</p>
  <p>You should keep in mind that, as opposed to traditional algorithms, here the time complexity depends not only on the input size but also on the model architecture.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-18T23:00:37.040Z
Answers.Text: If you're interested in the time complexity of a specific prediction algorithm, please, ask it in a separate question. Here I'm providing an answer to your question in the title. You should ask only 1 question per post.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-18T23:00:30.007Z
Answers.LastActivityDate: 2024-12-18T23:24:30.400Z
Answers.LastEditDate: 2024-12-18T23:24:30.400Z
Answers.UserDisplayName: nbro
Body: <p>I am used to calculating the time complexity of algorithms and data structures to understand how my code will perform in a production environment. However, when using machine learning (ML) and AI-based solutions, it becomes challenging to determine the asymptotic time complexity because the instructions are not explicitly written by me but instead learned from data. These learned models are often treated as a &quot;black box,&quot; making it harder to analyze their computational requirements.</p>
  <p>I want to focus specifically on the <strong>time complexity for prediction (inference)</strong>, not training. For instance:</p>
  <ol>
  <li>How can I determine the prediction time complexity of models such as <strong>k-Nearest Neighbors (k-NN)</strong>?</li>
  <li>How can I evaluate the prediction time complexity for <strong>binary classification models based on deep learning (e.g., a simple feedforward neural network)</strong>?</li>
  </ol>
  <p>Any detailed explanation or references to methodologies for analyzing the time complexity of ML models during prediction would be greatly appreciated.</p>
  
Tags: <machine-learning><deep-learning><deep-neural-networks><prediction><time-complexity>
Title: How to Determine the Time Complexity of Machine Learning Models for Prediction?
UserDisplayName: Dawid
ThreadText: # How to Determine the Time Complexity of Machine Learning Models for Prediction?
  
  (Asked by: username_0 on 2024-12-18)
  
  I am used to calculating the time complexity of algorithms and data structures to understand how my code will perform in a production environment. However, when using machine learning (ML) and AI-based solutions, it becomes challenging to determine the asymptotic time complexity because the instructions are not explicitly written by me but instead learned from data. These learned models are often treated as a "black box," making it harder to analyze their computational requirements.
  
  I want to focus specifically on the **time complexity for prediction (inference)**, not training. For instance:
  
  1. How can I determine the prediction time complexity of models such as **k-Nearest Neighbors (k-NN)**?
  2. How can I evaluate the prediction time complexity for **binary classification models based on deep learning (e.g., a simple feedforward neural network)**?
  
  Any detailed explanation or references to methodologies for analyzing the time complexity of ML models during prediction would be greatly appreciated.
  
  **Tags:** machine-learning, deep-learning, deep-neural-networks, prediction, time-complexity
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-12-19. Score: 1 | Accepted answer
  
  Indeed if the ML model you employed is kept as a blackbox, you cannot estimate its theoretical time complexity for your input at inference time. So you need to have some knowledge about your model's *inference mechanism* to estimate, and the more exact knowledge you gain the more accurate your estimation will achieve.
  
  For the example of common MLPs, it just has the forward pass mechanism at inference time which doesn't depend on the size of your input data (your input data is just represented by the input layer which is usually fixed in size) but instead on the modal parameters such as the number of total layers, the number of input neurons to a layer and the number of output neurons from the same layer.
  
  However, for stacked-transformer models with $L$ total layers like GPT, though they're also neural networks, due to their inherent *self-attention mechanism* it's well known that the time complexity of your input sequence with length $n$ is $O(L(n^2d+nd^2))$ where $d$ is the dimension of the embedding space. Similarly for $K$-NNs, your input at inference time directly affects the time complexity because its *inference mechanism* involves computing distances between the input and all the $N$ training samples which depends on the number of features $d$ of your input in addition to the model's parameters such as $K$ and $N$.
  
  Finally in practice you could use tools like TensorFlow or PyTorch's Profiler to measure time complexity empirically even with a blackbox ML model you're agnostic about.
  
  
  ---
  
  ### Answer by username_2 on 2024-12-18. Score: 1
  
  Analyzing the time complexity of the prediction algorithm of an ML model depends on the algorithm and model. For example, in the case of neural networks, prediction starts with a forward pass, which is a series of matrix multiplications.
  
  [Here](https://ai.stackexchange.com/a/13626/2444) I explain how you can compute the time complexity of the forward pass of an FFNN, [here](https://ai.stackexchange.com/a/22929/2444) the same for a CNN and [here](https://ai.stackexchange.com/a/33930/2444) for an LSTM.
  
  For other neural networks, you will need to perform a similar reasoning.
  
  In general, neural networks perform matrix multiplications and a single matrix multiplication can be done in $O(n^3)$, although there are matrix multiplication algorithms with a better time complexity. See e.g. [the Wikipedia article](https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication). If you multiply a matrix by a vector, that can be done in $O(n^2)$, assuming a square matrix.
  
  You should keep in mind that, as opposed to traditional algorithms, here the time complexity depends not only on the input size but also on the model architecture.
  
  > **Comments:**
  > **username_2**: If you're interested in the time complexity of a specific prediction algorithm, please, ask it in a separate question. Here I'm providing an answer to your question in the title. You should ask only 1 question per post.  
  
  ---
  
  