# Stochastic Optimization with Importance Sampling

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

## Key facts

- Cited by 91 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2014.

## Built on by (most cited first, 30 of 91)

- [LISA: Layerwise Importance Sampling for Memory-Efficient Large Language Model Fine-Tuning](https://mlsanity.com/paper/2403.17919/) (2024)
- [Large Scale Private Learning via Low-rank Reparametrization](https://mlsanity.com/paper/2106.09352/) (2021)
- [Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling](https://mlsanity.com/paper/2112.11256/) (2021)
- [Client Selection in Federated Learning: Principles, Challenges, and Opportunities](https://mlsanity.com/paper/2211.01549/) (2022)
- [Efficient Lottery Ticket Finding: Less Data is More](https://mlsanity.com/paper/2106.03225/) (2021)
- [Pareto Invariant Risk Minimization: Towards Mitigating the Optimization Dilemma in Out-of-Distribution Generalization](https://mlsanity.com/paper/2206.07766/) (2022)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [The Effect of Task Ordering in Continual Learning](https://mlsanity.com/paper/2205.13323/) (2022)
- [Federated Learning Under Intermittent Client Availability and Time-Varying Communication Constraints](https://mlsanity.com/paper/2205.06730/) (2022)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [Meta-learning with an Adaptive Task Scheduler](https://mlsanity.com/paper/2110.14057/) (2021)
- [DELTA: Diverse Client Sampling for Fasting Federated Learning](https://mlsanity.com/paper/2205.13925/) (2022)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Amortized Variational Inference: A Systematic Review](https://mlsanity.com/paper/2209.10888/) (2022)
- [Learning to Rebalance Multi-Modal Optimization by Adaptively Masking Subnetworks](https://mlsanity.com/paper/2404.08347/) (2024)
- [Upweighting Easy Samples in Fine-Tuning Mitigates Forgetting](https://mlsanity.com/paper/2502.02797/) (2025)
- [Large Batch Experience Replay](https://mlsanity.com/paper/2110.01528/) (2021)
- [Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning](https://mlsanity.com/paper/2206.02604/) (2022)
- [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021)
- [Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff](https://mlsanity.com/paper/2110.15590/) (2021)
- [DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Sampling](https://mlsanity.com/paper/2210.09634/) (2022)
- [Active Exploration for Neural Global Illumination of Variable Scenes](https://mlsanity.com/paper/2203.08272/) (2022)
- [Adaptive Training Distributions with Scalable Online Bilevel Optimization](https://mlsanity.com/paper/2311.11973/) (2023)
- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [Iterative Teaching by Label Synthesis](https://mlsanity.com/paper/2110.14432/) (2021)
- [Learning to Learn and Sample BRDFs](https://mlsanity.com/paper/2210.03510/) (2022)
- [Combating Data Imbalances in Federated Semi-supervised Learning with Dual Regulators](https://mlsanity.com/paper/2307.05358/) (2023)
- [Adaptive Heterogeneous Client Sampling for Federated Learning over Wireless Networks](https://mlsanity.com/paper/2404.13804/) (2024)
- [Fast Heterogeneous Federated Learning with Hybrid Client Selection](https://mlsanity.com/paper/2208.05135/) (2022)
- [Outlier-weighed Layerwise Sampling for LLM Fine-tuning](https://mlsanity.com/paper/2405.18380/) (2024)

## Abstract (arXiv)

Uniform sampling of training data has been commonly used in traditional stochastic optimization algorithms such as Proximal Stochastic Gradient Descent (prox-SGD) and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA). Although uniform sampling can guarantee that the sampled stochastic quantity is an unbiased estimate of the corresponding true quantity, the resulting estimator may have a rather high variance, which negatively affects the convergence of the underlying optimization procedure. In this paper we study stochastic optimization with importance sampling, which improves the convergence rate by reducing the stochastic variance. Specifically, we study prox-SGD (actually, stochastic mirror descent) with importance sampling and prox-SDCA with importance sampling. For prox-SGD, instead of adopting uniform sampling throughout the training process, the proposed algorithm employs importance sampling to minimize the variance of the stochastic gradient. For prox-SDCA, the proposed importance sampling scheme aims to achieve higher expected dual value at each dual coordinate ascent step. We provide extensive theoretical analysis to show that the convergence rates with the proposed importance sampling methods can be significantly improved under suitable conditions both for prox-SGD and for prox-SDCA. Experiments are provided to verify the theoretical analysis.