  Stochastic Gradient Algorithms (SGAs) are ubiquitous in computational
statistics, machine learning and optimisation. Recent years have brought an
influx of interest in SGAs, and the non-asymptotic analysis of their bias is by
now well-developed. However, relatively little is known about the optimal
choice of the random approximation (e.g mini-batching) of the gradient in SGAs
as this relies on the analysis of the variance and is problem specific. While
there have been numerous attempts to reduce the variance of SGAs, these
typically exploit a particular structure of the sampled distribution by
requiring a priori knowledge of its density's mode. It is thus unclear how to
adapt such algorithms to non-log-concave settings. In this paper, we construct
a Multi-index Antithetic Stochastic Gradient Algorithm (MASGA) whose
implementation is independent of the structure of the target measure and which
achieves performance on par with Monte Carlo estimators that have access to
unbiased samples from the distribution of interest. In other words, MASGA is an
optimal estimator from the mean square error-computational cost perspective
within the class of Monte Carlo estimators. We prove this fact rigorously for
log-concave settings and verify it numerically for some examples where the
log-concavity assumption is not satisfied.
