I'm still training my neural network for gender/age classification, and I'm currently experimenting with batch sizes along with everything else. As I've gathered, too small a batch size will lower accuracy, but too big a batch size and the gradient won't even form.
So, can I say that the recommened batch size is the closest power of two to 1/100th of the training dataset size or something like that?
I would say no, because the ideal batch size is not determined by the size of the dataset but by computational efficiency and learning efficiency.
The most efficient use of data to learn (based on number of elementary calculations) would be to use batch sizes of 1 with an appropriately low learning rate. The information from each sample is very noisy, but used with maximum efficiency.
The purpose of minibatches is to take advantage of the parallelism available in the hardware being used. If you compare the run time for different batch sizes, you will find that very small batch sizes are very slow compared with ones that are a bit bigger, but large batch sizes offer no additional speed (and learn more slowly). So a good choice is to pick a batch that takes significantly under twice the time to run as a batch half the size, but is not much slower per sample than a large batch.
With GPUs the same principles apply, but the ideal batch size will depend on how much memory the model uses. Here too you can empirically determine the time taken per sample for a wide range of batch sizes and pick a size that is a bit smaller than the one with maximum samples per second (this is determined by the ratio of the size of the GPU memory to the size of the model).
See Deep Learning by Goodfellow et al section 8.1.3
Elroch's answer is good practical advise. I thought I would mention a nice theoretical result that could be put into practice with some work.
OpenAI actually published a paper on this late last year, An Empirical Model of Large-Batch Training. They developed a statistic they call the gradient noise scale and show that it predicts the largest useful batch size.
Here's a figure from the paper.
Intuitively, for SGD-like updates, gradients of larger batches better estimate the gradient of the whole training set. However, at some point, you get diminishing returns, and computation is wasted.
Under some assumptions, they showed that the largest useful batch size (before diminishing returns) is given by $$\cal{B}=\frac{\textrm{tr}(\Sigma)}{|\it{G}|^\textrm{2}}$$
where $G$ is the matrix of gradients for all parameters and $\Sigma$ is the covariance matrix of $G$.
As explained the paper,
The noise scale is equal to the sum of the variances of the individual gradient components, divided by the global norm of the gradient
Notice that the formula doesn't depend on the size of the training set. It does, however, depend on the gradient, which varies over training. Also, $G$ and $\Sigma$ are with respect to the whole training set and must be approximated. A method for doing this is given in the paper.
