Multi-index antithetic stochastic gradient algorithm

Mateusz B. Majka, Marc Sabate Vidales, Lukasz Szpruch

Abstract

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. In this paper, we construct a Multi-index Antithetic Stochastic Gradient Algorithm (MASGA) whose implementation is independent of the structure of the target measure. Our rigorous theoretical analysis demonstrates that for log-concave targets, MASGA 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. To illustrate the robustness of our approach, we implement MASGA also in some simple non-log-concave numerical examples, however, without providing theoretical guarantees on our algorithm’s performance in such settings.

Introduction

Stochastic Gradient Algorithms (SGAs) are the workhorses of modern machine learning, powering everything from large-scale Bayesian inference to deep reinforcement learning. However, they face a fundamental trade-off: using small "mini-batches" of data saves computation but introduces significant noise (variance), while using the full dataset is often prohibitively expensive. When using Stochastic Gradient Langevin Dynamics (SGLD), practitioners must balance discretization bias from finite time-steps ($h$) and subsampling variance from mini-batch sizes ($s$).

Existing variance reduction techniques often rely on knowing the mode of the distribution to center estimates. Finding this mode in complex, high-dimensional spaces is a difficult problem in itself. In a new paper published in Statistics and Computing, researchers Mateusz B. Majka, Marc Sabate-Vidales, and Łukasz Szpruch introduce the Multi-index Antithetic Stochastic Gradient Algorithm (MASGA). This approach provides a robust, "black-box" way to achieve the efficiency of unbiased Monte Carlo sampling using only noisy, biased stochastic gradients, without requiring prior knowledge of the distribution's geometry.

Methodology

MASGA builds on the framework of Multi-level Monte Carlo (MLMC), which uses a hierarchy of coarse-to-fine approximations to estimate expectations. MASGA takes this a step further using two key innovations:

Multi-index Approach

Instead of a simple linear hierarchy, MASGA uses a 2D grid of approximations. One axis varies the time-step size ($h$), and the other varies the mini-batch size ($s$). This allows the algorithm to optimize the trade-off between discretization and subsampling errors simultaneously.

Antithetic Coupling

This is the core innovation. When calculating the difference between a "fine" path and a "coarse" path, MASGA uses an antithetic pair of coarse paths that are cleverly correlated. In the Taylor expansion of the error, the first-order terms from these two paths cancel each other out. This makes the variance of the difference terms decay much faster—improving the rate from $O(h)$ to $O(h^2)$—allowing the algorithm to use far fewer samples at the most expensive (finest) levels.

Empirical Results

The authors evaluated MASGA on both synthetic and real-world benchmarks, including the Covertype dataset (581,012 observations) for large-scale Bayesian Logistic Regression and a synthetic multi-modal Gaussian mixture.

Optimal Efficiency

The authors prove that for log-concave targets, MASGA's computational cost to reach an error $\epsilon$ is $O(\epsilon^{-2})$. This is the same complexity as vanilla Monte Carlo using unbiased samples. Essentially, MASGA removes the "penalty" usually paid for using noisy stochastic gradients.

Scaling and Variance Decay

In tests on the Covertype dataset, MASGA significantly outperformed standard SGLD and standard Multi-level SGLD. As the required accuracy increased, the cost savings of MASGA became more pronounced. Numerical experiments confirmed the theoretical predictions regarding variance decay and MSE scaling.

MSE and Variance scaling for MASGA across different subsample sizes.

While the theoretical proofs assume log-concavity, experiments on multi-modal distributions showed that MASGA still performs excellently, maintaining the $O(\epsilon^{-2})$ cost scaling even when convexity assumptions were violated.

Conclusion

MASGA provides a plug-and-play variance reduction method that does not require an optimization step to find the distribution's mode. This makes it more robust for complex potentials where the mode might be hard to find or where the distribution is non-convex. Future research directions include extending rigorous convergence proofs to non-convex potentials using reflection coupling and applying the framework to generative models like GANs or VAEs.

Summary updated

Abstract

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. In this paper, we construct a Multi-index Antithetic Stochastic Gradient Algorithm (MASGA) whose implementation is independent of the structure of the target measure. Our rigorous theoretical analysis demonstrates that for log-concave targets, MASGA 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. To illustrate the robustness of our approach, we implement MASGA also in some simple non-log-concave numerical examples, however, without providing theoretical guarantees on our algorithm’s performance in such settings.
BibTeX
@article{majka2023multi,
  author = {Mateusz B. Majka and Marc Sabate Vidales and Lukasz Szpruch},
  title = {{Multi-index antithetic stochastic gradient algorithm}},
  journal = {Stat. Comput.},
  year = {2023},
  doi = {10.1007/s11222-023-10220-8},
}
Figure