Title: A RESIZABLE MINI-BATCH GRADIENT DESCENT BASED ON A MULTI-ARMED BANDIT

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.

1. INTRODUCTION:

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:

w t+1 = w t -η t g t , g t = ∇ w f (w t )

where w t , g t , 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 (w t ) ≥ f (w t+1 ) and ultimately the sequence of w t 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.

2. RELATED WORKS:

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.

Figure 1 : An overall framework of considered resizable mini-batch gradient descent algorithm (RMGD). The RMGD samples a batch size from a probability distribution, and parameters are updated by mini-batch gradient using the selected batch size. Then the probability distribution is updated by checking the validation loss.

3. SETUP:

Let B = {b k } K k=1 be the set of possible batch size and π = {π k } K k=1 be the probability distribution of batch size where b k , π k , and K are the k th batch size, the probability of b k to be selected, and number of batch sizes respectively. This paper considers algorithm for multi-armed bandit over B according to Algorithm 1. Let w τ ∈ W be the model parameters at epoch τ , and wt 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 y k ∈ {0, 1} be the cost of choosing the batch size b k . In here, y k = 0 if the validation loss decreases by the selected batch size b k (well-updating) and y k = 1 otherwise (misupdating). The aim of the algorithm is to have low misupdating. For the cost function y k , 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.

4. RESIZABLE MINI-BATCH GRADIENT DESCENT:

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.

4.1. ALGORITHMS:

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. Compute gradient g t = ∇J( wt )

7:

Update wt+1 = wt -η τ g t 8:

end for 9:

Update w τ +1 = wT 10:

Observe validation loss (w τ +1 )

11: if (w τ +1 ) < (w τ ) 12:

Get cost y kτ = 0 for i = 1, 2, . . . , K 17:

if i = k τ 18:

Set temporal probability πi = π i τ e -βy kτ /π i τ 19: 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 -βy kτ /π i τ for i = 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 w0 is set to w τ , and MGD iterates T = m/b kτ1 times using the selected batch size b kτ where m is the total number of training samples:

wt+1 = wt -η τ g t , g t = ∇J( wt ).

After T iterations at epoch τ , the model parameters is updated as w τ +1 = wT . Then, the optimizer obtains validation loss , and outputs cost as follows:

y kτ = 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 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.

4.2. REGRET BOUND:

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

