A RESIZABLE MINI-BATCH GRADIENT DESCENT
Year: 2018

Abstract:
Determining the appropriate batch size for mini-batch gradient descent is always time consuming as it often relies on grid search. This paper considers a resizable mini-batch gradient descent (RMGD) algorithm based on a multi-armed bandit that achieves performance equivalent to that of best fixed batch-size. At each epoch, the RMGD samples a batch size according to a certain probability distribution proportional to a batch being successful in reducing the loss function. Sampling from this probability provides a mechanism for exploring different batch size and exploiting batch sizes with history of success. After obtaining the validation loss at each epoch with the sampled batch size, the probability distribution is updated to incorporate the effectiveness of the sampled batch size. Experimental results show that the RMGD achieves performance better than the best performing single batch size. It is surprising that the RMGD achieves better performance than grid search. Furthermore, it attains this performance in a shorter amount of time than grid search.

heading: 1 INTRODUCTION
text: Gradient descent (GD) is a common optimization algorithm for finding the minimum of the expected loss. It takes iterative steps proportional to the negative gradient of the loss function at each iteration. It is based on the observation that if the multi-variable loss functions f(w) is differentiable at point w, then f(w) decreases fastest in the direction of the negative gradient of f at w, i.e., −∇f(w). The model parameters are updated iteratively in GD as follows:
wt+1 = wt − ηtgt, gt = ∇wf(wt)
where wt, gt, and ηt are the model parameters, gradients of f with respect to w, and learning rate at time t respectively. For small enough ηt, f(wt) ≥ f(wt+1) and ultimately the sequence of wt will move down toward a local minimum. For a convex loss function, GD is guaranteed to converge to a global minimum with an appropriate learning rate.
There are various issues to consider in gradient-based optimization. First, GD can be extremely slow and impractical for large dataset: gradients of all the data have to be evaluated for each iteration. With larger data size, the convergence rate, the computational cost and memory become critical, and special care is required to minimize these factors. Second, for non-convex function which is often encountered in deep learning, GD can get stuck in a local minimum without the hope of escaping. Third, stochastic gradient descent (SGD), which is based on the gradient of a single training sample, has large gradient variance, and it requires a large number of iterations. This ultimately translates to slow convergence. Mini-batch gradient descent (MGD), which is based on the gradient over a small batch of training data, trades off between the robustness of SGD and the stability of GD. There are three advantages for using MGD over GD and SGD: 1) The batching allows both the efficiency of memory usage and implementations; 2) The model update frequency is higher than GD which allows for a more robust convergence avoiding local minimum; 3) MGD requires less iteration per epoch and provides a more stable update than SGD. For these reasons, MGD has been a popular algorithm for machine learning. However, selecting an appropriate batch size is difficult. Various studies suggest that there is a close link between performance and batch size used in MGD Breuel (2015); Keskar et al. (2016); Wilson & Martinez (2003).
There are various guidelines for selecting a batch size but have not been completely practical Bengio (2012). Grid search is a popular method but it comes at the expense of search time. There are a small number of adaptive MGD algorithms to replace grid search Byrd et al. (2012); De et al. (2016); Friedlander & Schmidt (2012). These algorithms increase the batch size gradually according to their own criterion. However, these algorithms are based on convex loss function and hard to be applied to deep learning. For non-convex optimization, it is difficult to determine the optimal batch size for best performance.
This paper considers a resizable mini-batch gradient descent (RMGD) algorithm based on a multi-armed bandit for achieving best performance in grid search by selecting an appropriate batch size at each epoch with a probability defined as a function of its previous success/failure. At each epoch, RMGD samples a batch size from its probability distribution, then uses the selected batch size for mini-batch gradient descent. After obtaining the validation loss at each epoch, the probability distribution is updated to incorporate the effectiveness of the sampled batch size. The benefit of RMGD is that it avoids the need for cumbersome grid search to achieve best performance and that it is simple enough to apply to any optimization algorithm using MGD. The detailed algorithm of RMGD are described in Section 4, and experimental results are presented in Section 5.

