The theory for the effectiveness of SGD was worked out on single example updates (i.e. minibatch size 1), so using larger minibatches isn't theoretically necessary.
It has two practical advantages:
One, if the computation can be vectorized, you might be able to compute gradients for a small minibatch >1 nearly equally as quickly, leading to significant speed increases in training.
In this case, the optimal minibatch size is a function of the particular hardware and implementation you're working with, so you're probably best off experimenting to find the sweet spot.
Two, computing the gradient on a minibatch size >1 will lead to more accurate gradients and more optimal steps. But this benefit will arrive and level off quickly once the minibatch size is increased beyond 1, so you can focus primarily on the first objective.
In the first part they are talking about large-scale SGD convergence in practice and in the second part theoretical results on the convergence of SGD when the optimisation problem is convex.
"The number of updates required to reach convergence usually increases with training set size".
I found this statement confusing but as @DeltaIV kindly pointed out in the comments I think they are talking about practical considerations for a fixed model as the dataset size $m \rightarrow \infty$. I think there are two relevant phenomena:
- performance tradeoffs when you try to do distributed SGD, or
- performance on a real-world non-convex optimisation problem
Computational tradeoffs for distributed SGD
In a large volume and high rate data scenario, you might want to try to implement a distributed version of SGD (or more likely minibatch SGD). Unfortunately making a distributed, efficient version of SGD is difficult as you need to frequently share the parameter state $w$. In particular, you incur a large overhead cost for synchronising between computers so it incentivises you use larger minibatchs. The following figure from (Li et al., 2014) illustrates this nicely
SGD here is minibatch SGD and the other lines are algorithms they propose.
However it's also known that for convex problems minibatchs incur a computational cost which effectively slows convergence with increased minibatch size. As you increase minibatch size $m'$ towards the dataset size $m$ it becomes slower and slower until you're just doing regular batch gradient descent. This decrease can be kinda drastic if a large mini-batch size is used. Again this is illustrated nicely by (Li et al, 2014):
Here they are plotting the minimum objective value they found on the KDD04 dataset after using $10^7$ datapoints.
Formally, if $f$ is a strongly convex function with global optimum $w^*$, and if $w_t$ is the output of SGD at the $t^{th}$ iteration. Then you can prove that in expectation you have:
$$
\mathbb{E}[f(w_t) - f(w^*)] \leq \mathcal{O}(\frac{1}{\sqrt{t}}).
$$
Note that this doesn't depend on the dataset size (this is relevant to your next question)! However for minibatch SGD with batch size $b$ the convergence to the optimum happens at a rate of $\mathcal{O}(\frac{1}{\sqrt{bt}} + \frac{1}{bt})$. When you have a very large amount of data (Li et al., 2014) make the point that:
Since the total number of examples examined is $bt$ while there is only
a $\sqrt{b}$ times improvement, the convergence speed degrades with
increasing minibatch size.
You have a trade-off between the synchronisation cost for small mini-batches, and the performance penalty for increased minibatch size. If you naively parallelise (minibatch) SGD you pay some penalty and your convergence rate slows as the data size increases.
Nonconvexity of the empirical optimisation problem
This is basically the point that @dopexxx has made. It's pretty well-known that the optimisation problem that you want to solve for deep neural nets in practice is not convex. In particular, it can have the following bad properties:
- local minima and saddle points
- plateau regions
- widely varying curvature
In general the shape you're trying to optimise over is thought to be a manifold and as far as I am aware all you can say about convergence is that you're going converge to (a noise ball around) a stationary point. It seems reasonable that the greater the variety of real world data, the more complicated this manifold will be. Because the real gradient is more complicated as $m$ increase you need more samples to approximate $\nabla f$ with SGD.
"However, as m approaches infinity, the model will eventually converge to its best possible test error before SGD has sampled every example in the training set. Increasing m further will not extend the amount of training time needed to reach the model’s best possible test error."
(Goodfellow et al., 2016) state this a little more precisely in the discussion in section 8.3.1, where they state:
The most important property of SGD and the related minibatch or online gradient-based optimisation is that computation time per update does not grow with the number of training examples. This allows convergence even when the number of training examples becomes very large. For a large enough dataset, SGD may converge to within some fixed tolerance of its final test set error before it has processed the entire training dataset.
(Bottou et al., 2017) offer the following clear explanation:
On an intuitive level, SG employs information more efficiently than a
batch method. To see this, consider a situation in which a training set, call it $S$, consists of ten
copies of a set $S_{sub}$. A minimizer of empirical risk for the larger set S is clearly given by a minimizer
for the smaller set $S_{sub}$, but if one were to apply a batch approach to minimize $R_n$ over $S$, then
each iteration would be ten times more expensive than if one only had one copy of $S_{sub}$. On the
other hand, SG performs the same computations in both scenarios, in the sense that the stochastic
gradient computations involve choosing elements from $S_{sub}$ with the same probabilities.
where $R_n$ is the empirical risk (essentially the training loss). If you let the number of copies get arbitrarily large, then SGD will certainly converge before it's sampled every data point.
I think this agrees with my statistical intuition. You can achieve $|x^{\text{opt}} - x_k| < \epsilon$ at iteration $k$ before you necessarily sample all the points in your dataset, because your tolerance for error $\epsilon$ really determines how much data you need to look at, i.e. how many iterations of SGD you need to complete.
I found the first part of the paper by (Bottou et al., 2017) quite helpful for understanding SGD better.
References
Bottou, Léon, Frank E. Curtis, and Jorge Nocedal. "Optimization methods for large-scale machine learning." arXiv preprint arXiv:1606.04838 (2016).
https://arxiv.org/pdf/1606.04838.pdf
Li, Mu, et al. "Efficient mini-batch training for stochastic optimization." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.
https://www.cs.cmu.edu/~muli/file/minibatch_sgd.pdf
Best Answer
The answer is no. The Q-network's parameters can be updated at once using all examples in a minibatch. Denote the members of the minibatch by $(s_1,a_1,r_1,s'_1),(s_2,a_2,r_2,s'_2),...,(s_M,a_M,r_M,s'_M)$ Then the loss is estimated relative to the current Q-network's parameters:
$$\hat{L}(\theta)=\frac{1}{M}\sum_{i=1}^M(Q(s_i,a_i;\theta)-(r_i+\gamma\max_{a'}{Q(s'_i,a';\theta)}))^2$$
This is an estimation of the true loss, which is an expectation over all $(s,a,r)$. In this way, the updating of the parameters of Q is like in SGD.
Notes: