# Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum Structure

arXiv: https://arxiv.org/abs/1610.00970 · HTML: https://mlsanity.com/paper/1610.00970/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2016.

## Built on by (most cited first, 8 of 8)

- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [Variance Reduction in Deep Learning: More Momentum is All You Need](https://mlsanity.com/paper/2111.11828/) (2021)
- [Demystifying SGD with Doubly Stochastic Gradients](https://mlsanity.com/paper/2406.00920/) (2024)
- [The Stochastic Proximal Distance Algorithm](https://mlsanity.com/paper/2210.12277/) (2022)
- [Joint control variate for faster black-box variational inference](https://mlsanity.com/paper/2210.07290/) (2022)
- [Learning Energy-Based Models by Self-normalising the Likelihood](https://mlsanity.com/paper/2503.07021/) (2025)

## Abstract (arXiv)

Stochastic optimization algorithms with variance reduction have proven successful for minimizing large finite sums of functions. Unfortunately, these techniques are unable to deal with stochastic perturbations of input data, induced for example by data augmentation. In such cases, the objective is no longer a finite sum, and the main candidate for optimization is the stochastic gradient descent method (SGD). In this paper, we introduce a variance reduction approach for these settings when the objective is composite and strongly convex. The convergence rate outperforms SGD with a typically much smaller constant factor, which depends on the variance of gradient estimates only due to perturbations on a single example.