# Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Builds on (most cited first, 17 of 17)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [Importance Sampling for Minibatches](https://mlsanity.com/paper/1602.02283/) (2016)
- [Safe Adaptive Importance Sampling](https://mlsanity.com/paper/1711.02637/) (2017)
- [A Simple Practical Accelerated Method for Finite Sums](https://mlsanity.com/paper/1602.02442/) (2016)
- [Online Variance Reduction for Stochastic Optimization](https://mlsanity.com/paper/1802.04715/) (2018)
- [Stochastic Optimization with Bandit Sampling](https://mlsanity.com/paper/1708.02544/) (2017)
- [Online Variance Reduction with Mixtures](https://mlsanity.com/paper/1903.12416/) (2019)
- [Non-stationary Stochastic Optimization under Lp,q-Variation Measures](https://mlsanity.com/paper/1708.03020/) (2017)

## 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)
- [Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff](https://mlsanity.com/paper/2110.15590/) (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)
- [Computational Complexity of Sub-Linear Convergent Algorithms](https://mlsanity.com/paper/2209.14558/) (2022)
- [Stochastic Gradient Descent with Strategic Querying](https://mlsanity.com/paper/2508.17144/) (2025)
- [Sample-Adaptive Zeroth-Order Post-Training](https://mlsanity.com/paper/2610.12566/) (2026)

## Abstract (arXiv)

Reducing the variance of the gradient estimator is known to improve the convergence rate of stochastic gradient-based optimization and sampling algorithms. One way of achieving variance reduction is to design importance sampling strategies. Recently, the problem of designing such schemes was formulated as an online learning problem with bandit feedback, and algorithms with sub-linear static regret were designed. In this work, we build on this framework and propose Avare, a simple and efficient algorithm for adaptive importance sampling for finite-sum optimization and sampling with decreasing step-sizes. Under standard technical conditions, we show that Avare achieves O(T2/3) and O(T5/6) dynamic regret for SGD and SGLD respectively when run with O(1/t) step sizes. We achieve this dynamic regret bound by leveraging our knowledge of the dynamics defined by the algorithm, and combining ideas from online learning and variance-reduced stochastic optimization. We validate empirically the performance of our algorithm and identify settings in which it leads to significant improvements.