# Stochastic Optimization with Optimal Importance Sampling

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 69 references that are in the map.
- First posted on arXiv 4 Apr 2025.

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

- [Meta-Learning in Neural Networks: A Survey](https://mlsanity.com/paper/2004.05439/) (2020)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [The Complexity of Making the Gradient Small in Stochastic Convex Optimization](https://mlsanity.com/paper/1902.04686/) (2019)
- [Asymptotic normality and optimality in nonsmooth stochastic approximation](https://mlsanity.com/paper/2301.06632/) (2023)
- [Achieving Efficiency in Black Box Simulation of Distribution Tails with Self-structuring Importance Samplers](https://mlsanity.com/paper/2102.07060/) (2021)
- [Adaptive Importance Sampling for Efficient Stochastic Root Finding and Quantile Estimation](https://mlsanity.com/paper/2102.10631/) (2021)
- [Importance Sampling for Minimization of Tail Risks: A Tutorial](https://mlsanity.com/paper/2307.04676/) (2023)

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

- [Optimal low-rank stochastic gradient estimation for LLM training](https://mlsanity.com/paper/2603.20632/) (2026)
- [Sample-Adaptive Zeroth-Order Post-Training](https://mlsanity.com/paper/2610.12566/) (2026)

## Abstract (arXiv)

Importance Sampling (IS) is a widely used variance reduction technique for enhancing the efficiency of Monte Carlo methods, particularly in rare-event simulation and related applications. Despite its effectiveness, the performance of IS is highly sensitive to the choice of the proposal distribution and often requires stochastic calibration. While the design and analysis of IS have been extensively studied in estimation settings, applying IS within stochastic optimization introduces a lesser-known fundamental challenge: the decision variable and the importance sampling distribution are mutually dependent, creating a circular optimization structure. This interdependence complicates both convergence analysis and variance control. In this paper, we consider the generic setting of convex stochastic optimization with linear constraints. We propose a single-loop stochastic approximation algorithm, based on a variant of Nesterov's dual averaging, that jointly updates the decision variable and the importance sampling distribution, notably without time-scale separation or nested optimization. The method is globally convergent and achieves the minimal asymptotic variance among stochastic gradient schemes, which moreover matches the performance of an oracle sampler adapted to the optimal solution and thus effectively resolves the circular optimization challenge.