École Nationale Supérieure de
Techniques Avancées

Abstract

In this report, we find simple expressions of the optimal minibatch size for the celebrated stochastic average gradient (SAGA) method. Our approach consists in finding the minibatch size that minimizes the total complexity of the minibatch SAGA algorithm, defined as the iteration complexity times the number of computations per iteration. These complexity results are taken from recent work by Gower, Richtárik and Bach (2018) who introduced the concept of expected smoothness constant. The latter is a characteristic of our optimization problem and controls the iteration complexity of several stochastic variance-reduced gradient methods. In order to get closed-form optimal minibatch, we first designed upper bounds of the expected smoothness constant in the case of SAGA for sampling without replacement, using direct computations and matrix concentration inequalities. Then, we plugged in these upper bounds into previous complexity results, in a way leading to a pessimistic total complexity, before finding their argument of the minimum: our estimation of the optimal minibatch size.