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