heading: 2 RELATED WORKS
text: There are only a few published results on the topic of batch size. It was empirically shown that SGD converged faster than GD on a large speech recognition database Wilson & Martinez (2003). It was determined that the range of learning rate resulting in low test errors was considerably getting smaller as the batch size increased on convolutional neural networks and that small batch size yielded the best test error, while large batch size could not yield comparable low error rate Breuel (2015). It was observed that larger batch size are more liable to converge to a sharp local minimum thus leading to poor generalization Keskar et al. (2016). It was found that the learning rate and the batch size controlled the trade-off between the depth and width of the minima in MGD Jastrzkebski et al. (2017).
A small number of adaptive MGD algorithms have been proposed. Byrd et al. (2012) introduced a methodology for using varying sample size in MGD. A relatively small batch size is chosen at the start, then the algorithm chooses a larger batch size when the optimization step does not produce improvement in the target objective function. They assumed that using a small batch size allowed rapid progress in the early stages, while a larger batch size yielded high accuracy. However, this assumption did not corresponded with later researches that reported the degradation of performance with large batch size Breuel (2015); Keskar et al. (2016); Mishkin et al. (2017). Another similar adaptive algorithm, which increases the batch size gradually as the iteration proceeded, was done by Friedlander & Schmidt (2012). The algorithm uses relatively few samples to approximate the gradient, and gradually increase the number of samples with a constant learning rate. It was observed that increasing the batch size is more effective than decaying the learning rate for reducing the number of iterations Smith et al. (2017). However, these increasing batch size algorithms lack flexibility since it is unidirectional. Balles et al. (2017) proposed a dynamic batch size adaptation algorithm. It estimates the variance of the stochastic gradients and adapts the batch size to decrease the variance. However, this algorithm needs to find the gradient variance and its computation depends on the number of model parameters.
Batch size can also be considered as a hyperparameter, and there have been some proposals based on bandit-based hyperparameter (but not batch size) optimization which maybe applicable for determining the best fixed batch size. Jamieson & Talwalkar (2016) introduced a successive halving algorithm. This algorithm uniformly allocates a budget to a set of hyperparameter configurations, evaluates the performance of all configurations, and throws out the worst half until one configuration remains. Li et al. (2017) introduced a novel bandit-based hyperparameter optimization algorithm referred as HYPERBAND. This algorithm considers the optimization problem as a resource allocation problem. The two algorithms mentioned above are not adaptive, and for searching a small hyperparameter space, the two algorithms will not be very effective. The experimental results in this paper show that adaptive MGD tends to perform better than fixed MGD.

