Ordering for Non-Replacement SGD
Yuetong Xu Baharan Mirzasoleiman
One approach for reducing run time and improving efficiency of machine
learning is to reduce the convergence rate of the optimization algorithm used.
Shuffling is an algorithm technique that is widely used in machine learning,
but it only started to gain attention theoretically in recent years. With
different convergence rates developed for random shuffling and incremental
gradient descent, we seek to find an ordering that can improve the convergence
rates for the non-replacement form of the algorithm. Based on existing bounds
of the distance between the optimal and current iterate, we derive an upper
bound that is dependent on the gradients at the beginning of the epoch. Through
analysis of the bound, we are able to develop optimal orderings for constant
and decreasing step sizes for strongly convex and convex functions. We further
test and verify our results through experiments on synthesis and real data
sets. In addition, we are able to combine the ordering with mini-batch and
further apply it to more complex neural networks, which show promising results.