Regret T (S) = E T τ =1 y kτ τ -min i T τ =1 y i τ (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,

EQUATION

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.

5. EXPERIMENTS:

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-CNN-C' Springenberg et al. ( 2014) is used for CIFAR10 and CIFAR100. The details of the dataset and experimental settings are presented in the appendix B. 

5.1. MNIST DATASET:

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 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.

5.2. CIFAR10 AND CIFAR100 DATASET:

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. 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 -βz i τ πi τ +1 = πi τ e -βz i τ .

The Bregman projection with respect to the negative entropy function becomes scaling by the 1norm. 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 βz i τ ≥ 0. Then, f τ (π).

EQUATION

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:

EQUATION

Therefore, the regret of the RMGD is bounded,

EQUATION

In particular, setting β = log(K)/(KT ), the regret is bounded by 2 K log(K)T , which is sublinear with T .

:

x is the least integer that is greater than or equal to x

Figures and Tables:

Selector samples a batch size b kτ ∈ B from the probability distribution π τ at each epoch τ where k τ is selected index. Here b k is associated with probability π k . The selected batch size b kτ is applied to optimizer for MGD at each epoch, and the selector gets cost y kτ from optimizer. Then, the selector Algorithm 1 Resizable Mini-batch Gradient Descent Input: B = {b k } K k=1 : Set of batch sizes π 0 = {1/K, . . . , 1/K} : Prior probability distribution Procedure:1: Initialize model parameters w 0 2: for epoch τ = 0, 1, 2, . . .

b kτ ∈ B from π τ 4: Set temporal parameters w0 = w τ 5: for t = 0, 1, . . . , T -1 where T = m/b kτ 6:

Figure 2: The probability distribution vs epoch using the RMGD. (top) The early stages of the training. (bottom) The later stages of the training. The white dot represents the selected batch size at each epoch. In the early stages of the training, RMGD updates the probabilities to search various batch sizes (exploration), and in the later stages, RMGD increases the probability of successful batch size (exploitation).

Figure 3: The probability distribution and selected batch size. The white dot is selected batch size at epoch. (top) The case that small batch size performs better. (middle) The case that large batch size performs better. (bottom) The case that best performing batch size varies.

Figure 4: The results of test accuracy for the MNIST dataset. The error bar is standard error. (left) The test accuracy of 100 times repeated experiments with AdamOptimizer. (right) The test accuracy of 100 times repeated experiments with AdagradOptimizer. In both cases, most RMGD settings outperform all fixed MGD algorithms.

Figure 5: The results of test accuracy for the CIFAR10 and CIFAR100 dataset. The error bar is standard error. (left) The test accuracy of 25 times repeated experiments on CIFAR10. (right) The test accuracy of 10 times repeated experiments on CIFAR100. In both cases, all RMGD settings outperform all fixed MGD algorithms.

by the Theorem 2.22 inShalev-Shwartz et al. (2012), where π * ∈ S is a fixed vector which minimizes the cumulative selecting loss,

Iterations and real time for training, and test accuracy of MNIST classification with AdamOptimizer. The 'total' is the sum of the average values from MGD 16 to 512, which means the whole grid search is performed.

Table content: <table><tr><td>Algorithms</td><td>Iterations</td><td>Real time (sec)</td><td colspan="2">Test accuracy (%)</td></tr><tr><td/><td/><td/><td>Mean ± SD</td><td>Max</td><td>Min</td></tr><tr><td>MGD (16)</td><td>343,800</td><td colspan="3">1,221.54 ± 36.00 99.327 ± 0.064 99.480 99.140</td></tr><tr><td>MGD (32)</td><td>171,900</td><td>697.82 ± 19.70</td><td colspan="2">99.322 ± 0.060 99.500 99.150</td></tr><tr><td>MGD (64)</td><td>86,000</td><td>379.14 ± 11.32</td><td colspan="2">99.328 ± 0.058 99.460 99.170</td></tr><tr><td>MGD (128)</td><td>43,000</td><td>262.33 ± 2.34</td><td colspan="2">99.314 ± 0.056 99.440 99.170</td></tr><tr><td>MGD (256)</td><td>21,500</td><td>208.13 ± 2.20</td><td colspan="2">99.295 ± 0.059 99.470 99.170</td></tr><tr><td>MGD (512)</td><td>10,800</td><td>180.06 ± 0.37</td><td colspan="2">99.254 ± 0.054 99.430 99.110</td></tr><tr><td>MGD (total)</td><td>677,000</td><td>2,949.02</td><td/></tr><tr><td>RMGD (basic)</td><td>68,309 ± 8,900</td><td>333.73 ± 25.38</td><td colspan="2">99.342 ± 0.064 99.480 99.110</td></tr><tr><td>RMGD (sub)</td><td>85,777 ± 12,112</td><td>400.73 ± 51.91</td><td colspan="2">99.357 ± 0.057 99.510 99.060</td></tr><tr><td colspan="2">RMGD (super) 67,948 ± 6,022</td><td>332.61 ± 22.26</td><td colspan="2">99.345 ± 0.058 99.460 99.110</td></tr><tr><td colspan="2">RMGD (hinge) 69,607 ± 8,887</td><td>337.38 ± 25.29</td><td colspan="2">99.341 ± 0.062 99.480 99.130</td></tr><tr><td>RMGD (ratio)</td><td>95,530 ± 8,281</td><td>449.37 ± 26.71</td><td colspan="2">99.339 ± 0.062 99.470 99.150</td></tr></table>

Iterations and real time for training, and test accuracy of MNIST classification with Ada-gradOptimizer.

Table content: <table><tr><td>Algorithms</td><td>Iterations</td><td>Real time (sec)</td><td colspan="2">Test accuracy (%)</td></tr><tr><td/><td/><td/><td>Mean ± SD</td><td>Max</td><td>Min</td></tr><tr><td>MGD (16)</td><td>343,800</td><td colspan="3">1,160.87 ± 22.34 99.268 ± 0.090 99.430 98.920</td></tr><tr><td>MGD (32)</td><td>171,900</td><td>640.68 ± 15.53</td><td colspan="2">99.270 ± 0.070 99.410 99.050</td></tr><tr><td>MGD (64)</td><td>86,000</td><td>367.40 ± 12.63</td><td colspan="2">99.277 ± 0.077 99.440 99.110</td></tr><tr><td>MGD (128)</td><td>43,000</td><td>262.48 ± 1.37</td><td colspan="2">99.269 ± 0.069 99.410 99.080</td></tr><tr><td>MGD (256)</td><td>21,500</td><td>195.60 ± 2.00</td><td colspan="2">99.240 ± 0.072 99.390 99.030</td></tr><tr><td>MGD (512)</td><td>10,800</td><td>170.31 ± 1.41</td><td colspan="2">99.198 ± 0.085 99.390 98.810</td></tr><tr><td>MGD (total)</td><td>677,000</td><td>2,797.34</td><td/></tr><tr><td colspan="2">RMGD (basic) 68,159 ± 8,447</td><td>323.33 ± 23.57</td><td colspan="2">99.286 ± 0.088 99.490 98.900</td></tr><tr><td>RMGD (sub)</td><td>81,479 ± 9,141</td><td>356.16 ± 28.06</td><td colspan="2">99.272 ± 0.092 99.460 98.960</td></tr><tr><td colspan="2">RMGD (super) 67,638 ± 7,733</td><td>320.38 ± 23.55</td><td colspan="2">99.280 ± 0.074 99.410 99.090</td></tr><tr><td colspan="2">RMGD (hinge) 68,199 ± 8,642</td><td>322.33 ± 24.03</td><td colspan="2">99.282 ± 0.089 99.420 98.900</td></tr><tr><td colspan="2">RMGD (ratio) 93,523 ± 9,871</td><td>452.69 ± 34.71</td><td colspan="2">99.283 ± 0.078 99.480 99.020</td></tr><tr><td colspan="5">results correspond with other studies Breuel (2015); Keskar et al. (2016); Mishkin et al. (2017).</td></tr></table>

Iterations and real time for training, and test accuracy on CIFAR10. 48,692 7,592.43 ± 403.65 88.004 ± 0.167 88.380 87.780 RMGD (sub) 507,186 ± 93,961 7,614.16 ± 514.20 87.992 ± 0.147 88.270 87.730 RMGD (super) 397,685 ± 33,535 7,426.11 ± 228.28 88.027 ± 0.179 88.340 87.760 RMGD (hinge) 459,664 ± 56,086 7,584.01 ± 439.62 88.003 ± 0.167 88.380 87.810 RMGD (ratio) 426,123 ± 15,213 7,561.72 ± 220.56 88.002 ± 0.129 88.330 87.770

Table content: <table><tr><td>Algorithms</td><td>Iterations</td><td>Real time (sec)</td><td colspan="2">Test accuracy (%)</td></tr><tr><td/><td/><td/><td>Mean ± SD</td><td>Max</td><td>Min</td></tr><tr><td>MGD (16)</td><td>1,072,050</td><td colspan="3">10,085.26 ± 216.48 87.778 ± 0.207 88.290 87.480</td></tr><tr><td>MGD (32)</td><td>536,200</td><td colspan="3">7,643.93 ± 459.95 87.851 ± 0.160 88.250 87.630</td></tr><tr><td>MGD (64)</td><td>268,100</td><td>6,160.16 ± 68.54</td><td colspan="2">87.853 ± 0.202 88.330 87.450</td></tr><tr><td>MGD (128)</td><td>134,050</td><td/><td/></tr></table>

Iterations and real time for training, and test accuracy on CIFAR100.

Table content: <table><tr><td>Algorithms</td><td>Iterations</td><td>Real time (sec)</td><td colspan="2">Test accuracy (%)</td></tr><tr><td/><td/><td/><td>Mean ± SD</td><td>Max</td><td>Min</td></tr><tr><td>MGD (16)</td><td>1,072,050</td><td colspan="3">12,097.47 ± 57.47 60.247 ± 0.690 61.940 59.620</td></tr><tr><td>MGD (32)</td><td>536,200</td><td colspan="3">8,058.14 ± 39.87 60.475 ± 0.721 61.750 59.290</td></tr><tr><td>MGD (64)</td><td>268,100</td><td colspan="3">6,400.21 ± 12.78 60.628 ± 0.795 61.950 59.170</td></tr><tr><td>MGD (128)</td><td>134,050</td><td colspan="3">5,598.85 ± 38.18 60.954 ± 0.834 62.120 59.530</td></tr><tr><td>MGD (256)</td><td>67,200</td><td colspan="3">5,245.88 ± 40.67 60.504 ± 0.553 61.560 59.830</td></tr><tr><td>MGD (total)</td><td>2,077,600</td><td>37,400.55</td><td/></tr><tr><td colspan="5">RMGD (basic) 425,416 ± 44,392 7,503.09 ± 281.79 61.203 ± 0.502 62.050 60.310</td></tr><tr><td>RMGD (sub)</td><td colspan="4">532,624 ± 69,195 7,841.88 ± 530.29 61.080 ± 0.720 61.910 59.900</td></tr><tr><td colspan="5">RMGD (super) 397,717 ± 20,091 7,408.00 ± 163.74 61.166 ± 0.560 61.970 60.320</td></tr><tr><td colspan="5">RMGD (hinge) 419,100 ± 53,491 7,476.71 ± 324.29 61.219 ± 0.714 62.060 59.580</td></tr><tr><td colspan="5">RMGD (ratio) 412,532 ± 15,660 7,456.50 ± 100.79 61.340 ± 0.411 61.880 60.550</td></tr></table>

Peer review (iclr2019):
 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. In Section 4.2, they prove a regret bound, but I don’t think that regret is really the correct notion, here (although it’s very close). This is a subtle point, so I’ll set up some notation. Let w(b_1, ..., b_t) be the result at the tth epoch, if the batch sizes b_1, …, b_t were used at the 1st through tth epochs. Let y(w,b) be 0 if training one epoch starting at w with batch size b would improve the validation error, and 1 otherwise. They show (unnumbered inequality on the middle of page 5) that .sum_t y(w(b_1,...,b_{t-1}),b_t) is close to .sum_t y(w(b_1,...,b_{t-1}),b^*), where b_t is the batch size that was chosen at time t, and b^* is the best fixed batch size. The key point here is that the comparator (the second sum) starts each epoch at the result that was found by their adaptive algorithm, *not* what would have been found if a batch size of b^* had been used from the beginning. In other words, their result does *not* show that their algorithm is close to outperforming a fixed choice of batch size (for that to hold, the comparator would need to be .sum_t y(w(b^*,...,b^*),b^*)). What they show is similar, but subtly different. They don’t put too much weight on this theoretical result, and in fact don’t even explicitly claim that the comparator in this result is that for a fixed choice of batch size, so really this is a minor issue, but I think that this is something that should be clarified, since it would be easy for a reader to draw an incorrect conclusion. With that said, their approach is well-motivated, and their experiments seem to show consistent small improvements in performance. I don’t think the performance improvements are totally conclusive, but one of the most appealing properties of their proposal is that it shouldn’t be much more computationally expensive than using a fixed minibatch size. Furthermore, their approach is potentially more robust, since you can presumably be less careful about choosing the set of candidate minibatch sizes, than you would be for choosing only one. So while the experiments don’t show a big improvement, their proposal has other benefits.