Answers.Body: <p>I will not tell you what the exact space complexity of training an FFNN with GD and BP is (because that actually depends on the specific implementation of GD and BP and I don't want to dive into the details of some specific implementation now, maybe later!), but I will guide you towards the specific answer, which you should be able to figure out alone (although it may take some time because you need to understand all the details of the BP algorithm), if you understand this answer.</p>
  <p>The <a href="https://en.wikipedia.org/wiki/Space_complexity" rel="nofollow noreferrer">space complexity</a> of an algorithm is just the amount of memory that you need to use during the execution of the algorithm. The space complexity, like the time complexity, is typically expressed as a function of the size of the input (or the number of inputs that you have) and, usually, <a href="https://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow noreferrer">in big-O notation, i.e. in the limiting case</a>. So, <span class="math-container">$n$</span> is not the same thing as <span class="math-container">$\mathcal{O}(n)$</span>, <span class="math-container">$\Omega(n)$</span> or <span class="math-container">$\Theta(n)$</span>. Moreover, you can also express the space/time complexity both in the worst, best, or average case, and this is orthogonal to upper (expressed with <span class="math-container">$\mathcal{O}$</span>), lower (<span class="math-container">$\Omega$</span>), or tight (<span class="math-container">$\Theta$</span>) bounds (check <a href="https://cs.stackexchange.com/a/23082/20691">this</a>).</p>
  <p>If you use gradient descent (GD) and back-propagation (BP) to train an FFNN, at each training iteration (i.e. a GD update), you need to store all the matrices that represent the parameters (or weights) of the FFNN, as well as the gradients and the learning rate (or other hyper-parameters). Let's denote the vector that contains all parameters of the FFNN as <span class="math-container">$\theta \in \mathbb{R}^m$</span>, so it has <span class="math-container">$m$</span> components. The gradient vector has the same dimensionality as <span class="math-container">$\theta$</span>, so we need <strong>at least</strong> to store <span class="math-container">$2m + 1$</span> parameters.</p>
  <p>Depending on how you implement BP, you may need more memory. For example, if you need to store all the intermediate terms of the partial derivatives, that will require more memory. To compute exactly the amount of required memory, you will have to expand the gradient vector into all their components (which may not be a pleasant experience). As I just said, this only contributes to the space complexity if you need to store these intermediate components, so, ultimately, the space complexity of an algorithm depends on the <strong>specific</strong> implementation of the algorithm.</p>
  <p>Moreover, to be precise, we cannot just say that the space complexity is <span class="math-container">$2m + 1$</span> or whatever the amount of memory that you require is (although many careless or ignorant people will just say that), because we are not expressing this complexity as a function of the size of the input in the <strong>limiting case</strong> (which is usually done when expressing the space complexity of an algorithm), the number of layers or the number of units per layer (and you probably want to express the space complexity as a function of these 3 possible variable hyper-parameters).</p>
  <p>If you take a look at <a href="https://ai.stackexchange.com/q/13612/2444">this answer</a>, where I describe how to compute the time complexity of the forward pass of an MLP (or FFNN) <em>as a function of the number of inputs and outputs, the number of layers, and units per layers</em>, then you can express the space complexity for training an FFNN in the same way. Given that you are already familiar with how space and time complexities of an algorithm are calculated (and given that this answer is already quite long), I will not repeat the description here.</p>
  <p>In any case, to answer one of your questions more directly, yes, the space complexity will depend on the number of inputs that you have, because the number of inputs will determine the number of weights in the first layer, which you need to store in memory. This is true in the case of FFNNs (or MLPs) but note that this would not be true in the case of CNNs (i.e. the number of parameters in the convolutional layers does not depend on the size of the input), and that's why CNNs are often said to be more memory efficient.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T17:55:45.500Z
Answers.Text: In the post attached by you, you only did the time complexity analysis of FFNN but I want a complexity analysis like this: https://ai.stackexchange.com/questions/5728/what-is-the-time-complexity-for-training-a-neural-network-using-back-propagation/20281?newreg=92fccd4d6b51442db4e6d1dcc1dcfccf   for space with backprop as I used it for training my model
Answers.UserDisplayName: Ritika Gupta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T17:57:30.023Z
Answers.Text: @RitikaGupta I'm telling you exactly how to do it. I'm not doing it because basically it's already done in my other answer: you just need to think a little bit and understand that and this answers.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T18:06:35.233Z
Answers.Text: I am unable to figure it out. In that post you only talked about the number of multiplications, in the link attached by me ,they are talking about number of units in each layer and in this post you talked about inputs also. I am confused.
Answers.UserDisplayName: Ritika Gupta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T18:10:48.150Z
Answers.Text: @RitikaGupta In principle, you don't have to store the outputs of a unit (or neuron or node, or whatever you want to call it). You just need to store the parameter (during the forward pass). These parameters is what you need to store in memory during the forward pass. During the backward pass, you also need to store the partial derivatives with respect to each parameter. Now, depending on how you implement back-propagation (aka forward pass), you may require more or less memory, but, as I say in this answer, you need at least $2*n + 1$ parameters.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T18:11:44.807Z
Answers.Text: As I also say in this answer, you can express this number of parameters as a function of the input, the number of layers, and the number of units. To do that, you just need to follow the same reasoning as in my other answer (that's why I'm saying that you can just look at that other answer). **However**, what you need to note is that you may also need to store more parameters than $2*n + 1$. This is because, to compute the gradient vector, you may need to compute intermediate components. This the part that is missing from this answer.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T18:11:48.077Z
Answers.Text: The specific answer to this question (i.e. how many intermediate components do you need to store in memory to compute the gradient vector) actually depends on the implementation of BP, that's why I'm avoiding doing it here. As you noticed, this answer is already long, so what you're asking for is a lot of effort, but this answer should guide you towards the right answer. If I have more time later, I may try to complete this answer, but, to be honest, I don't really want to go into the details of some implementation of BP.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T18:20:33.443Z
Answers.Text: I used BP of keras
Answers.UserDisplayName: Ritika Gupta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T18:24:38.943Z
Answers.Text: BTW Thanks a lot for your help and time @nbro. I am highly thankful to you for the valuable insights.
Answers.UserDisplayName: Ritika Gupta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-29T19:20:04.080Z
Answers.Text: @RitikaGupta I may come back later to this answer and try to complete it. I don't know when, though. Meanwhile, I suggest that you focus on the back-propagation of an MLP with 1 hidden layer and keep track of all components that you need to store in memory. Then do the same thing for an MLP with 2 hidden layers and try to see how the memory scales. I think you can find the equations of back-propagation for these simple cases on the web or in some good book.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-28T17:41:55.957Z
Answers.LastActivityDate: 2020-12-29T14:58:40.547Z
Answers.LastEditDate: 2020-12-29T14:58:40.547Z
Answers.UserDisplayName: nbro
Body: <p>Suppose that a simple feedforward neural network (FFNN) contains <span class="math-container">$n$</span> hidden layers, <span class="math-container">$m$</span> training examples, <span class="math-container">$x$</span> features, and <span class="math-container">$n_l$</span> nodes in each layer. What is the space complexity to train this FFNN using back-propagation?</p>
  <p>I know how to find the space complexity of algorithms. I found an answer <a href="https://neuron.eng.wayne.edu/tarek/MITbook/chap2/2_4.html#:%7E:text=In%20a%20neural%20net%20simulation,a%20measure%20of%20Kolmogorov%20complexity" rel="nofollow noreferrer">here</a>, but here it is said that the space complexity depends on the number of units, but I think it must also depend on the input size.</p>
  <p>Can someone help me in finding its worst-case space complexity?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T16:40:28.887Z
Comments.Text: Are you only interested in simple feed-forward neural networks (or MLPs)? I suppose so. If yes, edit your post to specify that and add the appropriate tag. If you were also interested in other more complicated neural networks, such as RNNs, the space complexity could be higher. For example, in the case of RNNs, you also need to store the matrices for the recurrent connections, so those already use more memory.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T16:42:09.300Z
Comments.Text: I want to know the space complexity analysis of normal feed forward NN with 3 hidden layers in particular
Comments.UserDisplayName: Ritika Gupta
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-28T17:07:09.567Z
Comments.Text: In the link it is mentioned that space complexity is measured in terms of units but I want to ask do input size has no role to play in this respect?
Comments.UserDisplayName: Ritika Gupta
Tags: <neural-networks><feedforward-neural-networks><computational-complexity><space-complexity>
Title: What is the space complexity for training a neural network using back-propagation?
UserDisplayName: Ritika Gupta
ThreadText: # What is the space complexity for training a neural network using back-propagation?
  
  (Asked by: username_0 on 2020-12-28)
  
  Suppose that a simple feedforward neural network (FFNN) contains $n$ hidden layers, $m$ training examples, $x$ features, and $n\_l$ nodes in each layer. What is the space complexity to train this FFNN using back-propagation?
  
  I know how to find the space complexity of algorithms. I found an answer [here](https://neuron.eng.wayne.edu/tarek/MITbook/chap2/2_4.html#:%7E:text=In%20a%20neural%20net%20simulation,a%20measure%20of%20Kolmogorov%20complexity), but here it is said that the space complexity depends on the number of units, but I think it must also depend on the input size.
  
  Can someone help me in finding its worst-case space complexity?
  
  **Tags:** neural-networks, feedforward-neural-networks, computational-complexity, space-complexity
  
  > **Comments:**
  > **username_1**: Are you only interested in simple feed-forward neural networks (or MLPs)? I suppose so. If yes, edit your post to specify that and add the appropriate tag. If you were also interested in other more complicated neural networks, such as RNNs, the space complexity could be higher. For example, in the case of RNNs, you also need to store the matrices for the recurrent connections, so those already use more memory.  
  > **username_0**: I want to know the space complexity analysis of normal feed forward NN with 3 hidden layers in particular  
  > **username_0**: In the link it is mentioned that space complexity is measured in terms of units but I want to ask do input size has no role to play in this respect?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-12-28. Score: 1
  
  I will not tell you what the exact space complexity of training an FFNN with GD and BP is (because that actually depends on the specific implementation of GD and BP and I don't want to dive into the details of some specific implementation now, maybe later!), but I will guide you towards the specific answer, which you should be able to figure out alone (although it may take some time because you need to understand all the details of the BP algorithm), if you understand this answer.
  
  The [space complexity](https://en.wikipedia.org/wiki/Space_complexity) of an algorithm is just the amount of memory that you need to use during the execution of the algorithm. The space complexity, like the time complexity, is typically expressed as a function of the size of the input (or the number of inputs that you have) and, usually, [in big-O notation, i.e. in the limiting case](https://en.wikipedia.org/wiki/Big_O_notation). So, $n$ is not the same thing as $\mathcal{O}(n)$, $\Omega(n)$ or $\Theta(n)$. Moreover, you can also express the space/time complexity both in the worst, best, or average case, and this is orthogonal to upper (expressed with $\mathcal{O}$), lower ($\Omega$), or tight ($\Theta$) bounds (check [this](https://cs.stackexchange.com/a/23082/20691)).
  
  If you use gradient descent (GD) and back-propagation (BP) to train an FFNN, at each training iteration (i.e. a GD update), you need to store all the matrices that represent the parameters (or weights) of the FFNN, as well as the gradients and the learning rate (or other hyper-parameters). Let's denote the vector that contains all parameters of the FFNN as $\theta \in \mathbb{R}^m$, so it has $m$ components. The gradient vector has the same dimensionality as $\theta$, so we need **at least** to store $2m + 1$ parameters.
  
  Depending on how you implement BP, you may need more memory. For example, if you need to store all the intermediate terms of the partial derivatives, that will require more memory. To compute exactly the amount of required memory, you will have to expand the gradient vector into all their components (which may not be a pleasant experience). As I just said, this only contributes to the space complexity if you need to store these intermediate components, so, ultimately, the space complexity of an algorithm depends on the **specific** implementation of the algorithm.
  
  Moreover, to be precise, we cannot just say that the space complexity is $2m + 1$ or whatever the amount of memory that you require is (although many careless or ignorant people will just say that), because we are not expressing this complexity as a function of the size of the input in the **limiting case** (which is usually done when expressing the space complexity of an algorithm), the number of layers or the number of units per layer (and you probably want to express the space complexity as a function of these 3 possible variable hyper-parameters).
  
  If you take a look at [this answer](https://ai.stackexchange.com/q/13612/2444), where I describe how to compute the time complexity of the forward pass of an MLP (or FFNN) *as a function of the number of inputs and outputs, the number of layers, and units per layers*, then you can express the space complexity for training an FFNN in the same way. Given that you are already familiar with how space and time complexities of an algorithm are calculated (and given that this answer is already quite long), I will not repeat the description here.
  
  In any case, to answer one of your questions more directly, yes, the space complexity will depend on the number of inputs that you have, because the number of inputs will determine the number of weights in the first layer, which you need to store in memory. This is true in the case of FFNNs (or MLPs) but note that this would not be true in the case of CNNs (i.e. the number of parameters in the convolutional layers does not depend on the size of the input), and that's why CNNs are often said to be more memory efficient.
  
  > **Comments:**
  > **username_0**: In the post attached by you, you only did the time complexity analysis of FFNN but I want a complexity analysis like this: https://ai.stackexchange.com/questions/5728/what-is-the-time-complexity-for-training-a-neural-network-using-back-propagation/20281?newreg=92fccd4d6b51442db4e6d1dcc1dcfccf   for space with backprop as I used it for training my model  
  > **username_1**: @username_0 I'm telling you exactly how to do it. I'm not doing it because basically it's already done in my other answer: you just need to think a little bit and understand that and this answers.  
  > **username_0**: I am unable to figure it out. In that post you only talked about the number of multiplications, in the link attached by me ,they are talking about number of units in each layer and in this post you talked about inputs also. I am confused.  
  > **username_1**: @username_0 In principle, you don't have to store the outputs of a unit (or neuron or node, or whatever you want to call it). You just need to store the parameter (during the forward pass). These parameters is what you need to store in memory during the forward pass. During the backward pass, you also need to store the partial derivatives with respect to each parameter. Now, depending on how you implement back-propagation (aka forward pass), you may require more or less memory, but, as I say in this answer, you need at least $2*n + 1$ parameters.  
  > **username_1**: As I also say in this answer, you can express this number of parameters as a function of the input, the number of layers, and the number of units. To do that, you just need to follow the same reasoning as in my other answer (that's why I'm saying that you can just look at that other answer). **However**, what you need to note is that you may also need to store more parameters than $2*n + 1$. This is because, to compute the gradient vector, you may need to compute intermediate components. This the part that is missing from this answer.  
  > **username_1**: The specific answer to this question (i.e. how many intermediate components do you need to store in memory to compute the gradient vector) actually depends on the implementation of BP, that's why I'm avoiding doing it here. As you noticed, this answer is already long, so what you're asking for is a lot of effort, but this answer should guide you towards the right answer. If I have more time later, I may try to complete this answer, but, to be honest, I don't really want to go into the details of some implementation of BP.  
  > **username_0**: I used BP of keras  
  > **username_0**: BTW Thanks a lot for your help and time @username_1. I am highly thankful to you for the valuable insights.  
  > **username_1**: @username_0 I may come back later to this answer and try to complete it. I don't know when, though. Meanwhile, I suggest that you focus on the back-propagation of an MLP with 1 hidden layer and keep track of all components that you need to store in memory. Then do the same thing for an MLP with 2 hidden layers and try to see how the memory scales. I think you can find the equations of back-propagation for these simple cases on the web or in some good book.  
  
  ---
  
  