Neural networks, general inquiry - how mini-batching fits into the big picture?

Question

I am graduate student in math, it is my first look at the Deep learning. One of the things that strike me when looking at this material is what seems to be a confusion between implementation details and the big picture or the big principles. This confusion starts right away with a simple feed-forward network "architecture".

Specifically, I now struggle to understand "the proper" context of "mini-batching". There are many online sources on neural networks, but so far I was not able to find, what to me seems, a satisfactory presentation of the material.

Here is the list of questions that I believe will help me to see the mini-batching in it's "natural context".

I am afraid that the questions might be too vague. But I have no other access to an expert in the field, am looking for comments that can point me to my incorrect understanding of the big picture, or incorrect break up of neural network to its "modules" and how mini-batching fits in those "modules".

Edited later: Additionally, I believe that someone who has coded or familiar with neural network framework probably has a conceptual view of what are the main moving parts and what is the best way to describe their proper mutual relationships.

---

1. How is mini-batching represented by a computational graph? By which I mean that given the "original" computational graph what changes should I make to this graph so that it represents the new computational graph associated with the mini batching?

Here is what I try to picture. Suppose we have a general framework of "computation graph". A framework that supports evaluation of gradients for any function represented as a graph (which is used to encode the neural network and then evaluate gradient for the training phase.) Given such a graph e.g

which reads:

I want to do mini-batching on x. Thinking of x as the training example, and of the value of s (output of the graph) as the loss associated with the training example. w is a parameter that I want to learn by running an optimization algorithm of my choice. So to keep things simple, I want my batch to be of size 2. Is this "new" graph below defines the mini-batching?

Here the two training examples are represented by x1 and x2 and I have an additional node in the graph that adds all losses s1 and s2 together (and perhaps normalized i.e. divided by the batch size).

2. If the above graph is indeed the mini-batching, what I do not understand is when exactly the efficiency people associate with the mini-batching can be exploited?.

Specifically, is it true that the biggest contribution is when we have an appropriate hardware that can parallelly process each of the sub-graphs (which on the last graph would be the blue and the black sub-graphs), if we do not have such a hardware is there any computational benefit to mini-batching?

3. Why people "couple" mini-batching with stochastic gradient descent averaging or (any other optimization algorithms averaging)?

Specifically, given any computational graph, why should optimization algorithm care how the graph was constructed? It seems to me that the way the loss function of the mini-batching is defined (as sum of losses for each sub-graph) gives absolute decoupling between mini-batching and optimization algorithm. If there is benefit for "averaging" over iterations of the optimization algorithms why should this averaging be necessarily coupled with the mini-batch size?

4. Somewhat related to the previous question why people "couple" mini-batching with gradient evaluation?

Specifically, If I have a general environment that can evaluate gradients (Jacobians), why does the environment's implementation "cares" which graph it is being fed? I can use general environment and feed it with "the new graph" and ask the environment to find the gradient with respect to w, and feed it to my optimization step.

5. Why is there so much emphasis on the indexing used in the implementation of mini-batching?.

Specifically, I encounter relatively long explanations on how one can "introduce" additional index to parameters in a feed-forward network, and use it to implement mini-batching. I again do not understand why this coupling is necessary, wouldn't any reasonable way to pass from an original computational graph (the black graph) to a new graph (combined blue+black graph) do the job?

Any comments references to literature are welcome! Thanks

Answer 1

First, some notation / recap.

In most supervised machine learning models, we want to minimize $\DeclareMathOperator{\E}{\mathbb E}$ $$ L(f) = \E_{(x, y) \sim P}\left[ \ell(f(x), y) + \lambda J(f) \right] ,$$ where $\ell : \mathcal Y \times \mathcal Y \to \mathbb R$ is a loss function, e.g. $\ell(y, y') = \tfrac12 (y - y')^2$, $J$ is some kind of regularization function that penalizes complexity of the model, and $\lambda$ is a weight trading off between the two.

Since we don't have access to the data distribution $P$, we instead use samples: $$ \hat L(f) = \frac{1}{n} \sum_{i=1}^n \ell(f(x_i), y_i) + \lambda J(f) .$$ Typically, we use an optimizer based on gradient information: $$ \nabla \hat L(f) = \frac1n \sum_{i=1}^n \nabla \ell(f(x_i), y_i) + \lambda \nabla J(f) .$$

"Minibatching" can be used to refer to two different things:

1. Evaluating $f(x_i)$ and/or $\nabla \ell(f(x_i), y_i)$ for several different $(x_i, y_i)$ pairs at the same time (with the same $f$).
2. Estimating $\hat L$ and $\nabla \hat L$ based on averages over subsamples of the data.

To answer your specific questions:

1. Yes, I think this is right.
2. Yes, it is the case that the biggest advantage in the neural network context is that minibatches can be evaluated on a GPU in almost the same time as a single-point batch would have been. Even on "traditional" CPUs, though, SIMD processing means that some (smaller) level of minibatching is potentially helpful. Note that the size of a minibatch also affects the relative number of function and gradient evaluations, and if those have dramatically different computational costs then the tradeoff can change.

3. You are correct that the gradient averaging does not have to be the same size as the computational averaging (though of course it can't be smaller). If you can only fit your model into GPU memory for 5 inputs at a time, you might decide to e.g. use optimization minibatches of size 50 but compute that in 10 separate passes. People generally don't do this for two reasons: one is that it's much simpler code-wise to do everything at the same time. The other is that, since you'll need to recompute the forward step with your new batch anyway, it takes almost exactly the same amount of time to do an optimization step with 5 inputs followed by another optimization step with 5 inputs as it does to do a single optimization step with 10 inputs computed over two passes, and the former usually gets you farther along in the optimization.

4. I'm not sure I understand this question, but typically we need to compute the gradients for specific inputs at a time; TensorFlow or Theano will do all it can in combining gradients at model-building time, but it just gives you some function that needs data to evaluate the actual gradient at that point. We need the average gradient on a batch of data, so we might as well compute it all at once.

5. I don't know what you're talking about here. An example of an explanation that doesn't make sense to you might help here.