Convergence of Stochastic Gradient Descent as a function of training set size

Question

I am going through the following section of the book by (Goodfellow et al., 2016), and I don't understand it quite well.

Stochastic gradient descent has many important uses outside the context of deep learning. It is the main way to train large linear models on very large datasets. For a fixed model size, the cost per SGD update does not depend on the training set size $m$. In practice, we often use a larger model as the training set size increases, but we are not forced to do so. The number of updates required to reach convergence usually increases with training set size. 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. From this point of view, one can argue that the asymptotic cost of training a model with SGD is $O(1)$ as a function of $m$.

Section 5.9, p.150

1. "The number of updates required to reach convergence usually increases with training set size". I can't get away around this one. In the normal gradient descent, it becomes computationally expensive to calculate the gradient at each step as the number of training examples increases. But I don't understand why the number of updates increases with the training size.
2. "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." I don't understand this as well

Can you provide some intuition/ arguments for the above two cases?

Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.

Answer 1

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:

1. performance tradeoffs when you try to do distributed SGD, or
2. 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

Answer 2

1. In SGD you use mini-batches of fixed size, let's call it $d$. So if you have for example: $m=1024$ and $d=8$, you need 128 updates to go thru the whole training set. If you increase the training set size to $m=2048$, you will need 256 updates. This means that the number of updates increased.

   Another thing is, that if there is more data, then you need more time to converge (because model has to learn more). Hopefully you should also converge to a better point.

   So the authors want to say that more time in this case means more updates (as contrary to GD, where the number of updates stays the same, but they are longer).

2. It just says that adding data to train set will not infinitively increase your model performance. In practice it means that if your training set is very big, performance of your model is rather limited by the model itself, not by the size of your training set.

Answer 3

The fact that as $m\to\infty$, the number of iterations $N$ needed for a deterministic optimization algorithm to reach the same loss value increases, is quite intuitive. Remember that Goodfellow et al. argument is made

For a fixed model size[..]

This means that you're increasing $m$, but the number of weights $n_w$ stays the same. It's clear that using a model of fixed complexity, it becomes increasingly harder to fit a larger training set.

The second point, i.e., the fact that instead $N$ for SGD reaches a maximum and then plateaus, can be understood in the following way. As $m$ grows indefinitely but the model stays the same, you'll reach a point where $m$ is sufficienty larger than the model capacity (let’s say, once $m$ is enough larger than the VC dimension of the model). At this point we don’t even need to examine all the training set examples, before the model has reached its minimum test set error, because the model isn’t able to overfit the training set anyway. Showing the model more random examples from the training set (which is what SGD does) will only make the training set error and the test set error oscillate around a minimum value, but neither of them will decrease significantly.

Answer 4

What I think it means is that the number of GD iterations required does not grow linearly with $m$. Imagine you are trying to estimate some $\theta$ parameter, with only one data vector $x$: You start with a guess, then have a better estimation based on $x_1$. next, you have even better estimation, based on $x_1$ and $x_2$. The more observations you have, the closer you get to the target. As you have more and more observations, the weight of each observation is getting smaller and thus the relative impact of each additional observation shrinks. Assuming you have no outliers (wait a sec with this), you either converge to target or get to tiny fluctuations within a number of steps which is almost constant. If you do have outliers then a surge would be observed but afterwards you'll go back to converging towards target (each outlier would require an amount of additional steps to cover for). That's as far as I can go with intuition, based on both the model and my experience with it. However, I can't provide you with sources.

Answer 5

1. A larger training set almost inevitably implies greater variability of examples. Thus, pulling random batches during training will yield, on average, a higher entropy (across batches, not within). And so, the function you try to approximate gets more complex and you need to train longer in order to converge.
2. Imagine, you want to solve a standard classification problem such as recognizing animals from images. Let's say you dataset comprises $10^9$ images and imagine this set of images $1cm$ high stack. The amount of discernibly different images is in the range of $10^{40}$ with the stack being $9.98 \times 10^{25} km$, which extends the diameter of the universe which is around $8.85 \times 10^{23} km$. (I saw this calculation at ICCV 2017; for details see slide no. 3 here). Now, imagine you train on this vast dataset ($m:=10^{40}$). Even if it would be computationally feasible, at some point it would not further help you to classify your animal images correctly. That means, while training you would realize that after having seen only $n<m$ samples your algorithm does not further improve and since $n\ll m$, you can validly argue that asymptotic training cost is in $\mathcal{O}(1)$

Answer 6

I think for this question, you need to understand the definition of convergence. Generally, the convergence defined by the number of steps required to reach a certain threshold (e.g., the norm of gradient). SGD will go through the dataset once, as the dataset size increase, the solution will become more accurate. Once reaching a certain point, more data will not help too much because of the convergence property of SGD. There is also another issue regarding this optimization problem, SGD only cares about error bound of samples, but we actually care about the generalization capability. So two problems are not equivalent.