# Stochastic Optimization with Bandit Sampling

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

## Key facts

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

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

- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [A Biased Graph Neural Network Sampler with Near-Optimal Regret](https://mlsanity.com/paper/2103.01089/) (2021)
- [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)
- [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)
- [Preferential Subsampling for Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2210.16189/) (2022)
- [Sample-Adaptive Zeroth-Order Post-Training](https://mlsanity.com/paper/2610.12566/) (2026)

## Abstract (arXiv)

Many stochastic optimization algorithms work by estimating the gradient of the cost function on the fly by sampling datapoints uniformly at random from a training set. However, the estimator might have a large variance, which inadvertently slows down the convergence rate of the algorithms. One way to reduce this variance is to sample the datapoints from a carefully selected non-uniform distribution. In this work, we propose a novel non-uniform sampling approach that uses the multi-armed bandit framework. Theoretically, we show that our algorithm asymptotically approximates the optimal variance within a factor of 3. Empirically, we show that using this datapoint-selection technique results in a significant reduction in the convergence time and variance of several stochastic optimization algorithms such as SGD, SVRG and SAGA. This approach for sampling datapoints is general, and can be used in conjunction with any algorithm that uses an unbiased gradient estimation -- we expect it to have broad applicability beyond the specific examples explored in this work.