1
$\begingroup$

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, 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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – nbro Dec 28 '20 at 16:40
  • $\begingroup$ I want to know the space complexity analysis of normal feed forward NN with 3 hidden layers in particular $\endgroup$ – Ritika Gupta Dec 28 '20 at 16:42
  • 1
    $\begingroup$ Wow! ai.stackexchange.com/questions/5728/… did you just copy paste my question and replace 'time' with 'space'? I don't know whether you did this for upvotes nor do I care, but plagiarism is viewed very seriously by academics. Try to change atleast few things form next time onwards. Also your link has no relation to space complexity. $\endgroup$ – user9947 Dec 28 '20 at 16:59
  • $\begingroup$ 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? $\endgroup$ – Ritika Gupta Dec 28 '20 at 17:07
0
$\begingroup$

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

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, 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.

$\endgroup$
9
  • $\begingroup$ In the post attached by you, you only did the time complexity analysis of FFNN but I want a complexity analysis like this: ai.stackexchange.com/questions/5728/… for space with backprop as I used it for training my model $\endgroup$ – Ritika Gupta Dec 28 '20 at 17:55
  • $\begingroup$ @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. $\endgroup$ – nbro Dec 28 '20 at 17:57
  • $\begingroup$ 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. $\endgroup$ – Ritika Gupta Dec 28 '20 at 18:06
  • $\begingroup$ @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. $\endgroup$ – nbro Dec 28 '20 at 18:10
  • $\begingroup$ 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. $\endgroup$ – nbro Dec 28 '20 at 18:11

Not the answer you're looking for? Browse other questions tagged or ask your own question.