Mini-batch algorithms with Barzilai-Borwein update step

As a way to accelerate stochastic schemes, mini-batch optimization has been a popular choice for large scale learning due to its good general performance and ease of parallel computing. However, the performance of mini-batch algorithms can vary significantly based on the choice of the step size sequence, and, in general, there is a paucity of guidance for making good choices. In this paper, we propose to use the Barzilai-Borwein (BB) update step to automatically compute step sizes for the state of the art mini-batch method (mini-batch semi-stochastic gradient descent (mS2GD) method), thereby obtaining a new optimization method: mS2GD-BB. We prove that mS2GD-BB converges linearly in expectation for nonsmooth strongly convex objective functions. We analyze the complexity of mS2GD-BB and show that it achieves as fast a rate as modern stochastic gradient methods. Numerical experiments on standard data sets indicate that the performance of mS2GD-BB is superior to some state of the art methods.