heading: 3 SETUP
text: Let B = {bk}Kk=1 be the set of possible batch size and π = {πk}Kk=1 be the probability distribution of batch size where bk, πk, and K are the kth batch size, the probability of bk to be selected, and number of batch sizes respectively. This paper considers algorithm for multi-armed bandit over B according to Algorithm 1. Letwτ ∈ W be the model parameters at epoch τ , and w̃t be the temporal parameters at sub iteration t. Let J : W → R be the training loss function and let g = ∇J(w) be the gradients of training loss function with respect to the model parameters. ητ is the learning rate at epoch τ . Let ` : W → R be the validation loss function, and yk ∈ {0, 1} be the cost of choosing the batch size bk. In here, yk = 0 if the validation loss decreases by the selected batch size bk (well-updating) and yk = 1 otherwise (misupdating). The aim of the algorithm is to have low misupdating. For the cost function yk, graduated losses such as hinge loss and percentage of nonnegative changes in validation loss can be variations of 0-1 loss. However, there are no differences in regret bound among them in this setting and it is experimentally confirmed that there are little performance gaps among them. Therefore, this paper introduces the 0-1 loss, which is simple and basic.

heading: 4 RESIZABLE MINI-BATCH GRADIENT DESCENT
text: The resizable mini-batch gradient descent (RMGD) sets the batch sizes as multi arms, and at each epoch it samples one of the batch sizes from probability distribution. Then, it suffers a cost of selecting this batch size. Using the cost, probability distribution is updated.

heading: 4.1 ALGORITHMS
text: The overall framework of the RMGD algorithm is shown in Figure 1. The RMGD consists of two components: batch size selector and parameter optimizer. The selector samples a batch size from probability distribution and updates the distribution. The optimizer is usual mini-batch gradient.
Selector samples a batch size bkτ ∈ B from the probability distribution πτ at each epoch τ where kτ is selected index. Here bk is associated with probability πk. The selected batch size bkτ is applied to optimizer for MGD at each epoch, and the selector gets cost ykτ from optimizer. Then, the selector
Algorithm 1 Resizable Mini-batch Gradient Descent Input: B = {bk}Kk=1 : Set of batch sizes π0 = {1/K, . . . , 1/K} : Prior probability distribution
Procedure: 1: Initialize model parameters w0 2: for epoch τ = 0, 1, 2, . . . 3: Select batch size bkτ ∈ B from πτ 4: Set temporal parameters w̃0 = wτ 5: for t = 0, 1, . . . , T − 1 where T = dm/bkτ e 6: Compute gradient gt = ∇J(w̃t) 7: Update w̃t+1 = w̃t − ητgt 8: end for 9: Update wτ+1 = w̃T 10: Observe validation loss `(wτ+1) 11: if `(wτ+1) < `(wτ ) 12: Get cost ykτ = 0 13: else 14: Get cost ykτ = 1 15: end if 16: for i = 1, 2, . . . ,K 17: if i = kτ 18: Set temporal probability π̃i = πiτe −βykτ /πiτ 19: else 20: Set temporal probability π̃i = πiτ 21: end if 22: end for 23: Update ∀i ∈ [K], πiτ+1 = π̃i/ ∑ j π̃ j 24: end for
updates probabilities by randomized weighted majority,
for i = kτ , π̃i = πiτe −βykτ /πiτ
for i 6= kτ , π̃i = πiτ ∀i, πiτ+1 = π̃i/ ∑ j π̃j
where β ∈ (0, 1) is positive hyperparameter. When τ = 0, πτ = {1/K, . . . , 1/K}.
Optimizer updates the model parameters w. For each epoch, temporal parameters w̃0 is set to wτ , and MGD iterates T = dm/bkτ e1 times using the selected batch size bkτ where m is the total number of training samples:
w̃t+1 = w̃t − ητgt, gt = ∇J(w̃t).
After T iterations at epoch τ , the model parameters is updated aswτ+1 = w̃T . Then, the optimizer obtains validation loss `, and outputs cost as follows:
ykτ = { 0 if `(wτ+1) < `(wτ ) 1 otherwise .
The RMGD samples an appropriate batch size from a probability distribution at each epoch. This probability distribution encourages exploration of different batch size and then later exploits batch size with history of success, which means decreasing validation loss. Figure 2 shows an example of training progress of RMGD. The figure represents the probability distribution with respect to epoch. The white dot represents the selected batch size at each epoch. In the early stage of training,
1dxe is the least integer that is greater than or equal to x
commonly, all batch sizes tend to decrease validation loss: π is uniform. Thus, all batch size have equal probability of being sampled (exploration). In the later stages of training, the probability distribution varies based on success and failure. Thus, better performing batch size gets higher probability to be sampled (exploitation). In this case, 256 is the best performing batch size.

heading: 4.2 REGRET BOUND
text: The regret bound of the RMGD follows the regret bound derived in Shalev-Shwartz et al. (2012). The goal of this algorithm is to have low regret for not selecting the best performing batch size such that
RegretT (S) = E [ T∑ τ=1 ykττ ] −min i T∑ τ=1 yiτ (1)
where the expectation is over the algorithm’s randomness of batch size selection and the second term on the right-hand side is the cumulative sum of the cost by the best fixed batch size which minimizes the cumulative sum of the cost. The regret of the RMGD is bounded,
E [ T∑ τ=1 ykττ ] −min i T∑ τ=1 yiτ ≤ logK β + βKT . (2)
In particular, setting β = √ log(K)/(KT ), the regret is bounded by 2 √ K log(K)T , which is sublinear with T . The detailed derivation of regret bound is described in the appendix A.

heading: 5 EXPERIMENTS
text: This section describes various experimental results on MNIST, CIFAR10, and CIFAR100 dataset. In the experiments, simple convolutional neural networks (CNN) is used for MNIST and ‘All-CNNC’ Springenberg et al. (2014) is used for CIFAR10 and CIFAR100. The details of the dataset and experimental settings are presented in the appendix B.

heading: 5.1 MNIST DATASET
text: The validity of the RMGD was assessed by performing image classification on the MNIST dataset using AdamOptimizer and AdagradOptimizer as optimizer. The experiments were repeated 100 times for each algorithm and each optimizer, then the results were analyzed for significance. Figure 3 shows the probability distribution and the selected batch size with respect to epoch during training for the RMGD. The white dot represents the batch size selected at each epoch. The top figure is the case that small batch size (32) performs better. After epoch 50, batch size 32 gets high probability and is selected more than others. It means that batch size 32 has less misupdating in this case. The gradually increasing batch size algorithm may not perform well in this case. The middle figure is the case that large batch size (512) performs better. After epoch 60, batch size 512 gets high probability and selected more than others. The bottom figure shows that the best performing batch size varies with epoch. During epoch from 40 to 55, batch size of 256 performs best, and best performing batch size switches to 128 during epoch from 60 to 70, then better performing batch size backs to 256 after epoch 80. In the results, any batch size can be a successful batch size in the later stages without any particular order. The RMGD is more flexible for such situation than the MGD or directional adaptive MGD such as gradually increasing batch size algorithm.
Figure 4 shows the test accuracy of each algorithm. The error bar is standard error. The number in parenthesis next to MGD represents the batch size used in the MGD. ’Basic’, ’sub’, ’super’, ’hinge’, and ’ratio’ in parenthesis next to RMGD represent RMGD settings ’batch size set equal to grid search, 0-1 loss’, ’subset of basic, 0-1 loss’, ’superset of basic, 0-1 loss’, ’basic set, hinge loss’, and ’basic set, percentage of non-negative changes in validation loss’, respectively. The left figure is the test accuracy with AdamOptimizer. The right figure is the test accuracy with AdagradOptimizer. Among the MGD algorithms, relatively small batch sizes (16 - 64) lead to higher performance than large batch sizes (128 - 512) and batch size 64 achieves the best performance in grid search. These
results correspond with other studies Breuel (2015); Keskar et al. (2016); Mishkin et al. (2017). Most RMGD settings outperform all fixed MGD algorithms in both case. Although the performance of RMGD is not significantly increased compared to the best MGD, the purpose of this algorithm is not to improve performance, but to ensure that the best performance is achieved without performing a grid search on the batch size. Rather, the improved performance of the RMGD is a surprising result. Therefore, the RMGD is said to be valid. There are little performance gap among RMGD settings. The ’sub’ setting outperforms the ’basic’ setting in left figure, but the opposite result is shown in right figure. Therefore, there is no clear tendency of performance change depending on the size of the batch size set.
Table 1 and 2 present iterations and real time for training, mean, maximum, and minimum of test accuracies for each algorithm with AdamOptimizer and AdagradOptimizer respectively. The MGD (total) is the summation of the iterations and real time of whole MGDs for grid search. The RMGD (basic) outperforms best performing MGD and is, also, faster than best performing MGD. Furthermore, it is 8 times faster than grid search in both cases. In the results, the RMGD is effective regardless of the optimizer.

heading: 5.2 CIFAR10 AND CIFAR100 DATASET
text: The CIFAR10 and CIFAR100 dataset were, also, used to assess effectiveness of the RMGD. The experiments were repeated 25 times and 10 times, respectively. In these experiments, all images
are whitened and contrast normalized before being input to the network. Figure 5 shows the test accuracy for each algorithm. The left figure represents the test accuracy on CIFAR10. In contrast to the MNIST results, relatively large batch sizes (128 - 256) lead to higher performance than small batch sizes (16 - 64) and batch size 256 achieves the best performance in grid search. The right figure represents the test accuracy on CIFAR100 and batch size 128 achieves the best performance in grid search. The results on MNIST, CIFAR10 and CIFAR100 indicate that it is difficult to know which batch size is optimal before performing a grid search. Meanwhile, all RMGD settings have again exceeded the best performance of fixed MGD. There are no significant performance gaps among RMGD settings, so there is no need to worry about choosing appropriate batch size set or selecting cost function.
Table 3 and 4 present the detailed results on CIFAR10 and CIFAR100 dataset. The RMGD (basic) is a little slower than single best performing MGD (256 for CIFAR10 and 128 for CIFAR100), however, it was much faster than grid search -about 4.6 times on CIFAR10 and 5.0 times on CIFAR100 faster. Therefore, this results, also, show the effectiveness of the RMGD.
It is difficult to compare the RMGD with other adaptive batch size algorithm, e.g. coupling adaptive batch sizes (CABS) Balles et al. (2017), directly since the underlying goals are different. While the goal of the RMGD is to reduce the validation loss in terms of generalization performance, the CABS determines the batch size to balance between the gradient variance and computation. However, it is obvious that the RMGD is simpler and easier to implement than any other adaptive algorithm cited in this paper, and comparing the test accuracy between the RMGD and the CABS on the CIFAR10 and CIFAR100 using the same experimental settings with ’All-CNN-C’ shows that the performance of the RMGD is higher than that of the CABS (CIFAR10: 87.862 ± 0.142, CIFAR100: 60.782 ± 0.421). And again, the purpose of this algorithm is not to outperform other algorithms, but to guarantee that the best performance is reached without grid search.
CONCLUSION
Selecting batch size affects the model quality and training efficiency, and determining the appropriate batch size is time consuming and requires considerable resources as it often relies on grid search. The focus of this paper is to design a simple robust algorithm that is theoretically sound and applicable in many situations.
This paper considers a resizable mini-batch gradient descent (RMGD) algorithm based on a multiarmed bandit that achieves equivalent performance to that of best fixed batch-size. At each epoch, the RMGD samples a batch size according to certain probability distribution of a batch being successful in reducing the loss function. Sampling from this probability provides a mechanism for exploring different batch size and exploiting batch sizes with history of success. After obtaining the validation loss at each epoch with the sampled batch size, the probability distribution is updated to incorporate the effectiveness of the sampled batch size.
The goal of this algorithm is not to achieve state-of-the-art accuracy but rather to select appropriate batch size which leads low misupdating and performs better. The RMGD essentially assists the learning process to explore the possible domain of the batch size and exploit successful batch size. The benefit of RMGD is that it avoids the need for cumbersome grid search to achieve best performance and that it is simple enough to apply to various field of machine learning including deep learning using MGD. Experimental results show that the RMGD achieves the best grid search performance on various dataset, networks, and optimizers. Furthermore, it, obviously, attains this performance in a shorter amount of time than the grid search. Also, there is no need to worry about which batch size set or cost function to choose when setting RMGD. In conclusion, the RMGD is effective and flexible mini-batch gradient descent algorithm.

heading: A REGRET BOUND
text: In the RMGD algorithm, there are K batch sizes as multi arms with the probability distribution π ∈ S, and at each epoch the algorithm should select one of the batch sizes bkτ . Then it receives a cost of selecting this arm, ykττ ∈ {0, 1} by testing the validation loss `. The vector yτ ∈ {0, 1}K represents the selecting cost for each batch size. The goal of this algorithm is to have low regret for not selecting the best performing batch size.
RegretT (S) = E [ T∑ τ=1 ykττ ] −min i T∑ τ=1 yiτ (3)
where the expectation is over the algorithm’s randomness of batch size selection.
Let S be the probability simplex, the selecting loss functions be fτ (π) = 〈π,yτ 〉2 and R : S → R be a regularization function that is often chosen to be strongly convex with respect to some norm || · ||. The algorithm select a batch size with probability P[bkτ ] = πkττ and therefore fτ (πτ ) is the expected cost of the selected batch size at epoch τ . The gradient of the selecting loss function is yτ . However, only one element ykττ is known at each epoch. To estimate gradient, random vector zτ is defined as follows:
ziτ =
{ yiτ/π i τ if i = kτ
0 otherwise
and expectation of zτ satisfies,
E[zτ |zτ−1, . . . ,z0] = K∑ i=1 P[bkτ ]ziτ = πkττ ykττ πkττ = ykττ .
The most natural learning rule is to set the probability distribution which has minimal cost on all past epochs. It is referred to as Follow-the-Regularized-Leader (FTRL) in online learning:
∀τ, πτ+1 = argmin π∈S
{ β
τ∑ t=1 ft(π) +R(π)
} ,
where β is positive hyperparameter. The FTRL has a problem that it requires solving an optimization problem at each epoch. To solve this problem, Online Mirror Descent (OMD) is applied. The OMD computes the current probability distribution iteratively based on a gradient update rule and the previous probability distribution and lies in the update being carried out in a ’dual’ space, defined by regularizer. This follows from considering ∇R as a mapping from RK onto itself. The OMD relies on Bregman divergence. The Bregman divergence between π and π̃ with respect to the regularizer R is given as: BR(π||π̃) = R(π)−R(π̃)−∇R(π̃) · (π − π̃), (4) and a Bregman projection of π̃ onto simplex S:
argmin π∈S
BR(π||π̃).
Then the probability distribution is updated by the OMD as follows:
∇R(π̃τ+1) = ∇R(π̃τ )− βzτ πτ+1 = argmin
π∈S BR(π||π̃τ+1).
In general, if R is strongly convex, then ∇R becomes a bijective mapping, thus π̃τ+1 can be recovered by the inverse gradient mapping (∇R)−1. Given that R is strongly convex, the OMD and FTRL produce equivalent predictions:
argmin π∈S BR(π||π̃τ+1) = argmin π∈S
{ β
τ∑ t=1 ft(π) +R(π) } 2〈π,y〉 is the inner product between vectors π and y
by the Lemma 1 in Hazan & Kale (2010). It makes sense to use the negative entropic regularization for R in RMGD setting:
R(π) = K∑ i=1 πi log(πi).
Then,∇R(π)i = log(πi) + 1. From the OMD, π̃τ+1 is updated as follows:
∇R(π̃τ+1) = ∇R(π̃τ )− βzτ log(π̃iτ+1) + 1 = log(π̃ i τ ) + 1− βziτ
π̃iτ+1 = π̃ i τe −βziτ .
The Bregman projection with respect to the negative entropy function becomes scaling by the `1- norm. Therefore,
πiτ+1 = π̃iτ+1∑ j π̃ j τ+1 . (5)
The probability distribution πτ is updated by the rule of the normalized exponentiated gradient (normalized-EG) algorithm described in Algorithm 1. Also, the selecting loss function is linear and it is satisfied that ∀τ, i we have βziτ ≥ 0. Then,
T∑ τ=1 〈πτ − π∗, zτ 〉 ≤ log(K) β + β T∑ τ=1 K∑ i=1 πiτ (z i τ ) 2 (6)
by the Theorem 2.22 in Shalev-Shwartz et al. (2012), where π∗ ∈ S is a fixed vector which minimizes the cumulative selecting loss,
π∗ = argmin π∈S T∑ τ=1 fτ (π).
Since fτ is convex and zτ is estimated gradients for all τ ,
E [ T∑ τ=1 (fτ (πτ )− fτ (π∗)) ] ≤ log(K) β + β T∑ τ=1 E [ K∑ i=1 πiτ (z i τ ) 2 ] (7)
by the Theorem 4.1 in Shalev-Shwartz et al. (2012). The last term is bounded as follows:
E [ K∑ i=1 πiτ (z i τ ) 2 ] = K∑ j=1 P[kτ = j] K∑ i=1 πiτ (z i τ ) 2
= K∑ j=1 (πjτ ) 2(yjτ/π j τ ) 2
= K∑ j=1 (yjτ ) 2 ≤ K. (8)
Therefore, the regret of the RMGD is bounded,
E [ T∑ τ=1 ykττ ] −min i T∑ τ=1 yiτ ≤ logK β + βKT . (9)
In particular, setting β = √ log(K)/(KT ), the regret is bounded by 2 √ K log(K)T , which is sublinear with T .

heading: B EXPERIMENTAL SETTINGS
text: DATASET
MNIST is a dataset of handwritten digits that is commonly used for image classification. Each sample is a black and white image and 28× 28 in size. The MNIST is split into three parts: 55,000 samples for training, 5,000 samples for validation, and 10,000 samples for test.
CIFAR10 consists of 60,000 32 × 32 color images in 10 classes (airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck), with 6,000 images per class. The CIFAR10 is split into three parts: 45,000 samples for training, 5,000 samples for validation, and 10,000 samples for test.
CIFAR100 consists of 60,000 32 × 32 color images in 100 classes. The CIFAR100 is split into three parts: 45,000 samples for training, 5,000 samples for validation, and 10,000 samples for test.
SETTINGS
The simple CNN consists of two convolution layers with 5 × 5 filter and 1 × 1 stride, two max pooling layers with 2 × 2 kernel and 2 × 2 stride, single fully-connected layer, and softmax classifier. Description of the ’All-CNN-C’ is provided in Table 5. For MNIST, AdamOptimizer with η = 10−4 and AdagradOptimizer with η = 0.1 are used as optimizer. The basic batch size set B = {16, 32, 64, 128, 256, 512}, subset of basic B− = {16, 64, 256}, and superset of basic B+ = {16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512}. The model is trained for a total of 100 epochs. For CIFAR10 and CIFAR100, MomentumOptimizer with fixed momentum of 0.9 is used as optimizer. The learning rate ηk is scaled up proportionately to the batch size (ηk = 0.05 ∗ bk/256) and decayed by a schedule S = [200, 250, 300] in which ηk is multiplied by a fixed multiplier of 0.1 after 200, 250, and 300 epochs respectively. The model is trained for a total of 350 epochs. Dropout is applied to the input image as well as after each convolution layer with stride 2. The dropout probabilities are 20% for dropping out inputs and 50% otherwise. The model is regularized with weight decay λ = 0.001. The basic batch size set B = {16, 32, 62, 128, 256}, subset of basic B− = {16, 64, 256}, and superset of basic B+ = {16, 24, 32, 48, 64, 96, 128, 192, 256}. For all experiments, rectified linear unit (ReLU) is used as activation function. For RMGD, β is set to √ log(6)/(6 ∗ 100) ≈ 0.055 for MNIST and √ log(5)/(5 ∗ 350) ≈ 0.030 for CIFAR10 and CIFAR100. The basic batch size selecting cost is 0-1 loss, hinge loss is max{0, `τ − `τ−1}, and ratio loss is max{0, (`τ − `τ−1)/`τ−1}.

Review summaries:
The authors consider the problem of determining the minibatch size for SGD by first fixing a set of candidate sizes, and then learning a distribution over those sizes using a MAB algorithm. A minibatch size is first sampled from the distribution, then one training epoch is performed. A validation error is then computed, and if it is lower than that of the last epoch, the cost of the minibatch is taken to be zero (otherwise one), and the distribution is updated. This is Algorithm 1.

The paper applies multi-armed bandits for choosing the size of the minibatch to be used in each training epoch of a standard CNN. The loss of the bandit is binary: zero if the validation loss decreases and 1 otherwise. In the experiments, the Exp3 bandit algorithm is run with Adam and Adagrad on MNIST, CIFAR-10, and CIFAR-100. The results show that the bandit approach allows to obtain a test error better (although not significantly better) than the test error corresponding to the best minibatch size among those considered by the bandit.