Mini-batch gradient descent and its variants are commonly used in deep learning. The principle of mini-batch gradient descent is to use noisy gradient calculated on a batch to estimate the real gradient, thus balancing the computation cost per iteration and the uncertainty of noisy gradient. However, its batch size is a fixed hyper parameter requiring manual setting before training the neural network. Yin et al. (2017) proposed a batch adaptive stochastic gradient descent (BA-SGD) that can dynamically choose a proper batch size as learning proceeds. We extend the BA-SGD to momentum algorithm, and evaluate both the BA-SGD and the batch adaptive momentum (BA-Momentum) on two deep learning tasks from natural language processing to image classification. Experiments confirm that batch adaptive methods can achieve a lower loss compared with mini-batch methods and methods that manually increase the batch size, after scanning the same epochs of data. Furthermore, our BA-Momentum is more robust against larger step sizes, in that it can dynamically enlarge the batch size to reduce the larger uncertainty brought by larger step sizes. We also identified an interesting phenomenon, batch size boom. The code implementing the batch adaptive framework is now open source, applicable to any gradient-based optimization problems.
The paper proposes a generalization of an algorithm by Yin et al. (2017), which performs SGD with adaptive batch sizes. The present paper generalizes the algorithm to SGD with momentum. Since the original algorithm was already formulated with a general utility function, the proposed algorithm is similar in structure but replaces the utility function so that it takes momentum into account. Experiments on an image classification task show improvements in the training loss. However, no test accuracies are reported and the learning curves have suspicious artifacts, see below. Experiments on a relation extraction task show little improvement over SGD with momentum and constant batch size.
COMMENTS:
The paper discusses a relevant issue. While adaptive learning algorithms are popular in deep learning, most algorithms adapt the learning rate or the momentum coefficient, but not the batch size. It appears to me that the main idea and the overall structure of the proposed algorithm is the same as in the one published by Yin et al. (2017), and that only few changes were necessary to include momentum. Given the incremental process, I find the presentation unnecessarily involved, and experiments not convincing enough.
Concerning the presentation, the paper dedicates two full pages on a review of the algorithm by Yin et al. (2017). The first page of this review states that, for large enough batch sizes, the change of the objective function in SGD is normal distributed with a variance that is inversely proportional the batch size. It seems to me that this is a direct consequence of the central limit theorem. The derivation, however, is quite technical and introduces some quantities that are never used (e.g., $\vec{\xi}_j$ is never used individually, only the combined term $\epsilon_t$ defined below Eq. 12 is). The second page of the review seems to discuss the main part of the algorithm, but I could not follow it. First, a "state" $s_t$ (also written as $S$) is introduced, which, according to the text, is "the objective value", which was earlier denoted by $F$. Nevertheless, the change of $s_t$, Eq. 5, appears to obey a different probability distribution than the change of $F$. The paper provides a verbal explanation for this discrepancy, saying that it is possible that $S$ is first reduced to the minimum $S^*$ of the objective and then increased again. However, in my understanding, the minimum of the objective is only realized at a singular point in parameter space. Crossing this point in an update step should have zero probability as long as the model has more than one parameter. The explanation also does not make it clear why the argument should apply to $S$ (or $s$) but not to $F$.
Page 5 provides pseudocode for the proposed algorithm. However, I couldn't find an explanation of the code. The code suggests that, for each update step, one gradually increases the batch size until it becomes larger or equal than a running estimate of the optimal batch size. While this may be a plausible strategy in practice, it seems to have a bias that is not addressed in the paper: the algorithm recalculates a noisy estimate of the optimal batch size after each increase of the batch size, and it terminates as soon as the noisy estimate happens to be small enough, resulting in a bias towards a smaller than optimal batch size. A probably more important issue is that the algorithm is sequential and hard to parallelize, where parallelization is usually the main motivation to use larger batch sizes. As the gradient noise scales inversely proportional to the batch size, I don't see why increasing the batch size should be preferred over decreasing the learning rate unless optimizations with a larger batch size can be parallelized. The experiments don't compare the two alternatives.
Concerning the experiments, it seems peculiar that the learning curves in Figure 1 remain at a constant value for a long time at the beginning of the optimization before they begin to drop. Do the authors understand this behavior? It could indicate that the magnitude of the random initialization was chosen too small. I.e., the parameters might have been initialized too close to zero, where the loss is stationary due to symmetries. Also, absolute values of the training loss can be deceptive since there is often no natural scale. A better indicator of convergence would be the test accuracy. The identification of the "batch size boom" is interesting.