Setting:
Fix positive integers $m_1,\dots,m_n$ an activation function $\sigma:\mathbb{R}\rightarrow\mathbb{R}$ be $C^1$ with Lipschitz derivative, and let $NN$ denote the set of all feed-forward neural networks for the form $$ f_{\theta}(x):= A_n\circ \sigma \dots \circ \sigma \circ A_1, $$ where $A_i(x)=M_ix+b_i$ where $M_i$ is an $m_{i+1}\times m_{i}$ matrix and $b_i$ is a vector in $\mathbb{R}^{m_{i+1}}$, and $\theta=(M_1,\dots,M_n,b_1,\dots,b_n) \in \mathbb{R}^L$.
Note: $\sigma$ is applied component-wise.
Let $l:\mathbb{R}^{m_n}\rightarrow [0,\infty)$ be a $C^1$ function with Lipschtiz gradient, let $\{x_i\}_{i=1}^N$ be elements of $\mathbb{R}^{m_1}$, and let $$ L(\theta)\triangleq \frac1{N}\sum_{i=1}^N \ell(f_{\theta}(x_i)) . $$
Question:
Suppose we want to optimize $L(\theta)$ over $\mathbb{R}^L$ using (resp. mini-batch) stochastic gradient descent (SGD). Then I have the following question:
What is the complexity of computing a single gradient update? This is probably a function of the data size, no?
Is the convergence rate of the (resp. mini-batch) SGD a function of $N$ (and/or the batch-size $b$)?
Intuitively one of these two must be a function of the data-size (and the mini-batch size).
I'm looking for non-empirical result and I don't want to assume that $\sigma$ is an affine map (like in the classical MLP).