# Online Learning to Sample

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2015.

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

- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling](https://mlsanity.com/paper/2203.04510/) (2022)
- [Robust On-Policy Sampling for Data-Efficient Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2111.14552/) (2021)
- [Active Exploration for Neural Global Illumination of Variable Scenes](https://mlsanity.com/paper/2203.08272/) (2022)
- [Learning to Learn and Sample BRDFs](https://mlsanity.com/paper/2210.03510/) (2022)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [Dynamic Gradient Aggregation for Federated Domain Adaptation](https://mlsanity.com/paper/2106.07578/) (2021)
- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [OLR-WA Online Regression with Weighted Average](https://mlsanity.com/paper/2307.02804/) (2023)
- [Sample-Adaptive Zeroth-Order Post-Training](https://mlsanity.com/paper/2610.12566/) (2026)

## Abstract (arXiv)

Stochastic Gradient Descent (SGD) is one of the most widely used techniques for online optimization in machine learning. In this work, we accelerate SGD by adaptively learning how to sample the most useful training examples at each time step. First, we show that SGD can be used to learn the best possible sampling distribution of an importance sampling estimator. Second, we show that the sampling distribution of an SGD algorithm can be estimated online by incrementally minimizing the variance of the gradient. The resulting algorithm - called Adaptive Weighted SGD (AW-SGD) - maintains a set of parameters to optimize, as well as a set of parameters to sample learning examples. We show that AWSGD yields faster convergence in three different applications: (i) image classification with deep features, where the sampling of images depends on their labels, (ii) matrix factorization, where rows and columns are not sampled uniformly, and (iii) reinforcement learning, where the optimized and exploration policies are estimated at the same time, where our approach corresponds to an off-policy gradient algorithm.