# Online Variance Reduction with Mixtures

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

## Key facts

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

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

- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback](https://mlsanity.com/paper/2112.14332/) (2021)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [Addressing Budget Allocation and Revenue Allocation in Data Market Environments Using an Adaptive Sampling Algorithm](https://mlsanity.com/paper/2306.02543/) (2023)
- [Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance](https://mlsanity.com/paper/2310.02698/) (2023)
- [L-SVRG and L-Katyusha with Adaptive Sampling](https://mlsanity.com/paper/2201.13387/) (2022)
- [Sample-Adaptive Zeroth-Order Post-Training](https://mlsanity.com/paper/2610.12566/) (2026)

## Abstract (arXiv)

Adaptive importance sampling for stochastic optimization is a promising approach that offers improved convergence through variance reduction. In this work, we propose a new framework for variance reduction that enables the use of mixtures over predefined sampling distributions, which can naturally encode prior knowledge about the data. While these sampling distributions are fixed, the mixture weights are adapted during the optimization process. We propose VRM, a novel and efficient adaptive scheme that asymptotically recovers the best mixture weights in hindsight and can also accommodate sampling distributions over sets of points. We empirically demonstrate the versatility of VRM in a range of applications.