We propose sequenced-replacement sampling (SRS) for training deep neural networks. The basic idea is to assign a fixed sequence index to each sample in the dataset. Once a mini-batch is randomly drawn in each training iteration, we refill the original dataset by successively adding samples according to their sequence index. Thus we carry out replacement sampling but in a batched and sequenced way. In a sense, SRS could be viewed as a way of performing "mini-batch augmentation". It is particularly useful for a task where we have a relatively small images-per-class such as CIFAR-100. Together with a longer period of initial large learning rate, it significantly improves the classification accuracy in CIFAR-100 over the current state-of-the-art results. Our experiments indicate that training deeper networks with SRS is less prone to over-fitting. In the best case, we achieve an error rate as low as 10.10%.
In this paper, the authors introduce a sampling strategy that aims to combine the benefits of with- and without-replacement SGD. With-replacement strategies add more randomness to the process, which the authors claim helps convergence, while the without-replacement strategies ensure equal usage of all datapoints. The authors present numerical results showing better convergence and improved final accuracy. While I found the idea appealing, I felt that the paper needs more work before it can be published. I detail some of my primary concerns below:
- The entire motivation of the paper is predicated on the hypothesis that more randomness is better for training. This is not generally true. Past work has shown that specific kinds of random noise aid convergence through exploration/saddle point avoidance/escaping spurious minima while others either make no change, or hurt. Noise from sampling tends to be a structured noise that aids exploration/convergence over batch gradient descent, but it is not immediately clear to me why the choice between with- and without-replacement should imply exploration. 
- Maybe it's obvious but I'm not grasping why, mathematically, the number of accessible configurations for SRS is the same as original replacement sampling (4th paragraph on page 3).
- Given that the central motivation of the work was to enable with-replacement strategies while still ensuring equal usage, I recommend that the authors include a histogram of datapoint usage for three strategies (with, without, hybrid). This should help convince the reader that the SRS indeed improves upon the usage statistics of with replacement. 
- If one were to create a hybrid sampling strategy, one that is natural is doing 50-50 sampling with and without replacement. In other words, for a batch size of 64, say, 32 are sampled with replacement and 32 without. By changing the ratio, you can also control what end of the sampling spectrum you want to be on. Did you try such a strategy? 
- For the numerical experiments, as I see it, there are 3 differences between the SRS setup and the baseline: location of batch normalization, learning rate, and batch size. The authors show (at the bottom of Page 6) that the performance boost does not come from learning rate or mini-batch size, but what about the placement of the BN layer? Seems like that still remains as a confounding factor?
- "SRS leads to much more fluctuations, and hence significantly more covariate shift". How do the authors define covariate shift? Can the authors substantiate this claim theoretically/empirically?
- The authors claim that the method works better when the dataset size is low compared to number of classes. Again, can the authors substantiate this claim theoretically/empirically? Maybe you can try running a sub-sampled version of CIFAR-10/100 with the baselines?
- The writing in the paper needs improving. A few sample phrases that need editing: "smaller mini-batch means a larger approximation", "more accessible configurations of mini-batches", "hence more exploration-induction", "less optimal local minimum"
- Minor comment: why is the queue filled with repeated samples? In Figure 1, why not have the system initialized with 1 2 3 in the pool and 4 5 in the queue? Seems like by repeating, there is an unnecessary bias towards those datapoints.