# Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 81 references that are in the map.
- First posted on arXiv 20 Aug 2024.

## Builds on (most cited first, 30 of 34)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [On the Convergence Theory of Gradient-Based Model-Agnostic Meta-Learning Algorithms](https://mlsanity.com/paper/1908.10400/) (2019)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Reinforcement Learning via Fenchel-Rockafellar Duality](https://mlsanity.com/paper/2001.01866/) (2020)
- [Multi-digit Number Recognition from Street View Imagery using Deep Convolutional Neural Networks](https://mlsanity.com/paper/1312.6082/) (2013)
- [On the Convergence of SGD with Biased Gradients](https://mlsanity.com/paper/2008.00051/) (2020)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning](https://mlsanity.com/paper/2002.07836/) (2020)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization](https://mlsanity.com/paper/2305.11965/) (2023)
- [What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?](https://mlsanity.com/paper/1902.00618/) (2019)
- [Stochastic Gradient Descent with Biased but Consistent Gradient Estimators](https://mlsanity.com/paper/1807.11880/) (2018)
- [Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applications](https://mlsanity.com/paper/1904.09929/) (2019)
- [Stochastic Constrained DRO with a Complexity Independent of Sample Size](https://mlsanity.com/paper/2210.05740/) (2022)
- [Multilevel Monte Carlo Variational Inference](https://mlsanity.com/paper/1902.00468/) (2019)
- [Contextual Stochastic Bilevel Optimization](https://mlsanity.com/paper/2310.18535/) (2023)
- [(Bandit) Convex Optimization with Biased Noisy Gradient Oracles](https://mlsanity.com/paper/1609.07087/) (2016)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Unbiased Simulation for Optimizing Stochastic Function Compositions](https://mlsanity.com/paper/1711.07564/) (2017)
- [Online Estimation and Optimization of Utility-Based Shortfall Risk](https://mlsanity.com/paper/2111.08805/) (2021)

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

- [MPO: An Efficient Post-Processing Framework for Mixing Diverse Preference Alignment](https://mlsanity.com/paper/2502.18699/) (2025)
- [Global Group Fairness in Federated Learning via Function Tracking](https://mlsanity.com/paper/2503.15163/) (2025)
- [Iterative Sampling Methods for Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2512.12550/) (2025)
- [Multistage Conditional Compositional Optimization](https://mlsanity.com/paper/2604.14075/) (2026)
- [Convex Optimization Is Free When Accuracy Is Expensive](https://mlsanity.com/paper/2609.35418/) (2026)

## Abstract (arXiv)

We consider stochastic optimization when one only has access to biased stochastic oracles of the objective and the gradient, and obtaining stochastic gradients with low biases comes at high costs. This setting captures various optimization paradigms, such as conditional stochastic optimization, distributionally robust optimization, shortfall risk optimization, and machine learning paradigms, such as contrastive learning. We examine a family of multi-level Monte Carlo (MLMC) gradient methods that exploit a delicate tradeoff among bias, variance, and oracle cost. We systematically study their total sample and computational complexities for strongly convex, convex, and nonconvex objectives and demonstrate their superiority over the widely used biased stochastic gradient method. When combined with the variance reduction techniques like SPIDER, these MLMC gradient methods can further reduce the complexity in the nonconvex regime. Our results imply that a series of stochastic optimization problems with biased oracles, previously considered to be more challenging, is fundamentally no harder than the classical stochastic optimization with unbiased oracles. We also delineate the boundary conditions under which these problems become more difficult. Moreover, MLMC gradient methods significantly improve the best-known complexities in the literature for conditional stochastic optimization and shortfall risk optimization. Our extensive numerical experiments on distributionally robust optimization, pricing and staffing scheduling problems, and contrastive learning demonstrate the superior performance of MLMC gradient methods.